Simple recursive Sudoku solverWhat is an algorithm to solve sudoku in efficient way in c?SudokuSharp Solver with advanced featuresSudoku solver in C++N-Queens - Brute force - bit by bitSolver for a number-game (8-queens applied to Sudoku)Sudoku Solver in C++ weekend challengeSudoku puzzle solving algorithm that uses a rule-based approach to narrow the depth searchSudoku solver recursive solution with clear structureRuby Sudoku Solver without classesFast and flexible Sudoku Solver in C++What is an algorithm to solve sudoku in efficient way in c?

Blender - show edges angles “direction”

Can the harmonic series explain the origin of the major scale?

Perfect riffle shuffles

Would it be legal for a US State to ban exports of a natural resource?

What is the term when two people sing in harmony, but they aren't singing the same notes?

Who must act to prevent Brexit on March 29th?

How to prevent YouTube from showing already watched videos?

Can somebody explain Brexit in a few child-proof sentences?

Is there a good way to store credentials outside of a password manager?

Simple recursive Sudoku solver

How to check participants in at events?

Is a naturally all "male" species possible?

What was required to accept "troll"?

Is there enough fresh water in the world to eradicate the drinking water crisis?

Can a controlled ghast be a leader of a pack of ghouls?

Organic chemistry Iodoform Reaction

Java - What do constructor type arguments mean when placed *before* the type?

Why are all the doors on Ferenginar (the Ferengi home world) far shorter than the average Ferengi?

Is there an wasy way to program in Tikz something like the one in the image?

Simple image editor tool to draw a simple box/rectangle in an existing image

How can I raise concerns with a new DM about XP splitting?

Is the next prime number always the next number divisible by the current prime number, except for any numbers previously divisible by primes?

What if somebody invests in my application?

Is there a problem with hiding "forgot password" until it's needed?



Simple recursive Sudoku solver


What is an algorithm to solve sudoku in efficient way in c?SudokuSharp Solver with advanced featuresSudoku solver in C++N-Queens - Brute force - bit by bitSolver for a number-game (8-queens applied to Sudoku)Sudoku Solver in C++ weekend challengeSudoku puzzle solving algorithm that uses a rule-based approach to narrow the depth searchSudoku solver recursive solution with clear structureRuby Sudoku Solver without classesFast and flexible Sudoku Solver in C++What is an algorithm to solve sudoku in efficient way in c?













12












$begingroup$


My Sudoku solver is fast enough and good with small data (4*4 and 9*9 Sudoku). But with a 16*16 board it takes too long and doesn't solve 25*25 Sudoku at all. How can I improve my program in order to solve giant Sudoku faster?



I use backtracking and recursion.



It should work with any size Sudoku by changing only the define of SIZE, so I can't make any specific bit fields or structs that only work for 9*9, for example.



#include <stdio.h>
#include <math.h>

#define SIZE 16
#define EMPTY 0

int SQRT = sqrt(SIZE);

int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number);
int Solve(int sudoku[SIZE][SIZE], int row, int col);

int main()
int sudoku[SIZE][SIZE] =
0,1,2,0,0,4,0,0,0,0,5,0,0,0,0,0,
0,0,0,0,0,2,0,0,0,0,0,0,0,14,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,
11,0,0,0,0,0,0,0,0,0,0,16,0,0,0,0,
0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,16,0,0,0,0,0,0,2,0,0,0,0,0,
0,0,0,0,0,0,0,0,11,0,0,0,0,0,0,0,
0,0,14,0,0,0,0,0,0,4,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,1,16,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,14,0,0,13,0,0,
0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,11,0,0,0,0,0,0,0,0,0,0,0,0,0,
16,0,0,0,0,0,11,0,0,3,0,0,0,0,0,0,
;
/*
int sudoku[SIZE][SIZE] =
6,5,0,8,7,3,0,9,0,
0,0,3,2,5,0,0,0,8,
9,8,0,1,0,4,3,5,7,
1,0,5,0,0,0,0,0,0,
4,0,0,0,0,0,0,0,2,
0,0,0,0,0,0,5,0,3,
5,7,8,3,0,1,0,2,6,
2,0,0,0,4,8,9,0,0,
0,9,0,6,2,5,0,8,1
;*/

if (Solve (sudoku,0,0))

for (int i=0; i<SIZE; i++)

for (int j=0; j<SIZE; j++)
printf("%2d ", sudoku[i][j]);

printf ("n");


else

printf ("No solution n");

return 0;


int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number)

int prRow = SQRT*(row/SQRT);
int prCol = SQRT*(col/SQRT);

for (int i=0;i<SIZE;i++)
if (sudoku[i][col] == number) return 0;
if (sudoku[row][i] == number) return 0;
if (sudoku[prRow + i / SQRT][prCol + i % SQRT] == number) return 0;
return 1;


int Solve(int sudoku[SIZE][SIZE], int row, int col)

if (SIZE == row)
return 1;


if (sudoku[row][col])
if (col == SIZE-1)
if (Solve (sudoku, row+1, 0)) return 1;
else
if (Solve(sudoku, row, col+1)) return 1;

return 0;


for (int number = 1; number <= SIZE; number ++)

if(IsValid(sudoku,row,col,number))

sudoku [row][col] = number;

if (col == SIZE-1)
if (Solve(sudoku, row+1, 0)) return 1;
else
if (Solve(sudoku, row, col+1)) return 1;


sudoku [row][col] = EMPTY;


return 0;










share|improve this question









New contributor




yeosco is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$







  • 1




    $begingroup$
    Can you add a 9x9 and 16x16 file? It will make answering easier.
    $endgroup$
    – Oscar Smith
    9 hours ago










  • $begingroup$
    When you added the 16 X 16 grid you left the size at 9 rather than changing it to 16. This might lead to the wrong results.
    $endgroup$
    – pacmaninbw
    9 hours ago






  • 3




    $begingroup$
    Sudoku is NP complete. No matter what improvements you make to your code, it will become exceptionally slow as SIZE becomes large.
    $endgroup$
    – Benjamin Kuykendall
    9 hours ago










  • $begingroup$
    @pacmaninbw oh sorry, I only forgot to change it while I was editing my post earlier. With that part there is no problem, but thank you!
    $endgroup$
    – yeosco
    9 hours ago






  • 1




    $begingroup$
    Have you tried to use any heuristic? For example if you try solving for the number that occurs the most often first you will have a smaller problem set to solve.
    $endgroup$
    – pacmaninbw
    9 hours ago















12












$begingroup$


My Sudoku solver is fast enough and good with small data (4*4 and 9*9 Sudoku). But with a 16*16 board it takes too long and doesn't solve 25*25 Sudoku at all. How can I improve my program in order to solve giant Sudoku faster?



I use backtracking and recursion.



It should work with any size Sudoku by changing only the define of SIZE, so I can't make any specific bit fields or structs that only work for 9*9, for example.



#include <stdio.h>
#include <math.h>

#define SIZE 16
#define EMPTY 0

