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