6 ms·

Out of curiosity, what's the lowest score you've seen on 17x17 so far?

DarkShikari 17y ago
I think about 51, I haven't been saving the best so far. I'll tee it to a file from now on. Edit: Oops, my random-restart code had an obvious bug. It's probably not very useful anyways, so I removed it. http://pastebin.com/m63191b11 http://pastebin.com/m63191b11
- scythe 17y ago
  Try just placing 73 1's. You need to be able to place that many, but I can't get more than 65.
  - RiderOfGiraffes 17y ago
    I've got 67 just using random placements with heuristics, programmed in Python. Apparently they've got 73 (which is 289/4 rounded up), and that's why they think this might be possible.
    - abentspoon 17y ago
      I've placed 74 using an IP solver 1 1 . . . . . 1 1 . . . . . 1 . . . 1 1 1 1 . . . . . . . . . . . . 1 . 1 . . 1 . . . . . 1 . . . . 1 1 . . 1 . . 1 . . . 1 . . . . 1 . 1 . . . 1 . . . . 1 . . . 1 . . . . . . 1 . 1 . 1 . . . . . 1 . . . . 1 . . . 1 1 . . 1 . . . . . . . . . 1 . . . 1 1 . . . . 1 . . . . . . . . 1 1 . . 1 . . . 1 . . 1 . . . 1 . . . . . 1 1 1 . . . . . . . . . . 1 . . 1 . . 1 1 . . . . . . . . . . . 1 . 1 . . 1 . 1 . . . . . . 1 . . . . . 1 . 1 1 . 1 . . . 1 . . . . . . . . 1 . 1 1 . . 1 . . 1 . . . . . . . . . . 1 1 1 . . . . . 1 . 1 . . . . . . . 1 . 1 . . . . . . . 1 . 1 . . . . . 1 1 The solver chokes on anything larger than a 6x6 grid, but I've had good luck adding one row at a time to a smaller solution. http://pastebin.com/m4c4696af http://pastebin.com/m4c4696af edit: He mentions that he already found a size 74 set in one of the linked pdfs. http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17.pdf http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17.pdf
DarkShikari 17y ago
Down to 39: 1 0 1 0 2 0 2 1 0 2 1 3 3 2 3 3 1 3 3 0 3 1 2 3 0 0 1 1 1 2 2 2 0 1 3 2 3 2 2 0 1 0 3 0 3 3 1 1 0 2 1 0 3 1 2 1 1 2 3 1 0 3 0 0 3 2 0 2 0 1 1 3 3 3 1 0 1 1 2 2 3 2 0 2 0 3 1 2 2 3 1 0 1 0 3 0 2 0 3 0 1 2 1 1 1 2 0 2 3 2 3 3 0 0 1 2 0 0 3 2 2 0 0 3 1 0 1 3 1 3 0 1 2 1 3 2 0 0 2 0 0 2 0 3 1 2 1 2 1 3 3 1 3 3 2 2 1 0 3 0 1 1 0 3 1 2 0 3 2 3 1 3 3 0 1 3 2 2 1 3 0 2 2 0 1 3 0 2 3 2 1 2 1 1 2 0 0 1 0 3 0 2 3 3 1 0 3 3 2 2 1 0 2 3 2 1 0 0 3 1 2 0 2 1 1 0 3 3 2 0 2 2 3 0 3 1 1 0 2 1 3 2 3 0 0 3 2 2 1 3 2 1 1 0 0 0 2 0 1 1 0 3 3 2 3 3 2 3 0 2 1 1 2 0 0 3 1 2 2 3 3 0 0 1 1 1 3 2 0
- lkozma 17y ago
  34 here (after some tweaks): 0 0 0 0 0 1 1 1 2 2 2 2 2 3 3 3 3 0 1 1 3 3 0 1 2 0 1 2 3 3 0 2 2 3 0 1 2 2 3 0 0 0 3 3 3 1 2 1 1 2 1 0 2 3 3 2 1 3 3 1 1 0 0 0 2 3 2 1 0 3 0 1 1 3 2 3 1 2 1 1 3 3 0 0 2 1 1 3 2 0 3 0 1 3 0 1 2 3 2 2 0 2 1 2 0 2 1 0 2 3 3 0 2 3 0 1 3 1 0 1 3 0 2 2 2 3 0 2 1 0 1 1 0 1 3 3 2 0 1 2 1 0 3 1 3 2 3 0 1 3 2 0 1 2 0 3 1 0 2 2 1 0 1 3 2 0 1 0 2 3 2 1 3 1 0 3 2 0 2 3 2 3 1 2 0 3 0 2 3 1 3 2 1 0 2 3 3 0 1 2 0 0 1 2 3 0 2 3 2 3 0 1 1 2 3 0 1 0 2 1 0 3 1 2 0 1 1 3 2 0 3 0 2 3 2 3 0 0 3 2 2 0 3 1 1 3 2 0 1 0 1 1 0 3 2 3 2 3 1 3 2 1 0 0 0 1 0 2 3 2 1 1 3 3 2 0 1 2 1 0 1 2 2 3 0 0 1 0 3
