Jigsaw Suduko Solver
This is a suduko solver that I wrote in cpp. It can solve most puzzles, even those of the jigsaw type. The code is well commented so you should be able to follow the flow quite easily. The program takes in a file that has specific formating. The file should contain a number and a letter, followed by a space for each box on the board. The number being the number that is located within that specific box or 0 if unknown The letter represents the bold outlined square which the box resides in. An example of the input file can be seen below.
0a 4a 0a 6b 8b 3b 1c 0c 2c 1a 0a 6a 0b 2b 4b 7c 0c 3c 0a 2a 3a 1b 0b 0b 0c 6c 0c 3d 6d 4d 0e 1e 0e 5f 2f 8f 5d 1d 8d 3e 6e 2e 0f 0f 7f 9d 7d 2d 5e 4e 8e 3f 1f 6f 0h 0h 0h 0g 0g 6g 2i 3i 1i 6h 3h 1h 2g 0g 0g 8i 0i 0i 2h 0h 0h 0g 3g 1g 6i 7i 0i
The code can be compiled using
gcc -Wall -o "sudukoSolver" "sudukoSolver.cpp"
The code:
//Jigsaw suduko solver
//Writte by: Bill Heaster
//apexlogic d0t net
#include <iostream>
#include <string>
#include <fstream>
#include <stdlib.h>
#include <sstream>
#include <vector>
#include <algorithm>
const static int maxBoxes=81;
//setup some global containers
//each square has a row and a column
//each square also has the box it is located within
//The square also contains a solution
//if there is no solution it will contain a list of possibilities
struct Box
{
int row;
int col;
char square;
std::vector<int> possible;
int solution;
};
//the game board consists of 81 boxes (9x9) because we know this we can create
//a global struct array that consists of the set number of boxes
Box *box = new Box[maxBoxes];
//removes a number of it exists within a vector
void erase(Box *b, int num)
{
b->possible.erase(std::remove(b->possible.begin(), b->possible.end(), num), b->possible.end());
return;
}
//for debug
void showBoard()
{
int cnt=0;
const static int maxCol=8;
while (cnt!=maxBoxes)
{
std::cout<<box[cnt].solution<<" ";
if(box[cnt].col ==maxCol)
{
std::cout<<std::endl;
}
cnt++;
}
}
void showPossible()
{
int cnt=0;
const static int maxCol=8;
while (cnt!=maxBoxes)
{
std::cout<<box[cnt].possible.size()<<" ";
if(box[cnt].col ==maxCol)
{
std::cout<<std::endl;
}
cnt++;
}
}
//load the file contents into the box array
int loadFile(char *fileName)
{
std::ifstream inFile;
std::string line;
std::string tempString = fileName;
inFile.open(tempString.c_str());
if(!inFile.is_open())
{
return-1;
}
int rowCnt=0;
int colCnt=0;
int boxNum=0;
/////////////DEBUG///////////////
//std::cout<<"boxID col row solution squareLetter"<<std::endl;
//read each line
while (std::getline(inFile, line))
{
int len = line.length();
for(int i=0; i<len; i++)
{
//get a char from the string
char c = line[i];
//if it's a space move to the next col
if(c==' ')
{
colCnt++;
boxNum++;
}
//otherwise assign a value to the next box
else
{
box[boxNum].row=rowCnt;
box[boxNum].col=colCnt;
int b= c -'0';//needed for char -> int conversion
//if there is a solution for this box
if(b!=0)
{
box[boxNum].solution= b;
}
else//if no solution fill the posibilites
{
//fill the posibilities vector
for(int j=1; j<=9; j++)
{
box[boxNum].possible.push_back(j);
}
box[boxNum].solution=0;
}
//get the square letter associated with this box
i++;
c=line[i];
box[boxNum].square= c;
/////////DEBUG//////////
//std::cout<<boxNum<<" "<<box[boxNum].col<<" "<<box[boxNum].row<<" "<<box[boxNum].solution<<" "<<box[boxNum].square<<std::endl;
}
}
//go to next row
rowCnt++;
boxNum++;
colCnt=0;
}
//once the file is coppied we can close it
inFile.close();
return 0;
}
void posCol(int boxNum)
{
int i =0;
while(i<maxBoxes)
{
if(i != boxNum)//if the cycled box isn't the one were using
{
//see if another box in this column contains the same 2 posibilities
if(box[i].col == box[boxNum].col)
{
if(box[i].possible.size()==2)
{
int match=0;
//check if possibilites match
if(box[i].possible.at(0) == box[boxNum].possible.at(0) && box[i].possible.at(1) == box[boxNum].possible.at(1))
{
match=1;
}
else if(box[i].possible.at(0) == box[boxNum].possible.at(1) && box[i].possible.at(1) == box[boxNum].possible.at(0))
{
match=1;
}
if(match)
{
//they match these are the only two spots in this column where these numbers can reside.
//remove this number from the other column boxes if it exists
int firstNumber, secondNumber=0;
firstNumber = box[boxNum].possible.at(0);
secondNumber= box[boxNum].possible.at(1);
int j=0;
while(j<maxBoxes)
{
if(j != boxNum && j != i)//if it isn't the current block or the other
{
if(box[j].col == box[boxNum].col)
{
//if it's in the same column remove the two possibilites from the others
erase(&box[j], firstNumber);
erase(&box[j], secondNumber);
}
}
j++;
}
}
}
}
}
i++;
}//end while
}
void posRow(int boxNum)
{
int i =0;
while(i<maxBoxes)
{
if(i != boxNum)//if the cycled box isn't the one were using
{
//see if another box in this column contains the same 2 posibilities
if(box[i].row == box[boxNum].row)
{
if(box[i].possible.size()==2)
{
int match=0;
//check if possibilites match
if(box[i].possible.at(0) == box[boxNum].possible.at(0) && box[i].possible.at(1) == box[boxNum].possible.at(1))
{
match=1;
}
else if(box[i].possible.at(0) == box[boxNum].possible.at(1) && box[i].possible.at(1) == box[boxNum].possible.at(0))
{
match=1;
}
if(match)
{
//they match these are the only two spots in this column where these numbers can reside.
//remove this number from the other column boxes if it exists
int firstNumber, secondNumber=0;
firstNumber = box[boxNum].possible.at(0);
secondNumber= box[boxNum].possible.at(1);
int j=0;
while(j<maxBoxes)
{
if(j != boxNum && j != i)//if it isn't the current block or the other
{
if(box[j].row == box[boxNum].row)
{
//if it's in the same column remove the two possibilites from the others
erase(&box[j], firstNumber);
erase(&box[j], secondNumber);
}
}
j++;
}
}
}
}
}
i++;
}//end while
}
void posSquare(int boxNum)
{
int i =0;
while(i<maxBoxes)
{
if(i != boxNum)//if the cycled box isn't the one were using
{
//see if another box in this column contains the same 2 posibilities
if(box[i].square == box[boxNum].square)
{
if(box[i].possible.size()==2)
{
int match=0;
//check if possibilites match
if(box[i].possible.at(0) == box[boxNum].possible.at(0) && box[i].possible.at(1) == box[boxNum].possible.at(1))
{
match=1;
}
else if(box[i].possible.at(0) == box[boxNum].possible.at(1) && box[i].possible.at(1) == box[boxNum].possible.at(0))
{
match=1;
}
if(match)
{
//they match these are the only two spots in this column where these numbers can reside.
//remove this number from the other column boxes if it exists
int firstNumber, secondNumber=0;
firstNumber = box[boxNum].possible.at(0);
secondNumber= box[boxNum].possible.at(1);
int j=0;
while(j<maxBoxes)
{
if(j != boxNum && j != i)//if it isn't the current block or the other
{
if(box[j].square == box[boxNum].square)
{
//if it's in the same column remove the two possibilites from the others
erase(&box[j], firstNumber);
erase(&box[j], secondNumber);
}
}
j++;
}
}
}
}
}
i++;
}//end while
}
void checkCol(int boxNum)
{
std::vector<int> colValues;
int i =0;
while(i<maxBoxes)
{
if(i != boxNum)//if the cycled box isn't the one were using
{
//check the col number the box lies in, put the numbers into an array
if(box[i].col == box[boxNum].col)
{
if(box[i].solution !=0)//if the compare box has a solution add it to the col values vector
{
colValues.push_back(box[i].solution);
}
}
}
i++;
}
//remove the colValues from our list of possibilites
for(unsigned int j=0; j<colValues.size(); j++)
{
erase(&box[boxNum], colValues[j]);
}
}
void checkRow(int boxNum)
{
std::vector<int> rowValues;
int i=0;
while(i<maxBoxes)
{
if(i != boxNum)//if the cycled box isn't the one were using
{
//check the row number the box lies in, put the numbers into an array
if(box[i].row == box[boxNum].row)
{
if(box[i].solution !=0)//if the compare box has a solution add it to the row values vector
{
rowValues.push_back(box[i].solution);
}
}
}
i++;
}
//remove the rowValues from our list of possibilites
for(unsigned int j=0; j<rowValues.size(); j++)
{
erase(&box[boxNum], rowValues[j]);
}
}
void checkSquare(int boxNum)
{
std::vector<int> squareValues;
int i=0;
while(i<maxBoxes)
{
if(i != boxNum)//if the cycled box isn't the one were using
{
//check the square number the box lies in, put the numbers into an array
if(box[i].square == box[boxNum].square)
{
if(box[i].solution !=0)//if the compare box has a solution add it to the row values vector
{
squareValues.push_back(box[i].solution);
}
}
}
i++;
}
//remove the rowValues from our list of possibilites
for(unsigned int j=0; j<squareValues.size(); j++)
{
erase(&box[boxNum], squareValues[j]);
}
}
int main(int argc, char**argv)
{
//load the file into the struct
if(argc<2)
{
std::cout<<"Usage: solver [array_file] "<<std::endl;
return 0;
}
if(loadFile(argv[1])<0)
{
std::cout<<"error opening file!"<<std::endl;
return 1;
}
//debug
showBoard();
//showPossible();
std::cout<<"///////////////////////////////////"<<std::endl;
std::cout<<std::endl;
int running =1;//set this to 1 to run the solver engine
int numTries=10000;
int cnt=0;
while(running)
{
//run the main solving loop
//in each run in the loop check rows, columns, squares and adjust posibilities
while(cnt<numTries)
{
for(int i=0; i<maxBoxes; i++)
{
//Only process the boxes that havent been solved yet
if(box[i].solution == 0)
{
//slim down our possibilities
checkCol(i);
checkRow(i);
checkSquare(i);
//check to see if our possibilities are down to 1, if it is we have a solution
if(box[i].possible.size()==1)
{
box[i].solution=box[i].possible.at(0);
}
//sometimes we need to use inference to remove some of the possibilities that can only exist in adjacent boxes
//this usually occurs when there are two posibilities left so we will look for that condition
if(box[i].possible.size()==2)
{
posCol(i);
posRow(i);
posSquare(i);
}
}
}
//std::cout<<std::endl;
//showPossible();
cnt++;
//std::cout<<"try number: "<<cnt<<std::endl;
}
running=0;
}
showBoard();
//std::cout<<std::endl;
//std::cout<<"///////////////////////////////////////////////////////////"<<std::endl<<"posibilities"<<std::endl<<"////////////////////////////////////////////////////"<<std::endl;
//showPossible();
return 0;
}