龙

哇咔咔

0%

LeetCode 37 Sudoku Solver

发表于 更新于 分类于 Disqus：
Leetcode第37题，解一个数独问题。

Description:

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

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

excemple:

image

solve:

image

题目理解：

数独应该每个人都玩过，它规则很简单，但是做起来很难，就是因为它可能性太多了。

那么这个问题要求解数独问题，首先肯定是需要使用递归来解，然后就可以想能不能动态规划，好像不能，那么就只能强行递归，复杂度不想计算，肯定是指数级，但是它是 9x9的格子，所以还好。

代码：

这里其实挺考验的，如何组织数据是一个大问题，直接影响到整个代码的结构，一定要想得简单一点。

下面代码也是进过很多次调整的，思路比最开始清晰多了。

另外，一个清晰的思路十分重要，不要上来就写，要先想清楚。

代码虽然很长，但是思路还是很清晰的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
public class Solution {
    /**
     * 第一，计算需要填写的格子的剩余可用的格子
     * 第二，取出当前操作数最少的格子
     * 第三，递归
     */

    /**
     * 负责初始化
     */
    public void solveSudoku(char[][] board) {
        boolean[][] r_used = new boolean[9][9];   // 行已使用的数字
        boolean[][] c_used = new boolean[9][9];   // 列已使用的数字
        boolean[][][] b_used = new boolean[3][3][9];  // 3x3 的大格子已使用的数字
        List<int[]> ems = new ArrayList<>();      // 空的格子的下标
        for ( int i = 0; i < 9; i++ ) {
            for ( int j = 0; j < 9; j++ ) {
                if ( board[i][j] == '.' ) {
                    int[] empty = {i, j, 0};      // 行 + 列 + 它可以使用的数字的个数
                    ems.add(empty);
                } else {
                    int num = board[i][j] - 49;   // char 转 int 这里多减一个 1 ， 因为 '1' 对应 0 下标
                    myAdjuster( i, j, num, true, r_used, c_used, b_used );
                }
            }
        }
        int min_idx = findMin( ems, r_used, c_used, b_used );
        mySolver ( board, ems, r_used, c_used, b_used, min_idx);
    }

    /**
     * 递归主体，对输入的 ems.get(idx) 这个格子填数字
     */
    private boolean mySolver ( char[][] bd, List<int[]> ems, boolean[][] r_used, boolean[][] c_used, boolean[][][] b_used, int idx ) {
        if ( idx == -1 ) return true;
        int[] em = ems.get(idx);
        ems.remove(em);     // 将这个格子先移除集合，因为现在要填数字
        int i = em[0], j = em[1];
        for ( int num = 0; num < 9; num++ ) {
            if ( !r_used[i][num] && !c_used[j][num] && !b_used[i/3][j/3][num] ) {  // 可以使用的数字
                myAdjuster( i, j, num, true, r_used, c_used, b_used );        // 调整所使用的数字
                int min_idx = findMin( ems, r_used, c_used, b_used );              // 找到下一个最小
                if ( mySolver ( bd, ems, r_used, c_used, b_used, min_idx) ) {      // 递归
                    bd[i][j] = (char)(num + 49);                                   // 成功表示问题已经解决
                    return true;
                }
                myAdjuster( i, j, num, false, r_used, c_used, b_used );       // 恢复调整
            }
        }
        ems.add(em);      // 添加回集合
        return false;
    }

    /**
     * 调整或者恢复 使用的下标
     */
    private void myAdjuster( int i, int j, int num, boolean add, boolean[][] r_used, boolean[][] c_used, boolean[][][] b_used ) {
        if (add) {
            r_used[i][num] = true;
            c_used[j][num] = true;
            b_used[i/3][j/3][num] = true;
        } else {
            r_used[i][num] = false;
            c_used[j][num] = false;
            b_used[i/3][j/3][num] = false;
        }
    }

    /**
     * 找到最小可操作的格子坐标
     */
    private int findMin( List<int[]> ems, boolean[][] r_used, boolean[][] c_used, boolean[][][] b_used ) {
        for ( int[] em : ems ) {
            int i = em[0], j = em[1];
            em[2] = 0;   // 将这个格子的计数先置零
            for ( int num = 0; num < 9; num++ ) {
                if ( !r_used[i][num] && !c_used[j][num] && !b_used[i/3][j/3][num] )   // 使用可用这个数字
                    em[2]++;
            }
        }
        int min = 1000, idx = -1;
        for ( int i = 0; i < ems.size(); i++ ) {   // 找到最小
            int[] em = ems.get(i);
            if ( em[2] < min ) {
                min = em[2];
                idx = i;
            }
        }
        return idx;
    }
}

