Everything work except for the fact that it cannot solve the whole puzzle, only a few rows. If somebody could just look over the recursive backtracking part of the algorithm, that would be greatly appreciated. Here's the snippet of code that I think is causing me grief:
/*
@member function: solve. this is the backtracking algorithm.
it relies on set_item to enter the values into data[][] and to keep track of the allowed values.
For some reason it doesn't get through much more than 16 recursive calls untill it stops,
I think I did the backtracking wrong...
@param: int row, col
@pre: once called, it goes through the algorithms using the coordinates passed in
@post: it inserts the apropriate value into data[][] and calles itself recursively to move onto the next coordinate
@return: void()
@throw: none
*/
void sudoku::solve(int row, int col)
{
int digit;
if (row == 9)
{
//solved
cout << "puzzle solved" << endl;
return void();
}
//I left this in so the operator can see what's happening for debugging purposes
cout << "Recursion depth: " << recursion_depth << endl;
//call the next step if necessary
if(data[row][col] != 0)
{
recursion_depth++;
r_count++;
if (col == 8)
solve(row+1,0);
else solve(row, col+1);
return void();
}
//generate digits
for (digit = 1; digit < 10; digit++)
{
cout << "testing digit " << digit << " in row " << row+1 << " column " << col+1 << endl;
if (allowed[row][col][digit])
{
set_item(digit,row,col);
set_recursion_depth(recursion_depth + 1);
r_count++;
//call next step
if (col == 8) solve (row+1,0);
else solve(row, col+1);
}
}
}Here's the whole code so you can try it for yourself:
/*
@title: sudoku solver implimentation file
@author: **************
@date: 10/15/08
*/
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <cassert>
using namespace std;
int r_count = 0;
/*
Class: sudoku.
Contains the algorithms and functions needed to solve a sudoku puzzle passed
into the copy constructor.
*/
class sudoku
{
private:
char data[9][9];
bool allowed[9][9][9];
void solve(int row, int col);
void set_item(char val, int x, int y);
void initialize();
int recursion_depth;
void set_recursion_depth(int rd) {recursion_depth = rd;};
public:
sudoku();
sudoku(int init_data[9][9]);
void getSolution();
void print(ostream &out);
int get_item(int x, int y);
inline bool allowed_set(char val, int x, int y){return allowed[x][y][val];}
bool is_solved();
};
/*
@member function: the default constructor
@param: none
@pre: none
@post: null_init() is called and the recursion depth is set to zero
@return: none
@throw: none
*/
sudoku::sudoku()
{
initialize();
recursion_depth = 0;
}
/*
@member function: the copy constructor
@param: an array of ints to copy
@pre: the array must be 9 by 9
@post: null_init() is first called which sets ALL values of the data[][] to allowed == true, then it inserts the initial data into data[][]
@return: none
@throw: none
*/
sudoku::sudoku(int init_data[9][9]){
initialize(); // sets all values of allowed[][][] == true
recursion_depth = 0;
for (int x = 0; x < 9; x++){
for (int y = 0; y < 9; y++){
assert(init_data[x][y] >= 0);
assert(init_data[x][y] <= 9);
//set the initial values
if (init_data[x][y] > 0){
if (allowed_set((char)init_data[x][y], x, y)){
set_item((char)init_data[x][y], x, y);
}
}
}
}
}
/*
@member function: getSolution()
@param: none
@pre: none
@post: solve is called with 0 for both the row and col passed in
@return: none, it's void
@throw: none
*/
void sudoku::getSolution()
{
solve(0,0);
}
/*
@member function: solve. this is the backtracking algorithm.
it relies on set_item to enter the values into data[][] and to keep track of the allowed values.
For some reason it doesn't get through much more than 16 recursive calls untill it stops,
I think I did the backtracking wrong...
@param: int row, col
@pre: once called, it goes through the algorithms using the coordinates passed in
@post: it inserts the apropriate value into data[][] and calles itself recursively to move onto the next coordinate
@return: void()
@throw: none
*/
void sudoku::solve(int row, int col)
{
int digit;
if (row == 9)
{
//solved
cout << "puzzle solved" << endl;
return void();
}
//I left this in so the operator can see what's happening for debugging purposes
cout << "Recursion depth: " << recursion_depth << endl;
//call the next step if necessary
if(data[row][col] != 0)
{
recursion_depth++;
r_count++;
if (col == 8)
solve(row+1,0);
else solve(row, col+1);
return void();
}
//generate digits
for (digit = 1; digit < 10; digit++)
{
cout << "testing digit " << digit << " in row " << row+1 << " column " << col+1 << endl;
if (allowed[row][col][digit])
{
set_item(digit,row,col);
set_recursion_depth(recursion_depth + 1);
r_count++;
//call next step
if (col == 8) solve (row+1,0);
else solve(row, col+1);
}
}
}
/*
@member function: set_item
@param: the value to enter and the coordinates
@pre: the set must be allowed and the value must be between 1 and 9
@post: data[][] = val, and then the allowed values are updated
@return: none
@throw: assertions
*/
void sudoku::set_item(char val, int x, int y)
{
assert(allowed_set(val, x, y));
assert(data[x][y] == 0);
assert(val >= 1);
assert(val <= 9);
data[x][y] = val;
// update allowed configurations
// set allowed[][][val] = false in rows and cols
for(int i = 0; i < 9; i++){
allowed[x][i][val] = false;
allowed[i][y][val] = false;
}
// now take care of the apropriate 3x3 block
int x_orig = 3 * (int) (x/3);
int y_orig = 3 * (int) (y/3);
for (int i = x_orig; i < x_orig + 3; i++){
for (int j = y_orig; j < y_orig + 3; j++){
allowed[i][j][val] = false;
}
}
for (int i = 0; i < 9; i++)
allowed[x][y][i] = false;
}
/*
@member function: get_item. i have a setter, might as well have a getter
@param: the coordinates
@pre: none
@post: none
@return: the int values of data[][] of the coordinate given
@throw: none
*/
int sudoku::get_item(int x, int y)
{
return (int) data[x][y];
}
/*
@member function: inititialize
@param: none
@pre: it's called only by the constructors
@post: all 729 values in data[][] are allowed
@return: none
@throw: none
*/
void sudoku::initialize()
{
for (int i = 0; i < 9; i++){
for (int j = 0; j < 9; j++){
data[i][j] = 0;
for (int k = 1; k < 10; k++){
allowed[i][j][k] = true;
}
}
}
}
/*
@member function: print
@param: the ostream to print to
@pre: the ostream's file must be opened
@post: the ostream now containes data[][] in the form of a sudoku grid
@return: none
@throw: none
*/
void sudoku::print(std::ostream &out)
{
for (int x = 0; x < 9; x++){
for (int y = 0; y < 9; y++){
out << (int) data[x][y] << " ";
}
out << endl;
}
out << endl;
}
int main(int argc, char*argv[1])
{
//open the files and test for error
ifstream infile;
ofstream outfile;
infile.open (argv[1]);
outfile.open (argv[2]);
if (argc < 3)
{
cout << "ERROR: Use this: ./<file name> input output" << endl;
return 1;
}
char c;
int board [9][9];
//read in the puzzle and insert it into the array board
for (int x = 0; x < 9; x++)
{
for (int y = 0; y < 9; y++)
{
infile >> c;
if (c == '*') board[x][y] = 0;
else board[x][y]= c-'0'; //reads in char c and converts it to int
}
}
//print out the array board
for (int x = 0; x < 9; x++)
{
for (int y = 0; y < 9 ; y++)
{
if (board[x][y] == 0) outfile << "* ";
else outfile << board[x][y] << " ";
}
outfile << endl;
}
outfile << endl;
//copy the board into an instance of the sudoku class
sudoku puzzle(board);
puzzle.getSolution();
puzzle.print(outfile);
outfile << "Recursive calls: " << r_count << endl;
//close the files
infile.close();
outfile.close();
return 0;
}When you go to execute it, use the form .<name you saved it as> <name of the input file> <name of the output file> . The program reads the "clues" from the input file and then prints it neatly to the output file. Insert the clues from left to right, top to bottom, and with * where there would be a blank. For example, this sudoku puzzle would look like this in the input file:
*42*15*9*8*5**9********7**5**9***2**28********51** and so onClearly this is was project for a class, but the due date was quit a while ago...a got a pretty low score on this one. I just think it would be cool to get this one working. Thanks for any help!
