Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @Saur2000,validated by @papyjo,@cedricdd and @Exanc.
If you have any issues, feel free to ping them.
It is never enough of these Japanese āfill the gridā puzzlesā¦ 
One concern: while it is a good practice that the validators are slightly easier then the IDE tests, this puzzle takes it a bit too far: my dumb backtracking solution takes 214 secs (!) to solve IDE TEST #04 (over a billion iterationsā¦), yet it still passes 100% of the validators.
As there is obviously a much better approach with cutting the iteration count by better utilizing the info from the partially filled grid, my code should not have passed. Now I am not motivated enough to improve itā¦
I should try to submit even if all the tests donāt pass more often, I never do that 
If you manage to find the motivation you could improve it by at least a factor of 713, test #4 is taking ~0.3s for me with our slow language. (assuming you went with PHP for that one too)
1 Like
I am passing IDE test case #4 100% of the time with my Python non-DLX Algorithm X implementation. Really great puzzle! Reducing the grid before starting the backtracking required a lot more thought than I first imagined.
Iām soooooo freaking lost on this puzzle, I canāt fathom a way to optimize the backtracking itās driving me crazy if anyone has a tip on how to optimize a backtracking algorythm for this puzzle I beg you to give me an hint
You may want to talk about what you do in your current code first?
yes indeed, Iām doing a simple backtracking algorythm but Iām doing it in a certain āorderā from cages to cages and starting by the cage with the least total ammount of possibilities to the one with the higher ammount, it works with the first test case, but I get timed out even at the second one, I tried to pass some data throught the backtracking algorythm and revert the changes made to them if it was a dead end but that always failed
Does your code try to eliminate certain impossible choices before starting the backtracking?
Letās take the first test as an example:
G. G4 G1 G.
R. G. B. B.
G. R. R4 B.
G. R. R2 B.
G3 G. R. B.
ā¢ The unknown Gs in rows 1 and 2 can be 2 or 3 or 5 only.
ā¢ The R in row 2 can be 1 only. So the G directly below cannot be 1 (and can be 2 or 4 only).
ā¢ The R diagonally neighbouring the R mentioned above cannot be 1 either, nor 2 nor 4 (and can be 3 or 5 only).
thanks for the hint ! I will rethink about this puzzle with this in mind !
1 Like
How are you coming along on your puzzle @Leo_Leclerc. Have you solved it yet? I thought I would take a look at my code this morning and see if I could optimize it more based on what Iāve learned the last several months doing other similar grid puzzles, primarily Killer Sudoku.
Obviously, backtracking comes with a cost. Every wrong path is wasted time. Iāve found that with these grid puzzles, there is usually a clever way or two to reduce the grid with known numbers before starting any backtracking. My current submission for Suguru Solver needs to use backtracking on all four test cases and these are my approximate average times as measured inside the CG IDE:
4x5 - 2 ms
8x8 - 200 ms
15x10 - 60 ms
20x20 - 2400 ms
After staring at the numbers this morning, I came up with a few more grid reduction techniques to add to what @5DN1L identified above. I can now solve 3 of the 4 test cases with no backtracking. I still need my backtracking to solve the 8x8 test case. Here are my new times:
4x5 - 2 ms
8x8 - 100 ms (I am doing less backtracking than before.)
15x10 - 15 ms
20x20 - 45 ms
Keep looking for those grid reduction techniques and let us know what you come up with! In the meantime, Iām going to keep staring at the 8x8 grid and try to find a way to solve it with no backtracking.
2 Likes