- machrider 17y ago
  I made some tweaks (and a bug fix or two), left it running overnight (four instances, one per CPU core)... They all get down to 12 to 14, but it seems like they stop progressing. Haven't seen 11 yet. Score: 12 2 3 0 1 3 2 1 2 2 3 1 2 0 3 1 3 0 2 1 1 2 2 1 1 0 3 3 3 3 3 2 0 0 0 2 2 1 1 0 3 3 3 1 0 2 0 1 3 3 0 2 3 2 0 1 1 1 0 3 2 1 3 0 2 2 0 3 1 1 2 1 3 1 0 2 2 0 2 0 0 3 3 1 1 0 1 1 3 3 0 2 2 0 0 1 3 1 0 2 3 1 2 3 2 3 0 2 1 0 0 0 0 1 2 1 3 2 1 3 1 3 3 2 3 1 0 1 2 2 0 3 0 1 2 0 2 2 0 2 1 3 0 3 1 0 2 3 1 2 0 0 1 3 3 0 2 0 1 3 1 2 3 3 2 1 1 2 2 0 0 0 0 2 3 2 3 2 0 2 1 0 3 1 1 1 3 3 2 0 1 3 3 0 2 3 3 0 1 1 0 1 2 2 1 0 1 0 2 1 0 2 3 1 3 2 2 2 1 3 0 3 3 2 2 2 0 2 0 1 1 1 1 3 3 0 3 2 0 3 3 0 3 2 1 3 2 1 0 0 1 2 0 1 2 2 1 3 3 0 0 3 1 3 1 2 0 2 3 2 0 2 1 0 1 3 0 2 2 3 1 3 2 2 0 0 0 1 3 1 Edit: I can't reply to you, so... http://pastebin.com/m33bccec1 http://pastebin.com/m33bccec1 It's not pretty, but I did a few things. Instead of taking the top n candidates and breeding them randomly, I kept all of them (NUM_STATES 200 and KEPT_STATES 200), but weight them according to score. So the best scores have the highest chance of passing their DNA down to the next generation, but the occasional loser gets lucky too. Mutation is also weighted, so the most likely number of mutations is zero, but it's possible to have up to 4. Increasing this value made the performance go down, but it's also possible that there is no way to get to a solution by incrementally tweaking a decent attempt. Which could explain why I'm stuck at 12. There are a few optimizations that may or may not make a difference, for instance in the scoring function. I think the pick_best_states function was not actually picking the best states. If you had two states with the same score, the first one is kept, but the next one is not. I fixed this. The stupid thing is, with NUM_STATES and KEPT_STATES at 200, it's basically an n^2 sort now. I never bothered to improve that. Finally, compiled with -O3 and let 'er rip.

