Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/37.html

37. Sudoku Solver

Level

Hard

Description

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

Image text

A sudoku puzzle…

Image text

…and its solution numbers marked in red.

Note:

  • The given board contain only digits 1-9 and the character '.'.
  • You may assume that the given Sudoku puzzle will have a single unique solution.
  • The given board size is always 9x9.

Algorithm

The algorithm for solving Sudoku is similar to other problems like Permutations, Combinations, and N-Queens. The idea is to fill each grid with a number between 1 to 9, and at each step, check if the number is legal. If it is legal, continue to the next recursion and set the number back to ‘.’ at the end. When checking the legality of the newly added number, it is sufficient to check its row, column, and 3x3 sub-box, as the previously added numbers are already valid.

One way to implement this algorithm is by using recursive functions with horizontal (i) and vertical (j) coordinates. Start filling the numbers line by line, beginning from line 0. If i reaches 9, it means all the numbers are successfully filled, and the function returns true. If j is greater than or equal to 9, the current line is filled, and the function switches to the next line. Otherwise, if the current position is not a point, it means that the current position does not need a number, so call the recursion on the next position.

If the current position needs a number, try filling in all the numbers from 1 to 9 and let c traverse from 1 to 9. Whenever you try to fill in a number, check if there is a conflict by using another sub-function, isValid(). If it is valid, assign the current position to this number and call the recursion on the next position. If the recursion returns true, it means that it can be filled successfully, and the function returns true. If it doesn’t work, reset the state and try again with the next number. If all numbers are tried, and it still fails, the function eventually returns false.

The principle of checking whether the current array is valid is similar to Valid Sudoku. However, it is simpler because we only need to check whether the newly added number will conflict with other positions and detect whether there are repeated numbers in the row, column, and sub-box of the newly added number.

Code

