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
#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++)
{
[B]if (check(a,i,j,rows))
{
rows[i][j] = (char)(a+48);
solve(rows);
}[/B]
}
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!