int SQRT = sqrt(SIZE);

int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number);
int Solve(int sudoku[SIZE][SIZE], int row, int col);

int main()
int sudoku[SIZE][SIZE] =
0,1,2,0,0,4,0,0,0,0,5,0,0,0,0,0,
0,0,0,0,0,2,0,0,0,0,0,0,0,14,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,
11,0,0,0,0,0,0,0,0,0,0,16,0,0,0,0,
0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,16,0,0,0,0,0,0,2,0,0,0,0,0,
0,0,0,0,0,0,0,0,11,0,0,0,0,0,0,0,
0,0,14,0,0,0,0,0,0,4,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,1,16,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,14,0,0,13,0,0,
0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,11,0,0,0,0,0,0,0,0,0,0,0,0,0,
16,0,0,0,0,0,11,0,0,3,0,0,0,0,0,0,
;
/*
int sudoku[SIZE][SIZE] =
6,5,0,8,7,3,0,9,0,
0,0,3,2,5,0,0,0,8,
9,8,0,1,0,4,3,5,7,
1,0,5,0,0,0,0,0,0,
4,0,0,0,0,0,0,0,2,
0,0,0,0,0,0,5,0,3,
5,7,8,3,0,1,0,2,6,
2,0,0,0,4,8,9,0,0,
0,9,0,6,2,5,0,8,1
;*/

if (Solve (sudoku,0,0))

for (int i=0; i<SIZE; i++)

for (int j=0; j<SIZE; j++)
printf("%2d ", sudoku[i][j]);

printf ("n");


else

printf ("No solution n");

return 0;


int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number)

int prRow = SQRT*(row/SQRT);
int prCol = SQRT*(col/SQRT);

for (int i=0;i<SIZE;i++)
if (sudoku[i][col] == number) return 0;
if (sudoku[row][i] == number) return 0;
if (sudoku[prRow + i / SQRT][prCol + i % SQRT] == number) return 0;
return 1;


int Solve(int sudoku[SIZE][SIZE], int row, int col)

if (SIZE == row)
return 1;


if (sudoku[row][col])
if (col == SIZE-1)
if (Solve (sudoku, row+1, 0)) return 1;
else
if (Solve(sudoku, row, col+1)) return 1;

return 0;


for (int number = 1; number <= SIZE; number ++)

if(IsValid(sudoku,row,col,number))

sudoku [row][col] = number;

if (col == SIZE-1)
if (Solve(sudoku, row+1, 0)) return 1;
else
if (Solve(sudoku, row, col+1)) return 1;


sudoku [row][col] = EMPTY;


return 0;










share|improve this question









New contributor




yeosco is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$







  • 1




    $begingroup$
    Can you add a 9x9 and 16x16 file? It will make answering easier.
    $endgroup$
    – Oscar Smith
    9 hours ago










  • $begingroup$
    When you added the 16 X 16 grid you left the size at 9 rather than changing it to 16. This might lead to the wrong results.
    $endgroup$
    – pacmaninbw
    9 hours ago






  • 3




    $begingroup$
    Sudoku is NP complete. No matter what improvements you make to your code, it will become exceptionally slow as SIZE becomes large.
    $endgroup$
    – Benjamin Kuykendall
    9 hours ago










  • $begingroup$
    @pacmaninbw oh sorry, I only forgot to change it while I was editing my post earlier. With that part there is no problem, but thank you!
    $endgroup$
    – yeosco
    9 hours ago






  • 1




    $begingroup$
    Have you tried to use any heuristic? For example if you try solving for the number that occurs the most often first you will have a smaller problem set to solve.
    $endgroup$
    – pacmaninbw
    9 hours ago













12












12








12


1



$begingroup$


My Sudoku solver is fast enough and good with small data (4*4 and 9*9 Sudoku). But with a 16*16 board it takes too long and doesn't solve 25*25 Sudoku at all. How can I improve my program in order to solve giant Sudoku faster?



I use backtracking and recursion.



It should work with any size Sudoku by changing only the define of SIZE, so I can't make any specific bit fields or structs that only work for 9*9, for example.



#include <stdio.h>
#include <math.h>

#define SIZE 16
#define EMPTY 0

int SQRT = sqrt(SIZE);

int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number);
int Solve(int sudoku[SIZE][SIZE], int row, int col);

int main()
int sudoku[SIZE][SIZE] =
0,1,2,0,0,4,0,0,0,0,5,0,0,0,0,0,
0,0,0,0,0,2,0,0,0,0,0,0,0,14,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,
11,0,0,0,0,0,0,0,0,0,0,16,0,0,0,0,
0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,16,0,0,0,0,0,0,2,0,0,0,0,0,
0,0,0,0,0,0,0,0,11,0,0,0,0,0,0,0,
0,0,14,0,0,0,0,0,0,4,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,1,16,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,14,0,0,13,0,0,
0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,11,0,0,0,0,0,0,0,0,0,0,0,0,0,
16,0,0,0,0,0,11,0,0,3,0,0,0,0,0,0,
;
/*
int sudoku[SIZE][SIZE] =
6,5,0,8,7,3,0,9,0,
0,0,3,2,5,0,0,0,8,
9,8,0,1,0,4,3,5,7,
1,0,5,0,0,0,0,0,0,
4,0,0,0,0,0,0,0,2,
0,0,0,0,0,0,5,0,3,
5,7,8,3,0,1,0,2,6,
2,0,0,0,4,8,9,0,0,
0,9,0,6,2,5,0,8,1
;*/

if (Solve (sudoku,0,0))

for (int i=0; i<SIZE; i++)

for (int j=0; j<SIZE; j++)
printf("%2d ", sudoku[i][j]);

printf ("n");


else

printf ("No solution n");

return 0;


int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number)

int prRow = SQRT*(row/SQRT);
int prCol = SQRT*(col/SQRT);

for (int i=0;i<SIZE;i++)
if (sudoku[i][col] == number) return 0;
if (sudoku[row][i] == number) return 0;
if (sudoku[prRow + i / SQRT][prCol + i % SQRT] == number) return 0;
return 1;


int Solve(int sudoku[SIZE][SIZE], int row, int col)

if (SIZE == row)
return 1;


if (sudoku[row][col])
if (col == SIZE-1)
if (Solve (sudoku, row+1, 0)) return 1;
else
if (Solve(sudoku, row, col+1)) return 1;

return 0;


for (int number = 1; number <= SIZE; number ++)

if(IsValid(sudoku,row,col,number))

sudoku [row][col] = number;

if (col == SIZE-1)
if (Solve(sudoku, row+1, 0)) return 1;
else
if (Solve(sudoku, row, col+1)) return 1;


sudoku [row][col] = EMPTY;


return 0;










share|improve this question









New contributor




yeosco is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




My Sudoku solver is fast enough and good with small data (4*4 and 9*9 Sudoku). But with a 16*16 board it takes too long and doesn't solve 25*25 Sudoku at all. How can I improve my program in order to solve giant Sudoku faster?



