ValidSudoku [source code]

public class ValidSudoku {
static
/******************************************************************************/
class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board.length != 9)
            return false;
        boolean[][] row_seen = new boolean[9][9], col_seen = new boolean[9][9];
        boolean[][][] small_seen = new boolean[3][3][9];
        for (int i = 0; i < 9; i++) {
            if (board[i].length != 9)
                return false;
            for (int j = 0; j < 9; j++) {
                char digit = board[i][j];
                if (digit == '.')
                    continue;
                if (!Character.isDigit (digit) || digit == '0')
                    return false;
                int index = digit - '0' - 1;
                if (row_seen[i][index])
                    return false;
                row_seen[i][index] = true;
                if (col_seen[j][index])
                    return false;
                col_seen[j][index] = true;
                int x = i / 3, y = j / 3;
                if (small_seen[x][y][index])
                    return false;
                small_seen[x][y][index] = true;
            }
        }
        return true;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ValidSudoku.Solution tester = new ValidSudoku.Solution();
        char[][][] inputs = {
            {{'.','8','7','6','5','4','3','2','1'},
            {'2','.','.','.','.','.','.','.','.'},
            {'3','.','.','.','.','.','.','.','.'},
            {'4','.','.','.','.','.','.','.','.'},
            {'5','.','.','.','.','.','.','.','.'},
            {'6','.','.','.','.','.','.','.','.'},
            {'7','.','.','.','.','.','.','.','.'},
            {'8','.','.','.','.','.','.','.','.'},
            {'9','.','.','.','.','.','.','.','.'}}, {{'1'}},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            char[][] board = inputs[2 * i];
            boolean ans = inputs[2 * i + 1][0][0] == '1';
            System.out.println (Printer.separator ());
            String input_str = Matrix.printMatrix (board);
            boolean output = tester.isValidSudoku (board);
            System.out.printf ("%s -> %s, expected:%b\n", 
                input_str, Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

这个看题目意思好像不是很难? 估计技巧就体现在你怎么实现的更有效率了; java的二维array是可以不同的row有不同的长度的, 所以这个最好也稍微验证一下;

另外, 这里虽然是要验证横向, 竖向, 还有小square,但是不代表你就要分别单独的走3个甚至更多的pass: 这个想法未免太naive了;

一开始的想法是所有的counts之类的都放到一个数组里面, 然后用offset来进行分段, 后来想想没必要, 简直是给自己加戏. 真正面试的时候你会这么浪费时间吗? 一个小的数学计算的失误就可能断送你一整个interview, 没有必要. 最后还是三种counts分开用三个matrix来进行记录, 反正感觉速度也不会差太多;

最后的速度是33ms (69%), 题目比较简单, 没什么好说的, 就是考一个index转换的熟练度;

没有editorial;

@makuiyu said in My short solution by C++. O(n2):

Three flags are used to check whether a number appear.

used1: check each row

used2: check each column

used3: check each sub-boxes

class Solution  
{  
public:  
    bool isValidSudoku(vector<vector<char> > &board)  
    {  
        int used1[9][9] = {0}, used2[9][9] = {0}, used3[9][9] = {0};  

        for(int i = 0; i < board.size(); ++ i)  
            for(int j = 0; j < board[i].size(); ++ j)  
                if(board[i][j] != '.')  
                {  
                    int num = board[i][j] - '0' - 1, k = i / 3 * 3 + j / 3;  
                    if(used1[i][num] || used2[j][num] || used3[k][num])  
                        return false;  
                    used1[i][num] = used2[j][num] = used3[k][num] = 1;  
                }  

        return true;  
    }  
};

差不多的思路; 好像discussion不少都懒得去检查length和entry的validity;

@jianchao.li.fighter said in My short solution by C++. O(n2):

Great code! I really love this line

int num = board[i][j] - '0' - 1, k = i / 3 * 3 + j / 3;  

The variable k so nicely maps all the cells belonging to the same box to the same element of used3 :-)

二维重新Map到一维, 也没什么难的;

@Lorraine921 said in Shared my concise Java code:

    public boolean isValidSudoku(char[][] board) {  
        for(int i = 0; i<9; i++){  
            HashSet<Character> rows = new HashSet<Character>();  
            HashSet<Character> columns = new HashSet<Character>();  
            HashSet<Character> cube = new HashSet<Character>();  
            for (int j = 0; j < 9;j++){  
                if(board[i][j]!='.' && !rows.add(board[i][j]))  
                    return false;  
                if(board[j][i]!='.' && !columns.add(board[j][i]))  
                    return false;  
                int RowIndex = 3*(i/3);  
                int ColIndex = 3*(i%3);  
                if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !cube.add(board[RowIndex + j/3][ColIndex + j%3]))  
                    return false;  
            }  
        }  
        return true;  
    }

