Source Code
#include <fstream>
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
using namespace std;
void sudokuSolver(int**, int&); //Function help solving sudoku
void horizontal(int**); //eliminate posibilities in rows
void vertical(int**); //eliminate posibilities in columns
void threeByThree(int**); //eliminate posibilities in 3 by 3 section
void readData(int**, ifstream&); //read data from "sudoku.txt"
void eliminationRule(int**); //if a single number can only be in that row, column
// and 3 by 3, then that cell must be that number
void check(int**); //if one posibility, that cell is that number
string output(int**); //outputing table
bool done(int**); //checks if it's done
void error(); //error message
int main()
{
int** table; //double pointer!!! fun fun....
int counter = 0;
int choice;
//allocation of double pointer
table = new int*[9];
for(int count = 0; count < 9; count++)
{
table[count] = new int[9];
}
//end allocation
cout << " ************************************************n"
<< " * Sudoku Solver v2.0 *n"
<< " * *n"
<< " * Author : Alka G Vulcan *n"
<< " * *n"
<< " * Contact : yake_2002 (at) Hotmail (dot) com *n"
<< " * *n"
<< " * Details : Reads data from "sudoku.txt" *n"
<< " * and solve sudoku. have 0 *n"
<< " * for unknow cell and seperate each *n"
<< " * cell by a space or any single char. *n"
<< " * *n"
<< " * Comment : let me know if there is any way *n"
<< " * to improve this code or any question *n"
<< " * about anything.... *n"
<< " * *n"
<< " * 0 indicates empty spot in sudoku *n"
<< " * *n"
<< " * Changes from previous : *n"
<< " * Implemented multi sudoku data capacity*n"
<< " * in "sudoku.txt" *n"
<< " * fixed sevral minor bugs where 1 wasn't*n"
<< " * correctly captured as possibile*n"
<< " * number *n"
<< " * changed data file to "sudoku.txt" *n"
<< " * *n"
<< " ************************************************nn";
cout << "Would you like to see sample of "sudoku.txt"?n1 for yes, 0 for non";
cin >> choice;
if(choice)
{
cout << "1. space between each numbers n"
<< "2. unknown number represented by 0 n"
<< "3. each 9 by 9 grid ceperated by a empty linenn"
<< "A sample table with 2 puzzles nn"
<< "0 0 0 0 4 0 0 5 2n"
<< "0 6 9 7 0 0 0 0 8n"
<< "0 3 0 8 0 0 0 0 0n"
<< "0 0 0 0 0 0 1 0 3n"
<< "0 7 5 0 3 0 2 4 0n"
<< "3 0 6 0 0 0 0 0 0n"
<< "0 0 0 0 0 7 0 8 0n"
<< "9 0 0 0 0 4 3 1 0n"
<< "7 8 0 0 9 0 0 0 0nn"
<< "0 0 0 1 9 0 3 0 0n"
<< "0 0 0 0 6 7 5 0 8n"
<< "7 9 5 0 0 8 0 0 0n"
<< "0 0 0 6 0 0 0 1 7n"
<< "0 7 1 0 2 0 4 3 0n"
<< "9 4 0 0 0 1 0 0 0n"
<< "0 0 0 8 0 0 7 5 3n"
<< "2 0 7 9 5 0 0 0 0n"
<< "0 0 8 0 7 3 0 0 0n";
}
cout << endl << endl
<< "How many sudoku tables in "sudoku.txt"?n";
cin >> choice;
cout << endl;
ifstream inData;
inData.open("sudoku.txt"); //open "sudoku.dat"
if(inData.fail())
error();
else
{
if(choice > 0)
{
cout << "Results......nn";
readData(table, inData);
sudokuSolver(table, counter);
cout << "1st table was done by " << counter << "th cycle.n"
<< output(table);
for(int n = 0; n < choice - 1; n++)
{
counter = 0;
inData.get();
readData(table, inData);
sudokuSolver(table, counter);
if( n == 0)
{
cout << "2nd table was done by " << counter << "th cycle.n"
<< output(table);
}
else
{
cout << n + 2 << "th table was done by " << counter << "th cycle.n"
<< output(table);
}
}
}
}
inData.close();
inData.clear();
cin.get();
for(int x = 0; x < 9; x++) //freeing allocated memories
{
delete [] table[x];
}
delete [] table;
cin.get();
}
void sudokuSolver(int** table, int&counter)
{
counter++;
for(int x = 0; x < 9; x++)
{
for (int y = 0; y < 9; y++)
{
if(table[x][y] == 0 || table[x][y] > 9) //if a cell is 0 or bigger then 9
{
table[x][y] = 987654321; //putting entire 9 possibilities in that cell
}
}
}
//calling actual sudoku solving functions
vertical(table);
horizontal(table);
threeByThree(table);
check(table);
eliminationRule(table);
//end of sudoku solving functions
//cout << output(table) << endl;
if(!done(table))
sudokuSolver(table, counter);
}
void vertical(int** table)
{
for(int x = 0; x < 9; x++)
{
for(int y = 0; y < 9; y++)
{
if(table[x][y] > 9) //if number is bigger then 9
{
for(int newX = 0; newX < 9; newX++)
{
int number = 0;
if(newX != x) //if it's not same cell
{
if(table[newX][y] == 9)
number = 900000000;
if(table[newX][y] == 8)
number = 80000000;
if(table[newX][y] == 7)
number = 7000000;
if(table[newX][y] == 6)
number = 600000;
if(table[newX][y] == 5)
number = 50000;
if(table[newX][y] == 4)
number = 4000;
if(table[newX][y] == 3)
number = 300;
if(table[newX][y] == 2)
number = 20;
if(table[newX][y] == 1)
number = 1;
}
table[x][y] -= number; //eliminate such possibility
}
}
}
}
}
void horizontal(int** table)
{
for(int x = 0; x < 9; x++)
{
for(int y = 0; y < 9; y++)
{
if(table[x][y] > 9)
{
for(int newY = 0; newY < 9; newY++)
{
int number = 0;
if(newY != y)
{
if(table[x][newY] == 9)
number = 900000000;
if(table[x][newY] == 8)
number = 80000000;
if(table[x][newY] == 7)
number = 7000000;
if(table[x][newY] == 6)
number = 600000;
if(table[x][newY] == 5)
number = 50000;
if(table[x][newY] == 4)
number = 4000;
if(table[x][newY] == 3)
number = 300;
if(table[x][newY] == 2)
number = 20;
if(table[x][newY] == 1)
number = 1;
}
//if number was eliminated previously by horizontal
for(int count = 0; count < 9; count++)
{
if(table[x][newY] == table[count][y])
number = 0;
}
//end
table[x][y] -= number;
}
}
}
}
}
void threeByThree(int** table)
{
for(int x = 0; x < 9; x++)
{
for(int y = 0; y < 9; y++)
{
if(table[x][y] > 9)
{
int newX, newY, checkY;
//setting 3x3 grid cells
if(x<9)
newX=6;
if(x<6)
newX=3;
if(x<3)
newX=0;
if(y<9)
newY=6;
if(y<6)
newY=3;
if(y<3)
newY=0;
//end of setting
checkY = newY; //to know when to move to next row
for(int count = 0; count < 9; count++, newY++)
{
int number = 0;
if(newY != y && newX !=x) //if not same cell
{
if(table[newX][newY] == 9)
number = 900000000;
if(table[newX][newY] == 8)
number = 80000000;
if(table[newX][newY] == 7)
number = 7000000;
if(table[newX][newY] == 6)
number = 600000;
if(table[newX][newY] == 5)
number = 50000;
if(table[newX][newY] == 4)
number = 4000;
if(table[newX][newY] == 3)
number = 300;
if(table[newX][newY] == 2)
number = 20;
if(table[newX][newY] == 1)
number = 1;
}
//if number was eliminated previously by horizontal
for(int count = 0; count < 9; count++)
{
if(count != newY)
{
if(table[newX][newY] == table[x][count])
number = 0;
}
}
//end
//if number was eliminated previously by vertical
for(int count = 0; count < 9; count++)
{
if(count != newX )
{
if(table[newX][newY] == table[count][y])
number = 0;
}
}
//end
table[x][y] -= number;
if(newY == checkY + 2) //if end column of 3x3 grid
{
newX++; //increment row
newY = checkY -1; //set column to -1 since it will get incrment soon
}
}
}
}
}
}
void check(int** table)
{
for(int x = 0; x < 9; x++)
{
for(int y = 0; y < 9; y++)
{
//if there is one posibility, then such number is that cell
if(table[x][y] == 900000000)
table[x][y] = 9;
if(table[x][y] == 80000000)
table[x][y] = 8;
if(table[x][y] == 7000000)
table[x][y] = 7;
if(table[x][y] == 600000)
table[x][y] = 6;
if(table[x][y] == 50000)
table[x][y] = 5;
if(table[x][y] == 4000)
table[x][y] = 4;
if(table[x][y] == 300)
table[x][y] = 3;
if(table[x][y] == 20)
table[x][y] = 2;
if(table[x][y] == 1)
table[x][y] = 1;
}
}
}
bool done(int** table)
{
bool flag = true;
for(int x = 0; x < 9; x ++)
{
for (int y = 0; y < 9; y++)
{
if(table[x][y] > 10 || table[x][y] == 0) //if cell is bigger then 10 or equal to 0
{
flag = false;
}
}
}
return flag;
}
string output(int** table)
{
ostringstream out; //using sstream, since it's more convineant
for(int x = 0; x < 9; x ++)
{
for (int y = 0; y < 9; y++)
{
out << setw(7) << table[x][y] << " ";
}
out << endl;
}
out << endl;
return out.str(); //returning sstream
}
void eliminationRule(int** table)
{
int test[9][9][9]; //first two digit for cell, last digit for possibility
//so if test[2][3][5] == 1, then 5 can be at row 2, column 3
int **temp;
temp = new int*[9];
for(int count = 0; count < 9; count++)
{
temp[count] = new int[9];
}
for(int x = 0; x < 9; x++)
{
for(int y = 0; y < 9; y++)
{
temp[x][y] = table[x][y];
}
}
for(int n = 9; n > 0; n--)
{
for(int x = 0; x < 9; x ++)
{
for(int y = 0; y < 9; y++)
{
test[x][y][n] = 0;
if(table[x][y] > 9)
{
int number=999999999;
//n * 10^(n-1)
if(n > 1)
number = n * (pow(10,static_cast<double>(n-1)));
else
number = 1;
//end
//I think because double to int conversion is imperfect
if((number % 2) != 0 && number != 1)
number+=1;
//end
if(temp[x][y] - number >= 0 || table[x][y] == n)
{
temp[x][y] -= number;
test[x][y][n] = 1; //number n is the possibility at such cell
}
}
}
}
}
for(int x = 0; x < 9; x++)
{
for (int y = 0; y < 9; y++)
{
for (int n = 9; n > 0; n--)
{
if(test[x][y][n] && table[x][y] > 9)
{
int newX, newY, checkY;
bool solo = true;
if(x<3)
newX=0;
else if(x<6)
newX=3;
else if(x<9)
newX=6;
if(y<3)
newY=0;
else if(y<6)
newY=3;
else if(y<9)
newY=6;
checkY = newY;
for(int m = 0; m < 9; m++) //check for vertical
{
if(test[m][y][n] && m != x)
solo = false;
}
for(int m = 0; m < 9; m++) //check for horizontal
{
if(test[x][m][n] && m != y)
solo = false;
}
for(int m = 0; m < 9; m++) //check for 3 by 3
{
if(test[newX][newY][n] && newX != x && newY != y)
{
solo = false;
}
if(newY == checkY + 2)
{
newX++;
newY = checkY - 1;
}
}
//if only that number can be at that cell
if(solo)
{
table[x][y] = n;
}
//end if
}
}
}
}
for(int x = 0; x < 9; x++)
{
for (int y = 0; y < 9; y++)
{
for (int n = 0; n < 9; n++)
{
if(test[x][y][n] && table[x][y] > 9)//if number is possibility in a cell and
//that cell is unknown number
{
bool solo = true;
for(int m = 0; m < 9; m++) //check for vertical
{
//if there is possible number present in that column
//or number it self is present in that column
if(test[m][y][n] && m != x || table[m][y] == n)
solo = false;
}
//if only that number can be at that cell
if(solo)
{
table[x][y] = n;
}
//end if
}
}
}
}
for(int x = 0; x < 9; x++)
{
for (int y = 0; y < 9; y++)
{
for (int n = 1; n < 10; n++)
{
if(test[x][y][n] && table[x][y] > 9) //if number is possibility in a cell and
//that cell is unknown number
{
bool solo = true;
for(int m = 0; m < 9; m++) //check for horizontal
{
//if there is possible number present in that row
//or number it self is present in that row
if(test[x][m][n] && m != y || table[x][m] == n)
solo = false;
}
//if only that number can be at that cell
if(solo)
{
table[x][y] = n;
}
//end if
}
}
}
}
for(int x = 0; x < 9; x ++)
{
delete [] temp[x];
}
delete [] temp;
}
void readData(int** table, ifstream& inData)
{
if(inData.fail()) //if failed to open
error();
int x = 0, y = 0;
for(int z = 0; z < 81; z++) //reading 81 char (9 x 9 sudoku table)
{
table[x][y] = inData.get()-48; //char - 48 is intiger... (look up ASCII table if need assistant)
inData.ignore(); //ignoring a space
if (y == 8) //if it's 9th column
{
x++; //increment row
y = -1; //reset column to -1 since it will get increment soon
}
y++; //increment column
}
}
void error()
{
cout << "ERROR... nn";
}
