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