[Community Puzzle] Sudoku Solver

https://www.codingame.com/training/medium/sudoku-solver

Send your feedback or ask for help here!

Created by @AllTheKingsMen,validated by @bbb000bbbyyy and @Razovsky.
If you have any issues, feel free to ping them.

There is a 4x4 Mini-Sudoku-solver puzzle in the hard section, while this one is 9x9 and in the medium section. Comparing with other community puzzles, ‘medium difficulty’ is the more appropriate.

Exactly same code solves both, if you make the grid size a parameter… Buy one, get one free :smile:

2 Likes

As far as I remember, the 4×4 can be brute forced, not the 9×9 one.

1 Like

IMO this puzzle should never have been validated anyway (though contribution guidelines do not seem to acknowledge that kind of problem), see discussions here.

I implemented a plain vanilla backtrack and it worked for both (the only little consideration is not to test all lines/columns/boxes, only that one that has the last changed cell.)
There might be “anti-backtrack” challenges (no or rare hints on the upper part of the grid or first empty cells tending to be 9 8 7, meaning the algorithm cannot prune early), but none of the test cases/validators seem to be of this kind, or the machine is now fast enough no matter what is the input.

Brute force for 4×4, back track for 9×9.

My code’s output for the third testcase is valid sudoku solution, but doesn’t match with the one from the original answer:
1243 doesn’t match with 4132
2314
3421
4132

You have to use every number in every smaller square exactly once. The ‘2’ appears twice in the top left square.

2 Likes

I’ve been trying to pass the last test of the 9x9 one (World’s Hardest Sudoku) and despite the fact my program resolves it, it says the execution time was too long.

I don’t know how fast it must be in python but I tried to apply every optimization I could and still not getting it.

-I took care of transmitting the y and x position when self calling my solve function for recursion
-used list comprehension as much as I could and where it was time profitable
-used local variables and function calls to save some processing time
-drastically limited variable assignation

I even tried to use numpy arrays but it was taking more time. I probably didn’t implement it the right way but man, this one is kinda tricky.
I don’t even know where I could add good optimizations yet. I’m gonna sleep, the rest might help me find solutions, but I’m all ears if any of you has any piece of advise to share.

Thanks for the challenge, very interesting.

I’m not using recursion, just an list with a pointer that wander and tries to fill the gaps.
I’m using backtracking.

I also used a slow language (PHP). For IDE Test 04 (“World’s hardest sudoku”) my solution takes 0.8740 sec and the recursive backtracking function is called 445,779 times. (It fills the grid going right, then down, trying numbers in ascending order. Different order would result different iterations count.)

If your algorithm uses much more iterations than this, then maybe you are not trimming back the search agressively enough. In each iterations I test if the current partial solution is possible at all, if not -> backtrack.

If the number of iterations is similar, then maybe you need to make the “testing currrent solution if it needs to be rejected” part a bit faster. For example do not check each column, row and box every time. Check only where the last cell was filled.

Thanks for your answers my friends.

I did a similar approach to TBali’s one, backtracking, nested loops top to bottom and trying at each 0 found to put a number, check if it can be placed, if not possible, increment till 9.
If 9 is reached an no number fit, I return False and my recursion starts the backtracking putting zero on the previously attempted move to try another possibilities (which I assume is the same for you when you say “In each iterations I test if the current partial solution is possible at all, if not -> backtrack.”)

If I can trust my mesures, my “solve_sudo” is executed in [0.3556542154401541] seconds with [49559] iterations.

I optimized a lot in my function to check if possible to place in row, column, square, I’m at lowest complexity there with the container I use.

I’ll try with another container but I’m quite wondering how fast this thing has to be… 0.35sec is not that heavy

Dang it, actually with a freaking exit(0) after final print, it works a lot better.

I’m so mad at me !
At least it’s solved and quite optimized, \o/
sudoku%20solved

1 Like

What a pleasure it was to solve this problem!
I’ve learned the whole new algorithm here. Well, new for me, but it was published 20 years ago to solve this exact problem.