I use backtracking and recursion.



It should work with any size Sudoku by changing only the define of SIZE, so I can't make any specific bit fields or structs that only work for 9*9, for example.



#include <stdio.h>
#include <math.h>

#define SIZE 16
#define EMPTY 0

int SQRT = sqrt(SIZE);

int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number);
int Solve(int sudoku[SIZE][SIZE], int row, int col);

int main()
int sudoku[SIZE][SIZE] =
0,1,2,0,0,4,0,0,0,0,5,0,0,0,0,0,
0,0,0,0,0,2,0,0,0,0,0,0,0,14,0,0,
0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,
11,0,0,0,0,0,0,0,0,0,0,16,0,0,0,0,
0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,16,0,0,0,0,0,0,2,0,0,0,0,0,
0,0,0,0,0,0,0,0,11,0,0,0,0,0,0,0,
0,0,14,0,0,0,0,0,0,4,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,1,16,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,14,0,0,13,0,0,
0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,11,0,0,0,0,0,0,0,0,0,0,0,0,0,
16,0,0,0,0,0,11,0,0,3,0,0,0,0,0,0,
;
/*
int sudoku[SIZE][SIZE] =
6,5,0,8,7,3,0,9,0,
0,0,3,2,5,0,0,0,8,
9,8,0,1,0,4,3,5,7,
1,0,5,0,0,0,0,0,0,
4,0,0,0,0,0,0,0,2,
0,0,0,0,0,0,5,0,3,
5,7,8,3,0,1,0,2,6,
2,0,0,0,4,8,9,0,0,
0,9,0,6,2,5,0,8,1
;*/

if (Solve (sudoku,0,0))

for (int i=0; i<SIZE; i++)

for (int j=0; j<SIZE; j++)
printf("%2d ", sudoku[i][j]);

printf ("n");


else

printf ("No solution n");

return 0;


int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number)

int prRow = SQRT*(row/SQRT);
int prCol = SQRT*(col/SQRT);

for (int i=0;i<SIZE;i++)
if (sudoku[i][col] == number) return 0;
if (sudoku[row][i] == number) return 0;
if (sudoku[prRow + i / SQRT][prCol + i % SQRT] == number) return 0;
return 1;


int Solve(int sudoku[SIZE][SIZE], int row, int col)

if (SIZE == row)
return 1;


if (sudoku[row][col])
if (col == SIZE-1)
if (Solve (sudoku, row+1, 0)) return 1;
else
if (Solve(sudoku, row, col+1)) return 1;

return 0;


for (int number = 1; number <= SIZE; number ++)

if(IsValid(sudoku,row,col,number))

sudoku [row][col] = number;

if (col == SIZE-1)
if (Solve(sudoku, row+1, 0)) return 1;
else
if (Solve(sudoku, row, col+1)) return 1;


sudoku [row][col] = EMPTY;


return 0;







performance c recursion sudoku






share|improve this question









New contributor




yeosco is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|improve this question









New contributor




yeosco is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this question




share|improve this question








edited 1 hour ago









Stephen Rauch

3,77061630




3,77061630






New contributor




yeosco is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 10 hours ago









yeoscoyeosco

615




615




New contributor




yeosco is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





yeosco is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






yeosco is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







  • 1




    $begingroup$
    Can you add a 9x9 and 16x16 file? It will make answering easier.
    $endgroup$
    – Oscar Smith
    9 hours ago










  • $begingroup$
    When you added the 16 X 16 grid you left the size at 9 rather than changing it to 16. This might lead to the wrong results.
    $endgroup$
    – pacmaninbw
    9 hours ago






  • 3




    $begingroup$
    Sudoku is NP complete. No matter what improvements you make to your code, it will become exceptionally slow as SIZE becomes large.
    $endgroup$
    – Benjamin Kuykendall
    9 hours ago










  • $begingroup$
    @pacmaninbw oh sorry, I only forgot to change it while I was editing my post earlier. With that part there is no problem, but thank you!
    $endgroup$
    – yeosco
    9 hours ago






  • 1




    $begingroup$
    Have you tried to use any heuristic? For example if you try solving for the number that occurs the most often first you will have a smaller problem set to solve.
    $endgroup$
    – pacmaninbw
    9 hours ago












  • 1




    $begingroup$
    Can you add a 9x9 and 16x16 file? It will make answering easier.
    $endgroup$
    – Oscar Smith
    9 hours ago










  • $begingroup$
    When you added the 16 X 16 grid you left the size at 9 rather than changing it to 16. This might lead to the wrong results.
    $endgroup$
    – pacmaninbw
    9 hours ago






  • 3




    $begingroup$
    Sudoku is NP complete. No matter what improvements you make to your code, it will become exceptionally slow as SIZE becomes large.
    $endgroup$
    – Benjamin Kuykendall
    9 hours ago










  • $begingroup$
    @pacmaninbw oh sorry, I only forgot to change it while I was editing my post earlier. With that part there is no problem, but thank you!
    $endgroup$
    – yeosco
    9 hours ago






  • 1




    $begingroup$
    Have you tried to use any heuristic? For example if you try solving for the number that occurs the most often first you will have a smaller problem set to solve.
    $endgroup$
    – pacmaninbw
    9 hours ago







1




1




$begingroup$
Can you add a 9x9 and 16x16 file? It will make answering easier.
$endgroup$
– Oscar Smith
9 hours ago




$begingroup$
Can you add a 9x9 and 16x16 file? It will make answering easier.
$endgroup$
– Oscar Smith
9 hours ago












$begingroup$
When you added the 16 X 16 grid you left the size at 9 rather than changing it to 16. This might lead to the wrong results.
$endgroup$
– pacmaninbw
9 hours ago




$begingroup$
When you added the 16 X 16 grid you left the size at 9 rather than changing it to 16. This might lead to the wrong results.
$endgroup$
– pacmaninbw
9 hours ago




3




3




$begingroup$
Sudoku is NP complete. No matter what improvements you make to your code, it will become exceptionally slow as SIZE becomes large.
$endgroup$
– Benjamin Kuykendall
9 hours ago




$begingroup$
Sudoku is NP complete. No matter what improvements you make to your code, it will become exceptionally slow as SIZE becomes large.
$endgroup$
– Benjamin Kuykendall
9 hours ago












$begingroup$
@pacmaninbw oh sorry, I only forgot to change it while I was editing my post earlier. With that part there is no problem, but thank you!
$endgroup$
– yeosco
9 hours ago




$begingroup$
@pacmaninbw oh sorry, I only forgot to change it while I was editing my post earlier. With that part there is no problem, but thank you!
$endgroup$
– yeosco
9 hours ago




1




1




$begingroup$
Have you tried to use any heuristic? For example if you try solving for the number that occurs the most often first you will have a smaller problem set to solve.
$endgroup$
– pacmaninbw
9 hours ago




$begingroup$
Have you tried to use any heuristic? For example if you try solving for the number that occurs the most often first you will have a smaller problem set to solve.
$endgroup$
– pacmaninbw
9 hours ago










