Hello, sudoku generator, need help
Author
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.
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#.
- 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#.
I wrote this sudoku generator in C++ a couple of years ago. Use freely.
EDIT: Actually, I later modified this program to follow the exact method described by Nyarlath, but I don't have the code with me.
#include <iostream>#include <cstdlib>#include <ctime>class BitCount { int bc[512];public: BitCount(){ bc[0]=0; for(int i=1;i<512;++i) bc=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='_'; 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[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[j]; if(v&&(v&(v-1))==0){ for(int x=0;x<9;++x){ if(x!=j){ int temp=s.t[x]&~v; if(s.t[x]!=temp){ s.t[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[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[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[j]==511); } else{ // then we try every square systematically i=n%9; j=(n/9)%9; if(s.t[j]==511) continue; } int temp=s.t[j]; s.t[j]=511; if(solve(s,2)!=1) s.t[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.
Author
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]
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=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='_'; 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[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[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[x]&~v; if(s.t[x]!=temp) { s.t[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[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[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; 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[j]; s.t[j]=511; if(solve(s,2)!=1) s.t[j]=temp; // We can't remove this one: restore } // Print the resulting diagram std::cout << s << std::endl;}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 a lot of time .
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 loopMore or less :P
Author
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).
Thank you for your help (both of you).
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 ;)
Author
Quote:Original post by NyarlathQuote: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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
