37. Sudoku Solver

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 '.'.

Constraints

• 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.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input:

A sudoku puzzle...

Output:

...and its solution numbers marked in red.

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private static final int SIZE = 9;
    public void solveSudoku(char[][] board) {
        Set<String> tracker = new HashSet<>();
        
        for(int i = 0; i < SIZE; i++) {
            for(int j = 0; j < SIZE; j++) {
                char ch = board[i][j];
                if(board[i][j] != '.') {
                    tracker.add(ch + "r" + i);
                    tracker.add(ch + "c" + j);
                    tracker.add(ch + "b" + i/3 + "-" + j/3);
                }
            }
        }
        
        solve(board, tracker);
    }
    private boolean solve(char[][] board, Set<String> tracker) {
        for(int row = 0; row < SIZE; row++) {
            for(int col = 0; col < SIZE; col++) {
                if(board[row][col] == '.') {
                    for(char n = '1'; n <= '9'; n++) {
                        
                        // check whether number already present
                        if(tracker.contains(n + "r" + row)
                           || tracker.contains(n + "c" + col)
                           || tracker.contains(n + "b" + row/3 + "-" + col/3)) {
                            continue;
                        }
                        
                        board[row][col] = n;
                        
                        tracker.add(n + "r" + row);
                        tracker.add(n + "c" + col);
                        tracker.add(n + "b" + row/3 + "-" + col/3);
                        
                        if(solve(board, tracker)) return true;
                        
                        tracker.remove(n + "r" + row);
                        tracker.remove(n + "c" + col);
                        tracker.remove(n + "b" + row/3 + "-" + col/3);
                        
                        board[row][col] = '.';
                        
                    }
                    return false;
                }
            }
        }
        return true;
    }
}

Solution 2

/**
 * Time complexity : Time complexity is constant here since the board size is 
 *    fixed and there is no N-parameter to measure. Though let's discuss the 
 *    number of operations needed : (9!)^9. Let's consider one row, i.e. not 
 *    more than 9 cells to fill. There are not more than 9 possibilities for 
 *    the first number to put, not more than 9×8 for the second one, not more 
 *    than 9×8×7 for the third one etc. In total that results in not more 
 *    than 9! possibilities for a just one row, that means not more than 
 *    (9!)^9  operations in total.
 * Space complexity : The board size is fixed, and the space is used to store 
 *    row, column and box trackers, each contains 81 elements.
 */

class Solution {
    private static final int SIZE = 9;
    private boolean[][] rowTracker = new boolean[SIZE][SIZE];
    private boolean[][] colTracker = new boolean[SIZE][SIZE];
    private boolean[][] boxTracker = new boolean[SIZE][SIZE];
    
    public void solveSudoku(char[][] board) {
        for(int i = 0; i < SIZE; i++) {
            for(int j = 0; j < SIZE; j++) {
                int n = board[i][j]-'1';
                if(board[i][j] != '.') {
                    rowTracker[i][n] = true;
                    colTracker[j][n] = true;
                    boxTracker[(i/3)*3 + j/3][n] = true;
                }
            }
        }
        fill(board, 0, 0);
    }
    private boolean fill(char[][] board, int row, int col) {
        if(row == 9) return true;
        
        int nextRow = (col == 8)? row+1: row;
        int nextCol = (col == 8)? 0: col+1;
        
        if(board[row][col] != '.') {
            return fill(board, nextRow, nextCol);
        }
        
        for(int n = 0; n < SIZE; n++) {           
            // check whether number already present
            if(rowTracker[row][n] || colTracker[col][n] 
               || boxTracker[(row/3)*3 + col/3][n]) {
                continue;
            }
            
            board[row][col] = (char) (n+'1');

            rowTracker[row][n] = true;
            colTracker[col][n] = true;
            boxTracker[(row/3)*3 + col/3][n] = true;

            if(fill(board, nextRow, nextCol)) return true;
            
            board[row][col] = '.';

            rowTracker[row][n] = false;
            colTracker[col][n] = false;
            boxTracker[(row/3)*3 + col/3][n] = false;
        }
        return false;
    }
}

Follow up

• Solving Sudoku using Bit-wise Algorithm - GFG