2 Answers
2






active

oldest

votes


















10












$begingroup$

The first thing that will help is to switch this from a recursive algorithm to an iterative one. This will prevent the stack overflow that prevents you from solving 25x25, and will be a bit faster to boot.



However to speed this up more, you will probably need to use a smarter algorithm. If you track what numbers are possible in each square, you will find that much of the time, there is only 1 possibility. In this case, you know what number goes there. You then can update all of the other squares in the same row, col, or box as the one you just filled in. To implement this efficiently, you would want to define a set (either a bitset or hashset) for what is available in each square, and use a heap to track which squares have the fewest remaining possibilities.






share|improve this answer









$endgroup$








  • 2




    $begingroup$
    Might I suggest Dancing links as an entry point for your search into a smarter algoriothm?
    $endgroup$
    – WorldSEnder
    5 hours ago










  • $begingroup$
    The max recursion depth of this algorithm = number of squares, I think. 25*25 is only 625. The recursion doesn't create a copy of the board in each stack frame, so it probably only uses about 32 bytes per frame on x86-64. (Solve doesn't have any locals other than its args to save across a recursive call: an 8-byte pointer and 2x 4-byte int. That plus a return address, and maintaining 16-byte stack alignment as per the ABI, probably adds up to a 32-byte stack frame on x86-64 Linux or OS X. Or maybe 48 bytes with Windows x64 where the shadow space alone takes 32 bytes.)
    $endgroup$
    – Peter Cordes
    1 hour ago











  • $begingroup$
    Anyway, that's only 25*25*48 = 30kB (not 30kiB) of stack memory max, which trivial (stack limits of 1MiB to 8MiB are common). Even a factor of 10 error in my reasoning isn't a problem. So it's not stack overflow, it's simply the O(SIZE^SIZE) exponential time complexity that stops SIZE=25 from running in usable time.
    $endgroup$
    – Peter Cordes
    1 hour ago











  • $begingroup$
    Yeah, any idea why it wasn't returning for 25x25 before? Just speed?
    $endgroup$
    – Oscar Smith
    1 hour ago










  • $begingroup$
    @OscarSmith: I'd assume just speed, yeah, that's compatible with the OP's wording. n^n grows very fast! Or maybe an unsolvable board? Anyway, Sudoku solutions finder using brute force and backtracking goes into detail on your suggestion to try cells with fewer possibilities first. There are several other Q&As in the "related" sidebar that look useful.
    $endgroup$
    – Peter Cordes
    1 hour ago


















7












$begingroup$

The strategy needs work: brute-force search is going to scale very badly. As an order-of-magnitude estimate, observe that the code calls IsValid() around SIZE times for each cell - that's O(n³), where n is the SIZE.



Be more consistent with formatting. It's easier to read (and to search) code if there's a consistent convention. To take a simple example, we have:




int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number)
int Solve(int sudoku[SIZE][SIZE], int row, int col)

if (Solve (sudoku,0,0))
if(IsValid(sudoku,row,col,number))



all with differing amounts of space around (. This kind of inconsistency gives an impression of code that's been written in a hurry, without consideration for the reader.



Instead of defining SIZE and deriving SQRT, it's simpler to start with SQRT and define SIZE to be (SQRT * SQRT). Then there's no need for <math.h> and no risk of floating-point approximation being unfortunately truncated when it's converted to integer.



The declaration of main() should be a prototype:



int main(void)





share|improve this answer









$endgroup$








  • 1




    $begingroup$
    Very good suggestion to make SQRT a compile-time constant. The code uses stuff like prRow + i / SQRT and i % SQRT, which will compile to a runtime integer division (like x86 idiv) because int SQRT is a non-const global! And with a non-constant initializer, so I don't think this is even valid C. But fun fact: gcc does accept it as C (doing constant-propagation through sqrt even with optimization disabled). But clang rejects it. godbolt.org/z/4jrJmL. Anyway yes, we get nasty idiv unless we use const int sqrt (or better unsigned) godbolt.org/z/NMB156
    $endgroup$
    – Peter Cordes
    4 hours ago










Your Answer





StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);






yeosco is a new contributor. Be nice, and check out our Code of Conduct.









draft saved

draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f216171%2fsimple-recursive-sudoku-solver%23new-answer', 'question_page');

);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









10












$begingroup$

The first thing that will help is to switch this from a recursive algorithm to an iterative one. This will prevent the stack overflow that prevents you from solving 25x25, and will be a bit faster to boot.



However to speed this up more, you will probably need to use a smarter algorithm. If you track what numbers are possible in each square, you will find that much of the time, there is only 1 possibility. In this case, you know what number goes there. You then can update all of the other squares in the same row, col, or box as the one you just filled in. To implement this efficiently, you would want to define a set (either a bitset or hashset) for what is available in each square, and use a heap to track which squares have the fewest remaining possibilities.






share|improve this answer









$endgroup$








  • 2




    $begingroup$
    Might I suggest Dancing links as an entry point for your search into a smarter algoriothm?
    $endgroup$
    – WorldSEnder
    5 hours ago










  • $begingroup$
    The max recursion depth of this algorithm = number of squares, I think. 25*25 is only 625. The recursion doesn't create a copy of the board in each stack frame, so it probably only uses about 32 bytes per frame on x86-64. (Solve doesn't have any locals other than its args to save across a recursive call: an 8-byte pointer and 2x 4-byte int. That plus a return address, and maintaining 16-byte stack alignment as per the ABI, probably adds up to a 32-byte stack frame on x86-64 Linux or OS X. Or maybe 48 bytes with Windows x64 where the shadow space alone takes 32 bytes.)
    $endgroup$
    – Peter Cordes
    1 hour ago











  • $begingroup$
    Anyway, that's only 25*25*48 = 30kB (not 30kiB) of stack memory max, which trivial (stack limits of 1MiB to 8MiB are common). Even a factor of 10 error in my reasoning isn't a problem. So it's not stack overflow, it's simply the O(SIZE^SIZE) exponential time complexity that stops SIZE=25 from running in usable time.
    $endgroup$
    – Peter Cordes
    1 hour ago











  • $begingroup$
    Yeah, any idea why it wasn't returning for 25x25 before? Just speed?
    $endgroup$
    – Oscar Smith
    1 hour ago










  • $begingroup$
    @OscarSmith: I'd assume just speed, yeah, that's compatible with the OP's wording. n^n grows very fast! Or maybe an unsolvable board? Anyway, Sudoku solutions finder using brute force and backtracking goes into detail on your suggestion to try cells with fewer possibilities first. There are several other Q&As in the "related" sidebar that look useful.
    $endgroup$
    – Peter Cordes
    1 hour ago















10












$begingroup$

The first thing that will help is to switch this from a recursive algorithm to an iterative one. This will prevent the stack overflow that prevents you from solving 25x25, and will be a bit faster to boot.



