Sign in to follow this  
Answer3

Hello, sudoku generator, need help

Recommended Posts

Hello, I am new here. I want to write a sudoku game in c, but I have problem. The problem is creating right sudoku board. I tried few options but after some time there is problem with placing numbers or it took a lot of time or just stuck in some place of time. May be there is some algorithms, some ideas or something that can help me? (I don't need code). I put this topic here, because it's not a game programing problem, it's more "just programing" problem. Sorry for my english, and I hope for answers. Thanks.

Share this post


Link to post
Share on other sites
Hi, I did implement a sudoku generator some time ago. What I did:

- Generate a random finished sudoku. To do that I made my solver give me a random solution to an empty sudoku.
- Traverse all the cells in a random order: remove the cell and solve the sudoku until you solve it all or you find two solutions. If it has more than one solution, put back the value of the cell.

Of course you need an efficient solver (generate a sudoku using my algorithm needs around 50 times the time needed to solve one), but I could generate hundreds of sudokus per second using c#.

Share this post


Link to post
Share on other sites
I wrote this sudoku generator in C++ a couple of years ago. Use freely.
#include <iostream>
#include <cstdlib>
#include <ctime>

class BitCount {
int bc[512];
public:
BitCount(){
bc[0]=0;
for(int i=1;i<512;++i)
bc[i]=bc[i>>1]+(i&1);
}
int operator()(unsigned x){
return bc[x];
}
} bit_count;

struct S{
int t[9][9];
};

S last_solution;

std::ostream &operator<<(std::ostream &o, const S &s){
static char display[512];
static bool initialized=false;

if(!initialized){
for(int i=0;i<512;++i)
display[i]='_';
for(int i=0;i<9;++i)
display[1u<<i]='1'+i;
}
for(int i=0;i<9;++i){
for(int j=0;j<9;++j)
o << display[s.t[i][j]] << ' ';
o << '\n';
}

return o;
}

int solve(S s, int n_sol, bool random=false){
bool changed;
do{
changed=false;
// Deduce some options that are not available
for(int i=0;i<9;++i){
for(int j=0;j<9;++j){
int v=s.t[i][j];
if(v&&(v&(v-1))==0){
for(int x=0;x<9;++x){
if(x!=j){
int temp=s.t[i][x]&~v;
if(s.t[i][x]!=temp){
s.t[i][x]=temp;
changed=true;
}
}
if(x!=i){
int temp=s.t[x][j]&~v;
if(s.t[x][j]!=temp){
s.t[x][j]=temp;
changed=true;
}
}
}
int bx=i/3*3;
int by=j/3*3;
for(int x=0;x<3;++x){
for(int y=0;y<3;++y){
if(bx+x!=i || by+y!=j){
int temp=s.t[bx+x][by+y]&~v;
if(s.t[bx+x][by+y]!=temp){
s.t[bx+x][by+y]=temp;
changed=true;
}
}
}
}
}
}
}
}while(changed);

// Find the spot with the fewest ones
int min_bit_count=10;
int bi=0,bj=0;
for(int i=0;i<9;++i){
for(int j=0;j<9;++j){
int this_bit_count = bit_count(s.t[i][j]);
if(this_bit_count==0)
return 0;
if(this_bit_count>1 && this_bit_count<min_bit_count){
min_bit_count = this_bit_count;
bi=i;
bj=j;
}
}
}

// Solved?
if(min_bit_count==10){
last_solution = s;
return 1;
}

if(random){
do{
bi=std::rand()%9;
bj=std::rand()%9;
}while(bit_count(s.t[bi][bj])!=min_bit_count);
}

// Back-tracking
int counter=0;
int s_t_bi_bj=s.t[bi][bj];
for(int i=0;i<9;++i){
if((1u<<i)&s_t_bi_bj){
s.t[bi][bj]=1u<<i;
counter += solve(s,n_sol-counter,random);
if(counter>=n_sol)
return counter;
}
s.t[bi][bj]=s_t_bi_bj;
}
return counter;
}

int main(){
std::srand(std::time(0));
S s;
for(int i=0;i<9;++i){
for(int j=0;j<9;++j)
s.t[i][j]=511;
}

// Generate a completed sudoku
solve(s,1,true);
s=last_solution;

// Try to remove numbers
for(int n=0;n<181;++n){
int i,j;
if(n<100){ // First we try random removals
do{
i=std::rand()%9;
j=std::rand()%9;
}while(s.t[i][j]==511);
}
else{ // then we try every square systematically
i=n%9;
j=(n/9)%9;
if(s.t[i][j]==511)
continue;
}
int temp=s.t[i][j];
s.t[i][j]=511;
if(solve(s,2)!=1)
s.t[i][j]=temp;
}
std::cout << s << std::endl;
}



EDIT: Actually, I later modified this program to follow the exact method described by Nyarlath, but I don't have the code with me.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nyarlath
Hi, I did implement a sudoku generator some time ago. What I did:

- Generate a random finished sudoku. To do that I made my solver give me a random solution to an empty sudoku.
- Traverse all the cells in a random order: remove the cell and solve the sudoku until you solve it all or you find two solutions. If it has more than one solution, put back the value of the cell.

Of course you need an efficient solver (generate a sudoku using my algorithm needs around 50 times the time needed to solve one), but I could generate hundreds of sudokus per second using c#.


Hi again. first of all thank your for answers.

- OK, lets say I wrote a solver, when I run it on empty board it's the same like placing random numbers in the first level and it may stuck in future.
- Placing just random numbers and then try to solve it, just to risky and it may work sometime and mostly may not.
- I tried to write backtracking algorithm on empty board, but in some place in time it just stuck and didn't continue. Lets say, theoretically if it not stuck it can take a lot of time .

if you explain little more.

Alvaro, I didn't understand all code, if you can explain it more deeply, I will appreciate that.

Thanks again.

[Edited by - Answer3 on October 14, 2008 3:59:30 AM]

Share this post


Link to post
Share on other sites
I added much-needed comments and implemented the attempted elimination of numbers in a random order correctly. Let me know if anything is not clear.

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>

// Simple look-up table to count how many bits are set in a 9-bit number
class BitCount {
int bc[512];
public:
BitCount() {
bc[0]=0;
for(int i=1;i<512;++i)
bc[i]=bc[i>>1]+(i&1);
}
int operator()(unsigned x) {
return bc[x];
}
} bit_count;

/*
The struct S represents what we know of the board. For each square
we'll have a 9-bit integer where a set bit means that it is in
principle possible that the square will have the value corresponding
to that bit.

To be clear, the mapping is:
1 -> 1
2 -> 2
4 -> 3
8 -> 4
16 -> 5
32 -> 6
64 -> 7
128 -> 8
256 -> 9

511 (the sum of all the above) means that we don't know anything about
this square.
*/

struct S {
int t[9][9];
};

// In this global variable we store the result of the recursive search
S last_solution;

// This just spits out the diagram
std::ostream &operator<<(std::ostream &o, const S &s) {
static char display[512];
static bool initialized=false;

if(!initialized) {
// Any square that is not a set number will be printed as '_'
for(int i=0;i<512;++i)
display[i]='_';
for(int i=0;i<9;++i)
display[1u<<i]='1'+i;
}
for(int i=0;i<9;++i) {
for(int j=0;j<9;++j)
o << display[s.t[i][j]] << ' ';
o << '\n';
}

return o;
}

/*
This function eliminates obvious possibilities and then tries to solve
the puzzle by backtracking, looping over the possibilities of one of
the squares that has the fewest possibilities left. The search is
stopped once n_sol solutions have been found. `random' indicates
whether we'll pick a random spot to do the backtracking step or not.
*/

int solve(S s, int n_sol, bool random=false) {
bool changed;
do {
changed=false;
// Deduce some options that are not available
for(int i=0;i<9;++i) {
for(int j=0;j<9;++j) {
int v=s.t[i][j];
if(bit_count(v)==1) { // If this number is set in stone
for(int x=0;x<9;++x) {
if(x!=j) { // This number is not present elsewhere in this row
int temp=s.t[i][x]&~v;
if(s.t[i][x]!=temp) {
s.t[i][x]=temp;
changed=true;
}
}
if(x!=i) { // This number is not present elsewhere in this column
int temp=s.t[x][j]&~v;
if(s.t[x][j]!=temp) {
s.t[x][j]=temp;
changed=true;
}
}
}
// This number is not present elsewhere in this 3x3 box
int bx=i/3*3;
int by=j/3*3;
for(int x=0;x<3;++x) {
for(int y=0;y<3;++y) {
if(bx+x!=i || by+y!=j) {
int temp=s.t[bx+x][by+y]&~v;
if(s.t[bx+x][by+y]!=temp) {
s.t[bx+x][by+y]=temp;
changed=true;
}
}
}
}
}
}
}
} while(changed);

// Now we can't deduce anything else with this simple rule

// Find the spot with the fewest ones
int min_bit_count=10;
int bi=0,bj=0;
for(int i=0;i<9;++i) {
for(int j=0;j<9;++j) {
int this_bit_count = bit_count(s.t[i][j]);
if(this_bit_count==0)
return 0;
if(this_bit_count>1 && this_bit_count<min_bit_count) {
min_bit_count = this_bit_count;
bi=i;
bj=j;
}
}
}

// Solved?
if(min_bit_count==10) {
last_solution = s;
return 1;
}

if(random) { // Find a random point with the minimum number of possibilities
do {
bi=std::rand()%9;
bj=std::rand()%9;
}while(bit_count(s.t[bi][bj])!=min_bit_count);
}

// Back-tracking
int counter=0;
int s_t_bi_bj=s.t[bi][bj];
for(int i=0;i<9;++i) {
if((1u<<i)&s_t_bi_bj) {
s.t[bi][bj]=1u<<i;
counter += solve(s,n_sol-counter,random);
if(counter>=n_sol)
return counter;
}
s.t[bi][bj]=s_t_bi_bj;
}
return counter;
}

int main() {
std::srand(std::time(0));
S s;
for(int i=0;i<9;++i) {
for(int j=0;j<9;++j)
s.t[i][j]=511;
}

// Generate a completed sudoku
solve(s,1,true);
s=last_solution;

// Pick a random order
int order[81];
for(int i=0;i<81;++i)
order[i]=i;
std::random_shuffle(order,order+81);

// Try to remove numbers
for(int n=0;n<81;++n) {
int o=order[n];
int i=o%9;
int j=o/9;
int temp=s.t[i][j];
s.t[i][j]=511;
if(solve(s,2)!=1)
s.t[i][j]=temp; // We can't remove this one: restore
}

// Print the resulting diagram
std::cout << s << std::endl;
}



Share this post


Link to post
Share on other sites
Quote:
Original post by Answer3
- I tried to write backtracking algorithm on empty board, but in some place in time it just stuck and didn't continue. Lets say, theoretically if it not stuck it can take [b] a lot of time [b].

Well, the first thing you need to implement a generator is a solver. Specifically, one that can solve any sudoku and never stuck. It also must be able to tell you that the grid presented is not a valid sudoku if it has no solution or more than one. I assumed you already had that, and you should actually fix it before you start to implement a generator.

Generate a sudoku is not simple as filling a grid with random numbers, you have to ensure that there is one and only one solution (and possibly that you provide the least possible numbers, although I saw some retard publishing non-minimal sudokus).

How I did implement my sudoku solver:

Terminology:
cell is 1x1
line is 9x1
column is 1x9
square is 3x3

Algorithm:
mark all cells UNFIXED
initialize the a list of all candidate values for each cell to 1, 2, 3, 4, 5, 6, 7, 8, 9
resize to 1 the list of the values for the cell you know the value (initial conditions, constraints), don't mark as fixed

loop until all are marked FIXED
set flag = false
loop over all cells
if the cell is NOT marked as fixed and the list of the values for the cell has size one
remove the value of the current cell from all cells in the same line, column and square of the current cell
if the list of candidate values is empty then ABORT
mark the current cell as FIXED
set flag = true
end if
end loop
//comment: here you can do some other test (I did some/many, but someway complicated)
while flag == false
choose a not already FIXED cell and assign it one of its candidate values (call it V)
re-run this algorithm (recursion)
if the recursion ABORTs
unassign V (choose a different cell or value at next cycle)
if all cells and values have been tried then ABORT
else
set flag == true
end if
end while
end loop


More or less :P

Share this post


Link to post
Share on other sites
Quote:
Original post by Answer3
OK, I wrote a back-tracking solver, what I am doing now?

Test it on many boards of which you know the solution (some with a single solution, others with many and some without solution).

Then find a solution of an empty board; The solver should be able to find all the solutions (in some billion years ;), but you need just a random one (why you think you cannot?). That is the starting point of the algorithm I wrote in my first post. You are very close to the generator now ;)

