| | |
recursive sudoku solver (asap)
Please support our C++ advertiser: Intel Parallel Studio Home
![]() |
hello everyone.. thx for droppin'
i need to write a program, a recursive sudoku solver
and this is what i have so far...
main.cpp
sudoku.cpp
sudoku.h
when i run it,, there's an error on the recursive function solve
and i don't understand why... i'm really stuck..
really need help asap(to be submitted after several hours).. thx!
i need to write a program, a recursive sudoku solver
and this is what i have so far...
main.cpp
#include <iostream>
#include <vector>
#include "sudoku.h"
using namespace std;
int main()
{
vector< vector<char> > rows;
// Load grid
rows=load();
// Check if grid is consistent.
if (checkall(rows))
{
cout << "Valid grid." << endl;
}
else
{
cout << "Invalid grid; exiting";
return 0;
}
// Print initial grid
print(rows);
// Solve grid.
solve(rows);
// Check solution.
cout << "Checking solution... "<<endl;
if (checkall(rows))
{
cout << "valid!" << endl;
}
else
{
cout << "not valid!" << endl;
}
return 0;
}sudoku.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include "sudoku.h"
using namespace std;
// Read grid from file sudoku.dat
vector< vector<char> > load()
{
char line;
int o;
ifstream data("sudoku.dat");
cout << "Loading grid..." << endl;
vector <char> nums;
vector < vector<char> > rows;
for (int i=0; i!=9; i++)
{
for (int j=0; j!=9; j++)
{
data>>line;
nums.push_back(line);
}
rows.push_back(nums);
nums.resize(0);
}
return rows;
}
// Print grid with nice format
void print(vector< vector<char> > rows)
{
for (int i=0; i!=9; i++)
{
for (int j=0; j!=9; j++)
{
cout << rows[i][j];
if (j==2 || j==5)
{
cout << " ";
}
else if (j==8)
{
cout << endl;
if (i==2 || i==5)
{
cout << endl;
}
}
else
{
cout << " ";
}
}
}
}
// Returns a string containing the center of the block
// to which position i,j belongs.
string block(int i, int j)
{
char x,y;
string result = "00";
switch (i)
{
case 1:
case 2:
case 3:
x='2';
break;
case 4:
case 5:
case 6:
x='5';
break;
case 7:
case 8:
case 9:
x='8';
break;
}
switch (j)
{
case 1:
case 2:
case 3:
y='2';
break;
case 4:
case 5:
case 6:
y='5';
break;
case 7:
case 8:
case 9:
y='8';
break;
}
result[0] = x;
result[1] = y;
return result;
}
// Checks whether value num can be placed at position i,j.
bool check(int num, int i, int j, vector< vector<char> > rows)
{
char value = (char)(num+48);
string center;
int x,y;
if (value == '-')
{
return true;
}
// check row
for (int k=0; k!=9; k++)
{
if (rows[i][k]==value && k!=j)
{
return false;
}
}
// check column
for (int k=0; k!=9; k++)
{
if (rows[k][j]==value && k!=i)
{
return false;
}
}
// check region
center = block(i,j);
x = center[0]-48;
y = center[1]-48;
for (int m=-1; m<=1; m++)
{
for (int n=-1; n<=1; n++)
{
if (rows[x+m][y+n]==value && !((x+m)==i && (y+n)==j))
{
return false;
}
}
}
return true;
}
// Recursive Sudoku solver
void solve(vector< vector<char> > rows)
{
bool solved;
int i,j;
if (solved)
{
return;
}
// Find next empty value
for (i=0; i!=9; i++)
{
for (j=0; j!=9; j++)
{
if (rows[i][j] == '-')
{
break;
}
}
if (rows[i][j] == '-')
{
break;
}
}
// If no empty value is found, grid is solved
if (i==8 && j==8)
{
cout << "Grid solved!" << endl;
solved = true;
print(rows);
return;
}
// Try next possible number and solve the rest recursively
for (int a=1; a<=9; a++)
{
if (check(a,i,j,rows))
{
rows[i][j] = (char)(a+48);
solve(rows);
}
}
rows[i][j] = '-';
return;
}
//Check all values on grid for consistency (ignores empty values)
bool checkall(vector< vector<char> > rows)
{
int i,j;
char value;
for (i=0; i!=9; i++)
{
for (j=0; j!=9; j++)
{
if (rows[i][j] != '-')
{
value = rows[i][j];
if (!(check((int)value,i,j,rows)))
{
return false;
}
}
}
return true;
}
return true;
}sudoku.h
#include <vector> using namespace std; vector< vector<char> > load(); void print(vector< vector<char> > rows); string block(int i, int j); bool check(int num, int i, int j, vector< vector<char> > rows); void solve(vector< vector<char> > rows); bool checkall(vector< vector<char> > rows);
when i run it,, there's an error on the recursive function solve
and i don't understand why... i'm really stuck..
really need help asap(to be submitted after several hours).. thx!
I am living in a mere program...
> for (int i=0; i!=9; i++)
1. Define a constant for the size, say
2. Using < is more usual for a for loop. As in
> bool check(int num, int i, int j, vector< vector<char> > rows)
You're passing by value. Which means anything you do to update this will NOT be reflected in the caller. Meaning main() gets no results. Use a reference.
Ditto for calling yourself recursively.
> if (i==8 && j==8)
Are you sure? The values reach 9 at the end?
1. Define a constant for the size, say
const int squareSize = 9; 2. Using < is more usual for a for loop. As in
for ( int i = 0; i < squareSize ; i++ ) > bool check(int num, int i, int j, vector< vector<char> > rows)
You're passing by value. Which means anything you do to update this will NOT be reflected in the caller. Meaning main() gets no results. Use a reference.
Ditto for calling yourself recursively.
> if (i==8 && j==8)
Are you sure? The values reach 9 at the end?
•
•
Join Date: Nov 2008
Posts: 392
Reputation:
Solved Threads: 72
Additionally, to the errors above: Errors on initialization.
You have a faliure to limit range on
line
You call block() with i=0, j=0 but your switch [Very UGLY] takes 1-9 and has no default to tell you you have an error.
That results in a memory violation later.
There are others, but please please (a) use -warning-all or (-Wall for gcc). ie. put the warnings in and assume all warnings are errors.
(b) run through a debugger.
c++ Syntax (Toggle Plain Text)
bool solved; int i,j; if (solved) // ERROR: Un-initialized variable { return; }
You have a faliure to limit range on
line
c++ Syntax (Toggle Plain Text)
// Find next empty value for (i=0; i!=9; i++) { for (j=0; j!=9; j++) { if (rows[i][j] == '-') break; } if (rows[i][j] == '-') // ERROR j == 9 here and is out of range { break; } }
You call block() with i=0, j=0 but your switch [Very UGLY] takes 1-9 and has no default to tell you you have an error.
That results in a memory violation later.
There are others, but please please (a) use -warning-all or (-Wall for gcc). ie. put the warnings in and assume all warnings are errors.
(b) run through a debugger.
experience is the most expensive way to learn anything
thx for the great helps...
these are the new codes
main.cpp
sudoku.cpp
sudoku.h
my problem now is: the program doesn't print the solved grid..
and i can't find why.... really sorry
thx again.. sorry for this program,, i just don't have much time now
thx for helping.. if possible, i would appreciate a fixed revised code of mine..
these are the new codes
main.cpp
#include <iostream>
#include <vector>
#include "sudoku.h"
using namespace std;
int main()
{
vector< vector<char> > rows;
// Load grid
rows=load();
// Check if grid is consistent.
if (checkall(&rows))
{
cout << "Valid grid." << endl;
}
else
{
cout << "Invalid grid; exiting";
return 0;
}
// Print initial grid
print(&rows);
// Solve grid.
solve(&rows);
// Check solution.
cout << "Checking solution... "<<endl;
if (checkall(&rows))
{
cout << "valid!" << endl;
}
else
{
cout << "not valid!" << endl;
}
return 0;
}sudoku.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include "sudoku.h"
using namespace std;
// Read grid from file sudoku.dat
vector< vector<char> > load()
{
char line;
ifstream data("sudoku.dat");
cout << "Loading grid..." << endl;
vector <char> nums;
vector < vector<char> > rows;
for (int i=0; i<squaresize; i++)
{
for (int j=0; j<squaresize; j++)
{
data>>line;
nums.push_back(line);
}
rows.push_back(nums);
nums.resize(0);
}
return rows;
}
// Print grid with nice format
void print(vector< vector<char> > *rows)
{
for (int i=0; i<squaresize; i++)
{
for (int j=0; j<squaresize; j++)
{
cout << (*rows)[i][j];
if (j==2 || j==5)
{
cout << " ";
}
else if (j==8)
{
cout << endl;
if (i==2 || i==5)
{
cout << endl;
}
}
else
{
cout << " ";
}
}
}
}
// Returns a string containing the center of the block
// to which position i,j belongs.
string block(int i, int j)
{
char x,y;
string result = "00";
switch (i)
{
case 0:
case 1:
case 2:
x='2';
break;
case 3:
case 4:
case 5:
x='5';
break;
case 6:
case 7:
case 8:
x='8';
break;
}
switch (j)
{
case 0:
case 1:
case 2:
y='2';
break;
case 3:
case 4:
case 5:
y='5';
break;
case 6:
case 7:
case 8:
y='8';
break;
}
result[0] = x;
result[1] = y;
return result;
}
// Checks whether value num can be placed at position i,j.
bool check(int num, int i, int j, vector< vector<char> > *rows)
{
char value = (char)(num+48);
string center;
int x,y;
if (value == '-')
{
return true;
}
// check row
for (int k=0; k<squaresize; k++)
{
if ((*rows)[i][k]==value && k!=j)
{
return false;
}
}
// check column
for (int k=0; k<squaresize; k++)
{
if ((*rows)[k][j]==value && k!=i)
{
return false;
}
}
// check region
center = block(i,j);
x = center[0]-48;
y = center[1]-48;
for (int m=-1; m<=1; m++)
{
for (int n=-1; n<=1; n++)
{
if ((*rows)[x+m][y+n]==value && !((x+m)==i && (y+n)==j))
{
return false;
}
}
}
return true;
}
// Recursive Sudoku solver
void solve(vector< vector<char> > *rows)
{
bool solved;
int i,j;
if (solved)
{
return;
}
// Find next empty value
for (i=0; i<squaresize; i++)
{
for (j=0; j<squaresize; j++)
{
if ((*rows)[i][j] == '-')
{
break;
}
}
if ((*rows)[i][j] == '-')
{
break;
}
}
// If no empty value is found, grid is solved
if (i==9 && j==9)
{
cout << "Grid solved!" << endl;
solved = true;
print((rows));
return;
}
// Try next possible number and solve the rest recursively
for (int a=1; a<=9; a++)
{
if (check(a,i,j,rows))
{
(*rows)[i][j] = (char)(a+48);
solve(rows);
}
}
(*rows)[i][j] = '-';
return;
}
//Check all values on grid for consistency (ignores empty values)
bool checkall(vector< vector<char> > *rows)
{
int i,j;
char value;
for (i=0; i<squaresize; i++)
{
for (j=0; j<squaresize; j++)
{
if ((*rows)[i][j] != '-')
{
value = (*rows)[i][j];
if (!(check((int)value,i,j,rows)))
{
return false;
}
}
}
return true;
}
return true;
}sudoku.h
#include <vector> using namespace std; const int squaresize=9; vector< vector<char> > load(); void print(vector< vector<char> > *); string block(int i, int j); bool check(int num, int i, int j, vector< vector<char> > *); void solve(vector< vector<char> > *); bool checkall(vector< vector<char> > *);
my problem now is: the program doesn't print the solved grid..
and i can't find why.... really sorry
thx again.. sorry for this program,, i just don't have much time now
thx for helping.. if possible, i would appreciate a fixed revised code of mine..
I am living in a mere program...
•
•
•
•
Why are you using a pointer, and not a reference?
You're still not initialising solved.
You're still running off the end of an array.
here's the current solve function..
void solve(vector< vector<char> > &rows)
{
bool solved=false;
int i,j;
if (solved)
{
return;
}
// Find next empty value
for (i=0; i<squaresize; i++)
{
for (j=0; j<squaresize; j++)
{
if (rows[i][j] == '-')
{
break;
}
}
if (rows[i][j-1] == '-')
{
break;
}
}
// If no empty value is found, grid is solved
if (i==9 && j==9)
{
cout << "Grid solved!" << endl;
solved = true;
print(rows);
return;
}
// Try next possible number and solve the rest recursively
for (int a=1; a<=9; a++)
{
if (check(a,i,j,rows))
{
rows[i][j] = (char)(a+48);
solve(rows);
}
}
rows[i][j] = '-';
return;
}but there's still problems in memory while running the program.. is the rows still incorrect? please fix my code.... i really don't understand why there's memory problem,, and why it doesn't print the solved grid..
I am living in a mere program...
i think the problem is here:
in solve function:
in check function,,
and in block function
i don't know how to fix the problem in the debugger.. pls help
thx!
in solve function:
for (int a=0; a<9; a++)
{
if (i==9)
{
if (check(a,i-1,j,rows))
{
rows[i-1][j] = (char)(a+48);
solve(rows);
}
}
if (check(a,i,j,rows))
{
rows[i][j] = (char)(a+48);
solve(rows);
}
}
rows[i][j] = '-';
return;center = block(i,j);
x = center[0]-48;
y = center[1]-48;
for (int m=0; m<=2; m++)
{
for (int n=0; n<=2; n++)
{
if (rows[x+m][y+n]==value && !((x+m)==i && (y+n)==j))
{
return false;
}
}
}
return true;and in block function
string block(int i, int j)
{
char x,y;
string result = "00";
switch (i)
{
case 0:
case 1:
case 2:
x='1';
break;
case 3:
case 4:
case 5:
x='4';
break;
case 6:
case 7:
case 8:
x='7';
break;
}
switch (j)
{
case 0:
case 1:
case 2:
y='1';
break;
case 3:
case 4:
case 5:
y='4';
break;
case 6:
case 7:
case 8:
y='7';
break;
}
result[0] = x;
result[1] = y;
return result;
}i don't know how to fix the problem in the debugger.. pls help
thx!
I am living in a mere program...
sorry,, now i'm triple posting... time trouble
this is my latest sudoku.cpp
it's working except in printing the solved grid.. the last row is what only printed correctly... pls help me modify the bolded part.. i think it's there... thx.. really need asap!
this is my latest sudoku.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include "sudoku.h"
using namespace std;
// Read grid from file sudoku.dat
vector< vector<char> > load()
{
char line;
ifstream data("sudoku.dat");
cout << "Loading grid..." << endl;
vector <char> nums;
vector < vector<char> > rows;
for (int i=0; i<squaresize; i++)
{
for (int j=0; j<squaresize; j++)
{
data>>line;
nums.push_back(line);
}
rows.push_back(nums);
nums.resize(0);
}
return rows;
}
// Print grid with nice format
void print(vector< vector<char> > &rows)
{
for (int i=0; i<squaresize; i++)
{
for (int j=0; j<squaresize; j++)
{
cout << rows[i][j];
if (j==2 || j==5)
{
cout << " ";
}
else if (j==8)
{
cout << endl;
if (i==2 || i==5)
{
cout << endl;
}
}
else
{
cout << " ";
}
}
}
}
// Returns a string containing the center of the block
// to which position i,j belongs.
string block(int i, int j)
{
char x,y;
string result = "00";
switch (i)
{
case 0:
case 1:
case 2:
x='1';
break;
case 3:
case 4:
case 5:
x='4';
break;
case 6:
case 7:
case 8:
x='7';
break;
}
switch (j)
{
case 0:
case 1:
case 2:
y='1';
break;
case 3:
case 4:
case 5:
y='4';
break;
case 6:
case 7:
case 8:
y='7';
break;
}
result[0] = x;
result[1] = y;
return result;
}
// Checks whether value num can be placed at position i,j.
bool check(int num, int i, int j, vector< vector<char> > &rows)
{
char value = (char)(num+48);
string center;
int x,y;
if (value == '-')
{
return true;
}
// check row
for (int k=0; k<squaresize; k++)
{
if (rows[i][k]==value && k!=j)
{
return false;
}
}
// check column
for (int k=0; k<squaresize; k++)
{
if (rows[k][j]==value && k!=i)
{
return false;
}
}
// check region
center = block(i,j);
x = center[0]-48;
y = center[1]-48;
for (int m=0; m<=2; m++)
{
for (int n=0; n<=2; n++)
{
if(x==7 && y==7)
{
for (int m=-1; m<=1; m++)
{
for (int n=-1; n<=1; n++)
{
if(x==-1 && y==-1)
{
if (rows[x+m+1][y+n+1]==value && !((x+m+1)==i && (y+n+1)==j))
{
return false;
}
}
else if(x==-1)
{
if (rows[x+m+1][y+n]==value && !((x+m+1)==i && (y+n)==j))
{
return false;
}
}
else if(y==-1)
{
if (rows[x+m][y+n+1]==value && !((x+m)==i && (y+n+1)==j))
{
return false;
}
}
else if(rows[x+m][y+n]==value && !((x+m)==i && (y+n)==j))
{
return false;
}
}
}
return true;
}
// Recursive Sudoku solver
void solve(vector< vector<char> > &rows)
{
bool solved=false;
int i,j;
if (solved)
{
return;
}
// Find next empty value
for (i=0; i<squaresize; i++)
{
for (j=0; j<squaresize; j++)
{
if (rows[i][j] == '-')
{
break;
}
}
if (rows[i][j-1] == '-')
{
break;
}
}
// If no empty value is found, grid is solved
if (i==9 && j==9)
{
cout << "Grid solved!" << endl;
solved = true;
print(rows);
return;
}
// Try next possible number and solve the rest recursively
for (int a=1; a<=9; a++)
{
if (i==9)
{
if (check(a,i-1,j,rows))
{
rows[i-1][j] = (char)(a+48);
solve(rows);
}
}
else
{
if (check(a,i,j,rows))
{
rows[i][j] = (char)(a+48);
solve(rows);
}
}
}
}
//Check all values on grid for consistency (ignores empty values)
bool checkall(vector< vector<char> > rows)
{
int i,j;
char value;
for (i=0; i<squaresize; i++)
{
for (j=0; j<squaresize; j++)
{
if (rows[i][j] != '-')
{
value = rows[i][j];
if (!(check((int)value,i,j,rows)))
{
return false;
}
}
}
return true;
}
return true;
}it's working except in printing the solved grid.. the last row is what only printed correctly... pls help me modify the bolded part.. i think it's there... thx.. really need asap!
Last edited by azwraith69; Feb 15th, 2009 at 1:24 am.
I am living in a mere program...
![]() |
Other Threads in the C++ Forum
- Previous Thread: C++ classes!
- Next Thread: ipod simulator program
| Thread Tools | Search this Thread |
api array arrays based beginner binary c++ c/c++ calculator char char* class classes code compile console conversion count delete deploy desktop directshow dll download dynamic dynamiccharacterarray encryption error file forms fstream function functions game givemetehcodez google graph gui homeworkhelp homeworkhelper iamthwee ifstream input int integer java lib linkedlist linker linux list loop looping loops map math matrix memory news number numbertoword output parameter pointer problem program programming project proxy python random read recursion recursive reference return rpg sorting string strings struct temperature template templates test text text-file tree unix url variable vector video visual visualstudio win32 windows winsock wordfrequency wxwidgets