However to speed this up more, you will probably need to use a smarter algorithm. If you track what numbers are possible in each square, you will find that much of the time, there is only 1 possibility. In this case, you know what number goes there. You then can update all of the other squares in the same row, col, or box as the one you just filled in. To implement this efficiently, you would want to define a set (either a bitset or hashset) for what is available in each square, and use a heap to track which squares have the fewest remaining possibilities.






share|improve this answer









$endgroup$








  • 2




    $begingroup$
    Might I suggest Dancing links as an entry point for your search into a smarter algoriothm?
    $endgroup$
    – WorldSEnder
    5 hours ago










  • $begingroup$
    The max recursion depth of this algorithm = number of squares, I think. 25*25 is only 625. The recursion doesn't create a copy of the board in each stack frame, so it probably only uses about 32 bytes per frame on x86-64. (Solve doesn't have any locals other than its args to save across a recursive call: an 8-byte pointer and 2x 4-byte int. That plus a return address, and maintaining 16-byte stack alignment as per the ABI, probably adds up to a 32-byte stack frame on x86-64 Linux or OS X. Or maybe 48 bytes with Windows x64 where the shadow space alone takes 32 bytes.)
    $endgroup$
    – Peter Cordes
    1 hour ago











  • $begingroup$
    Anyway, that's only 25*25*48 = 30kB (not 30kiB) of stack memory max, which trivial (stack limits of 1MiB to 8MiB are common). Even a factor of 10 error in my reasoning isn't a problem. So it's not stack overflow, it's simply the O(SIZE^SIZE) exponential time complexity that stops SIZE=25 from running in usable time.
    $endgroup$
    – Peter Cordes
    1 hour ago











  • $begingroup$
    Yeah, any idea why it wasn't returning for 25x25 before? Just speed?
    $endgroup$
    – Oscar Smith
    1 hour ago










  • $begingroup$
    @OscarSmith: I'd assume just speed, yeah, that's compatible with the OP's wording. n^n grows very fast! Or maybe an unsolvable board? Anyway, Sudoku solutions finder using brute force and backtracking goes into detail on your suggestion to try cells with fewer possibilities first. There are several other Q&As in the "related" sidebar that look useful.
    $endgroup$
    – Peter Cordes
    1 hour ago













10












10








10





$begingroup$

The first thing that will help is to switch this from a recursive algorithm to an iterative one. This will prevent the stack overflow that prevents you from solving 25x25, and will be a bit faster to boot.



However to speed this up more, you will probably need to use a smarter algorithm. If you track what numbers are possible in each square, you will find that much of the time, there is only 1 possibility. In this case, you know what number goes there. You then can update all of the other squares in the same row, col, or box as the one you just filled in. To implement this efficiently, you would want to define a set (either a bitset or hashset) for what is available in each square, and use a heap to track which squares have the fewest remaining possibilities.






share|improve this answer









$endgroup$



The first thing that will help is to switch this from a recursive algorithm to an iterative one. This will prevent the stack overflow that prevents you from solving 25x25, and will be a bit faster to boot.



However to speed this up more, you will probably need to use a smarter algorithm. If you track what numbers are possible in each square, you will find that much of the time, there is only 1 possibility. In this case, you know what number goes there. You then can update all of the other squares in the same row, col, or box as the one you just filled in. To implement this efficiently, you would want to define a set (either a bitset or hashset) for what is available in each square, and use a heap to track which squares have the fewest remaining possibilities.







share|improve this answer












share|improve this answer



share|improve this answer










answered 9 hours ago









Oscar SmithOscar Smith

2,8931123




2,8931123







  • 2




    $begingroup$
    Might I suggest Dancing links as an entry point for your search into a smarter algoriothm?
    $endgroup$
    – WorldSEnder
    5 hours ago










  • $begingroup$
    The max recursion depth of this algorithm = number of squares, I think. 25*25 is only 625. The recursion doesn't create a copy of the board in each stack frame, so it probably only uses about 32 bytes per frame on x86-64. (Solve doesn't have any locals other than its args to save across a recursive call: an 8-byte pointer and 2x 4-byte int. That plus a return address, and maintaining 16-byte stack alignment as per the ABI, probably adds up to a 32-byte stack frame on x86-64 Linux or OS X. Or maybe 48 bytes with Windows x64 where the shadow space alone takes 32 bytes.)
    $endgroup$
    – Peter Cordes
    1 hour ago











  • $begingroup$
    Anyway, that's only 25*25*48 = 30kB (not 30kiB) of stack memory max, which trivial (stack limits of 1MiB to 8MiB are common). Even a factor of 10 error in my reasoning isn't a problem. So it's not stack overflow, it's simply the O(SIZE^SIZE) exponential time complexity that stops SIZE=25 from running in usable time.
    $endgroup$
    – Peter Cordes
    1 hour ago











  • $begingroup$
    Yeah, any idea why it wasn't returning for 25x25 before? Just speed?
    $endgroup$
    – Oscar Smith
    1 hour ago










  • $begingroup$
    @OscarSmith: I'd assume just speed, yeah, that's compatible with the OP's wording. n^n grows very fast! Or maybe an unsolvable board? Anyway, Sudoku solutions finder using brute force and backtracking goes into detail on your suggestion to try cells with fewer possibilities first. There are several other Q&As in the "related" sidebar that look useful.
    $endgroup$
    – Peter Cordes
    1 hour ago












  • 2




    $begingroup$
    Might I suggest Dancing links as an entry point for your search into a smarter algoriothm?
    $endgroup$
    – WorldSEnder
    5 hours ago










  • $begingroup$
    The max recursion depth of this algorithm = number of squares, I think. 25*25 is only 625. The recursion doesn't create a copy of the board in each stack frame, so it probably only uses about 32 bytes per frame on x86-64. (Solve doesn't have any locals other than its args to save across a recursive call: an 8-byte pointer and 2x 4-byte int. That plus a return address, and maintaining 16-byte stack alignment as per the ABI, probably adds up to a 32-byte stack frame on x86-64 Linux or OS X. Or maybe 48 bytes with Windows x64 where the shadow space alone takes 32 bytes.)
    $endgroup$
    – Peter Cordes
    1 hour ago











  • $begingroup$
    Anyway, that's only 25*25*48 = 30kB (not 30kiB) of stack memory max, which trivial (stack limits of 1MiB to 8MiB are common). Even a factor of 10 error in my reasoning isn't a problem. So it's not stack overflow, it's simply the O(SIZE^SIZE) exponential time complexity that stops SIZE=25 from running in usable time.
    $endgroup$
    – Peter Cordes
    1 hour ago











  • $begingroup$
    Yeah, any idea why it wasn't returning for 25x25 before? Just speed?
    $endgroup$
    – Oscar Smith
    1 hour ago










  • $begingroup$
    @OscarSmith: I'd assume just speed, yeah, that's compatible with the OP's wording. n^n grows very fast! Or maybe an unsolvable board? Anyway, Sudoku solutions finder using brute force and backtracking goes into detail on your suggestion to try cells with fewer possibilities first. There are several other Q&As in the "related" sidebar that look useful.
    $endgroup$
    – Peter Cordes
    1 hour ago







