I just wanted to post the code I wrote for an OO C++ solution to solving sudoku puzzles. I'd like to invite anyone to ask questions, give comments, or make critiques on the methods or algorithms in the code.
For a recent job interview, I was tasked with writing a sudoku solver. I chose C++ and an object-oriented approach and wrote the first program to mimic my human search methods. I've since refined it to a more algorithm-oriented approach, but still using objects. The main file and header file for the two classes I used (a class "board" and a class "square") are included below. I'm happy to post the implementation of both classes if requested.
This is a command-line program that takes in a file in the format
1....7.9.
.3..2...8
..96..5..
..53..9..
.1..8...2
6....4...
3......1.
.4......7
..7...3..
with the '.' character being a blank. It will detect most invalid puzzles, and should be able to find a solution to any sudoku puzzle. It uses recursion in several places, which I am particularly happy with.
MAIN.CPP:
/********************************************
*
* Module: main.cpp
* Author: Louis Savalli
* Purpose: Implements a Sudoku solver program.
* The user is prompted to enter a file
* containing the sudoku puzzle, and
* this program prints the solved puzzle
* to the console.
*
********************************************/
#include <iostream>
#include <ios>
#include <fstream>
#include <stdlib.h>
#include "sudoku_utils.h"
void give_num_to_square(board & inBoard, int row, int col, int num);
void remove_num_from_possibles(board & inBoard, int row, int col, int num);
using namespace std;
/********************************************
* Function: get_file_from_user
* Author: Louis Savalli
* Purpose: prompts the user for the file name
* In: character pointer
* Returns: nothing
*********************************************/
void get_file_from_user(char *inFile){
cout << endl << "Please enter the name of the file holding the Sudoku puzzle: ";
cin >> inFile;
}
/********************************************
* Function: data_valid
* Author: Louis Savalli
* Purpose: validates data in a line from sudoku file.
* Only non-zero digits and periods are valid
* characters, and only a line length of SIZE.
* In: character pointer
* Returns: true if valid, false otherwise
*********************************************/
bool data_valid( char *inStr){
int i;
if(strlen(inStr) > SIZE || strlen(inStr) < 1){
cout << "ERROR: line missing or length not " << SIZE << endl;
return false;
}
for(i=0; i<SIZE; i++){
if(isdigit(inStr[i]) == false &&
inStr[i] != '.'){
cout << "ERROR in line [" << inStr << "], ";
cout << "non-digit or non-period encountered" << endl;
return false;
}
if(inStr[i] == '0'){
cout << "ERROR: zero is invalid" << endl;
return false;
}
} /* end for loop */
return true;
} /* end data_valid */
/********************************************
* Function: all_valid
* Author: Louis Savalli
* Purpose: determines if all rows, columns, and
* boxes are valid (no duplicates)
* In: reference to the board
* Returns: true if all is valid, false otherwise
*********************************************/
bool all_valid(board & inBoard){
if(inBoard.rows_valid() == false ||
inBoard.columns_valid() == false ||
inBoard.boxes_valid() == false)
return false;
return true;
} /* end all_valid */
/********************************************
* Function: is_board_solved
* Author: Louis Savalli
* Purpose: determines if board is solved
* In: reference to the board
* Returns: true if solved, false otherwise
*********************************************/
bool is_board_solved(board & inBoard){
if((inBoard.get_num_solved() == (SIZE*SIZE)) &&
(all_valid(inBoard) == true))
return true;
return false;
} /* end is_board_solved */
/********************************************
* Function: process_file
* Author: Louis Savalli
* Purpose: parses the input file into the
* board and square objects. Also
* validates the board. As numbers are assigned
* to the squares, they are eliminated as possibilites
* for other squares in the same row, box, or column.
* If during this process, the program finds
* only one value is possible for a square,
* it will assign the value and recursively
* repeat the process of eliminating that number
* as a possibility for other squares.
* In: pointer to a file stream and a reference to the board
* Returns: 0 on failure, 1 on success
*********************************************/
int process_file(std::ifstream & inFileStream, board & inBoard){
int row, column;
char line[15];
char tempChar[2];
/* this loop reads in one line,
* validates it, then puts it into the board */
for(row=0; row<SIZE; row++){
memset(line, '\0', sizeof(line));
inFileStream.getline(line, 14, '\n');
if(data_valid(line) == false){
return 0;
}
for(column=0; column<SIZE; column++){
tempChar[0] = line[column];
tempChar[1] = '\0';
give_num_to_square(inBoard, row, column, tempChar[0] == '.' ? 0 : atoi(&tempChar[0]));
}
} /* end row for loop */
if(all_valid(inBoard) == false){
cout << "ERROR: duplicates found in row, column, or box. Puzzle is invalid." << endl;
return 0;
}
return 1;
} /* end process_file */
/********************************************
* Function: rm_num_from_possibles_in_col
* Author: Louis Savalli
* Purpose: removes the given number from the
* set of possible numbers for each square
* in the given column
* In: reference to the board, the number to be eliminated, and
* the column to eliminate it from
* Returns: nothing
*********************************************/
void rm_num_from_possibles_in_col(board & inBoard, int num, int col){
int row;
for(row=0; row<SIZE; row++)
remove_num_from_possibles(inBoard, row, col, num);
return;
} /* end rm_num_from_possibles_in_col */
/********************************************
* Function: rm_num_from_possibles_in_row
* Author: Louis Savalli
* Purpose: removes the given number from the
* set of possible numbers for each square
* in the given row
* In: reference to the board, the number to be eliminated, and
* the row to eliminate it from
* Returns: nothing
*********************************************/
void rm_num_from_possibles_in_row(board & inBoard,int num, int row){
int col;
for(col=0; col<SIZE; col++)
remove_num_from_possibles(inBoard, row, col, num);
return;
}
/********************************************
* Function: rm_num_from_possibles_in_box
* Author: Louis Savalli
* Purpose: removes the given number from the
* set of possible numbers for each square
* in the given box
* In: reference to the board, the number to be eliminated, and
* the box to eliminate it from
* Returns: nothing
*********************************************/
void rm_num_from_possibles_in_box(board & inBoard,int num, int box){
int row, col;
for(row=0; row<SIZE; row++)
for(col=0; col<SIZE; col++)
if(inBoard.theSquare[row][col]->get_box() == box)
remove_num_from_possibles(inBoard, row, col, num);
return;
} /* end rm_num_from_possibles_in_box */
/********************************************
* Function: remove_num_from_possibles
* Author: Louis Savalli
* Purpose: removes the given number as a possibility
* for the square in the given row and column.
* This is a seperate function so it can
* check if this removal results in the
* assignment of value to the square. If
* it does, the square is assigned the
* value.
* In: reference to the board, row, column, and number
* Returns: nothing
*********************************************/
void remove_num_from_possibles(board & inBoard, int row, int col, int num){
int newNum;
inBoard.theSquare[row][col]->remove_possible_num(num);
newNum = inBoard.theSquare[row][col]->is_one_num_left();
if(newNum > 0) //this square has been solved, recursively call give_num_to_square
give_num_to_square(inBoard, row, col, newNum);
} /* end remove_num_from_possibles */
/********************************************
* Function: give_num_to_square
* Author: Louis Savalli
* Purpose: this function assigns the given value
* to the square at the given row and column.
* It then removes this number from the possibleNums
* array of other squares in the same
* row, column, and box. If those removals
* result in the finding of another square's value,
* this function is called recursively.
* In: reference to the board, row, column, and number
* Returns: nothing
*********************************************/
void give_num_to_square(board & inBoard, int row, int col, int num){
int box;
/* this conditional prevents over-writing a square that has been already
* assigned a number. This happens during the processing of
* easy puzzles, when the program can assign values to squares
* before the value is read in from the input file.
*/
if(inBoard.theSquare[row][col]->get_num() > 0)
return;
inBoard.theSquare[row][col]->assign_num(num);
if(num != 0){
rm_num_from_possibles_in_col(inBoard, num, col);
rm_num_from_possibles_in_row(inBoard, num, row);
box = inBoard.theSquare[row][col]->get_box();
rm_num_from_possibles_in_box(inBoard, num, box);
inBoard.increment_num_solved();
}
} /* end give_num_to_square */
/**********************************************************
* Function: smart_brute_force
* Author: Louis Savalli
* Purpose: intelligently use brute force to solve the Sudoku puzzle
* In: reference to the board, a test board (used for recursion), and
* an integer level which represents the level of recursion
* Returns: returns 0 if no valid solution was found, 1 if yes
* Notes:
* The function will pick a square with the least
* number of possible choices, guess one choice, then
* play out that scenario filling in numbers accordingly.
* If the scenario turns out to be incorrect, the program
* identifies the choice as not a possibility, removes it,
* then continues processing. This is done with recursion.
*************************************************************/
int smart_brute_force(board *inBoard, const board & inTestBoard, int level){
board localTestBoard; /* used to keep a "master" board for each recursive level */
board loopBoard; /* used inside the main loop */
int k,i;
int *possibles;
int row, col;
int locPossibleNums[SIZE];
if(level == 0)
localTestBoard = board(*inBoard); //board localTestBoard is copy of inBoard;
else
localTestBoard = board(inTestBoard);//board localTestBoard is copy of inTestBoard;
loopBoard = board(localTestBoard);
/*
The idea here is that the program will guess numbers for this one chosen
square, then play out the scenario until it gets the number right. Once
the number is guessed correctly, the function will go on to the next recursive call
and can't go back, because the same process will be repeated at the next level.
So the worst case scenario would be that the last possible choice in each recursive
level was the correct number, but lets say that you have 8 recursive levels and each has
to go through 6 choices, that's still only 1.6 million iterations - which really isn't so
bad.
*/
possibles = localTestBoard.get_square_least_pos(&row, &col);
for(i=0; i<SIZE; i++)
locPossibleNums[i] = possibles[i];
for(k=0; k<SIZE; k++){
if(locPossibleNums[k] == 0){
continue;
}
else{
give_num_to_square(loopBoard, row, col,locPossibleNums[k]);
if(is_board_solved(loopBoard) == true){
*inBoard = board(loopBoard);
return 1;
}
else if (all_valid(loopBoard) == true){
if(smart_brute_force(inBoard, loopBoard, (level+1)) == 1){
break;
}
else{
/* here, an incorrect choice was made. Reset the board */
loopBoard = board(localTestBoard);
}
} /* end else if all_valid */
else{
/* here, an incorrect choice was made. Reset the board */
loopBoard = board(localTestBoard);
}
} /* else from possibles[k] */
} /* end of possibles for loop */
/* This means all possibles were looped through and no valid solution
* was found, so zero must be returned */
if(k >= SIZE)
return 0;
return 1; //if we're here, the puzzle has been solved
} /* end smart_brute_force */
/***************************************************
* Begin main
****************************************************/
int main(){
ifstream inFileStream;
char inFileName[30];
board theBoard;
/***************************************
* Prompt the user for a file name,
* then open the file and process it into
* the board and square objects
****************************************/
memset(inFileName, '\0', sizeof(inFileName));
get_file_from_user(inFileName);
inFileStream.open(inFileName, ifstream::in);
if(inFileStream.is_open() == false){
cout << "ERROR: Cannot find/read, program terminating... " << endl;
return 1;
}
if(process_file(inFileStream, theBoard) == 0){
cout << "Error processing file, program terminating..." << endl;
return 1;
}
inFileStream.close();
/****************************************************
* Solve the puzzle. At this point, all given
* numbers are assigned to their proper squares, and
* all unsolved squares have their possibleNums array
* narrowed down to the smallest possible number.
*****************************************************/
if(!(theBoard.get_num_solved() == (SIZE*SIZE) && all_valid(theBoard)))
smart_brute_force(&theBoard, theBoard, 0);
/**********************************************
* Print results
***********************************************/
if(theBoard.get_num_solved() == (SIZE*SIZE)){
if(all_valid(theBoard) == false){
cout << "Error in program, no solution has been found." << endl << endl;
}
else{
cout << endl << "Done! Your solution is: " << endl << endl;
}
}
else{
cout << endl << "Not done, but " << theBoard.get_num_solved() << " were solved." << endl << endl;
}
theBoard.print_board();
return 0;
} /* end main */SUDOKU_UTILS.H:
/********************************************
*
* Module: sudoku_utils.h
* Author: Louis Savalli
* Purpose: interface for classes used in Sudoko
* solver program
*
********************************************/
#ifndef SUDOKU_UTILS_H_INCLUDED
#define SUDOKU_UTILS_H_INCLUDED
#define SIZE 9
/**********************************************
* Class: square
* Author: Louis Savalli
* Purpose: represents a single square in a Sudoku
* board
************************************************/
class square {
public:
square(int inRow, int inColumn); // constructor; initialize all values
~square(); // destructor
square(const square &inSquare); // copy constructor
int get_row(); // returns row of square
int get_column(); // returns column of square
int get_box(); // returns box of square
int get_num(); // returns number assigned to this square
void assign_num (int x); // assigns number to this square
void remove_possible_num(int x); // removes value from array of possible numbers
bool is_solved(); // returns true if square is solved, which means theNum != 0
int is_one_num_left(); // returns 1-9 if it is the only number left, 0 otherwise
void print_possible_nums(); // for debugging purposes, prints out possibleNums array
int *get_possible_nums(); // returns pointer possibleNums array
int get_num_possibles(); //returns number of possible numbers
private:
int row; // row number of square
int column; // column number of square
int box; /* box number of square, where top row has boxes
* 1-3 from left to right, second row has
* boxes 3-6, etc */
int possibleNums[SIZE]; //holds numbers that are still possible for this square to have
int theNum; // holds actual number the square is once found
};
/**********************************************
* Class: board
* Author: Louis Savalli
* Purpose: represents the Sudoku board, made up of
* square objects
************************************************/
class board {
public:
board(); // constructor
~board(); // destructor
board(const board &origBoard); // copy constructor
int get_num_solved(); // returns number of squares solved on board
void increment_num_solved(); // increments count of number of squares solved
int set_num_solved(int x); // sets numSolved
square *theSquare[SIZE][SIZE]; // board is made up of 2d array of square objects
void print_board(); // prints board to console
bool rows_valid(); // returns true if rows are valid, no duplicates
bool columns_valid(); // returns true if columns are valid, no duplicates
bool boxes_valid(); // returns true if boxes are valid, no duplicates
int *get_square_least_pos(int *row, int *col); //returns row and column of square with least number of possibles,
//and pointer to possibleNums array
private:
int numSolved; // holds number of squares solved on the board, must be managed by user
};
#endif // SUDOKU_UTILS_H_INCLUDED