Sudoku solver puzzle.cpp

#include<iostream>
#include<string>
#include <fstream>
#include<cstdlib>
#include"cell.h"
#include"puzzle.h"
using namespace std;

//isSolved=======================================================================================================================================
int Puzzle::isSolved(){
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            if(this->checkConflicts(i, j) == 1) return 0;
        }
    }

    return 1;
}

//Test Readout=====================================================================================================================================
void Puzzle::testRead(){
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cout << "Set up Cell [" << i << "][" << j << "]";
            cout << " with value: " << this->board[i][j].getValue();
            cout << " and candidates: ";
            for(int k=1; k <=9; k++){
                cout <<this->board[i][j].getCandidate(k);
            }
            cout << endl;
        }
    }

    for(int i=0; i<9; i++){
        for(int j=0;j<9;j++){
            cout << this->board[i][j].getValue();
        }
    }
    cout << endl;
}


//Eliminate Candidates function====================================================================================================================================================================

void Puzzle::eliminateCandidates(){

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

            //if the cell value is zero, find conflicting cells and eliminate them from candidates array of current cell
            if(this->board[i][j].getValue() == 0){

                //Row elimination
                for (int k=0; k<9; k++){
                        //if another cell in the row has a definite value, eliminate that as a candidate from the current cell.
                        if(this->board[k][j].getValue() != 0) this->board[i][j].setCandidate(this->board[k][j].getValue(), 0);
                }

                //Column elimination
                for (int k=0; k<9; k++){
                        //if another cell in the column has a definite value, eliminate that as a candidate from the current cell
                        if(this->board[i][k].getValue() != 0) this->board[i][j].setCandidate(this->board[i][k].getValue(), 0);
                }

                //Block elimination

                // *00
                // 000
                // 000
                if((j == 0 || j == 3 || j == 6) && (i == 0 || i == 3 || i == 6))
                    {
                    if(this->board[i][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j+1].getValue(),0);
                    if(this->board[i][j+2].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j+2].getValue(),0);
                    if(this->board[i+1][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j].getValue(),0);
                    if(this->board[i+2][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i+2][j].getValue(),0);
                    if(this->board[i+1][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j+1].getValue(),0);
                    if(this->board[i+1][j+2].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j+2].getValue(),0);
                    if(this->board[i+2][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i+2][j+1].getValue(),0);
                    if(this->board[i+2][j+2].getValue() != 0) this->board[i][j].setCandidate(this->board[i+2][j+2].getValue(),0);
                  }

                //  000
                //  000
                //  *00
                if((j == 0 || j == 3 || j == 6) && (i == 2 || i == 5 || i == 8))
                  {
                     if(this->board[i-1][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j].getValue(),0);
                     if(this->board[i-2][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i-2][j].getValue(),0);
                     if(this->board[i][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j+1].getValue(),0);
                     if(this->board[i][j+2].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j+2].getValue(),0);
                     if(this->board[i-1][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j+1].getValue(),0);
                     if(this->board[i-1][j+2].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j+2].getValue(),0);
                     if(this->board[i-2][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i-2][j+1].getValue(),0);
                     if(this->board[i-2][j+2].getValue() != 0) this->board[i][j].setCandidate(this->board[i-2][j+2].getValue(),0);
                  }

                // 000
                // *00
                // 000
                if((j == 0 || j == 3 || j == 6) && (i == 1 || i == 4 || i == 7))
                  {
                     if(this->board[i-1][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j].getValue(),0);
                     if(this->board[i-1][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j+1].getValue(),0);
                     if(this->board[i-1][j+2].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j+2].getValue(),0);
                     if(this->board[i][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j+1].getValue(),0);
                     if(this->board[i][j+2].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j+2].getValue(),0);
                     if(this->board[i+1][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j].getValue(),0);
                     if(this->board[i+1][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j+1].getValue(),0);
                     if(this->board[i+1][j+2].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j+2].getValue(),0);
                  }

                // 0*0
                // 000
                // 000
                if((j == 1 || j == 4 || j == 7) && (i == 0 || i == 3 || i == 6))
                  {
                    if(this->board[i][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j-1].getValue(),0);
                    if(this->board[i][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j+1].getValue(),0);
                    if(this->board[i+1][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j+1].getValue(),0);
                    if(this->board[i+1][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j-1].getValue(),0);
                    if(this->board[i+1][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j].getValue(),0);
                    if(this->board[i+2][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i+2][j-1].getValue(),0);
                    if(this->board[i+2][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i+2][j].getValue(),0);
                    if(this->board[i+2][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i+2][j+1].getValue(),0);
                  }

                // 000
                // 0*0
                // 000
                if((j == 1 || j == 4 || j == 7) && (i == 1 || i == 4 || i == 7))
                  {
                     if(this->board[i-1][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j].getValue(),0);
                     if(this->board[i-1][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j-1].getValue(),0);
                     if(this->board[i-1][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j+1].getValue(),0);
                     if(this->board[i][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j+1].getValue(),0);
                     if(this->board[i][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j-1].getValue(),0);
                     if(this->board[i+1][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j+1].getValue(),0);
                     if(this->board[i+1][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j].getValue(),0);
                     if(this->board[i+1][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j-1].getValue(),0);
                  }


                // 000
                // 000
                // 0*0
                if((j == 1 || j == 4 || j == 7) && (i == 2 || i == 5 || i == 8))
                  {
                     if(this->board[i][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j-1].getValue(),0);
                     if(this->board[i][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j+1].getValue(),0);
                     if(this->board[i-1][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j].getValue(),0);
                     if(this->board[i-1][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j+1].getValue(),0);
                     if(this->board[i-1][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j-1].getValue(),0);
                     if(this->board[i-2][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i-2][j].getValue(),0);
                     if(this->board[i-2][j+1].getValue() != 0) this->board[i][j].setCandidate(this->board[i-2][j+1].getValue(),0);
                     if(this->board[i-2][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i-2][j-1].getValue(),0);
                  }

                // 00*
                // 000
                // 000
                if((j == 2 || j == 5 || j == 8) && (i == 0 || i == 3 || i == 6))
                  {
                     if(this->board[i][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j-1].getValue(),0);
                     if(this->board[i][j-2].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j-2].getValue(),0);
                     if(this->board[i+1][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j].getValue(),0);
                     if(this->board[i+1][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j-1].getValue(),0);
                     if(this->board[i+1][j-2].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j-2].getValue(),0);
                     if(this->board[i+2][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i+2][j].getValue(),0);
                     if(this->board[i+2][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i+2][j-1].getValue(),0);
                     if(this->board[i+2][j-2].getValue() != 0) this->board[i][j].setCandidate(this->board[i+2][j-2].getValue(),0);
                  }

                // 000
                // 00*
                // 000
                if((j == 2 || j == 5 || j == 8) && (i == 1 || i == 4 || i == 7))
                  {
                     if(this->board[i-1][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j].getValue(),0);
                     if(this->board[i-1][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j-1].getValue(),0);
                     if(this->board[i-1][j-2].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j-2].getValue(),0);
                     if(this->board[i][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j-1].getValue(),0);
                     if(this->board[i][j-2].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j-2].getValue(),0);
                     if(this->board[i+1][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j].getValue(),0);
                     if(this->board[i+1][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j-1].getValue(),0);
                     if(this->board[i+1][j-2].getValue() != 0) this->board[i][j].setCandidate(this->board[i+1][j-2].getValue(),0);
                  }

                // 000
                // 000
                // 00*
                if((j == 2 || j == 5 || j == 8) && (i == 2 || i == 5 || i == 8))
                  {
                     if(this->board[i][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j-1].getValue(),0);
                     if(this->board[i][j-2].getValue() != 0) this->board[i][j].setCandidate(this->board[i][j-2].getValue(),0);
                     if(this->board[i-1][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j].getValue(),0);
                     if(this->board[i-1][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j-1].getValue(),0);
                     if(this->board[i-1][j-2].getValue() != 0) this->board[i][j].setCandidate(this->board[i-1][j-2].getValue(),0);
                     if(this->board[i-2][j].getValue() != 0) this->board[i][j].setCandidate(this->board[i-2][j].getValue(),0);
                     if(this->board[i-2][j-1].getValue() != 0) this->board[i][j].setCandidate(this->board[i-2][j-1].getValue(),0);
                     if(this->board[i-2][j-2].getValue() != 0) this->board[i][j].setCandidate(this->board[i-2][j-2].getValue(),0);
                  }

            } //if this->board[i][j] == 0
        }//for j
    }//for i
}
//===================================================================================================================================================================================================