2




2




$begingroup$
Might I suggest Dancing links as an entry point for your search into a smarter algoriothm?
$endgroup$
– WorldSEnder
5 hours ago




$begingroup$
Might I suggest Dancing links as an entry point for your search into a smarter algoriothm?
$endgroup$
– WorldSEnder
5 hours ago












$begingroup$
The max recursion depth of this algorithm = number of squares, I think. 25*25 is only 625. The recursion doesn't create a copy of the board in each stack frame, so it probably only uses about 32 bytes per frame on x86-64. (Solve doesn't have any locals other than its args to save across a recursive call: an 8-byte pointer and 2x 4-byte int. That plus a return address, and maintaining 16-byte stack alignment as per the ABI, probably adds up to a 32-byte stack frame on x86-64 Linux or OS X. Or maybe 48 bytes with Windows x64 where the shadow space alone takes 32 bytes.)
$endgroup$
– Peter Cordes
1 hour ago





$begingroup$
The max recursion depth of this algorithm = number of squares, I think. 25*25 is only 625. The recursion doesn't create a copy of the board in each stack frame, so it probably only uses about 32 bytes per frame on x86-64. (Solve doesn't have any locals other than its args to save across a recursive call: an 8-byte pointer and 2x 4-byte int. That plus a return address, and maintaining 16-byte stack alignment as per the ABI, probably adds up to a 32-byte stack frame on x86-64 Linux or OS X. Or maybe 48 bytes with Windows x64 where the shadow space alone takes 32 bytes.)
$endgroup$
– Peter Cordes
1 hour ago













$begingroup$
Anyway, that's only 25*25*48 = 30kB (not 30kiB) of stack memory max, which trivial (stack limits of 1MiB to 8MiB are common). Even a factor of 10 error in my reasoning isn't a problem. So it's not stack overflow, it's simply the O(SIZE^SIZE) exponential time complexity that stops SIZE=25 from running in usable time.
$endgroup$
– Peter Cordes
1 hour ago





$begingroup$
Anyway, that's only 25*25*48 = 30kB (not 30kiB) of stack memory max, which trivial (stack limits of 1MiB to 8MiB are common). Even a factor of 10 error in my reasoning isn't a problem. So it's not stack overflow, it's simply the O(SIZE^SIZE) exponential time complexity that stops SIZE=25 from running in usable time.
$endgroup$
– Peter Cordes
1 hour ago













$begingroup$
Yeah, any idea why it wasn't returning for 25x25 before? Just speed?
$endgroup$
– Oscar Smith
1 hour ago




$begingroup$
Yeah, any idea why it wasn't returning for 25x25 before? Just speed?
$endgroup$
– Oscar Smith
1 hour ago












$begingroup$
@OscarSmith: I'd assume just speed, yeah, that's compatible with the OP's wording. n^n grows very fast! Or maybe an unsolvable board? Anyway, Sudoku solutions finder using brute force and backtracking goes into detail on your suggestion to try cells with fewer possibilities first. There are several other Q&As in the "related" sidebar that look useful.
$endgroup$
– Peter Cordes
1 hour ago




$begingroup$
@OscarSmith: I'd assume just speed, yeah, that's compatible with the OP's wording. n^n grows very fast! Or maybe an unsolvable board? Anyway, Sudoku solutions finder using brute force and backtracking goes into detail on your suggestion to try cells with fewer possibilities first. There are several other Q&As in the "related" sidebar that look useful.
$endgroup$
– Peter Cordes
1 hour ago













7












$begingroup$

The strategy needs work: brute-force search is going to scale very badly. As an order-of-magnitude estimate, observe that the code calls IsValid() around SIZE times for each cell - that's O(n³), where n is the SIZE.



Be more consistent with formatting. It's easier to read (and to search) code if there's a consistent convention. To take a simple example, we have:




int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number)
int Solve(int sudoku[SIZE][SIZE], int row, int col)

if (Solve (sudoku,0,0))
if(IsValid(sudoku,row,col,number))



all with differing amounts of space around (. This kind of inconsistency gives an impression of code that's been written in a hurry, without consideration for the reader.



Instead of defining SIZE and deriving SQRT, it's simpler to start with SQRT and define SIZE to be (SQRT * SQRT). Then there's no need for <math.h> and no risk of floating-point approximation being unfortunately truncated when it's converted to integer.



The declaration of main() should be a prototype:



int main(void)





share|improve this answer









$endgroup$








  • 1




    $begingroup$
    Very good suggestion to make SQRT a compile-time constant. The code uses stuff like prRow + i / SQRT and i % SQRT, which will compile to a runtime integer division (like x86 idiv) because int SQRT is a non-const global! And with a non-constant initializer, so I don't think this is even valid C. But fun fact: gcc does accept it as C (doing constant-propagation through sqrt even with optimization disabled). But clang rejects it. godbolt.org/z/4jrJmL. Anyway yes, we get nasty idiv unless we use const int sqrt (or better unsigned) godbolt.org/z/NMB156
    $endgroup$
    – Peter Cordes
    4 hours ago















7












$begingroup$

The strategy needs work: brute-force search is going to scale very badly. As an order-of-magnitude estimate, observe that the code calls IsValid() around SIZE times for each cell - that's O(n³), where n is the SIZE.



Be more consistent with formatting. It's easier to read (and to search) code if there's a consistent convention. To take a simple example, we have:




int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number)
int Solve(int sudoku[SIZE][SIZE], int row, int col)

if (Solve (sudoku,0,0))
if(IsValid(sudoku,row,col,number))



all with differing amounts of space around (. This kind of inconsistency gives an impression of code that's been written in a hurry, without consideration for the reader.



Instead of defining SIZE and deriving SQRT, it's simpler to start with SQRT and define SIZE to be (SQRT * SQRT). Then there's no need for <math.h> and no risk of floating-point approximation being unfortunately truncated when it's converted to integer.



The declaration of main() should be a prototype:



int main(void)





share|improve this answer









$endgroup$








  • 1




    $begingroup$
    Very good suggestion to make SQRT a compile-time constant. The code uses stuff like prRow + i / SQRT and i % SQRT, which will compile to a runtime integer division (like x86 idiv) because int SQRT is a non-const global! And with a non-constant initializer, so I don't think this is even valid C. But fun fact: gcc does accept it as C (doing constant-propagation through sqrt even with optimization disabled). But clang rejects it. godbolt.org/z/4jrJmL. Anyway yes, we get nasty idiv unless we use const int sqrt (or better unsigned) godbolt.org/z/NMB156
    $endgroup$
    – Peter Cordes
    4 hours ago













7












7








7





$begingroup$

The strategy needs work: brute-force search is going to scale very badly. As an order-of-magnitude estimate, observe that the code calls IsValid() around SIZE times for each cell - that's O(n³), where n is the SIZE.



Be more consistent with formatting. It's easier to read (and to search) code if there's a consistent convention. To take a simple example, we have:




int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number)
int Solve(int sudoku[SIZE][SIZE], int row, int col)

