Convert SUDOKU solver from Depth-First to Breadth-First
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Convert SUDOKU solver from Depth-First to Breadth-First

  1. #1
    Join Date
    Feb 2013
    Posts
    11

    Convert SUDOKU solver from Depth-First to Breadth-First

    Code:
    /* 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;
    }

  2. #2
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,847

    Re: Convert SUDOKU solver from Depth-First to Breadth-First

    So what's the c++ question?
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  3. #3
    Join Date
    Feb 2013
    Posts
    11

    Re: Convert SUDOKU solver from Depth-First to Breadth-First

    When I convert from stack to queue (.top to .front) the program does not work correctly. It always displays the message that there is no solution to the pattern inputed by the user.

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: Convert SUDOKU solver from Depth-First to Breadth-First

    Quote Originally Posted by devilsummer View Post
    When I convert from stack to queue (.top to .front) the program does not work correctly. It always displays the message that there is no solution to the pattern inputed by the user.
    I'm not going to debug your code but in principle it should be sufficient to switch data structures. Although in practice I doubt this will always work. I think the algorithm must be designed with this ability in mind.

    I suggest you redesign your program using the breadth-first algorithm described here,

    http://en.wikipedia.org/wiki/Breadth-first_search

    Then switching to depth-first by simply substituting the queue for a stack should work because it's explicitly stated it will.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center