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:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
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

Examples

Input:

Output:

Solutions

/**
 * 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;
    }
}

/**
 * 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

Previous36. Valid Sudoku Next38. Count and Say

Last updated 5 years ago

/** * 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; } }

/** * 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; } }

hashtagDescription

hashtagConstraints

hashtagApproach

hashtagLinks

hashtagExamples

hashtagSolutions

hashtagFollow up