Sudoku solver

sudoku.cpp

// The sudoku solver by anup

#include<iostream>
#include<string.h>
using namespace std;

struct Cell
{
    int _Row,_Column;
    int _Value;
    bool _Fixed;
    Cell(int Value,int Row,int Column)
    {
        _Row=Row;
        _Column=Column;
        _Value=Value;
        if(_Value==0)
            _Fixed=false;
        else
            _Fixed=true;

    }
};
class Sudoku
{
    Cell *CellArray[81];
    int Rotation;
public:
    bool LoadPuzzle(const char* Puzzle)
    {
        if(strlen(Puzzle)!=81)
            return false;
        for(int Row=0; Row<9; Row++)
            for(int Column=0; Column<9; Column++)
            {
                int Value=(int)(Puzzle[9*Row+Column]-(char)48);
                if((Value<0)||(Value>9))
                    cout<<"Wierd value '"<<Puzzle[9*Row+Column]<<"' given! ignoring it!\n";
                CellArray[Row*9+Column]=new Cell(Value,Row,Column);//Create a new cell
            }
        return true;
    }
    void PrintPuzzle()
    {
        for(int Row=0; Row<9; Row++)
        {
            for(int Column=0; Column<9; Column++)
            {
                if(CellArray[9*Row+Column]->_Value==0)
                    cout<<"_  ";
                else
                    cout<<CellArray[9*Row+Column]->_Value<<"  ";
                if(Column%3==2)
                    cout<<" ";
            }
            if(Row%3==2)
                cout<<"\n";
            cout<<"\n\n";
        }
    }
    int FindFirstPosition()
    {
        int i=0;
        while(CellArray[i]->_Value==0)
            i++;
        return i;
    }
    //rotates the Sudoku puzzle
    void Rotate()
    {
        Cell *BackUp[81];//create a backup table
        for(int i=0; i<81; i++)
            BackUp[i]=CellArray[i];//save the address only :D
        //now rotate each row and column
        /*
        we do clockwise rotation

        [0,0] goes to [0,8]
        [1,0] goes to [0,7]
        [1,2] goes to [2,7]
        */
        for(int Row=0; Row<9; Row++)
        {
            for(int Column=0; Column<9; Column++)
            {
                int NewRow=Column;
                int NewColumn=8-Row;
                CellArray[9*NewRow+NewColumn]=BackUp[9*Row+Column];
                //assign a new value of row and column for the cell
                CellArray[9*NewRow+NewColumn]->_Column=NewColumn;
                CellArray[9*NewRow+NewColumn]->_Row=NewRow;
            }
        }
    }
    void RotatePuzzle()
    {
        Cell *BackUp[81];

        for(int i=0; i<81; i++)
        {
            BackUp[i]=new Cell(CellArray[i]->_Value,CellArray[i]->_Row,CellArray[i]->_Column);
            BackUp[i]->_Fixed=CellArray[i]->_Fixed;
        }

        //this is quite a neat trick for a brute force sudoku solver
        int SmallestPosition=FindFirstPosition();
        int SmallestRotation=0;

        for(int rotation=1; rotation<=3; rotation++)
        {
            //rotate the puzzle and see where the first character exists
            Rotate();
            int Position=FindFirstPosition();
            if(Position<SmallestPosition)
            {
                SmallestRotation=rotation;
                SmallestPosition=Position;
            }
            /*cout<<" After "<<rotation<<" rotations, smallestposition="<<SmallestPosition<<" and position="<<Position<<" the puzzle looks like\n";
            PrintPuzzle();*/

        }
        Rotate();//one rotation and the table rotates 4 times(which means it is as it was)
        //save the smallest rortation
        Rotation=SmallestRotation;
        //cout<<"Smallest rotation is "<<SmallestRotation<<endl;
        //rotate SmallestRotation times
        for(int i=1; i<=SmallestRotation; i++)
            Rotate();
        //cout<<"Finalized puzzle is \n";
        //PrintPuzzle();

    }
    //re-rotate the puzzle to make it same as before
    void ReRotatePuzzle()
    {
        if(Rotation==0)
            return;
        int Rerotations=4-Rotation;
        for(int i=1; i<=Rerotations; i++)
            Rotate();//rotate again to make the previous puzzle
    }
    bool CanExist(int Value,const Cell& In)
    {

        //see if the number exists in the row of the cell
        for(int Row=0; Row<9; Row++)
        {
            if((In._Row != Row) && CellArray[9*Row+In._Column]->_Value==Value)
                return false;
        }
        //see if number exists in the column
        for(int Column=0; Column<9; Column++)
        {
            if((In._Column != Column) && CellArray[9*In._Row+Column]->_Value==Value)
                return false;
        }
        //now check for the occurance of value in each 3x3 box
        int Three[]= {0,0,0,3,3,3,6,6,6};
        int RowFrom=Three[In._Row];
        int RowTill=RowFrom+3;

        int ColFrom=Three[In._Column];
        int ColTill=ColFrom+3;

        for(int Column=ColFrom; Column<ColTill; Column++)
            for(int Row=RowFrom; Row<RowTill; Row++)
                if((Row != In._Row) && (Column != In._Column) && CellArray[9*Row+Column]->_Value==Value)
                    return false;
        return true;
    }

