0

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 on

Clearly 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!

2
Contributors
1
Reply
4
Views
8 Years
Discussion Span
Last Post by mvmalderen
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.