if (Solve (sudoku,0,0))
if(IsValid(sudoku,row,col,number))



all with differing amounts of space around (. This kind of inconsistency gives an impression of code that's been written in a hurry, without consideration for the reader.



Instead of defining SIZE and deriving SQRT, it's simpler to start with SQRT and define SIZE to be (SQRT * SQRT). Then there's no need for <math.h> and no risk of floating-point approximation being unfortunately truncated when it's converted to integer.



The declaration of main() should be a prototype:



int main(void)





share|improve this answer









$endgroup$



The strategy needs work: brute-force search is going to scale very badly. As an order-of-magnitude estimate, observe that the code calls IsValid() around SIZE times for each cell - that's O(n³), where n is the SIZE.



Be more consistent with formatting. It's easier to read (and to search) code if there's a consistent convention. To take a simple example, we have:




int IsValid (int sudoku[SIZE][SIZE], int row, int col, int number)
int Solve(int sudoku[SIZE][SIZE], int row, int col)

if (Solve (sudoku,0,0))
if(IsValid(sudoku,row,col,number))



all with differing amounts of space around (. This kind of inconsistency gives an impression of code that's been written in a hurry, without consideration for the reader.



Instead of defining SIZE and deriving SQRT, it's simpler to start with SQRT and define SIZE to be (SQRT * SQRT). Then there's no need for <math.h> and no risk of floating-point approximation being unfortunately truncated when it's converted to integer.



The declaration of main() should be a prototype:



int main(void)






share|improve this answer












share|improve this answer



share|improve this answer










answered 9 hours ago









Toby SpeightToby Speight

26.6k742118




26.6k742118







  • 1




    $begingroup$
    Very good suggestion to make SQRT a compile-time constant. The code uses stuff like prRow + i / SQRT and i % SQRT, which will compile to a runtime integer division (like x86 idiv) because int SQRT is a non-const global! And with a non-constant initializer, so I don't think this is even valid C. But fun fact: gcc does accept it as C (doing constant-propagation through sqrt even with optimization disabled). But clang rejects it. godbolt.org/z/4jrJmL. Anyway yes, we get nasty idiv unless we use const int sqrt (or better unsigned) godbolt.org/z/NMB156
    $endgroup$
    – Peter Cordes
    4 hours ago












  • 1




    $begingroup$
    Very good suggestion to make SQRT a compile-time constant. The code uses stuff like prRow + i / SQRT and i % SQRT, which will compile to a runtime integer division (like x86 idiv) because int SQRT is a non-const global! And with a non-constant initializer, so I don't think this is even valid C. But fun fact: gcc does accept it as C (doing constant-propagation through sqrt even with optimization disabled). But clang rejects it. godbolt.org/z/4jrJmL. Anyway yes, we get nasty idiv unless we use const int sqrt (or better unsigned) godbolt.org/z/NMB156
    $endgroup$
    – Peter Cordes
    4 hours ago







1




1




$begingroup$
Very good suggestion to make SQRT a compile-time constant. The code uses stuff like prRow + i / SQRT and i % SQRT, which will compile to a runtime integer division (like x86 idiv) because int SQRT is a non-const global! And with a non-constant initializer, so I don't think this is even valid C. But fun fact: gcc does accept it as C (doing constant-propagation through sqrt even with optimization disabled). But clang rejects it. godbolt.org/z/4jrJmL. Anyway yes, we get nasty idiv unless we use const int sqrt (or better unsigned) godbolt.org/z/NMB156
$endgroup$
– Peter Cordes
4 hours ago




$begingroup$
Very good suggestion to make SQRT a compile-time constant. The code uses stuff like prRow + i / SQRT and i % SQRT, which will compile to a runtime integer division (like x86 idiv) because int SQRT is a non-const global! And with a non-constant initializer, so I don't think this is even valid C. But fun fact: gcc does accept it as C (doing constant-propagation through sqrt even with optimization disabled). But clang rejects it. godbolt.org/z/4jrJmL. Anyway yes, we get nasty idiv unless we use const int sqrt (or better unsigned) godbolt.org/z/NMB156
$endgroup$
– Peter Cordes
4 hours ago










yeosco is a new contributor. Be nice, and check out our Code of Conduct.









draft saved

draft discarded


















yeosco is a new contributor. Be nice, and check out our Code of Conduct.












yeosco is a new contributor. Be nice, and check out our Code of Conduct.











yeosco is a new contributor. Be nice, and check out our Code of Conduct.














Thanks for contributing an answer to Code Review Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid


  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f216171%2fsimple-recursive-sudoku-solver%23new-answer', 'question_page');

);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Францішак Багушэвіч Змест Сям'я | Біяграфія | Творчасць | Мова Багушэвіча | Ацэнкі дзейнасці | Цікавыя факты | Спадчына | Выбраная бібліяграфія | Ушанаванне памяці | У філатэліі | Зноскі | Літаратура | Спасылкі | НавігацыяЛяхоўскі У. Рупіўся дзеля Бога і людзей: Жыццёвы шлях Лявона Вітан-Дубейкаўскага // Вольскі і Памідораў з песняй пра немца Адвакат, паэт, народны заступнік Ашмянскі веснікВ Минске появится площадь Богушевича и улица Сырокомли, Белорусская деловая газета, 19 июля 2001 г.Айцец беларускай нацыянальнай ідэі паўстаў у бронзе Сяргей Аляксандравіч Адашкевіч (1918, Мінск). 80-я гады. Бюст «Францішак Багушэвіч».Яўген Мікалаевіч Ціхановіч. «Партрэт Францішка Багушэвіча»Мікола Мікалаевіч Купава. «Партрэт зачынальніка новай беларускай літаратуры Францішка Багушэвіча»Уладзімір Іванавіч Мелехаў. На помніку «Змагарам за родную мову» Барэльеф «Францішак Багушэвіч»Памяць пра Багушэвіча на Віленшчыне Страчаная сталіца. Беларускія шыльды на вуліцах Вільні«Krynica». Ideologia i przywódcy białoruskiego katolicyzmuФранцішак БагушэвічТворы на knihi.comТворы Францішка Багушэвіча на bellib.byСодаль Уладзімір. Францішак Багушэвіч на Лідчыне;Луцкевіч Антон. Жыцьцё і творчасьць Фр. Багушэвіча ў успамінах ягоных сучасьнікаў // Запісы Беларускага Навуковага таварыства. Вільня, 1938. Сшытак 1. С. 16-34.Большая российская1188761710000 0000 5537 633Xn9209310021619551927869394п

Беларусь Змест Назва Гісторыя Геаграфія Сімволіка Дзяржаўны лад Палітычныя партыі Міжнароднае становішча і знешняя палітыка Адміністрацыйны падзел Насельніцтва Эканоміка Культура і грамадства Сацыяльная сфера Узброеныя сілы Заўвагі Літаратура Спасылкі НавігацыяHGЯOiТоп-2011 г. (па версіі ej.by)Топ-2013 г. (па версіі ej.by)Топ-2016 г. (па версіі ej.by)Топ-2017 г. (па версіі ej.by)Нацыянальны статыстычны камітэт Рэспублікі БеларусьШчыльнасць насельніцтва па краінахhttp://naviny.by/rubrics/society/2011/09/16/ic_articles_116_175144/А. Калечыц, У. Ксяндзоў. Спробы засялення краю неандэртальскім чалавекам.І ў Менску былі мамантыА. Калечыц, У. Ксяндзоў. Старажытны каменны век (палеаліт). Першапачатковае засяленне тэрыторыіГ. Штыхаў. Балты і славяне ў VI—VIII стст.М. Клімаў. Полацкае княства ў IX—XI стст.Г. Штыхаў, В. Ляўко. Палітычная гісторыя Полацкай зямліГ. Штыхаў. Дзяржаўны лад у землях-княствахГ. Штыхаў. Дзяржаўны лад у землях-княствахБеларускія землі ў складзе Вялікага Княства ЛітоўскагаЛюблінская унія 1569 г."The Early Stages of Independence"Zapomniane prawdy25 гадоў таму было аб'яўлена, што Язэп Пілсудскі — беларус (фота)Наша вадаДакументы ЧАЭС: Забруджванне тэрыторыі Беларусі « ЧАЭС Зона адчужэнняСведения о политических партиях, зарегистрированных в Республике Беларусь // Министерство юстиции Республики БеларусьСтатыстычны бюлетэнь „Полаўзроставая структура насельніцтва Рэспублікі Беларусь на 1 студзеня 2012 года і сярэднегадовая колькасць насельніцтва за 2011 год“Индекс человеческого развития Беларуси — не было бы нижеБеларусь занимает первое место в СНГ по индексу развития с учетом гендерного факцёраНацыянальны статыстычны камітэт Рэспублікі БеларусьКанстытуцыя РБ. Артыкул 17Трансфармацыйныя задачы БеларусіВыйсце з крызісу — далейшае рэфармаванне Беларускі рубель — сусветны лідар па дэвальвацыяхПра змену коштаў у кастрычніку 2011 г.Бядней за беларусаў у СНД толькі таджыкіСярэдні заробак у верасні дасягнуў 2,26 мільёна рублёўЭканомікаГаласуем за ТОП-100 беларускай прозыСучасныя беларускія мастакіАрхитектура Беларуси BELARUS.BYА. Каханоўскі. Культура Беларусі ўсярэдзіне XVII—XVIII ст.Анталогія беларускай народнай песні, гуказапісы спеваўБеларускія Музычныя IнструментыБеларускі рок, які мы страцілі. Топ-10 гуртоў«Мясцовы час» — нязгаслая легенда беларускай рок-музыкіСЯРГЕЙ БУДКІН. МЫ НЯ ЗНАЕМ СВАЁЙ МУЗЫКІМ. А. Каладзінскі. НАРОДНЫ ТЭАТРМагнацкія культурныя цэнтрыПублічная дыскусія «Беларуская новая пьеса: без беларускай мовы ці беларуская?»Беларускія драматургі па-ранейшаму лепш ставяцца за мяжой, чым на радзіме«Працэс незалежнага кіно пайшоў, і дзяржаву турбуе яго непадкантрольнасць»Беларускія філосафы ў пошуках прасторыВсе идём в библиотекуАрхіваванаАб Нацыянальнай праграме даследавання і выкарыстання касмічнай прасторы ў мірных мэтах на 2008—2012 гадыУ космас — разам.У суседнім з Барысаўскім раёне пабудуюць Камандна-вымяральны пунктСвяты і абрады беларусаў«Мірныя бульбашы з малой краіны» — 5 непраўдзівых стэрэатыпаў пра БеларусьМ. Раманюк. Беларускае народнае адзеннеУ Беларусі скарачаецца колькасць злачынстваўЛукашэнка незадаволены мінскімі ўладамі Крадзяжы складаюць у Мінску каля 70% злачынстваў Узровень злачыннасці ў Мінскай вобласці — адзін з самых высокіх у краіне Генпракуратура аналізуе стан са злачыннасцю ў Беларусі па каэфіцыенце злачыннасці У Беларусі стабілізавалася крымінагеннае становішча, лічыць генпракурорЗамежнікі сталі здзяйсняць у Беларусі больш злачынстваўМУС Беларусі турбуе рост рэцыдыўнай злачыннасціЯ з ЖЭСа. Дазволіце вас абкрасці! Рэйтынг усіх службаў і падраздзяленняў ГУУС Мінгарвыканкама вырасАб КДБ РБГісторыя Аператыўна-аналітычнага цэнтра РБГісторыя ДКФРТаможняagentura.ruБеларусьBelarus.by — Афіцыйны сайт Рэспублікі БеларусьСайт урада БеларусіRadzima.org — Збор архітэктурных помнікаў, гісторыя Беларусі«Глобус Беларуси»Гербы и флаги БеларусиАсаблівасці каменнага веку на БеларусіА. Калечыц, У. Ксяндзоў. Старажытны каменны век (палеаліт). Першапачатковае засяленне тэрыторыіУ. Ксяндзоў. Сярэдні каменны век (мезаліт). Засяленне краю плямёнамі паляўнічых, рыбакоў і збіральнікаўА. Калечыц, М. Чарняўскі. Плямёны на тэрыторыі Беларусі ў новым каменным веку (неаліце)А. Калечыц, У. Ксяндзоў, М. Чарняўскі. Гаспадарчыя заняткі ў каменным векуЭ. Зайкоўскі. Духоўная культура ў каменным векуАсаблівасці бронзавага веку на БеларусіФарміраванне супольнасцей ранняга перыяду бронзавага векуФотографии БеларусиРоля беларускіх зямель ва ўтварэнні і ўмацаванні ВКЛВ. Фадзеева. З гісторыі развіцця беларускай народнай вышыўкіDMOZGran catalanaБольшая российскаяBritannica (анлайн)Швейцарскі гістарычны15325917611952699xDA123282154079143-90000 0001 2171 2080n9112870100577502ge128882171858027501086026362074122714179пппппп

ValueError: Expected n_neighbors <= n_samples, but n_samples = 1, n_neighbors = 6 (SMOTE) The 2019 Stack Overflow Developer Survey Results Are InCan SMOTE be applied over sequence of words (sentences)?ValueError when doing validation with random forestsSMOTE and multi class oversamplingLogic behind SMOTE-NC?ValueError: Error when checking target: expected dense_1 to have shape (7,) but got array with shape (1,)SmoteBoost: Should SMOTE be ran individually for each iteration/tree in the boosting?solving multi-class imbalance classification using smote and OSSUsing SMOTE for Synthetic Data generation to improve performance on unbalanced dataproblem of entry format for a simple model in KerasSVM SMOTE fit_resample() function runs forever with no result