Convert SUDOKU solver from Depth-First to Breadth-First

[devilsummer]

/* Sudoku solver using dept-first search*/

#include <iostream>
#include <stack>
using namespace std;

struct valpos												//structure which carries information about the position of the cell and its value
{
	int val;
	int row;
	int col;
};
class sudoku				
{
public:
	stack<valpos> record;
	int field[4][4];
	sudoku()
	{
		for(int a=0;a<4;a++)
		{
			for(int b=0;b<4;b++)
			{
				field[a][b]=0;									//initializing the whole field to 0 i.e. emtying all cells
			}
		}
	}
	void insert(int row,int col,int val)						//insert function
	{
		if(row<4 && row>=0 && col<4 && col>=0 && val<=4 && val>0 && field[row][col]==0)			//conditions about rows, columns, and values which will be inserted
		{
			valpos temp;
			temp.row=row;
			temp.col=col;
			temp.val=val;
			record.push(temp);
			field[row][col]=val;
		}
	}
	bool checkrow(int row,int col,int val)												//check validation for row
	{
		for(int a=0;a<4;a++)
		{
			if(field[row][a]==val && a!=col)
			{
				return 0;
			}
		}
		return 1;
	}
	bool checkcol(int row,int col, int val)										//check validation for column
	{
		for (int b=0;b<4;b++)
		{
			if(field[b][col]==val && b!=row)
			{
				return 0;
			}
		}
		return 1;
	}
	bool checksq(int row, int col, int val)										//check validation for the (little) square
	{
		if (row<2 && col<2)														/* conditions about rules of sudoku*/		
		{
			for(int a=0;a<2;a++)
			{
				for(int b=0;b<2;b++)
				{
					if(field[a][b]==val && a!=row && b!=col)
					{
						return 0;
					}
				}
			}
		}
		else if(row<2 && col>1)
		{
			for(int a=0;a<2;a++)
			{
				for(int b=2;b<4;b++)
				{
					if(field[a][b]==val && a!=row && b!=col)
					{
						return 0;
					}
				}
			}
		}
		else if(row>1 && col <2)
		{
			for(int a=2;a<4;a++)
			{
				for(int b=0;b<2;b++)
				{
					if(field[a][b]==val && a!=row && b!=col)
					{
						return 0;
					}
				}
			}
		}
		else if(row>1 && col>1)
		{
			for(int a=2;a<4;a++)
			{
				for(int b=2;b<4;b++)
				{
					if(field[a][b]==val && a!=row && b!=col)
					{
						return 0;
					}
				}
			}
		}
		return 1;
	}
	bool checkvalid(int row, int col, int val)												// check the whole validation if all the validations above are true
	{
		if(checkrow(row,col,val) && checkcol(row,col,val)&& checksq(row,col,val))
		{
			return 1;
		}
		else
		{
			return 0;
		}
	}
	bool issolved(bool partial)	//if partial is 0, the function will return true only for a fully completed sudoku, if it is 1, it will also return true for partially completed puzzles
	{
		for(int a=0;a<4;a++)
		{
			for(int b=0;b<4;b++)
			{
				if(field[a][b]==0)
				{
					if(!partial)
					{
						return 0;
					}
				}
				else if(!checkvalid(a,b,field[a][b]))
				{
					return 0;
				}
			}
		}
		return 1;
	}
	bool solve()												//function named solved, to solve the sudoku
	{
		if(!issolved(0))
		{
			for(int a=1;a<=4;a++)
			{
				nextfree(a);
				if(issolved(1))
				{
					solve();
				}
				else
				{
					undo();
				}
			}
			if(!issolved(0))
			{
				undo();
			}
		}
		return issolved(0);
	}
	void nextfree(int val)											//find the next free cell (dept-first search)
	{
		int x;
		int y;
		bool found=false;
		for(int a=0;a<4;a++)
		{
			for(int b=0;b<4;b++)
			{
				if(field[a][b]==0 && found==false)
				{
					x=a;
					y=b;
					found=true;
				}
			}
		}
		if(found==true)
		{
			insert(x,y,val);
		}
	}
	void undo()		//when a push from the stack is not correclty done, this function goes one step back, pops the value and pushes another one 
	{
		field[record.top().row][record.top().col]=0;
		record.pop();
	}
	void draw()														//draws the matrix i.e. the sudoku 
	{
		for(int a=0;a<4;a++)
		{
			for(int b=0;b<4;b++)
			{
				cout << field[a][b] << " ";
			}
			cout << endl << endl;
		}
	}
};
int main()
{
	sudoku a;
	cout << "\n\t*Welcome to the 4x4 Sudoku Solver*" << endl;
	int values;
	int x;
	int y;
	int val;

	
	cout<<"\n\nHow many initial values you want to enter to the sudoku: ";
	cout<<"\n\nOr you can input 0 values in order for the sudoku to find a soultion itself.";
	cin >> values;
	cout<<"\nEnter location where you want to input these "<<values<<" values.";
	for(int s=1;s<=values;s++)
	{
		cout<<"\n\tRow:";
		cin >> x;
		cout<<"\tColumn: ";
		cin >> y;
		cout<<"\tValue: ";	
		cin >> val;
		a.insert(x-1,y-1,val);										//calls function insert
	}
	if(a.solve())
	{
		a.draw();
	}
	else
	{
		cout << "Initial configuration is wrong" << endl;
	}
	return 0;
}