//Find Single Candidate===============================================================================================================================================================================
int Puzzle::findSingleCandidate(){

    int candCount = 0;
    int singleCand = 0;
    int i,j,k;
    i=0;
    j=0;
    k=1;

    for(i=0; i<9; i++){
        for(j=0; j<9; j++){
            if(this->board[i][j].getValue() == 0){

                candCount = 0;

                //count number of possible candidates
                for(k = 1; k<=9; k++){
                    if(this->board[i][j].getCandidate(k) == 1){
                        candCount++;
                        singleCand = k;
                    }
                }

                //if there is only one candidate, break.
                if(candCount == 1){
                    this->board[i][j].setValue(singleCand);
                    this->board[i][j].setCandidate(singleCand, 0);
                    return 1;
                }

            }// if this->board[i][j].getValue() == 0
        }//for j
    }//for i
    return 0;
}

//=====================================================================================================================================================================================================


//Check conflicts======================================================================================================================================================================================
int Puzzle::checkConflicts(int i, int j){
    //Returns 1 if there is a conflict with the current value stored in this->board[i][j]. Returns 0 otherwise.

    int k;

        //Row compare
        for (k=0; k<9; k++){
                //skip self comparison
                if(k==i) continue;
                //if another cell in the row has a definite value, eliminate that as a candidate from the current cell.
                 else if(this->board[k][j].getValue()  == this->board[i][j].getValue()) return 1;
        }

        //Column compare
        for (k=0; k<9; k++){
                //skip self comparison
                if(k==j) continue;
                //if another cell in the column has a definite value, eliminate that as a candidate from the current cell.
                else if(this->board[i][k].getValue()  == this->board[i][j].getValue()) return 1;
        }

        //Block compare
        // *00
        // 000
        // 000
        if((j == 0 || j == 3 || j == 6) && (i == 0 || i == 3 || i == 6))
            {
            if(this->board[i][j+1].getValue() == this->board[i][j].getValue()) return 1;
            if(this->board[i][j+2].getValue() == this->board[i][j].getValue()) return 1;
            if(this->board[i+1][j].getValue() == this->board[i][j].getValue()) return 1;
            if(this->board[i+2][j].getValue() == this->board[i][j].getValue()) return 1;
            if(this->board[i+1][j+1].getValue() == this->board[i][j].getValue()) return 1;
            if(this->board[i+1][j+2].getValue() == this->board[i][j].getValue()) return 1;
            if(this->board[i+2][j+1].getValue() == this->board[i][j].getValue()) return 1;
            if(this->board[i+2][j+2].getValue() == this->board[i][j].getValue()) return 1;
          }

        //  000
        //  000
        //  *00
        if((j == 0 || j == 3 || j == 6) && (i == 2 || i == 5 || i == 8))
          {
             if(this->board[i-1][j].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-2][j].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i][j+1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i][j+2].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-1][j+1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-1][j+2].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-2][j+1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-2][j+2].getValue() == this->board[i][j].getValue()) return 1;
          }

        // 000
        // *00
        // 000
        if((j == 0 || j == 3 || j == 6) && (i == 1 || i == 4 || i == 7))
          {
             if(this->board[i-1][j].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-1][j+1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-1][j+2].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i][j+1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i][j+2].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+1][j].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+1][j+1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+1][j+2].getValue() == this->board[i][j].getValue()) return 1;
          }

        // 0*0
        // 000
        // 000
        if((j == 1 || j == 4 || j == 7) && (i == 0 || i == 3 || i == 6))
          {
            if(this->board[i][j-1].getValue() == this->board[i][j].getValue()) return 1;
            if(this->board[i][j+1].getValue() == this->board[i][j].getValue()) return 1;
            if(this->board[i+1][j+1].getValue() == this->board[i][j].getValue()) return 1;
            if(this->board[i+1][j-1].getValue() == this->board[i][j].getValue()) return 1;
            if(this->board[i+1][j].getValue() == this->board[i][j].getValue()) return 1;
            if(this->board[i+2][j-1].getValue() == this->board[i][j].getValue()) return 1;
            if(this->board[i+2][j].getValue() == this->board[i][j].getValue()) return 1;
            if(this->board[i+2][j+1].getValue() == this->board[i][j].getValue()) return 1;
          }

        // 000
        // 0*0
        // 000
        if((j == 1 || j == 4 || j == 7) && (i == 1 || i == 4 || i == 7))
          {
             if(this->board[i-1][j].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-1][j-1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-1][j+1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i][j+1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i][j-1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+1][j+1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+1][j].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+1][j-1].getValue() == this->board[i][j].getValue()) return 1;
          }


        // 000
        // 000
        // 0*0
        if((j == 1 || j == 4 || j == 7) && (i == 2 || i == 5 || i == 8))
          {
             if(this->board[i][j-1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i][j+1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-1][j].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-1][j+1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-1][j-1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-2][j].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-2][j+1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-2][j-1].getValue() == this->board[i][j].getValue()) return 1;
          }

        // 00*
        // 000
        // 000
        if((j == 2 || j == 5 || j == 8) && (i == 0 || i == 3 || i == 6))
          {
             if(this->board[i][j-1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i][j-2].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+1][j].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+1][j-1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+1][j-2].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+2][j].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+2][j-1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+2][j-2].getValue() == this->board[i][j].getValue()) return 1;
          }

        // 000
        // 00*
        // 000
        if((j == 2 || j == 5 || j == 8) && (i == 1 || i == 4 || i == 7))
          {
             if(this->board[i-1][j].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-1][j-1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-1][j-2].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i][j-1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i][j-2].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+1][j].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+1][j-1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i+1][j-2].getValue() == this->board[i][j].getValue()) return 1;
          }

        // 000
        // 000
        // 00*
        if((j == 2 || j == 5 || j == 8) && (i == 2 || i == 5 || i == 8))
          {
             if(this->board[i][j-1].getValue() == this->board[i][j].getValue())  return 1;
             if(this->board[i][j-2].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-1][j].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-1][j-1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-1][j-2].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-2][j].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-2][j-1].getValue() == this->board[i][j].getValue()) return 1;
             if(this->board[i-2][j-2].getValue() == this->board[i][j].getValue()) return 1;
          }

    //No conflict detected, return 0;
    return 0;
}

//===================================================================================================================================================================================================