Share this post


Link to post
Share on other sites
Quote:
Original post by Nyarlath
Quote:
Original post by Answer3
OK, I wrote a back-tracking solver, what I am doing now?

Test it on many boards of which you know the solution (some with a single solution, others with many and some without solution).

Then find a solution of an empty board; The solver should be able to find all the solutions (in some billion years ;), but you need just a random one (why you think you cannot?). That is the starting point of the algorithm I wrote in my first post. You are very close to the generator now ;)


Hi, again.

I tested it on some boards, the solver works perfectly.

But, I didn't understand what did you mean when you said "All solutions of empty board". I run it on empty board and it gave me only one solution.

Otherwise, I thought about placing a little number of numbers and then try to solve it, but it risky and I dropped this idea off.

Thank you again.

Share this post


Link to post
Share on other sites
Quote:
Original post by Answer3
[...]

But, I didn't understand what did you mean when you said "All solutions of empty board". I run it on empty board and it gave me only one solution.


In your backtracking step, you probably loop over all the possible numbers that can go in a particular square. Just pick your square randomly, or pick the order in which you search those numbers randomly. The result will be a random full board.

Share this post


Link to post
Share on other sites
Quote:
Original post by Answer3
I run it on empty board and it gave me only one solution.


It gives you the first solution it founds (the first line is probably 123456789 and the second is 456123789 and so on, if no randomness is involved).

That's fine for the moment, keep this filled board as starting point.

Now you need to be able to detect that/if there is more than one solution. You just shouldn't stop your algorithm when it founds a solution; if you find one, remember it and continue with your back-tracking algorithm until all possible values of every cell are tried. If you find a second solution, stop the algorithm and return the solution previously found and a boolean indicating that there are other solution.

Now you can implement the second step of the algorithm of my first post!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this