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