https://www.codingame.com/training/hard/neighbor-sum-grids
Send your feedback or ask for help here!
Nice puzzle, I thought it would be as straightforward as most backtracking puzzles here but it was actually refreshing cause you really need to do your search in a specific order to kill bad explorations soon enough otherwise the last testcases are totally out of reach.
I think the tag “brute force” should be removed cause an actual brute force would be unrealistic here, it would be factorial 23 for the last testcase, which is ~10^22.
3 Likes
@pardouin Thanks for the comment!
As for the tags, have a look at the first message in the contribution comments:
[CG]Thibaud > Updating the tag “Exhaustive Search” to “Brute Force” as it’s the only puzzle using the former.
I think “Exhaustive Search” was an acceptable tag for this puzzle, maybe “Brute Force” is not as appropriate indeed, but whatever… Anyway it’s a hard puzzle so one should expect to have to think about it twice before coding.
I’m open to suggestions regarding the tags to use. I was trying to clean a bit the tags at the time
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)
4 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 
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 (Backtracking - Wikipedia) 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 
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
The “brute force” tag was somewhat out of place and misleading. In the end, to get 100% at this puzzle, you always reach the point where you would need to check the validity of your result when it is already guaranteed that the result is correct and all resolutions take place under 85ms. What if a “bits manipulations” or “sorting” tag was used instead of the “brute force” one?
Another thing is that I did not use backtracking in the wikipedia sens. So I’m not sure about the other tag either…
Then, concerning the validator test cases, it is weird that during the process of completing the puzzle to 100% I did have more submit external validators passed than IDE validators passed. But I understand that a human is only ever able of ensuring test cases consistency in limited ways when he can only conduct this process mentally.
@Serge_Billault I know but as explained above in this thread, the original tag was Exhaustive Search and was changed to Brute-force by CG staff. As I said before: Anyway it’s a hard puzzle so one should expect to have to think about it twice before coding.
EDIT: I removed the Brute-force tag. That said, lots of puzzles currently under this tag are not strictly-speaking brute-force-able either.
1 Like