[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:

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/
sudoku%20solved

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) :frowning:

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