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 
3 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.
1 Like
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/
3 Likes
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.
Hello guys , i’ve got a problem , i solved every tests in c but when i submit it block on de subgrid problem and i don’t see it. Can you help me ??? Sorry it’s really not optimized but i just began in coding and my first objective is to solve all the easy puzzles.
Blockquote int main()
{
bool f = true ;
int sudoku[9][9], c = 0 ;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
scanf("%d", &sudoku[i][j] );
}
}
for ( int k = 0 ; k < 9 ; k ++){
for (int i = 0; i < 9 ; i++) {
for ( int j = 0 ; j < 9; j++){
if (sudoku[k][i] == sudoku[k][j] ){ c++;}
}
if ( c < 2){c = 0;}
else {goto fin ;}
}
}
for ( int k = 0 ; k < 9 ; k ++){
for (int i = 0; i < 9 ; i++) {
for ( int j = 0 ; j < 9; j++){
if (sudoku[i][k] == sudoku[j][k] ){ c++;}
}
if ( c < 2){c = 0;}
else {goto fin ;}
}
}
for ( int k = 0 ; k < 9 ; k += 3){// subgrill x of the grill
for ( int x = 0 ; x < 9; x += 3){// subgrill y of the grill
int tab[9] = { 1,2,3,4,5,6,7,8,9};//tab with each number possible by grill
for ( int i = 0 ; i < 3 ; i++){// x of the sub grill
for ( int j = 0 ; j < 3 ; j++){// y of the surbgrill
for (int z =0 ; z < 9 ; z++){//take off the correspondent number of the tab
if ( sudoku[i][j] == tab[z]){ tab[z] = 0;}
}
}
}
for (int m = 0 ; m < 9; m++){
c += tab[m];//if there was a mising number took frome the tab c !=0
}
if ( c != 0){break;}
}
}
fin :
if ( c != 0)
f = false;
// Write an answer using printf(). DON'T FORGET THE TRAILING \n
// To debug: fprintf(stderr, "Debug messages...\n");
printf(f ? "true": "false");
return 0;
}
how to do sudoku vadilator? or however you spell
There’s a puzzle ranked “easy” when you only create the validator. You should give it a try.
But basically you can use a function valid(i, j, number) to check if number can be placed in cell i, j.
In your function:
- if number is already in row i, return false
- if number is already in column j, return false
- if number is already in subsquare containing cell i, j, return false
return true (will be executed only if all previous tests fail)
The tricky part is the subsquare, you can start by finding the coordinates I, J of the top-left cell of the subsquare and then iterate over rows in range I…I+2 and columns in range J…J+2.
I, J are basically the smallest multiples of 3 which are <= i, <= j.
If you finish this puzzle and want free xp, there’s a very similar one in “hard” called mini sudoku solver.
2 Likes
Mine is pretty optimized (uses backtracking) , but still cannot solve the last one (World’s Hardest Sudoku). It takes 49558 calls to solve it (Python 3) 
I get the same counter of tries for the last test but it’s still very fast.
Are you using immutable data / cloning matrix at each try ? That could explain your performance problem.
Hmmm I’m not sure I’m still a beginner. I have a list of stings from the input. And I change it every time this way: sudoku[i][:j] + str(n) + sudoku[i][j+1:] (for n in range (1,10) and i and j are for looping trough the sudoku from left to righ and down) also I change it back to 0 the same way