I think about 51, I haven't been saving the best so far. I'll tee it to a file from now on. Edit: Oops, my random-restart code had an obvious bug. It's probably not very useful anyways, so I removed it. http://pastebin.com/m63191b11 http://pastebin.com/m63191b11

scythe 17y ago
Try just placing 73 1's. You need to be able to place that many, but I can't get more than 65.
- RiderOfGiraffes 17y ago
  I've got 67 just using random placements with heuristics, programmed in Python. Apparently they've got 73 (which is 289/4 rounded up), and that's why they think this might be possible.
  - abentspoon 17y ago
    I've placed 74 using an IP solver 1 1 . . . . . 1 1 . . . . . 1 . . . 1 1 1 1 . . . . . . . . . . . . 1 . 1 . . 1 . . . . . 1 . . . . 1 1 . . 1 . . 1 . . . 1 . . . . 1 . 1 . . . 1 . . . . 1 . . . 1 . . . . . . 1 . 1 . 1 . . . . . 1 . . . . 1 . . . 1 1 . . 1 . . . . . . . . . 1 . . . 1 1 . . . . 1 . . . . . . . . 1 1 . . 1 . . . 1 . . 1 . . . 1 . . . . . 1 1 1 . . . . . . . . . . 1 . . 1 . . 1 1 . . . . . . . . . . . 1 . 1 . . 1 . 1 . . . . . . 1 . . . . . 1 . 1 1 . 1 . . . 1 . . . . . . . . 1 . 1 1 . . 1 . . 1 . . . . . . . . . . 1 1 1 . . . . . 1 . 1 . . . . . . . 1 . 1 . . . . . . . 1 . 1 . . . . . 1 1 The solver chokes on anything larger than a 6x6 grid, but I've had good luck adding one row at a time to a smaller solution. http://pastebin.com/m4c4696af http://pastebin.com/m4c4696af edit: He mentions that he already found a size 74 set in one of the linked pdfs. http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17.pdf http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17.pdf

DarkShikari 17y ago

Down to 39: 1 0 1 0 2 0 2 1 0 2 1 3 3 2 3 3 1 3 3 0 3 1 2 3 0 0 1 1 1 2 2 2 0 1 3 2 3 2 2 0 1 0 3 0 3 3 1 1 0 2 1 0 3 1 2 1 1 2 3 1 0 3 0 0 3 2 0 2 0 1 1 3 3 3 1 0 1 1 2 2 3 2 0 2 0 3 1 2 2 3 1 0 1 0 3 0 2 0 3 0 1 2 1 1 1 2 0 2 3 2 3 3 0 0 1 2 0 0 3 2 2 0 0 3 1 0 1 3 1 3 0 1 2 1 3 2 0 0 2 0 0 2 0 3 1 2 1 2 1 3 3 1 3 3 2 2 1 0 3 0 1 1 0 3 1 2 0 3 2 3 1 3 3 0 1 3 2 2 1 3 0 2 2 0 1 3 0 2 3 2 1 2 1 1 2 0 0 1 0 3 0 2 3 3 1 0 3 3 2 2 1 0 2 3 2 1 0 0 3 1 2 0 2 1 1 0 3 3 2 0 2 2 3 0 3 1 1 0 2 1 3 2 3 0 0 3 2 2 1 3 2 1 1 0 0 0 2 0 1 1 0 3 3 2 3 3 2 3 0 2 1 1 2 0 0 3 1 2 2 3 3 0 0 1 1 1 3 2 0

