| View previous topic :: View next topic |
| Author |
Message |
| monkeyfoahead
| | Joined: 12 Apr 2008 | | Posts: 3 | | : | |
Items |
|
 Posted: Sun Apr 13, 2008 3:24 pm Post subject: Sudoku Generator in C++ |
 |
|
Hey everyone. I stumbled upon this place looking for a answer to a problem I encountered while writing my own generator. My problem is this:
I wrote a genereator that randomly picks cells in a matrix and randomly fills them in. I use arrays of bools to determine if the number has been used before or not. The problem I have is that I cannot create a valid puzzle. All my puzzles get deadlocked during generation becuase I cannot think of a valid method to make sure a number wont be entered that would disallow entering the only possible number in another field.
Here is my code
| Code: |
#include <iostream>
#include<ctime>
using namespace std;
class Sudoku
{
public:
Sudoku()
{//constructors purpose is to ensure all values are initialized to zero...duh
for(int i=0;i<=8;i++)
{
matrix[0][i]=0;
matrix[1][i]=0;
matrix[2][i]=0;
matrix[3][i]=0;
matrix[4][i]=0;
matrix[5][i]=0;
matrix[6][i]=0;
matrix[7][i]=0;
matrix[8][i]=0;
cellInUse[0][i]=0;
cellInUse[1][i]=0;
cellInUse[2][i]=0;
cellInUse[3][i]=0;
cellInUse[4][i]=0;
cellInUse[5][i]=0;
cellInUse[6][i]=0;
cellInUse[7][i]=0;
cellInUse[8][i]=0;
row0[i]=false;
row1[i]=false;
row2[i]=false;
row3[i]=false;
row4[i]=false;
row5[i]=false;
row6[i]=false;
row7[i]=false;
row8[i]=false;
column0[i]=false;
column1[i]=false;
column2[i]=false;
column3[i]=false;
column4[i]=false;
column5[i]=false;
column6[i]=false;
column7[i]=false;
column8[i]=false;
block1[i]=false;
block2[i]=false;
block3[i]=false;
block4[i]=false;
block5[i]=false;
block6[i]=false;
block7[i]=false;
}
//Begin to populate the grid with valid soduku numbers...
while(checkIfDone()==false)
{
getXY();
fillTheCell();
}
}
protected:
int matrix[9][9];
int x;
int y;
bool cellInUse[9][9];
bool row0[9];
bool row1[9];
bool row2[9];
bool row3[9];
bool row4[9];
bool row5[9];
bool row6[9];
bool row7[9];
bool row8[9];
bool column0[9];
bool column1[9];
bool column2[9];
bool column3[9];
bool column4[9];
bool column5[9];
bool column6[9];
bool column7[9];
bool column8[9];
bool block1[9];
bool block2[9];
bool block3[9];
bool block4[9];
bool block5[9];
bool block6[9];
bool block7[9];
bool checkIfDone();
void getXY();
void fillTheCell();
};
/* The purpose of getXY() is to fill variables X and Y with valid values. Once this has been done
It checks to see if the cell contains a value. If it does contain a value the program first checks to see
if ALL the spaces are full. This is to prevent an infinite loop at the end of the program. Then it will pick a
new cell to fill.*/
void Sudoku::getXY()
{
x=rand() % 9 + 0;
y=rand() % 9 + 0;
while(cellInUse[x][y]==true)
{
x=rand() % 9 + 0;
y=rand() % 9 + 0;
}
}
/*Here comes the hardest part. The plan is to copy a random value into a buffer. Then we will check the value against
the appropriate bool arrays(using the x coord and y coord) to see if the particular value is in use. A bool will be flagged true
as soon as a conflict is found. I only use one bool becuase if the buffer has been used already anywhere (in respect to its
x and y) then it obviously wont be input. If it has been used the program will flag the bool and continue with the rest of the checks.
If it makes it all the way through the checks without being flagged once than we can safely assume it is not being used. Input it into the matrix and
check it off in the approraite bool arrays AND the cellInUse. BTW I check the flag bool at the end.*/
void Sudoku::fillTheCell()
{
int buffer=rand() % 9 + 1;
bool myFlag=false;
//compare the buffer against all Y bool arrays
switch (y)
{
case 0:
while(row0[buffer]==true)
{
myFlag=true;
break;
}
break;
case 1:
while(row1[buffer]==true)
{
myFlag=true;
break;
}
break;
case 2:
while(row2[buffer]==true)
{
myFlag=true;
break;
}
break;
case 3:
while(row3[buffer]==true)
{
myFlag=true;
break;
}
break;
case 4:
while(row4[buffer]==true)
{
myFlag=true;
break;
}
break;
case 5:
while(row5[buffer]==true)
{
myFlag=true;
break;
}
break;
case 6:
while(row6[buffer]==true)
{
myFlag=true;
break;
}
break;
case 7:
while(row7[buffer]==true)
{
myFlag=true;
break;
}
break;
case 8:
while(row8[buffer]==true)
{
myFlag=true;
break;
}
break;
}
/* Now compare against all x arrays*/
switch (x)
{
case 0:
while(column0[buffer]==true)
{
myFlag=true;
break;
}
break;
case 1:
while(column1[buffer]==true)
{
myFlag=true;
break;
}
break;
case 2:
while(column2[buffer]==true)
{
myFlag=true;
break;
}
break;
case 3:
while(column3[buffer]==true)
{
myFlag=true;
break;
}
break;
case 4:
while(column4[buffer]==true)
{
myFlag=true;
break;
}
break;
case 5:
while(column5[buffer]==true)
{
myFlag=true;
break;
}
break;
case 6:
while(column6[buffer]==true)
{
myFlag=true;
break;
}
break;
case 7:
while(column7[buffer]==true)
{
myFlag=true;
break;
}
break;
case 8:
while(column8[buffer]==true)
{
myFlag=true;
break;
}
break;
}
/************************************************************
**************************************************************
******I have not implemented those small 3x3 grids***********
******I will though, I need to test it without them************
******It makes for easier debugging**************************
*************************************************************
**************************************************************/
/*Now we check the flag to determine if we are going to input to the grid itself
and mark the cell as used in our bool grid cellInUse[][].*/
if(myFlag==true)
{
return;
}
//This is where the program records changes that are being made. It inputs to the grid. Marks that it has input there
//in cellinuse[][] and marks off the rows and columns its in.
if(myFlag==false)
{
cellInUse[x][y]=true;
switch (y)
{
case 0: row0[buffer]=true; break;
case 1: row1[buffer]=true; break;
case 2: row2[buffer]=true; break;
case 3: row3[buffer]=true; break;
case 4: row4[buffer]=true; break;
case 5: row5[buffer]=true; break;
case 6: row6[buffer]=true; break;
case 7: row7[buffer]=true; break;
case 8: row8[buffer]=true; break;
}
//-----------------------------------------------
switch (x)
{
case 0: column0[buffer]=true; break;
case 1: column1[buffer]=true; break;
case 2: column2[buffer]=true; break;
case 3: column3[buffer]=true; break;
case 4: column4[buffer]=true; break;
case 5: column5[buffer]=true; break;
case 6: column6[buffer]=true; break;
case 7: column7[buffer]=true; break;
case 8: column8[buffer]=true; break;
}
matrix[x][y]=buffer;
}
}
bool Sudoku::checkIfDone()
{
for(int i=0;i<8;i++)
{
if(row0[i]==false)
{return false;}
if(row1[i]==false)
{return false;}
if(row2[i]==false)
{return false;}
if(row3[i]==false)
{return false;}
if(row4[i]==false)
{return false;}
if(row5[i]==false)
{return false;}
if(row6[i]==false)
{return false;}
if(row7[i]==false)
{return false;}
if(row8[i]==false)
{return false;}
if(column0[i]=false)
{return false;}
if(column1[i]=false)
{return false;}
if(column2[i]=false)
{return false;}
if(column3[i]=false)
{return false;}
if(column4[i]=false)
{return false;}
if(column5[i]=false)
{return false;}
if(column6[i]=false)
{return false;}
if(column7[i]=false)
{return false;}
if(column8[i]=false)
{return false;}
}
return true;
}
int main()
{
srand (74563);
Sudoku s;
system("pause");
}
|
I am very new to Sudoku. I am a newbie programmer and started this project becuase it sounded cool. I am the kind of guy who will not move on to the next project until the current project is completely finished though. So I really need to get this done lol.
So my question is this: Is there a function I can implement into the sudoku class that will fix this problem? Ive tried and tried again with no results. I will appreciate any help. Thanks. |
|
| Back to top |
|
 |
