By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,203 Members | 1,392 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,203 IT Pros & Developers. It's quick & easy.

sudoku coding help

P: n/a
hy guys

i am having a problem with my sudoku program which i coded using c++.;
currently in my program if a duplicate number exist in either
row/column/block i would make the particualr square 0. but thats not i
want to do. I want to recurse back until until it find a correct
number. i will post the function which i need the help;
---coding----------------------------------------------------------
void generation(int newGrid[9][9])
{
int randV; //variables
int r,c;
for( r=0;r<9;r++)
{
for(c=0;c<9;c++)
{
randV=(rand()%9)+1; //random generator
if(newGrid[r][c]==0) //if empty squares
{
newGrid[r][c]=randV;
if(!isLegal()) //check row/column/grid
newGrid[r][c]=0; //make the square 0
}
}
}

Apr 18 '06 #1
Share this Question
Share on Google+
12 Replies


P: n/a
ka*********@gmail.com wrote:
hy guys
Hy yourself
i am having a problem with my sudoku program which i coded using c++.;
currently in my program if a duplicate number exist in either
row/column/block i would make the particualr square 0. but thats not i
want to do. I want to recurse back until until it find a correct
number.
What is "recurse back"? Back where?

"Recurse" usually means "call itself" or "cause a call to itself through
calling other function that eventually calls this one". What does it mean
to do it "back"? Did you mean, maybe, return some kind of error code so
that the caller of your function would call it again?

Perhaps if you describe, in a human language, preferably English, what
you expect your program to do, and we could try helping you to put it in
C++ terms...
i will post the function which i need the help;
---coding----------------------------------------------------------
void generation(int newGrid[9][9])
{
int randV; //variables
int r,c;
for( r=0;r<9;r++)
{
for(c=0;c<9;c++)
{
randV=(rand()%9)+1; //random generator
if(newGrid[r][c]==0) //if empty squares
{
newGrid[r][c]=randV;
if(!isLegal()) //check row/column/grid
newGrid[r][c]=0; //make the square 0
}
}
}


V
--
Please remove capital As from my address when replying by mail
Apr 18 '06 #2

P: n/a
<ka*********@gmail.com> wrote:
i am having a problem with my sudoku program which i coded using c++.;
currently in my program if a duplicate number exist in either
row/column/block i would make the particualr square 0. but thats not i
want to do. I want to recurse back until until it find a correct
number. i will post the function which i need the help;
---coding----------------------------------------------------------
void generation(int newGrid[9][9])
{
int randV; //variables
int r,c;
for( r=0;r<9;r++)
{
for(c=0;c<9;c++)
{
randV=(rand()%9)+1; //random generator
if(newGrid[r][c]==0) //if empty squares
{
newGrid[r][c]=randV;
if(!isLegal()) //check row/column/grid
newGrid[r][c]=0; //make the square 0
}
}
}


The intent it to generate a complete array, remove some digits, and present
the residue as a sudoku. Is that right? And there is a pre-condition,
newgrid[9][9] contains all zeros when generation is called, is that right?
If my guess is right, you would have to get rid of the pre-condition to call
generation recursively.

I don't see any reason to use recursion unless this is a school assignment.
I suggest you learn about "shuffle" and start over. with this part of your
code. What you have so far is, I think, doomed to be incredibly slow. Not
that shuffle will make it a cinch, but it seems like a more reasonable
starting point - but possibly still unusably slow..

I think you have started coding without sufficient attention to the design.
Try this: print the highest value of r and c when a problem is detected.
Print a message every time a new record is achieved. I think r is going
to be way shy of 9 and the time - wall clock time - between new highs is
going to already be measured in many minutes.
Apr 18 '06 #3

P: n/a
ka*********@gmail.com wrote:
hy guys

i am having a problem with my sudoku program which i coded using c++.;
currently in my program if a duplicate number exist in either
row/column/block i would make the particualr square 0. but thats not i
want to do. I want to recurse back until until it find a correct
number. i will post the function which i need the help;


I assume you want to backtrack if you reach an illegal situation. This
can indeed be done easiest with recursion like so (not tested):

bool
generation(int newGrid[9][9], int r, int c)
{
if(c == 9)
{
if(++r == 9)
return true;
c = 0;
}
do
{
const int randV = (rand() % 9) + 1;
newGrid[r][c] = randV;
if(!isLegal(newGrid, r, c))
return false;
}
while(!generation(newGrid, r, c + 1));
return true;
}

You would initially call it with r and c = 0.

That said I am pretty sure this will never fly because it is too slow.
Given enough time it should however in principal create a valid sudoku
(a poor rand() implementation could send it in an infinite loop though).

Apr 18 '06 #4

P: n/a
"osmium" writes:
I think you have started coding without sufficient attention to the
design. Try this: print the highest value of r and c when a problem is
detected. Print a message every time a new record is achieved. I think r
is going to be way shy of 9 and the time - wall clock time - between new
highs is going to already be measured in many minutes.


Let me elaborate on the need for some more design before you start coding.
I suppose I will screw up here, somehow, all I can do is hope that no one is
reading this.

I believe there are 9^81 different ways to fill in the 81 cells of a 9x9
grid with the digits 1..9.
There are 6.67e21 different arrangements, full grids, that satisfy the
soduko
rules, ready to be made into a puzzle - by removing most of the digits. So
if you set out to create a full grid by drawing random numbers, the
probability of success each time you start is 6.67e21/(9^81) or 3.39e-56.
Those are really not very good odds. It's going to take a
whole lot of tries to get your first successful grid.

http://www.afjarvis.staff.shef.ac.uk...u/bertram.html


Apr 18 '06 #5

P: n/a
ka*********@gmail.com wrote:
hy guys

i am having a problem with my sudoku program which i coded using c++.;
currently in my program if a duplicate number exist in either
row/column/block i would make the particualr square 0. but thats not i
want to do. I want to recurse back until until it find a correct
number. i will post the function which i need the help;
---coding----------------------------------------------------------
void generation(int newGrid[9][9])
{
int randV; //variables
int r,c;
for( r=0;r<9;r++)
{
for(c=0;c<9;c++)
{
randV=(rand()%9)+1; //random generator
if(newGrid[r][c]==0) //if empty squares
{
newGrid[r][c]=randV;
if(!isLegal()) //check row/column/grid
newGrid[r][c]=0; //make the square 0
}
}
}


May I suggest you create a program to solve a sudoku puzzle. Then create
the sudoku generator which can then check that all puzzles generated
have a unique solution. Naturally you'll have to investigate the
different logical techniques used for solving sudoku puzzles, as well as
developing a trial method for those puzzles that cannot be solved using
the logical techniques implemented.

JB
Apr 19 '06 #6

P: n/a
Markus Schoder wrote:
ka*********@gmail.com wrote:
hy guys

i am having a problem with my sudoku program which i coded using c++.;
currently in my program if a duplicate number exist in either
row/column/block i would make the particualr square 0. but thats not i
want to do. I want to recurse back until until it find a correct
number. i will post the function which i need the help;
I assume you want to backtrack if you reach an illegal situation. This
can indeed be done easiest with recursion like so (not tested):


[...code snipped...]
That said I am pretty sure this will never fly because it is too slow.
Given enough time it should however in principal create a valid sudoku
(a poor rand() implementation could send it in an infinite loop though).


Turns out you can generate a random sudoku grid surprisingly fast with
some additional validity checks to cause early backtracking. Below is a
complete program that does it. There is a tiny bit of non-standard C++
in there. You need uint8_t and int16_t types from the C99 stdint.h
header and the ffs() function (find first bit set) from POSIX.

#include <cstdlib>
#include <stdint.h>
#include <iostream>
#include <vector>
#include <strings.h>

using namespace std;

class sudoku
{
public:
struct avail_t
{
int16_t a[9][9];
};

bool solve();
uint8_t get(const int r, const int c) const {return grid_[r][c];}
void set(const uint8_t v, const int r, const int c)
{grid_[r][c] = v; avail_.a[r][c] = -1;}
vector<uint8_t> get_valid(int r, int c) const;
bool update_avail(uint8_t v, int r, int c);
avail_t get_avail() const {return avail_;}
void set_avail(const avail_t &avail) {avail_ = avail;}

private:
bool generation(int r, int c);

uint8_t grid_[9][9];
avail_t avail_;
};

vector<uint8_t>
sudoku::get_valid(int r, int c) const
{
vector<uint8_t> valids;
int mask = avail_.a[r][c];
while(mask)
{
valids.push_back(ffs(mask) - 1);
mask &= mask - 1;
}
return valids;
}

bool
sudoku::update_avail(const uint8_t v, const int r, const int c)
{
const int16_t mask = ~int16_t(1 << v);
for(int c1 = 0; c1 < 9; ++c1)
{
if(c1 != c && avail_.a[r][c1] >= 0)
{
if(!(avail_.a[r][c1] &= mask))
return false;
}
}
for(int r1 = 0; r1 < 9; ++r1)
{
if(r1 != r && avail_.a[r1][c] >= 0)
{
if(!(avail_.a[r1][c] &= mask))
return false;
}
}
const int ra = r / 3 * 3;
const int ca = c / 3 * 3;
for(int r1 = ra; r1 < ra + 3; ++r1)
for(int c1 = ca; c1 < ca + 3; ++c1)
if((r1 != r || c1 != c) && avail_.a[r1][c1] >= 0)
{
if(!(avail_.a[r1][c1] &= mask))
return false;
}
return true;
}

bool
sudoku::generation(int r, int c)
{
if(c == 9)
{
if(++r == 9)
return true;
c = 0;
}
const vector<uint8_t> valids = get_valid(r, c);
if(valids.empty())
return false;
const int i0 = rand() % valids.size();
int i = i0;
do
{
const uint8_t v = valids[i];
const avail_t old_avail = get_avail();
if(update_avail(v, r, c))
{
set(v, r, c);
if(generation(r, c + 1))
return true;
}
set_avail(old_avail);
if(++i == (int)valids.size())
i = 0;
}
while(i != i0);
return false;
}

bool
sudoku::solve()
{
for(int r = 0; r < 9; ++r)
for(int c = 0; c < 9; ++c)
avail_.a[r][c] = (1 << 9) - 1;
return generation(0, 0);
}

int
main(const int argc, const char *const argv[])
{
ios::sync_with_stdio(false);
if(argc >= 2)
srand(strtol(argv[1], 0, 10));
sudoku s;
if(!s.solve())
{
cerr << "No sudoku grid found (bug)!\n";
return 1;
}
for(int r = 0; r < 9; ++r)
{
for(int c = 0; c < 9; ++c)
cout << char('1' + s.get(r, c));
cout << '\n';
}
}

Apr 20 '06 #7

P: n/a
Markus Schoder wrote:
ka*********@gmail.com wrote:
hy guys

i am having a problem with my sudoku program which i coded using c++.;
currently in my program if a duplicate number exist in either
row/column/block i would make the particualr square 0. but thats not i
want to do. I want to recurse back until until it find a correct
number. i will post the function which i need the help;


I assume you want to backtrack if you reach an illegal situation. This
can indeed be done easiest with recursion like so (not tested):

bool
generation(int newGrid[9][9], int r, int c)
{
if(c == 9)
{
if(++r == 9)
return true;
c = 0;
}
do
{
const int randV = (rand() % 9) + 1;
newGrid[r][c] = randV;
if(!isLegal(newGrid, r, c))
return false;
}
while(!generation(newGrid, r, c + 1));
return true;
}

You would initially call it with r and c = 0.

That said I am pretty sure this will never fly because it is too slow.
Given enough time it should however in principal create a valid sudoku
(a poor rand() implementation could send it in an infinite loop though).

I just have to reply.....why?
As an exercise it is a good one to get into but I usually solve those in
my head in about 5 minutes. After years of programming it just seems to
happen naturally. If you added error checking for any and all possible
solutions you might find more than one, even though there should be only
one. Happy accidents do happen, and as I said it is a good coding
exercise without having to worry about 'visual' anything.
Good luck.
Bill (new here) (old coder from DOS days) Baka
Apr 21 '06 #8

P: n/a
Bill Baka wrote:
Markus Schoder wrote:
ka*********@gmail.com wrote:
hy guys

i am having a problem with my sudoku program which i coded using c++.;
currently in my program if a duplicate number exist in either
row/column/block i would make the particualr square 0. but thats not i
want to do. I want to recurse back until until it find a correct
number. i will post the function which i need the help;
I assume you want to backtrack if you reach an illegal situation. This
can indeed be done easiest with recursion like so (not tested):
[...code snipped...]
You would initially call it with r and c = 0.

That said I am pretty sure this will never fly because it is too slow.
Given enough time it should however in principal create a valid sudoku
(a poor rand() implementation could send it in an infinite loop though).

I just have to reply.....why?


For fun. Way more fun than actually solving a sudoku yourself which I
consider rather boring but your mileage may vary.
As an exercise it is a good one to get into but I usually solve those in
my head in about 5 minutes. After years of programming it just seems to
happen naturally. If you added error checking for any and all possible
solutions you might find more than one, even though there should be only
one. Happy accidents do happen, and as I said it is a good coding
exercise without having to worry about 'visual' anything.


You realize this _generates_ a full sudoku grid it does not solve a
sudoku -- though I think it would be easy to use it for solving as well.

Apr 21 '06 #9

P: n/a
hi guys

i still dont get how to correct my coding i know its a minor problem.
could u please point out where i have gone wrong, and explain where how
i can solve it.
code-------------------------------------------------------


#include<iostream.h>
#include<iomanip>
#include<cstdlib>
#include<string> //defining necessary library
#include<cassert>
#include<time.h>

using namespace std;

const int miniGridSize=3;
const int GridSize=9; //initlialisation
int newGrid[GridSize][GridSize]={
{0,6,0,1,0,4,0,5,0},
{0,0,8,3,0,5,6,0,0},
{2,0,0,0,0,0,0,0,1}, //initialization of the values.
{8,0,0,4,0,7,0,0,6},
{0,0,6,0,0,0,3,0,0},
{7,0,0,9,0,1,0,0,4},
{5,0,0,0,0,0,0,0,2},
{0,0,7,2,0,6,9,0,0},
{0,4,0,5,0,8,0,7,0}};

void print(); //function print
//void sudoku_shuffle(int[9][9]);
void makeNewGrid(int[9][9]);
void fillsquare(int depth,int x,int y); //function declarations
bool isRowLegal(int);
bool isColLegal(int);
bool isMiniGridLegal(int,int);
bool checkForDuplicate(int[9]);
bool isLegal();
void generation(int[9][9]);
int main()
{
srand((unsigned)time(0)); //initialize random generator;

int num,x,y;
char response; //declaration of variables.
option:
cout<<"Menu for sudoku:"<<endl;
cout<<"----------------"<<endl; //defining menu option

cout<<"(0)print the original grid"<<endl;
cout<<"(1)print the possible generation of numbers(NOTE->WORK
PARTIALLY)"<<endl;
cout<<"(2)test validity of numbers(row/column/minigrid"<<endl;
cout<<"(3)exit the program"<<endl;

cout<<endl;

int choice;
cout<<"enter choice:"<<endl; //get user input
cin>>choice;

switch(choice) //switch case
{
case 0:
cout<<"original grid"<<endl<<endl;
print();
cout<<"sudoku not solved"<<endl;
goto option;
break;

case 1:
generation(newGrid); //calling generation function
print(); //calling print()
goto option; //goto option menu
break;

case 2:

cout<<"testing row/column/minigrid for validity of numbers"<<endl;

makeNewGrid(newGrid); //calling clear grid()


do{
cout<<"enter number:="<<endl; //geting user input number,x and
y cordinates
//for testing row/column/block
cin>>num;

cout<<"x cordinate:"<<endl;
cin>>x;

cout<<"y cordinate:"<<endl;
cin>>y;

fillsquare(num,x,y);

if(isLegal()) //validation of row.col.block
{
print(); //if valid print grid and display
cout<<"sudoku solved"<<endl;
}else
{
cout<<"not solved"<<endl;
newGrid[x][y]=0; //if invalid display and empty
specific sqr
}
cout<<"do you test numbers"<<endl<<endl;
cin>>response; //user input

}while(response=='Y'||'y');

goto option;
break;
case 3:
exit(0); //exit program
break;

default:
cout<<"wrong choice:"<<endl; //default option
goto option;
}
return 0;

}
/************************************************** ****************************************/
///function got the
problem////////////////////////////////////////////////////////////////

void generation(int newGrid[9][9]) //generation function with arg
{
int randV; //initialise variables
int r,c;


for(int count=0;count<81;count++) //run through loop 81 times
{
for( r=0;r<9;r++) //row
{

for(c=0;c<9;c++) //col
{
if(newGrid[r][c]==0) //if grid not full and empty sqrs exist
{
randV=rand()%9+1;
newGrid[r][c]=randV; //inialize a random num
if(!isLegal())//if not valid
{
newGrid[r][c]=0; //make it 0

}

}

}
}
}

}
/************************************************** ***************************************/


bool checkForDuplicate(int arr[9]) //duplicate function bool
{

bool foundNoDuplicate=true; //make var true

bool tally[GridSize+1];

int x,i; //declaration of variable

for(i=0;i<=9;i++)

tally[i]=false; //initialize the array variable to false

for(i=0;i<9;i++)
{
x=arr[i]; //return arr numbers to variable called x for checking

if(x!=0) //ignore empty squares
{
if(tally[x]) //
foundNoDuplicate=false; //if found duplicate make it true
tally[x]=true; //make bool array true
}

}

return foundNoDuplicate;
}
bool isLegal()
{
bool rowLegal=true;
bool colLegal=true;
bool miniGridLegal=true;
int i;

for(i=0;i<GridSize;i++)
{
rowLegal=rowLegal && isRowLegal(i);
}
for(i=0;i<GridSize;i++)
{
colLegal=colLegal && isColLegal(i);
}
for(i=0;i<GridSize;i++)
{
miniGridLegal=miniGridLegal && isMiniGridLegal(3*(i/3),3*(i%3));
}
return rowLegal && colLegal && miniGridLegal; //if all vaues are true
then return true
}

bool isMiniGridLegal(int x,int y) //checking for bllock
validation
{
int miniGrid[9];

int offset;
for(offset=0;offset<GridSize;offset++)
{
miniGrid[offset]=newGrid[x+offset/miniGridSize][y+offset%miniGridSize];
//assigning valeues to minigrid arry(checking horizontally and
vertically in the minigrid(
}
bool legal=checkForDuplicate(miniGrid); //checking for duplicate with
in array

if(!legal){
cout<<"duplicate values in minigrid="<<x<<" , "<<y<<endl;
}

return legal;
}
bool isRowLegal(int y) //checking for row validation
{
int row[9]; //create a rray of 9

int x;

for(x=0;x<9;x++)
{
row[x]=newGrid[x][y]; //put each row value to array
}
bool legal=checkForDuplicate(row); //check for duplicate within array
and return result

if(!legal){ //if not valid display-
cout<<"there are duplicate values in col="<<y<<endl;
}
return legal;
}

bool isColLegal(int x) //checking for col validation
{
int col[9]; //create a array of 9
int y;
for(y=0;y<9;y++)
{
col[y]=newGrid[x][y]; //put each col values to array
}
bool legal=checkForDuplicate(col); //check for the duplicates within
col array and return the result to legal variable

if(!legal){ //if not legal display
cout<<"There are duplicate values in row="<<x<<endl;
}

return legal;
}

void fillsquare(int digit,int x,int y) //fill square function with arg
{

if((0<=x) && (x<9) && (0<=y) && (y<9)) //checking for valid grids and
insert the number
{
newGrid[x][y]=digit; //to specific grid

}
}
void makeNewGrid(int newGrid[GridSize][GridSize]) //clear grid
function
{
int i,j;

for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{

newGrid[i][j]=0;
}
}
}
/*
void sudoku_shuffle(int newGrid[GridSize][GridSize]) //function for
shuffle sudoku
{

srand((unsigned)time(0));
//position=0;

int row,col;

int randValue=0;

for(row=0;row<9;row++)
{
for(col=0;col<9;col++)
{

randValue=rand()%9+1;
if(newGrid[row][col]==0)
{

// if((0<randValue) &&(randValue<=GridSize))
newGrid[row][col]=randValue;
}

}
}

}

*/

void print() //function for the print
{
for(int row=0;row<GridSize;row++)
{
for(int col=0;col<GridSize;col++)
{
if(newGrid[row][col]==0) //if empty grids display "_"
cout<<"["<<"_"<<"]";
else

cout<<"["<<newGrid[row][col]<<"]"; //else print numbers
}
cout<<endl;
}
}

Apr 22 '06 #10

P: n/a
<ka*********@gmail.com> wrote:
i still dont get how to correct my coding i know its a minor problem.
could u please point out where i have gone wrong, and explain where how
i can solve it.


<snip>

It would be nice if we knew what the program was supposed to do.

Apr 22 '06 #11

P: n/a
osmium wrote:
<ka*********@gmail.com> wrote:
i still dont get how to correct my coding i know its a minor problem.
could u please point out where i have gone wrong, and explain where how
i can solve it.

<snip>
It would be nice if we knew what the program was supposed to do.


It appears to be a solver of Sudoku puzzles using a brute-force method
of guessing values for unknown cells. There is no way to undo a guess
that does not immediately produce a conflict but results in a state
which cannot be solved. This would be a good place to use recursion,
to make a guess, then see if the resulting state can solved (by calling
the same function recursively), then if not, undoing the guess and
trying something else.
Apr 22 '06 #12

P: n/a
ka*********@gmail.com wrote:
hi guys

i still dont get how to correct my coding i know its a minor problem.
could u please point out where i have gone wrong, and explain where how
i can solve it.


Your generation function is still broken. Similar to my earlier post
try the following instead:

bool
recgeneration(int newGrid[9][9], int r, int c)
{
if(c == 9)
{
if(++r == 9)
return true;
c = 0;
}
if(newGrid[r][c] != 0)
return recgeneration(newGrid, r, c + 1);
do
{
const int randV = (rand() % 9) + 1;
newGrid[r][c] = randV;
if(!isLegal())
{
newGrid[r][c] = 0;
return false;
}
}
while(!recgeneration(newGrid, r, c + 1));
return true;
}

void
generation(int newGrid[9][9])
{
recgeneration(newGrid, 0, 0);
}

This should be correct but probably is too slow.

I changed the program that I posted earlier so it can solve sudokus now
including ambiguity detection. It is a bit long so I do not post it
here now.

Apr 22 '06 #13

This discussion thread is closed

Replies have been disabled for this discussion.