lkozma 17y ago
34 here (after some tweaks): 0 0 0 0 0 1 1 1 2 2 2 2 2 3 3 3 3 0 1 1 3 3 0 1 2 0 1 2 3 3 0 2 2 3 0 1 2 2 3 0 0 0 3 3 3 1 2 1 1 2 1 0 2 3 3 2 1 3 3 1 1 0 0 0 2 3 2 1 0 3 0 1 1 3 2 3 1 2 1 1 3 3 0 0 2 1 1 3 2 0 3 0 1 3 0 1 2 3 2 2 0 2 1 2 0 2 1 0 2 3 3 0 2 3 0 1 3 1 0 1 3 0 2 2 2 3 0 2 1 0 1 1 0 1 3 3 2 0 1 2 1 0 3 1 3 2 3 0 1 3 2 0 1 2 0 3 1 0 2 2 1 0 1 3 2 0 1 0 2 3 2 1 3 1 0 3 2 0 2 3 2 3 1 2 0 3 0 2 3 1 3 2 1 0 2 3 3 0 1 2 0 0 1 2 3 0 2 3 2 3 0 1 1 2 3 0 1 0 2 1 0 3 1 2 0 1 1 3 2 0 3 0 2 3 2 3 0 0 3 2 2 0 3 1 1 3 2 0 1 0 1 1 0 3 2 3 2 3 1 3 2 1 0 0 0 1 0 2 3 2 1 1 3 3 2 0 1 2 1 0 1 2 2 3 0 0 1 0 3
machrider 17y ago
I made some tweaks (and a bug fix or two), left it running overnight (four instances, one per CPU core)... They all get down to 12 to 14, but it seems like they stop progressing. Haven't seen 11 yet. Score: 12 2 3 0 1 3 2 1 2 2 3 1 2 0 3 1 3 0 2 1 1 2 2 1 1 0 3 3 3 3 3 2 0 0 0 2 2 1 1 0 3 3 3 1 0 2 0 1 3 3 0 2 3 2 0 1 1 1 0 3 2 1 3 0 2 2 0 3 1 1 2 1 3 1 0 2 2 0 2 0 0 3 3 1 1 0 1 1 3 3 0 2 2 0 0 1 3 1 0 2 3 1 2 3 2 3 0 2 1 0 0 0 0 1 2 1 3 2 1 3 1 3 3 2 3 1 0 1 2 2 0 3 0 1 2 0 2 2 0 2 1 3 0 3 1 0 2 3 1 2 0 0 1 3 3 0 2 0 1 3 1 2 3 3 2 1 1 2 2 0 0 0 0 2 3 2 3 2 0 2 1 0 3 1 1 1 3 3 2 0 1 3 3 0 2 3 3 0 1 1 0 1 2 2 1 0 1 0 2 1 0 2 3 1 3 2 2 2 1 3 0 3 3 2 2 2 0 2 0 1 1 1 1 3 3 0 3 2 0 3 3 0 3 2 1 3 2 1 0 0 1 2 0 1 2 2 1 3 3 0 0 3 1 3 1 2 0 2 3 2 0 2 1 0 1 3 0 2 2 3 1 3 2 2 0 0 0 1 3 1 Edit: I can't reply to you, so... http://pastebin.com/m33bccec1 http://pastebin.com/m33bccec1 It's not pretty, but I did a few things. Instead of taking the top n candidates and breeding them randomly, I kept all of them (NUM_STATES 200 and KEPT_STATES 200), but weight them according to score. So the best scores have the highest chance of passing their DNA down to the next generation, but the occasional loser gets lucky too. Mutation is also weighted, so the most likely number of mutations is zero, but it's possible to have up to 4. Increasing this value made the performance go down, but it's also possible that there is no way to get to a solution by incrementally tweaking a decent attempt. Which could explain why I'm stuck at 12. There are a few optimizations that may or may not make a difference, for instance in the scoring function. I think the pick_best_states function was not actually picking the best states. If you had two states with the same score, the first one is kept, but the next one is not. I fixed this. The stupid thing is, with NUM_STATES and KEPT_STATES at 200, it's basically an n^2 sort now. I never bothered to improve that. Finally, compiled with -O3 and let 'er rip.