c++ - 如何想出这样的解决方案？(检查数独是否有效)

Question

https://oj.leetcode.com/problems/valid-sudoku/问题是确定数独是否有效

要解决此问题，只需检查问题中所述的 3 条规则。

1. 每一行的数字 1-9 必须只出现一次。

2. 每列的数字 1-9 必须只出现一次

3. 并且数字 1-9 必须在网格的 9 个子框中的每个子框中只出现一次。

于是想了想，想出了一个类似这样的解决方案:这没什么大不了的，因为首先对行进行哈希处理，然后为列维护哈希，最后为子矩阵维护哈希。

class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        map<char, bool> row;
        map<char, bool> col;
        map<char, bool> block;

        for (int i=0;i<9;i++){
            col.clear();
            row.clear();
            for (int j=0;j<9;j++){
                if (board[i][j]!='.'){
                    if (col[board[i][j]]){
                        return false;
                    }else{
                        col[board[i][j]]=true;
                    }
                }
                if (board[j][i]!='.'){
                    if (row[board[j][i]]){
                        return false;
                    }else{
                        row[board[j][i]]=true;
                    }
                }
            }
        }

        for (int ii=0;ii<9;ii=ii+3){
            for (int jj=0;jj<9;jj=jj+3){
                block.clear();
                for (int i=ii;i<ii+3;i++){
                    for (int j=jj;j<jj+3;j++){
                        if (board[i][j]!='.'){
                            if (block[board[i][j]]){
                                return false;
                            }else{
                                block[board[i][j]]=true;
                            }
                        }
                    }
                }       
            }
        }

        return true;
    }
};

不过后来我查看了一些代码，发现了这个:

Class Solution
    {public:
        bool isValidSudoku(vector<vector<char> > &board) {
            // Start typing your C/C++ solution below
            // DO NOT write int main() function
            vector<vector<bool> > rows(9, vector<bool>(9, false));
            vector<vector<bool> > cols(9, vector<bool>(9, false));
            vector<vector<bool> > blocks(9, vector<bool>(9, false));

            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    if (board[i][j] == '.') continue;
                    int c = board[i][j] - '1';
                    if (rows[i][c] || cols[j][c] || blocks[i - i % 3 + j / 3][c])
                        return false;
                    rows[i][c] = cols[j][c] = blocks[i - i % 3 + j / 3][c] = true;
                }
            }
            return true;
        }

    };

如您所见，这是一个非常巧妙的解决方案，但对我来说最引人注目的部分是“ block [i - i % 3 + j/3][c]”，我的问题是你如何制作这样的表达式“i - i % 3 + j/3"对于子数组？据我所知，没有用于从 9x9 访问 3X3 矩阵的通用公式。如果有人能给出通用规则来编写这样整洁的代码，我会非常高兴。

Answer 1

我们想从 (row, col) 获取一个函数到 block 号。这是我们希望看到的结果图

000 111 222
000 111 222
000 111 222
333 444 555
333 444 555
333 444 555
666 777 888
666 777 888
666 777 888

让我们看第一行。这种重复结构来自整数除法。所以，如果您尝试 col/3，您将得到第一行。

现在让我们看看整个表格。让我们从所有行中减去第一个表达式，这样它将显示所有 A[row][col] 满足 A[row][col] + col/3 = block_no.

000 000 000
000 000 000
000 000 000
333 333 333
333 333 333
333 333 333
666 666 666
666 666 666
666 666 666

嘿，它不再依赖于列号了。如果将其除以 3，您将看到我们刚刚使用的结构，并决定您需要 row/3。

所以，所有一起:col/3 + 3 * (row/3)。

右边的部分看起来很像“向下舍入到最接近的3的倍数”的操作。它可以通过另一种方式实现:你可以减去所有超过那个最接近的倍数。这正是模运算符所做的。所以我们可以将其简化为

col/3 + row - row % 3。