Sudoku solver main.cpp

#include<iostream>
#include<string>
#include<stack>
#include"cell.h"
#include"puzzle.h"

using namespace std;

int main(int argc, char* argv[]){

    Puzzle puzzle;
    Puzzle curPuzzle;
    Puzzle pushPuzzle;
    stack<Puzzle> altStack;

    string input = "54.2.9..1...5....4..7...9..8...3..67...6.5...93..1...2..1...6..2....6...3..1.7.49";


    //Validate Input======================================================================================================
    if(input.length() != 81){
        cout <<"INVALID INPUT -- not 81 chars" << endl;;
        return 1;
    }

    for(unsigned int i=0; i<input.length(); i++){

        if(input[i] != '.' && input[i] != '1' && input[i] != '2' && input[i] != '3' && input[i] != '4' && input[i] != '5' &&
        input[i] != '6' && input[i] != '7' && input[i] != '8' && input[i] != '9' ){

            cout << "INVALID INPUT - CHARACTER " << input[i] << " at location " << i << endl;
            return 1;
        }
    }

    //Set up initial puzzle========================================================================================================

    for(int i=0; i<9; i++){
        for(int j=0;j<9;j++){

            //row and column
            puzzle.board[i][j].setRow(i);
            puzzle.board[i][j].setColumn(j);

            if(input.at((i*9)+j) == '.'){
                //set . to 0
                puzzle.board[i][j].setValue(0);

                //set candidates to 1s, because they are initilized as zero.
                for(int k=1; k <=9; k++){
                    puzzle.board[i][j].setCandidate(k,1);
                }
            }else{
                //otherwise set cell value and eliminate its candidates

                puzzle.board[i][j].setValue(input.at((i*9)+j) - 48 );
            }
        }
    }

//puzzle.eliminateCandidates();
//puzzle.testRead();

    //Push initial board onto stack================================================================================
    altStack.push(puzzle);

    while(!altStack.empty()){
        curPuzzle = altStack.top();
        altStack.pop();

        //Initial candidate elimination===============================================================================================
        curPuzzle.eliminateCandidates();

//curPuzzle.testRead();

        //Naked SIngles==============================================================================

        while(curPuzzle.findSingleCandidate() == 1){

                puzzle.eliminateCandidates();
        }

//cout << "The current puzzle after elimination is: " << endl;
//curPuzzle.testRead();

        //Guess Solver
        while(curPuzzle.isSolved() == 0){

        int i=0,j=0,k=0;

            //Find first empty cell
            for(i=0; i<9; i++){
                for(j=0; j<9; j++){
                    if(curPuzzle.board[i][j].getValue() == 0) break;
                }

                if( (j<9) && curPuzzle.board[i][j].getValue() == 0) break;
            }

//            //if there are no empty cells and no conflicts then puzzle is sovled  ---  MAY BE NOT NEEDED
//            if( (i==9) && (j==9) && (curPuzzle.isSolved() == 1) ){
//                cout << "SOLUTION FOUND: " << endl;
//                for(int i=0; i<9; i++){
//                    for(int j=0;j<9;j++){
//                        cout << curPuzzle.board[i][j].getValue();
//                    }
//                }
//                break;
//            }

//cout << "First Empty Cell: [" << i << "][" << j << "]" << " with candidates ";
//for(k=1; k<=9;k++){
//    cout << curPuzzle.board[i][j].getCandidate(k);
//}
//cout << endl;

            //find first valid candidate
            for(k=1; k<=9;k++){
                if(curPuzzle.board[i][j].getCandidate(k) == 1) break;
            }

//cout << "First valid candidate is " << k << endl;

            //if it runs through all candidates, scrap the board and go back one on the stack
            if(k == 10) break;

            //Set the guessed candidate to the cell
            curPuzzle.board[i][j].setValue(k);

            //check for board conflicts
            if(curPuzzle.checkConflicts(i,j) == 1){
                //set cell as a zero again
                curPuzzle.board[i][j].setValue(0);

                //Remove canddidate from possible candidates
                curPuzzle.board[i][j].setCandidate(k,0);

//cout << "CONFLICT DETECTED - RESET CELL [" << i << "][" << j <<"] to 0" << " from " << k << endl;
            }else{
//cout << "Cell [" << i << "][" << j << "] set as candidate " << k << endl;

                //Remove canddidate from possible candidates
                curPuzzle.board[i][j].setCandidate(k,0);

                //Push current board onto stack with a reset value
                pushPuzzle = curPuzzle;
                pushPuzzle.board[i][j].setValue(0);

                altStack.push(pushPuzzle);
            }

            if(curPuzzle.isSolved() == 1){
                cout << "SOLUTION FOUND: " << endl;
                for(int i=0; i<9; i++){
                    for(int j=0;j<9;j++){
                        cout << curPuzzle.board[i][j].getValue();
                    }
                }
            }
        }

    }

    return 0;
}