| monkeyfoahead
| | Joined: 12 Apr 2008 | | Posts: 3 | | : | |
Items |
|
| Posted: Sun Apr 13, 2008 11:28 pm Post subject: |
|
|
| Or let me rephrase that question: What techniques are available for ensuring you generate a vaild puzzle(that would be possible to implement in my code without much difficulty)? |
|
| Back to top |
|
|
| Sisophon2001
 | | Joined: 05 Mar 2008 | | Posts: 32 | | : | | Location: Cambodia |
Items |
|
| Posted: Mon Apr 14, 2008 2:46 am Post subject: |
|
|
Looking through the code you posted, I don't see where you check each box for duplicate numbers. You will need to check that also, but you will still get deadlocks, and when you do you need to backtrack, undoing your entries and trying a new value. While the first placement must be random, you must then systematically check each possible value for a cell so you know when to backtrack ans avoid the deadlocks.
This may be difficult with your existing code, because it would have been easier to structure your code from the start to allow backtracking. Also you can use the C library function memset() to initialize your arrays and save typing.
If I have time later today I will make C sample for you to show the simplest way that I have seen to fill a grid.
Garvan
EDIT: This is the simplest sudoku solver I have seen. Original code by Oli Charlesworth in C but I actually never saw the C version, I translated this from basic, and made it a random grid generator instead of a solver. I took me ages to translate, I need more practice with C.
| Code: | //
// Credits: Oli Charlesworth, for the tiny C solver
//
#include <stdlib>
#include <stdio>
#include <string>
#include <time>
int solve (char* );
int main(int argc, char *argv[]) {
char p[82];
memset (p,48,81);
p[81]=0;
srand( (unsigned)time( NULL ) );
solve(p);
return 0;
}
int solve (char* v) {
char* r=v;
char i=0, n = 0, k = 48;
int j, m=0;
while(*r>k) {
i++;
r++;
if(*r==0) {
puts(r-i);
return 1;
}
}
k = (rand() % 9) + 49;
while(n<9) {
j=81;
while(j) {
j--;
if(r[j-i]-k) {
m=1;
}
else {
m=0;
if(((i/9)^(j/9))&&((i % 9)^(j % 9))) {
if(((i/27)^(j/27))||(((i % 9)/3)^((j % 9)/3))) m=1;
}
}
*r*=m;
}
if(*r) {
*r=k;
if (solve(v)) return 1;
}
*r=1;
n++;
if (++k == 58) k = 49;
}
return 0;
}
|
|
|
| Back to top |
|
|
| monkeyfoahead
| | Joined: 12 Apr 2008 | | Posts: 3 | | : | |
Items |
|
| Posted: Mon Apr 14, 2008 10:13 pm Post subject: |
|
|
| Sisophon2001 wrote: | | Looking through the code you posted, I don't see where you check each box for duplicate numbers. |
Well all the bools for columns and rows guarantee no duplicates.
Thankyou so much for your help. I am going to take sometime tonight and try and restructure my code. I will keep you posted. |
|
| Back to top |
|
|
| sudoku1
| | Joined: 07 Aug 2008 | | Posts: 7 | | : | |
Items |
|
| Posted: Thu Aug 07, 2008 7:24 pm Post subject: Grid Generation |
|
|
I have programmed a generation of sudoku, with the following techniques:
1- generate a full grid, by randomly set at maximum 20 cells (for 9x9 grids), and finally filled the remaining ones by searching a possible solution using recursive method
2- mask a certain number of cells (depending on difficulty) with some filters based on pre-defined motif to be eliminated in order to get a single solution grid.
Simple to say, more difficult to implement...
JMN |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
