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

---

So what's the c++ question?

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.

Quote:

---

Originally Posted by devilsummer

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.