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?
What does the "3am" section means in manpages?
Can the electrostatic force be infinite in magnitude?
Why are all the doors on Ferenginar (the Ferengi home world) far shorter than the average Ferengi?
Is the next prime number always the next number divisible by the current prime number, except for any numbers previously divisible by primes?
Simulating a probability of 1 of 2^N with less than N random bits
Organic chemistry Iodoform Reaction
Is there an wasy way to program in Tikz something like the one in the image?
Reply ‘no position’ while the job posting is still there (‘HiWi’ position in Germany)
What is Sitecore Managed Cloud?
Greatest common substring
Would it be legal for a US State to ban exports of a natural resource?
Can a Gentile theist be saved?
Is infinity mathematically observable?
Blender - show edges angles “direction”
Resetting two CD4017 counters simultaneously, only one resets
Can I Retrieve Email Addresses from BCC?
Is there an Impartial Brexit Deal comparison site?
Is there a problem with hiding "forgot password" until it's needed?
What (else) happened July 1st 1858 in London?
Is there enough fresh water in the world to eradicate the drinking water crisis?
Indicating multiple different modes of speech (fantasy language or telepathy)
How did Monica know how to operate Carol's "designer"?
Teaching indefinite integrals that require special-casing
Can I create an upright 7-foot × 5-foot wall with the Minor Illusion spell?
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?
$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;
performance c recursion sudoku
New contributor
$endgroup$
add a comment |
$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;
performance c recursion sudoku
New contributor
$endgroup$
1
$begingroup$
Can you add a 9x9 and 16x16 file? It will make answering easier.
$endgroup$
– Oscar Smith
8 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
8 hours ago
3
$begingroup$
Sudoku is NP complete. No matter what improvements you make to your code, it will become exceptionally slow asSIZE
becomes large.
$endgroup$
– Benjamin Kuykendall
8 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
8 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
8 hours ago
add a comment |
$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;
performance c recursion sudoku
New contributor
$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
performance c recursion sudoku
New contributor
New contributor
edited 9 mins ago
Stephen Rauch
3,77061630
3,77061630
New contributor
asked 9 hours ago
yeoscoyeosco
615
615
New contributor
New contributor
1
$begingroup$
Can you add a 9x9 and 16x16 file? It will make answering easier.
$endgroup$
– Oscar Smith
8 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
8 hours ago
3
$begingroup$
Sudoku is NP complete. No matter what improvements you make to your code, it will become exceptionally slow asSIZE
becomes large.
$endgroup$
– Benjamin Kuykendall
8 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
8 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
8 hours ago
add a comment |
1
$begingroup$
Can you add a 9x9 and 16x16 file? It will make answering easier.
$endgroup$
– Oscar Smith
8 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
8 hours ago
3
$begingroup$
Sudoku is NP complete. No matter what improvements you make to your code, it will become exceptionally slow asSIZE
becomes large.
$endgroup$
– Benjamin Kuykendall
8 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
8 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
8 hours ago
1
1
$begingroup$
Can you add a 9x9 and 16x16 file? It will make answering easier.
$endgroup$
– Oscar Smith
8 hours ago
$begingroup$
Can you add a 9x9 and 16x16 file? It will make answering easier.
$endgroup$
– Oscar Smith
8 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
8 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
8 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
8 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
8 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
8 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
8 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
8 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
8 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$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.
$endgroup$
2
$begingroup$
Might I suggest Dancing links as an entry point for your search into a smarter algoriothm?
$endgroup$
– WorldSEnder
4 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-byteint
. 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
18 mins ago
$begingroup$
Anyway, that's only25*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 theO(SIZE^SIZE)
exponential time complexity that stops SIZE=25 from running in usable time.
$endgroup$
– Peter Cordes
13 mins ago
$begingroup$
Yeah, any idea why it wasn't returning for 25x25 before? Just speed?
$endgroup$
– Oscar Smith
10 mins 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
8 mins ago
add a comment |
$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)
$endgroup$
1
$begingroup$
Very good suggestion to makeSQRT
a compile-time constant. The code uses stuff likeprRow + i / SQRT
andi % SQRT
, which will compile to a runtime integer division (like x86idiv
) becauseint 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 throughsqrt
even with optimization disabled). But clang rejects it. godbolt.org/z/4jrJmL. Anyway yes, we get nastyidiv
unless we useconst int sqrt
(or better unsigned) godbolt.org/z/NMB156
$endgroup$
– Peter Cordes
3 hours ago
add a comment |
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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.
$endgroup$
2
$begingroup$
Might I suggest Dancing links as an entry point for your search into a smarter algoriothm?
$endgroup$
– WorldSEnder
4 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-byteint
. 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
18 mins ago
$begingroup$
Anyway, that's only25*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 theO(SIZE^SIZE)
exponential time complexity that stops SIZE=25 from running in usable time.
$endgroup$
– Peter Cordes
13 mins ago
$begingroup$
Yeah, any idea why it wasn't returning for 25x25 before? Just speed?
$endgroup$
– Oscar Smith
10 mins 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
8 mins ago
add a comment |
$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.
$endgroup$
2
$begingroup$
Might I suggest Dancing links as an entry point for your search into a smarter algoriothm?
$endgroup$
– WorldSEnder
4 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-byteint
. 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
18 mins ago
$begingroup$
Anyway, that's only25*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 theO(SIZE^SIZE)
exponential time complexity that stops SIZE=25 from running in usable time.
$endgroup$
– Peter Cordes
13 mins ago
$begingroup$
Yeah, any idea why it wasn't returning for 25x25 before? Just speed?
$endgroup$
– Oscar Smith
10 mins 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
8 mins ago
add a comment |
$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.
$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.
answered 8 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
4 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-byteint
. 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
18 mins ago
$begingroup$
Anyway, that's only25*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 theO(SIZE^SIZE)
exponential time complexity that stops SIZE=25 from running in usable time.
$endgroup$
– Peter Cordes
13 mins ago
$begingroup$
Yeah, any idea why it wasn't returning for 25x25 before? Just speed?
$endgroup$
– Oscar Smith
10 mins 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
8 mins ago
add a comment |
2
$begingroup$
Might I suggest Dancing links as an entry point for your search into a smarter algoriothm?
$endgroup$
– WorldSEnder
4 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-byteint
. 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
18 mins ago
$begingroup$
Anyway, that's only25*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 theO(SIZE^SIZE)
exponential time complexity that stops SIZE=25 from running in usable time.
$endgroup$
– Peter Cordes
13 mins ago
$begingroup$
Yeah, any idea why it wasn't returning for 25x25 before? Just speed?
$endgroup$
– Oscar Smith
10 mins 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
8 mins ago
2
2
$begingroup$
Might I suggest Dancing links as an entry point for your search into a smarter algoriothm?
$endgroup$
– WorldSEnder
4 hours ago
$begingroup$
Might I suggest Dancing links as an entry point for your search into a smarter algoriothm?
$endgroup$
– WorldSEnder
4 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
18 mins 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
18 mins 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
13 mins 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
13 mins ago
$begingroup$
Yeah, any idea why it wasn't returning for 25x25 before? Just speed?
$endgroup$
– Oscar Smith
10 mins ago
$begingroup$
Yeah, any idea why it wasn't returning for 25x25 before? Just speed?
$endgroup$
– Oscar Smith
10 mins 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
8 mins 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
8 mins ago
add a comment |
$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)
$endgroup$
1
$begingroup$
Very good suggestion to makeSQRT
a compile-time constant. The code uses stuff likeprRow + i / SQRT
andi % SQRT
, which will compile to a runtime integer division (like x86idiv
) becauseint 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 throughsqrt
even with optimization disabled). But clang rejects it. godbolt.org/z/4jrJmL. Anyway yes, we get nastyidiv
unless we useconst int sqrt
(or better unsigned) godbolt.org/z/NMB156
$endgroup$
– Peter Cordes
3 hours ago
add a comment |
$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)
$endgroup$
1
$begingroup$
Very good suggestion to makeSQRT
a compile-time constant. The code uses stuff likeprRow + i / SQRT
andi % SQRT
, which will compile to a runtime integer division (like x86idiv
) becauseint 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 throughsqrt
even with optimization disabled). But clang rejects it. godbolt.org/z/4jrJmL. Anyway yes, we get nastyidiv
unless we useconst int sqrt
(or better unsigned) godbolt.org/z/NMB156
$endgroup$
– Peter Cordes
3 hours ago
add a comment |
$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)
$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)
answered 8 hours ago
Toby SpeightToby Speight
26.6k742118
26.6k742118
1
$begingroup$
Very good suggestion to makeSQRT
a compile-time constant. The code uses stuff likeprRow + i / SQRT
andi % SQRT
, which will compile to a runtime integer division (like x86idiv
) becauseint 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 throughsqrt
even with optimization disabled). But clang rejects it. godbolt.org/z/4jrJmL. Anyway yes, we get nastyidiv
unless we useconst int sqrt
(or better unsigned) godbolt.org/z/NMB156
$endgroup$
– Peter Cordes
3 hours ago
add a comment |
1
$begingroup$
Very good suggestion to makeSQRT
a compile-time constant. The code uses stuff likeprRow + i / SQRT
andi % SQRT
, which will compile to a runtime integer division (like x86idiv
) becauseint 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 throughsqrt
even with optimization disabled). But clang rejects it. godbolt.org/z/4jrJmL. Anyway yes, we get nastyidiv
unless we useconst int sqrt
(or better unsigned) godbolt.org/z/NMB156
$endgroup$
– Peter Cordes
3 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
3 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
3 hours ago
add a comment |
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.
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
1
$begingroup$
Can you add a 9x9 and 16x16 file? It will make answering easier.
$endgroup$
– Oscar Smith
8 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
8 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
8 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
8 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
8 hours ago