Welcome to HBH! If you have tried to register and didn't get a verification email, please using the following link to resend the verification email.
SUDOKU SOLVING PROGRAM in C++
it took me about a week to write this dang thing because my initial input data was impossibly wrong…. lol….
this program read file "sudoku.txt" and solves sudoku…. "sudoku.txt" looks something like this….
0 0 9 1 0 0 8 0 3 2 4 1 0 0 0 0 0 0 0 0 8 0 0 2 1 0 6 1 0 0 0 5 7 0 0 4 0 0 2 0 1 0 6 0 0 5 0 0 2 8 0 0 0 7 9 0 5 4 0 0 3 0 0 0 0 0 0 0 0 5 8 2 8 0 7 0 0 1 4 0 0
where 0 indicate yet to be figured number…..
it's written in C++ so ya need compiler such as DevC++…
well here is another gigantic code by me….
/* updated at march 17, 08 /*
Real programmers don't document.
'If it was hard to write, it should be hard to understand.'
arthor : Alka G Vulcan
contact : yake_2002 (at) Hotmail (dot) come
comment : if cell is 0, initially fill that cell with 987654321,
which mean number 9 ~ 1 is the possibility at that cell
sloppiest pusdo code....
horizontal function eliminate possibility in that column
vertical function eliminiate possibility in that row
threeByThree function eliminiate possibility in that 3 x 3 section
elimination rule function check if a possibility can only be in that cell
if so, that possibility is that cell
*/
#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.dat\" *\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"
<< " ************************************************\n\n";
cout << "Would you like to see sample of \"sudoku.txt\"?\n1 for yes, 0 for no\n";
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 line\n\n"
<< "A sample \n\n"
<< "0 0 0 0 4 0 0 5 2\n"
<< "0 6 9 7 0 0 0 0 8\n"
<< "0 3 0 8 0 0 0 0 0\n"
<< "0 0 0 0 0 0 1 0 3\n"
<< "0 7 5 0 3 0 2 4 0\n"
<< "3 0 6 0 0 0 0 0 0\n"
<< "0 0 0 0 0 7 0 8 0\n"
<< "9 0 0 0 0 4 3 1 0\n"
<< "7 8 0 0 9 0 0 0 0\n\n"
<< "0 0 0 1 9 0 3 0 0\n"
<< "0 0 0 0 6 7 5 0 8\n"
<< "7 9 5 0 0 8 0 0 0\n"
<< "0 0 0 6 0 0 0 1 7\n"
<< "0 7 1 0 2 0 4 3 0\n"
<< "9 4 0 0 0 1 0 0 0\n"
<< "0 0 0 8 0 0 7 5 3\n"
<< "2 0 7 9 5 0 0 0 0\n"
<< "0 0 8 0 7 3 0 0 0\n";
}
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......\n\n";
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 = 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 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 error()
{
cout << "This is what just happened. \n\n"
<<"####################################WWKKKK######################################"
<<"############################WWLLii;; ..ttGGWW##############################"
<<"##########################EE.. ..ttWW##########################"
<<"########################LL ;;WW########################"
<<"######################DD.. ;; tt########################"
<<"######################;; ttKK KK######################"
<<"####################WW ..WWii ff######################"
<<"####################GG ttWW.. ii######################"
<<"####################ff::WW;; ..;;.. ;;ii.. ..######################"
<<"####################LLttKK ..KK##WW;; ..WW##GG ;;######################"
<<"####################EEjjEE ff######ff tt######;;;; ii######################"
<<"######################LLKK LL######;;......KK####iiKK jj######################"
<<"########################EE iiKKDDtt GGWW..;;GGff..WW..DD######################"
<<"######################ff;; ..####ff DDWW########################"
<<"######################.. ff####DD ::WW######################"
<<"######################KKii jjLLttff tt########################"
<<"##########################KKjj.. iiGGKK##########################"
<<"##############################KK.. ;;WW##############################"
<<"##########################GGEE##KKLLjjii;;ttLLWWKKLL############################"
<<"########KKjjEE############GG..KKDDKKGGGGKKEEWW##;;ff##################EEDD######"
<<"########;; ..GG##########GG LL####WWWW######KK LL##############GG:: GG####"
<<"####WWff ..KK########EE ii##KKKK##WWWWWWLL DD##########WWtt LL####"
<<"##DD.. .. ;;WW########tt LLDDDDWWEEKKGG..ii############;; LL####"
<<"##.. ..KKff ;;WW########ff ttWW##########tt ..ii;;WW##"
<<"##.. GG####ff ;;GG########GG.. ;;WW########KKii ..ffKKKKDDDD LL##"
<<"##GG....ii;;tt iiWW######KKGGffttGG########WWff....GGGGffii;;ii....WW##"
<<"####KKjj;;.. ..LL##################WWLL.. ;;..ttLLKKKKKKKKKK####"
<<"##########WWDDttii.. ;;ttKK######WWGG;; ..iiffWW##################"
<<"####################KKff;; ..ttKK##;; iiKK########################"
<<"##########################KKtt ..ffDDtt..ttEE############################"
<<"##############################WWtt ..ttWW##############################"
<<"########################KKLL..;;WW##KKtt.. ..iiDD##########################"
<<"####ff;;ttGGWWKKKKKKff;; ..ii######WWff.. ..ttEE####################"
<<"##iiii ;;LLWW############WWff.. iiLLLLLLLLLLLLDD####"
<<"EE WW;;..;; ;;LL######################KKii ;;.. ..DD##"
<<"##;;ff..tt##;; iiKK##############################EEii..LLtt ..GG ::##"
<<"##WW;; ii##;;..GG######################################DD;;LLEE;; .. tt##"
<<"####jj ..;;EE##########################################WWiiffWWffff LLGG####"
<<"####KKttttDDWW################################################ttttDDjj..WW######"
<<"################################################################EEttiiGG########"
<<"################################################################################"
<<endl;
}
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
}
}
P.S. I had pretty cool skull going on but deleting empty space screw things up little bit…. i'm upset…. lol….
well done, i could have done this in java with a partner, but now than im in school with C++ ill need to study this, they're on for loops, im on this kind of stuff, i have my own agenda, this code should help, so thanks man, mind if i contact you with some questions about it? or if youve made a page about your progs like previously suggested, then wannnnna post the link, thanks again