# 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 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 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 on other sites
Quote:
 Original post by NyarlathHi, 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#.

- 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 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 numberclass 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 squarewe'll have a 9-bit integer where a set bit means that it is inprinciple possible that the square will have the value correspondingto that bit.To be clear, the mapping is:  1 -> 1  2 -> 2  4 -> 3  8 -> 4 16 -> 5 32 -> 6 64 -> 7128 -> 8256 -> 9511 (the sum of all the above) means that we don't know anything aboutthis square.*/ struct S {  int t[9][9];};// In this global variable we store the result of the recursive searchS last_solution;// This just spits out the diagramstd::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 solvethe puzzle by backtracking, looping over the possibilities of one ofthe squares that has the fewest possibilities left. The search isstopped once n_sol solutions have been found. random' indicateswhether 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 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 3x3Algorithm:  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 on other sites
OK, I wrote a back-tracking solver, what I am doing now? (I cannot run this on simple empty board ...)

Thank you for your help (both of you).

##### Share on other sites
Quote:
 Original post by Answer3OK, 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 on other sites
Quote:
Original post by Nyarlath
Quote:
 Original post by Answer3OK, 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 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 on other sites
Quote:
 Original post by Answer3I 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!

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628375
• Total Posts
2982310

• 10
• 9
• 14
• 24
• 11