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;
}