刚开始看了半天硬是没有看懂这个人想要表达什么; 直接打印trace看看他到底在算什么:

i:(0)  
    j:(0)  
    (0, 0) -> (0, 0)  
    j:(1)  
    (0, 1) -> (0, 1)  
    j:(2)  
    (0, 2) -> (0, 2)  
    j:(3)  
    (0, 3) -> (1, 0)  
    j:(4)  
    (0, 4) -> (1, 1)  
    j:(5)  
    (0, 5) -> (1, 2)  
    j:(6)  
    (0, 6) -> (2, 0)  
    j:(7)  
    (0, 7) -> (2, 1)  
    j:(8)  
    (0, 8) -> (2, 2)  
i:(1)  
    j:(0)  
    (1, 0) -> (0, 3)  
    j:(1)  
    (1, 1) -> (0, 4)  
    j:(2)  
    (1, 2) -> (0, 5)  
    j:(3)  
    (1, 3) -> (1, 3)  
    j:(4)  
    (1, 4) -> (1, 4)  
    j:(5)  
    (1, 5) -> (1, 5)  
    j:(6)  
    (1, 6) -> (2, 3)  
    j:(7)  
    (1, 7) -> (2, 4)  
    j:(8)  
    (1, 8) -> (2, 5)

这个就还是比较直接的了, 他在扫每一个row的时候, 同时扫一个cube; 强行的让一个row跟一个cube的计算有一个对应性而已; 我认为他这个算法不如我这个算法: 还是在走到每一个entry的时候, 直接更新它本身对应的row, column和cube比较合理一些;

@jaqenhgar said in Shared my concise Java code:

Great solution!. Just trying to explain how to think about % and /. These two operators can be helpful for matrix traversal problems.

For a block traversal, it goes the following way.

0,0, 0,1, 0,2; < --- 3 Horizontal Steps followed by 1 Vertical step to next level.

1,0, 1,1, 1,2; < --- 3 Horizontal Steps followed by 1 Vertical step to next level.

2,0, 2,1, 2,2; < --- 3 Horizontal Steps.

And so on...
But, the j iterates from 0 to 9.

But we need to stop after 3 horizontal steps, and go down 1 step vertical.

Use % for horizontal traversal. Because % increments by 1 for each j : 0%3 = 0 , 1%3 = 1, 2%3 = 2, and resets back. So this covers horizontal traversal for each block by 3 steps.

Use / for vertical traversal. Because / increments by 1 after every 3 j: 0/3 = 0; 1/3 = 0; 2/3 =0; 3/3 = 1.

So far, for a given block, you can traverse the whole block using just j.

