Solve the Sudoku - backtracking

sudoku.cpp

#include<bits/stdc++.h>
using namespace std;

bool check(int mat[9][9],int I,int J,int k){
    for(int i=0;i<9;i++){
        if(mat[I][i] == k)
            return false;
    }
    for(int i=0;i<9;i++){
        if(mat[i][J] == k)
            return false;
    }
    int bx = I/3;
    int by = J/3;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(mat[i+bx*3][j+by*3]==k){
                return false;
            }
        }
    }
    return true;
}

void another(int mat[9][9],int I,int J){
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            if(mat[i][j]==0){
                for(int k=1;k<10;k++){
                    if(check(mat,i,j,k)){
                        mat[i][j]=k;
                        another(mat,i,j);
                        mat[i][j]=0;
                    }
                }
                return;
            }
        }
    }
    for(int i=0;i<9;i++){
	   for(int j=0;j<9;j++){
	       cout<<mat[i][j]<<" ";
	   }
	   
    }
    cout<<"\n";
}

int main()
 {
	int t;
	cin>>t;
	while(t--){
	    int mat[9][9];
	    for(int i=0;i<9;i++){
	        for(int j=0;j<9;j++){
	            cin>>mat[i][j];
	        }
	    }
	    another(mat,0,0);
	}
	return 0;
}

Given an incomplete Sudoku configuration in terms of a 9 x 9 2-D square matrix (mat[][]). The task to print a solved Sudoku. For simplicity, you may assume that there will be only one unique solution.

Input:
1
3 0 6 5 0 8 4 0 0
5 2 0 0 0 0 0 0 0
0 8 7 0 0 0 0 3 1
0 0 3 0 1 0 0 8 0
9 0 0 8 6 3 0 0 5
0 5 0 0 9 0 6 0 0
1 3 0 0 0 0 2 5 0
0 0 0 0 0 0 0 7 4
0 0 5 2 0 6 3 0 0
Output:
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9

Idea is to assign numbers from 1 to 9 in each vacant place and check if it is valid. If valid then proceed to fill other blank cells. If we encounter that no number can be inserted then we backtrack and change the value assigned in the cell. Backtracking works by creating a state tree that branches out based on the available options. If in any branch we do not find the solution we go to the nearest root and travel to a different option from there. This process can be implemented using recursion.

Recursion takes the matrix and two indices that contain the index of the current location. For each location in the matrix, it checks for each number if it can be inserted. Then we call the function recursively. If everything works out and we found a solution then the matrix will be printed first and the setting of mat[i][j]=0 (backtracking) will be done later. If we found a solution then the last call of the function 'another' will not go through the for loops, but instead, simply print the matrix. When it returns than the whole recursive stack will be backtracked. I had a problem figuring this out. Also, the return statement after the 3rd for loop prevents the program from skipping the location in which it was unable to fit any number. Think when will the program be at this location. If we couldn't find any number to fit we have to backtrack and this is what this return does.

In case we change the rules of sudoku (some hybrid), then all we need to change is the check function. This will also print multiple solutions if they exist.