Neighbor-Sum Grids

Looking for tips about this nice puzzle.
I’m using a basic heuristic to filter out mandatory/impossible values on a given board, then use backtracking when the heuristic can’t progress anymore.
I can handle ~70k simulations before time out but it’s not enough to go through the tests with 22 and 23 unknowns. Should I focus on a better heuristic or simply keep optimizing ? I’ve done quite a bit already by storing eligible values in bits and using dirty flags to avoid reapplying the heuristic unnecessarily.

My first attempt was simple backtracking, trying to fill out the grid cell-by-cell, but that was also way too slow.
What worked in the end was still backtracking, but done differently:

  • different state representation: instead of 2d array of cell value, an 1d array of ‘value’ => position mapping
  • backtracking goes differently: instead of by cell (finding what value it should have), it goes by value 1…25 (finding where this value should go)
  • x,y position can be encoded as single integer 0…24. Benefit: this value can encode a bit position in a bitmask…
  • neighbors of each cell can be precomputed as a bitmask using the encoding above.
  • this makes checking if the neighbor-sum rule is still ok or broken much faster. (if broken => backtrack)
3 Likes

Thanks for the tips, though I’ve done most of that already.
I’ll try backtracking by value instead of by cell. Currently for each iteration I pick the cell that has the most neighbors with set values, that tends to group set values and limit outcomes faster (but not fast enough :)).

I check the neighbor-sum rule differently from as I did originally (i.e. cycle through neighbor cells): Instead a ‘for i’ cycle till half of the possible values - then checking if ‘i’ and ‘target - i’ are both neighbors of ‘target’ - this can be done with simple bitwise operation because of the neighbor and cell position representation using the bitboard described above.

I did that too :slight_smile:
Backtracking by value puts me up to 130k iterations before time out, that’s a pretty nice improvement. But still not enough.

For me at IDE test case 08 (23 missing) think time = 0.0623 sec, iterations = 33653.
(Iterations meaning number of backtrack() function calls. But I check for ‘reject’ before calling backtrack() recursively and not after as in the standard BT pseudocode (https://en.wikipedia.org/wiki/Backtracking) so my iterations count might be lower because of this.
Or: it might be that you simply timeout because you don’t prune the search space good enough.
I don’t have more ideas/hints, let me know in PM if you want to see my code to compare with yours.

I did some refactoring so my code run really fast now, ~1million iterations before time out. But since you can solve the last test with only 30k it’s clear that I need to work on my heuristic now.
At least I’m learning a lot about bitwise manipulations, never thought much of it outside of the basic & and |.

Finally got it, I sweat way to much on this one :sweat_smile:
Pretty proud of my final heuristic though, only 160 backtracking iterations for test 8 with 23 missing.
Anyway thanks for the help @TBali, much appreciated.

2 Likes