But because j is just 0 to 9, it will stay only first block. But to increment block, use i. To move horizontally to next block, use % again : ColIndex = 3 * i%3 (Multiply by 3 so that the next block is after 3 columns. Ie 0,0 is start of first block, second block is 0,3 (not 0,1);

Similarly, to move to next block vertically, use / and multiply by 3 as explained above. Hope this helps.

2015年写的总结, 不应该啊, 那时候大家连这种基本的index计算都不知道?

这个作者的做法其实就是把几个循环合并在一起; 检查cube这一步跟前面检查row和column的步骤其实是不对应的; 他这里完成的就是假如我给你一个i = 0..9, j = 0..9这两个外层循环, 你给我把9个cube按顺序循环一次; 当然, 如果是单独给的这个需求, 最好的思路其实就是我写test的那种思路, index cube, 而不是entry; 但是他这里就是要把cube这个跟row/col写在一起, 所以最后的计算就搞复杂了;

上面这个解释实际上太imperative了, 不理解背后的declarative的原理, 还是没有办法真正的掌握这个计算方式; 现在告诉你, 用这两个0..9来控制这样一个for each block: for each entry in block的计算, 你怎么设置? 当然是i控制block, 然后j控制position inside block. 这里就是这个方法; 首先, 给你一个i, 那么我们现在要走的就是block i, 但是因为我们希望在一个二维的层面上traverse, 所以这个block的二维坐标是(i / 3, i % 3). 然后我们再用j控制在每一个block里面的traverse; 我们在知道了i和j之后, 想要知道我们实际上正站在board本身的那个坐标上面, 比如说是(x, y). 那么怎么计算? 这个计算实际上我是没有做过的, 所以会有点生疏. 画画图就知道了, 比如i是4, 那么我们在的block的二维坐标就是(1, 1), 但是这个是board坐标吗? 假如我们知道j是5, 那么实际的(x, y)应该是多少? 想要找到这个, 首先我们要知道block的原点在哪里, 实际上就是((i / 3) * 3, (i % 3) * 3), 然后在block内的offset是多少呢? 两个方向上分别就是(j / 3, j % 3). 这个应该不难理解了;

我自己对这个写法的解释:

@vegito2002 said in Shared my concise Java code:

This solution calculate the traversal of cubes in a not so intuitive way, and that's why it's a little hard to understand at first. For the rows and columns checking, (i, j) stands for the normal coordinate of board itself. But for cube checking, i and j actually stands for two different things: i is the index of the cube, and j is the index of the entry within cube i.

Just see this:

for i in 1..9:  
    # traversing cube i  
    for j in 1..9:  
        # traversing entry j of cube i  
        (x, y) = ((i / 3) * 3 + j / 3, (i % 3) * 3 + j % 3), and access board[x, y]

To achieve the iteration above, I would instead do traversal like

for i_cube in 0..2: for j_cube in 0..2: for i in 0..2: for j in 0..2:  
    (x, y) = (3 * i_cube + i, 3 * j_cube + j) for board[x, y]

But this would require more nesting and it would not integrate well with the iterations for rows and columns.

For (i, j) = (4, 5), consider which block we are looking at? That is cube i = 4, but to make calculation of x, y easier, we have to change that into 2D coordinate: cube (4 / 3, 4 % 3) = (1, 1). Now, we use j to traverse within this cube. But how do we do that? Well, we first determine the base of this cube, which is its topleft corner. It is easy to calculate as (1 * 3, 1 * 3) = (3, 3). Now we just have to get the bi-directional offsets from (3,3) to the position (4, 5) within the same cube. That offset is also easy to calculate: (j / 3, j % 3) = (1, 2). Check out the illustration below:

Stefan的做法, 用一个set搞定:

@StefanPochmann said in Short+Simple Java using Strings:

Collect the set of things we see, encoded as strings. For example:

• '4' in row 7 is encoded as "(4)7".
• '4' in column 7 is encoded as "7(4)".
• '4' in the top-right block is encoded as "0(4)2".

Scream false if we ever fail to add something because it was already added (i.e., seen before).

    public boolean isValidSudoku(char[][] board) {  
        Set seen = new HashSet();  
        for (int i=0; i<9; ++i) {  
            for (int j=0; j<9; ++j) {  
                if (board[i][j] != '.') {  
                    String b = "(" + board[i][j] + ")";  
                    if (!seen.add(b + i) || !seen.add(j + b) || !seen.add(i/3 + b + j/3))  
                        return false;  
                }  
            }  
        }  
        return true;  
    }

---

Edit: Just occurred to me that we can also make it really clear and self-explaining. I'm loving it.

    public boolean isValidSudoku(char[][] board) {  
        Set seen = new HashSet();  
        for (int i=0; i<9; ++i) {  
            for (int j=0; j<9; ++j) {  
                char number = board[i][j];  
                if (number != '.')  
                    if (!seen.add(number + " in row " + i) ||  
                        !seen.add(number + " in column " + j) ||  
                        !seen.add(number + " in block " + i/3 + "-" + j/3))  
                        return false;  
            }  
        }  
        return true;  
    }

我一开始也是想过用string来做的, 不过后来想想还是算了, 这个题目完全不用搞string来浪费速度;

这个有意思啊:

@hsmishka said in Yet another java 2ms solution:

    public boolean isValidSudoku(char[][] board) {  
        int [] vset = new int [9];  
        int [] hset = new int [9];  
        int [] bckt = new int [9];  
        int idx = 0;  
        for (int i = 0; i < 9; i++) {  
            for (int j = 0; j < 9; j++) {  
                if (board[i][j] != '.') {  
                    idx = 1 << (board[i][j] - '0') ;  
                    if ((hset[i] & idx) > 0 ||  
                        (vset[j] & idx) > 0 ||  
                        (bckt[(i / 3) * 3 + j / 3] & idx) > 0) return false;  
                    hset[i] |= idx;  
                    vset[j] |= idx;  
                    bckt[(i / 3) * 3 + j / 3] |= idx;  
                }  
            }  
        }  
        return true;  
    }

他实际上是用一个integer本身来当做一个set, 用bitmap的思路来完成一个记录; 这个实际上也不是一个非常复杂的东西, 按理来说应该掌握;

不过他这个算法并没有2ms, 30ms左右;

@hsmishka said in Yet another java 2ms solution:

In case of hset, for istance, it sets the bit in row to mark that we saw number from board[i][j]. One could use BitSet instead, but it is alittle slower because method calls slower than plain bit operations. Though smart compiler may optimize it.

submission基本波动;

Problem Description

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:

• A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Difficulty:Medium
Total Accepted:143.2K
Total Submissions:386K
Contributor:LeetCode
Companies
uberapplesnapchat
Related Topics
hash table
Similar Questions
Sudoku Solver