乘风破浪：LeetCode真题_037

乘风破浪：LeetCode真题_037_Sudoku Solver

一、前言

这次我们对于上次的模型做一个扩展并求解。

二、Sudoku Solver

2.1 问题

2.2 分析与解决

这道题让我们按照规则，填写数独表上的内容，并且已知假设答案是唯一的。这里我们直到一个3*3的方格内的数字不能重复，因此须要填写完成，就需要所有的数字，因此我们可以尝试使用图遍历中的深度优先和广度优先遍历来不断地试探，直到得到最后的结果。同样的递归也能达成上面的要求。

class Solution {
    int[][] hCounts;
    int[][] vCounts;
    int[][][] sqCounts;
    public void solveSudoku(char[][] board) {
        hCounts = new int[9][9];
        vCounts = new int[9][9];
        sqCounts = new int[3][3][9];
        for (int row=0;row<9;row++) {
            for (int col=0;col<9;col++) 
                if (board[row][col] != '.') 
                    set(board, row, col, board[row][col]);
        }
        solve(board, 0, 0);
    }
    private boolean solve(char[][] board, int row, int col) {
        if (row == board.length) 
            return true;
        if (col == board[0].length) 
            return solve(board, row+1, 0);
        if (board[row][col] != '.')
            return solve(board, row, col+1);
        
        for (int i=1;i<10;i++) {
            char n = (char)('0' + i);
            if (canAdd(row, col, n)) {
                set(board, row, col, n);
                if (solve(board, row, col+1)) 
                    return true;
                unset(board, row, col, n);
            }
        }
        return false;
    }
    private boolean canAdd(int row, int col, char c) {
        int n = c-'0'-1;
        return hCounts[row][n] == 0 && vCounts[col][n] == 0 && sqCounts[row/3][col/3][n] == 0;
    }
    private void set(char[][] board, int row, int col, char c) {
        board[row][col] = c;
        int n = c-'0'-1;
        hCounts[row][n]++;
        vCounts[col][n]++;
        sqCounts[row/3][col/3][n]++;
    }
    private void unset(char[][] board, int row, int col, char c) {
        board[row][col] = '.';
        int n = c-'0'-1;
        hCounts[row][n]--;
        vCounts[col][n]--;
        sqCounts[row/3][col/3][n]--;
    }
}

这道题的算法可以说是非常经典的，进行了一些抽象，首先是初始化，通过三个数组来检验能不能添加元素进去。方法也很简单，如果存在过某个数值，就加一，然后再添加的时候需要判断一下是不是能够加入进去。

 1     private boolean canAdd(int row, int col, char c) {
 2         int n = c-'0'-1;
 3         return hCounts[row][n] == 0 && vCounts[col][n] == 0 && sqCounts[row/3][col/3][n] == 0;
 4     }
 5     private void set(char[][] board, int row, int col, char c) {
 6         board[row][col] = c;
 7         int n = c-'0'-1;
 8         hCounts[row][n]++;
 9         vCounts[col][n]++;
10         sqCounts[row/3][col/3][n]++;
11     }

之后我们从最开始的[0,0]按行遍历，通过递归算法，如果能将字符加入进去就加入，继续调用，不能的话就撤回，然后继续遍历，先对每一行的每一列的元素进行遍历，当完成之后遍历下一行，直至结束。

 1     private boolean solve(char[][] board, int row, int col) {
 2         if (row == board.length) //已经遍历到表外了，结束，成功。
 3             return true;
 4         if (col == board[0].length) //开始下一行
 5             return solve(board, row+1, 0);
 6         if (board[row][col] != '.')  //不为.则继续下一列。
 7             return solve(board, row, col+1);
 8         
 9         for (int i=1;i<10;i++) {
10             char n = (char)('0' + i);
11             if (canAdd(row, col, n)) {
12                 set(board, row, col, n);
13                 if (solve(board, row, col+1)) 
14                     return true;
15                 unset(board, row, col, n);//不成功，回退
16             }
17         }
18         return false;  //最后都没成功，返回false
19     }

三、总结

涉及到图的问题，让我们想到了八皇后问题，同样的联想到这个题的解法。