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.

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

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/

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.