运行时间：8ms。
复杂度：指数。
击败：94.23%

image

代码二：

上面的代码每次去找最下操作的格子的时候显得比较复杂，那么将更新与格子的可操作数维护放在一起做，就得到下面的代码，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
public class Solution {
    /**
     * 第一，计算需要填写的格子的剩余可用的格子
     * 第二，取出当前操作数最少的格子
     * 第三，递归
     */
    
    private class Ep {
        boolean[] used = new boolean[9];
        int count = 9;
        int row, col, block;
        
        public Ep(int row, int col, int block) {
            this.row = row;
            this.col = col;
            this.block = block;
        }
        
        public boolean set(int num, boolean flag) {
            if ( used[num] != flag ) {
                count = true == flag ? count - 1 : count + 1;
                used[num] = flag;
                return true;
            } 
            return false;
        }
    }
    
    /**
     * 负责初始化
     */
    public void solveSudoku(char[][] board) {
        List<Ep> ems = new ArrayList<>();      // 空的格子的下标
        for ( int i = 0; i < 9; i++ ) {
            for ( int j = 0; j < 9; j++ ) {
                if ( board[i][j] == '.' ) {
                    Ep empty = new Ep(i, j, (i/3)*3 + j/3 + 1);      // 行 + 列 + 格子
                    ems.add(empty);
                } 
            }
        }
        int min_idx = -1;
        boolean[] temp = new boolean[ems.size()];
        for ( int i = 0; i < 9; i++ ) {
            for ( int j = 0; j < 9; j++ ) {
                if ( board[i][j] != '.' ) {
                    int num = board[i][j] - 49;   // char 转 int 这里多减一个 1 ， 因为 '1' 对应 0 下标
                    min_idx = myAdjuster( ems, i, j, num, true , temp);
                }
            }
        }
        mySolver ( board, ems, min_idx);
    }

    /**
     * 递归主体，对输入的 ems.get(idx) 这个格子填数字
     */
    private boolean mySolver ( char[][] bd, List<Ep> ems, int idx ) {
        if ( idx == -1 ) return true;
        Ep em = ems.get(idx);
        ems.remove(idx);     // 将这个格子先移除集合，因为现在要填数字
        boolean[] adjust = new boolean[ems.size()];
        for ( int num = 0; num < 9; num++ ) {
            if ( false == em.used[num] ) {  // 可以使用的数字
                int min_idx = myAdjuster( ems, em.row, em.col, num, true, adjust );        // 调整所使用的数字
                if ( mySolver ( bd, ems, min_idx) ) {      // 递归
                    bd[em.row][em.col] = (char)(num + 49);                                   // 成功表示问题已经解决
                    return true;
                }
                myAdjuster( ems, em.row, em.col, num, false, adjust );       // 恢复调整
            }
        }
        ems.add(idx, em);      // 添加回集合
        return false;
    }

    /**
     * 调整或者恢复 使用的下标
     */
    private int myAdjuster( List<Ep> ems, int i, int j, int num, boolean flag, boolean[] adjust) {
        if ( flag == true ) {
            int block = (i/3)*3 + j/3 + 1;
            int min = Integer.MAX_VALUE, idx = -1;
            for ( int ii = 0, bound = ems.size(); ii < bound; ii++ ) {
                Ep em = ems.get(ii);
                if ( em.row == i || em.col == j || em.block == block )
                    adjust[ii] = em.set(num, flag);
                if ( min > em.count ) {
                    min = em.count;
                    idx = ii;
                }
            } 
             return idx;
        } else {
            for ( int ii = 0; ii < adjust.length; ii++ ) {
                if ( adjust[ii] ) {
                    ems.get(ii).set(num, false);
                    adjust[ii] = false;
                }
            }
            return -1;
        }
    }
}

上面的维护操作直接与格子绑定在一起，将它建立成为一个格子对象，这样耗费了更多的空间，换来的就是可以维护格子的操作数。

复杂度：指数。
运行时间：4ms。
击败：99.15%

image