Solve Sudoku

1. You are give a partially filled 9*9 2-D array(arr) which represents an incomplete sudoku state.
2. You are required to assign the digits from 1 to 9 to the empty cells following some rules.
Rule 1 -> Digits from 1-9 must occur exactly once in each row.
Rule 2 -> Digits from 1-9 must occur exactly once in each column.
Rule 3 -> Digits from 1-9 must occur exactly once in each 3x3 sub-array of the given 2D array.

Assumption -> The given Sudoku puzzle will have a single unique solution.

Input Format

9*9 integers ranging from 1 to 9.
0 represents an empty cell.

Output Format

You have to print the solved sudoku.

Question Video Constraints

0 <= arr[i][j] <= 9

Sample Input

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

Sample 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 

• Editorial

  Let us go through the rules again -

  Each row should have number from 1 to 9 without repetition.

  Each row should have number from 1 to 9 without repetition.

  Each 3 X 3 box should have number from 1 to 9 without repetition.

  Sudoku can be divided into 9, 3 X 3 boxes as shown in the image below.

  

  With the help of recursion and backtracking, we will try to place every number from 1 to 9 on the cell where zero is present. Before using that number, we will first check whether that number is valid or not by checking whether the current row, column or sub matrix contains the number already. If that number is already present we will not place it. If it is not present, we will place the number on the current cell (mark) and move to the next cell which has zero. If we have tried all the numbers and we still do not find any valid number, we will use backtracking and unmark all the cells that we marked before and repeat the process for new number.

  If we reach to the end of the sudoku, it means that we have found a valid sudoku, and we will print it.

  Signature:

  public static void solveSudoku(int[][] board, int i, int j)

  board - given 9 X 9 sudoku board.

  i -  current row index

  j - current column index

  Code:

  public static void solveSudoku(int[][] board, int i, int j) {
                                      if (i == board.length){
                                        display(board);
                                        return;
                                      }
                                      int ni = 0;
                                      int nj = 0;
                                      if(j == board[0].length - 1){
                                        ni = i + 1;
                                        nj = 0;
                                      } else {
                                        ni = i;
                                        nj = j + 1;
                                      }
                                      if(board[i][j] != 0){
                                        solveSudoku(board, ni, nj);
                                      } else {
                                        for(int val = 1; val <= 9; val++){
                                          if(isValid(board, i, j, val)){
                                            board[i][j] = val;
                                            solveSudoku(board, ni, nj);
                                            board[i][j] = 0;
                                          }
                                        }
                                      }
                                  }
                                  public static boolean isValid(int[][] board, int x, int y, int val) {
                                    int n = board.length;
                                    for (int i = 0; i < n; i++) {
                                      if (board[x][i] == val) {
                                        return false;
                                      }
                                    }
                                  
                                    for (int i = 0; i < n; i++) {
                                      if (board[i][y] == val) {
                                        return false;
                                      }
                                    }
                                  
                                    x = x / 3 * 3;
                                    y = y / 3 * 3;
                                    for (int i = 0; i < 3; i++) {
                                      for (int j = 0; j < 3; j++) {
                                        if (board[x + i][y + j] == val) {
                                          return false;
                                        }
                                      }
                                    }
                                  
                                    return true;
                                  }

  java false

  Code Explained:

  From the main function we will call solveSudoku, passing the board and 0,0 for i,j.

  First we will make the new i,j from the current i,j. We will check if j is at the end of the current row (j == 8). If it is ni = i + 1 and nj = 0. Else, nj = j +1 and ni = i.

  If the board[i][j] == 0, then we will try to put every number from 1 to 9 in that cell, else we will just call the recursive function for the ni and nj.

  To check whether the number is a valid option or not, we will create another function, isValid to which we will pass board, current row index, current column index and the number for which we are checking.

  Row Check:

  We will use a for loop on the current row, by changing the column index and check whether the val is present on that row. If it is, return false as this number is already present on the current row.

  Column Check:

  We will use a for loop on the current column, by changing the row index and check whether the val is present on that column. If it is, return false as this number is already present on the current column.

  Box Check:

  Board can be divided into 9 3 X 3 submatrices. 

  

  For every submarix , the cell marked as * is the common.  If we somehow reach the cell marked as * from the respective submatrix, then with the help of two for loops we can search that respective submatrix.

  To get the index of the top leftmost point for the submatrix we use the relation -

  x = x / 3 * 3

  y = y / 3 * 3

  For example if x = 8 and y = 1, then the index of the * cell will be -

  6 , 0

  By relation we get

  x = 8 /3 * 3

  x = 6

  y = 1 /3 * 3

  y = 0

  Now with help of two for loops we will search whether the val is present in that submatrix or not.

  Code Flow:

  We will start from 0,0 cell. If that cell is zero, we will check which all numbers from 1 to 9 can be placed. If isValid returns true, then we will place that number there, we will mark the current cell by placing that number in that cell. If after certain steps, we find that no number can be placed, we will backtrack and un-mark all the cells that we marked and place a new number.

  In pre - order we will mark the cell, in post - order we will unmark the cell.

  Base Case:

  If the row index is equal to the 9, it means we have filled the board (we are out of the board). We will print it and return.

• Asked in Companies
• Related Topics