Backtracking - Question 3

Leetcode 37. Sudoku Solver

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 digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

Constraints:

board.length == 9

board[i].length == 9

board[i][j] is a digit or '.'.

It is guaranteed that the input board has only one solution.

Analysis:

This is a another classic backtracking question.

We can try to solve the Sudoku row by row.

Base case: if finish the last row, then we find a one solution, done;

if finish one row, we can move onto the next row;

if the current position is a number, move onto the next position;

if not a number, we can make nine trials: 1 - 9. If one of them can reach the end and return true, we find one solution, done; if none of them is valid, return false.

Pay attention to the place how to make a trial, proceed; if not find a solution, step back and start the next trial, ..., until finish all the trials (or find one solution, which can stop earlier).

See the code below:

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        if(sS(board, 0, 0)) return;
    }
private:
    bool sS(vector<vector<char>>& bd, int x, int y) {
        if(x==9) return true;// find one solution
        if(y==9) return sS(bd, x+1, 0); // one row is finished, move onto the next row
        if(bd[x][y] != '.') return sS(bd, x, y+1);
        for(int i=1; i<=9; ++i) {
            if(isValid(bd, x, y, i)) {
                bd[x][y] = i + '0';// make a trial
                if(sS(bd, x, y+1)) return true;
                bd[x][y] = '.';// step back
            }
        }
        return false;// tried all possibles, but did not find one solution
    }
    bool isValid(vector<vector<char>>& bd, int x, int y, int val) {
        for(int i=0; i<9; ++i) {// check the column
            if(i == x || bd[i][y] == '.') continue;
            if(bd[i][y] == val + '0') return false;
        }
        for(int i=0; i<9; ++i) {// check the row
            if(i == y || bd[x][i] == '.') continue;
            if(bd[x][i] == val + '0') return false;
        }
        for(int i=x/3*3; i<x/3*3 + 3; ++i) {// check the 3 x 3 region
            for(int j=y/3*3; j<y/3*3 + 3; ++j) {
                if(i==x && j==y || bd[i][j] == '.') continue;
                if(bd[i][j] == val + '0') return false;
            }
        }
        return true;
    }
};

 

Upper Layer