    bool Solve(int Number)
    {
        //cout<<"Processing Number "<<Number<<endl;
        Cell *CurCell=CellArray[Number];
        //first of all, check if the cell is constant. If it is constant, pass the value to another cell.
        if(CurCell->_Fixed)
        {
            //cout<<"Cell is constant. Giving handle to another cell...\n";
            //check if this is the last cell. If so, it is considered success
            if(Number==80)
                return true;
            else
                return Solve(Number+1);
        }
        //try every number from 1 to 9
        else
        {
            for(int CheckValue=1; CheckValue<=9; CheckValue++)
            {
                //cout<<"Trying with value "<<i<<endl;
                CurCell->_Value=CheckValue;
                //see if a number can exist in this cell without contradiction
                if(CanExist(CheckValue,*CurCell))
                {
                    //if this is the last cell, return true cause we dont need to ask any other cells
                    if(Number==80)
                        return true;
                    //yes it can, now see for the next cell
                    //	cout<<"Giving handle to another cell\n";
                    if(Solve(Number+1)==true)
                        return true;
                    //ow! some later one cell complained. go for another number
                }
            }
            //none of the letters from 1 to 9 can exist in this cell. So, there must be some problem.  Set value to 0 and return false
            CurCell->_Value=0;
            return false;
        }
    }
};

int main()
{
    Sudoku Game;
    cout<<"The Sudoku Solver\n\n";
    //cout<<"\nEnter a Sudoku puzzle ";
    char* Puzzle="053070020020006000800030000008005001007040800600200400000090002000100050080020970";
    if(!Game.LoadPuzzle(Puzzle))
    {
        cout<<"\nOops! Cant read that kinda text! plz try again...enter the numbers and enter 0 for blank...okay boy try again!\n";
    }
    cout<<"The puzzle you gave is \n\n";
    Game.PrintPuzzle();
    cout<<"\nRotating puzzle\n";
    Game.RotatePuzzle();//rotate to make it quicker to guess result
    Game.PrintPuzzle();
    cout<<"\n\n";
    cout<<"Solving...please wait.\n";
    if(!Game.Solve(0))
    {
        cout<<"The Sudoku puzzle is unsolveable";
        Game.PrintPuzzle();
    }
    else
    {
        //Game.ReRotatePuzzle();//rerotate to make original view
        Game.ReRotatePuzzle();
        cout<<"Okay, i solved it! the solution is \n\n";
        Game.PrintPuzzle();
    }
    return 0;
}