Quick actions

cmd+k|ctrl+k

Navigation

Languages

Sudoku Solver v2

Snippet info

Language

Cpp

Visibility

public

Author

hyqxyz

Created

2015-07-29T09:58:27Z

Updated

2015-07-31T10:45:49Z

#include <iostream>
using namespace std;


class Solver{
  public:
    bool checkSpot(int r, int c, int n){
        for( int i = 0; i < 9; i ++ ){
            if(sudoku[r][i] == n || sudoku[i][c] == n) return false;
        }
        int boxr = ((int)(r/3)) * 3;
        int boxc = ((int)(c/3)) * 3;        
        for( int i = 0; i < 3; i ++ ){
            for( int j = 0; j < 3; j++ ){
                if( sudoku[boxr+i][boxc+j] == n ) return false;    
            }
        }
        return true;
    }
    
    bool backTracker(int r=0, int c=0){
        steps++;
        if(r == 9) return true; 
        if(sudoku[r][c] == 0){
            for( int i = 1; i < 10; i++){
                if(checkSpot(r,c,i)){
                    sudoku[r][c] = i;
                    if(  backTracker( r + ((int)(c+1)/9), (c+1)%9  ) ) return true;
                }
            }
            sudoku[r][c] = 0;
            return false;
        }
        else if( backTracker( r + ((int)(c+1)/9), (c+1)%9  ) ){
            return true;
        }
        else{
            return false;
        }
    }
    
    void output(){
        for( int x = 0; x < 9 ; x++ ){
            if(x % 3 == 0){
                cout << " +  -  -  -  +  -  -  -  +  -  -  -  + " << endl;
            }  
            for( int y = 0; y < 9; y ++){
                if(y % 3 == 0){
                    cout << " + ";
                }
                cout <<  " "<< sudoku[x][y] << " ";
            }
            cout << " +" << endl;
        }
        cout << " +  -  -  -  +  -  -  -  +  -  -  -  + " << endl << endl;
        cout << "[SUDOKU SOLVED][TOOK " << steps << " STEPS]" << endl;
    } 
  private:
     int sudoku[9][9] = {
      {0,6,0,9,0,0,8,0,0},
      {5,0,0,6,0,0,3,1,4},
      {0,7,8,0,0,0,9,0,5},
      {8,0,0,0,5,0,2,9,0},
      {0,0,5,7,0,8,4,0,0},
      {0,3,1,0,2,0,0,0,8},
      {2,0,6,0,0,0,1,4,0},
      {3,8,4,0,0,6,0,0,9},
      {0,0,9,0,0,2,0,8,0}
    };
    int steps = 0;
};

int main() {
    Solver s;
    s.backTracker();
    s.output();
    return 0;
}
INFO