Java

  • 
    public class Sudoku_Solver {
    
    
    	public class Solution {
    
    	    boolean found = false;
    
    	    public void solveSudoku(char[][] b) {
    
    	        if (b == null || b.length == 0)     return;
    
    	        dfs(b, 0, 0);
    	    }
    
    	    public void dfs (char[][] b, int row, int col) {
    
    	        if (row == b.length) {
    	            found = true;
    	            return;
    	        }
    
    	        for (int i = row; i < b.length; i++) {
    	            for (int j = col; j < b[0].length; j++) {
    	                if (b[i][j] != '.') {
    	                    continue;
                        }
    
    	                // try from 1 to 9
    	                int num = 1;
    	                while (num <= 9) {
    
    	                    if (isValid(b, i, j, num)) {
    	                        b[i][j] = (char)('0' + num); // @note@note: must add cast
    
    	                        if (col < b[0].length - 1) {
    	                            dfs(b, row, col + 1);
    
    	                            if (found) {
    	                                return;
                                    }
    
    	                        } else {
    	                            // dfs(b, row + 1, col);
    	                            dfs(b, row + 1, 0); // @note@note: index-0 of next row
    
    	                            if (found) {
    	                                return;
                                    }
    	                        }
    
    	                        b[i][j] = '.'; // reset
    	                    }
    
    	                    num++;
    	                }
    	            }
    	        }
    	    }
    
    	    public boolean isValid (char[][] b, int row, int col, int num) {
    
    	        // search row
    	        for (int i = 0; i < b[0].length; i++) {
    	            if (b[row][i] == '0' + num)     return false;
    	        }
    
    	        // search column
    	        for (int i = 0; i < b.length; i++) {
    	            if (b[i][col] == '0' + num)     return false;
    	        }
    
    	        // search sub-square
    	        int rowSub = row / 3;
    	        int colSub = col / 3;
    	        for (int i = rowSub; i < rowSub + 3; i++) {
    	            for (int j = colSub; j < colSub + 3; j++) {
    	                if (b[i][j] == '0' + num)     return false;
    	            }
    	        }
    
    	        return true;
    	    }
    	}
    
    
    	public class Solution_2 {
    
    	    // +1 is for index simplicity
    	    boolean[][] row = new boolean[9][9 + 1];
    	    boolean[][] col = new boolean[9][9 + 1];
    	    boolean[][] sub = new boolean[9][9 + 1];
    
    	    // hard code number 9 is not good practise BTW
    	    public void solveSudoku(char[][] board) {
    	        if(board == null || board.length == 0) {
    	            return;
    	        }
    
    	        solve(board, 0, 0);
    	    }
    
    	    public boolean solve(char[][] b, int i, int j) { // r: row, c: col
    
    	        if(i == 8 && j == 9) { // reaching end of this matrix
    	            return true;
    	        }
    
    	        if(b[i][j] != '.') {
    	            char currentChar = b[i][j];
    	            row[i][currentChar - '0'] = true;
    	            col[j][currentChar - '0'] = true;
    	            sub[i - i % 3 + j / 3][currentChar - '0'] = true;
    
    	            if(i < 9) {
    	                 solve(b, i + 1, j);
    	            } else {
    	                solve(b, i, j + 1);
    	            }
    
    	        } else {
    
    	            for(int test = 1; test <= 9; test++) {
    	                if(row[i][test] == false && col[j][test] == false && sub[i - i % 3 + j / 3][test] == false) {
    	                    // set this test in marking map to be true
    	                    row[i][test] = true;
    	                    col[j][test] = true;
    	                    sub[i - i % 3 + j / 3][test] = true;
    
    	                    boolean isFound = false;
    	                    if(i < 9) {
    	                        isFound = solve(b, i + 1, j);
    	                    } else {
    	                        isFound = solve(b, i, j + 1);
    	                    }
    
    	                    if(isFound) {
    	                        return true;
    	                    }
    
    	                    // reset test value
    	                    row[i][test] = false;
    	                    col[j][test] = false;
    	                    sub[i - i % 3 + j / 3][test] = false;
    
    	                }
    	            }
    	        }
    
    	        return false;
    	    }
    	}
    }
    
  • // OJ: https://leetcode.com/problems/sudoku-solver/
    // Time: O((9!)^9)
    // Space: O(81)
    class Solution {
        int row[9][9] = {}, col[9][9] = {}, box[9][9] = {};
        bool valid(int x, int y, int i) {
            return row[x][i] == 0 && col[y][i] == 0 && box[x / 3 * 3 + y / 3][i] == 0;
        }
        bool dfs(vector<vector<char>> &A, int x, int y) {
            if (y == 9) {
                ++x;
                y = 0;
            }
            if (x == 9) return true;
            if (A[x][y] == '.') {
                for (int i = 0; i < 9; ++i) {
                    if (!valid(x, y, i)) continue;
                    A[x][y] = '1' + i;
                    row[x][i] = col[y][i] = box[x / 3 * 3 + y / 3][i] = 1;
                    if (dfs(A, x, y + 1)) return true;
                    row[x][i] = col[y][i] = box[x / 3 * 3 + y / 3][i] = 0;
                    A[x][y] = '.';
                }
                return false;
            }
            return dfs(A, x, y + 1);
        }
    public:
        void solveSudoku(vector<vector<char>>& A) {
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    if (A[i][j] == '.') continue;
                    row[i][A[i][j] - '1'] = 1;
                    col[j][A[i][j] - '1'] = 1;
                    box[i / 3 * 3 + j / 3][A[i][j] - '1'] = 1;
                }
            }
            dfs(A, 0, 0);
        }
    };
    
  • class Solution:
        def solveSudoku(self, board: List[List[str]]) -> None:
            def dfs(k):
                nonlocal ok
                if k == len(t):
                    ok = True
                    return
                i, j = t[k]
                for v in range(9):
                    if row[i][v] == col[j][v] == block[i // 3][j // 3][v] == False:
                        row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True
                        board[i][j] = str(v + 1)
                        dfs(k + 1)
                        row[i][v] = col[j][v] = block[i // 3][j // 3][v] = False
                    if ok:
                        return
    
            row = [[False] * 9 for _ in range(9)]
            col = [[False] * 9 for _ in range(9)]
            block = [[[False] * 9 for _ in range(3)] for _ in range(3)]
            t = []
            ok = False
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        t.append((i, j))
                    else:
                        v = int(board[i][j]) - 1
                        row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True
            dfs(0)
    
    ############
    
    class Solution(object):
      def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        cacheBox = [[0] * len(board) for _ in range(len(board))]
        cacheRow = [[0] * len(board) for _ in range(len(board))]
        cacheCol = [[0] * len(board) for _ in range(len(board))]
    
        def helper(board, i, j, cacheRow, cacheCol, cacheBox):
          if board[i][j] == ".":
            for k in range(1, 10):
              if i < 0 or i >= len(board) or j < 0 or j >= len(board):
                continue
              ib = (i / 3) * 3 + j / 3
              if cacheRow[i][k - 1] == 1 or cacheCol[j][k - 1] == 1 or cacheBox[ib][k - 1] == 1:
                continue
    
              cacheRow[i][k - 1] = cacheCol[j][k - 1] = cacheBox[ib][k - 1] = 1
              board[i][j] = str(k)
              if i == j == len(board) - 1:
                return True
              if i + 1 < len(board):
                if helper(board, i + 1, j, cacheRow, cacheCol, cacheBox):
                  return True
              elif j + 1 < len(board):
                if helper(board, 0, j + 1, cacheRow, cacheCol, cacheBox):
                  return True
              board[i][j] = "."
              cacheRow[i][k - 1] = cacheCol[j][k - 1] = cacheBox[ib][k - 1] = 0
          else:
            if i == j == len(board) - 1:
              return True
            if i + 1 < len(board):
              if helper(board, i + 1, j, cacheRow, cacheCol, cacheBox):
                return True
            elif j + 1 < len(board):
              if helper(board, 0, j + 1, cacheRow, cacheCol, cacheBox):
                return True
          return False
    
        for i in range(len(board)):
          for j in range(len(board)):
            if board[i][j] != ".":
              ib = (i / 3) * 3 + j / 3
              k = int(board[i][j]) - 1
              cacheRow[i][k] = cacheCol[j][k] = cacheBox[ib][k] = 1
        print
        helper(board, 0, 0, cacheRow, cacheCol, cacheBox)
    
    

All Problems

All Solutions