Valid Sudoku

• Easy
• tag: set API, loop
• 类似: sudoku, matrix loop

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: "."

思路

• 判断所有行/列/小九宫格是否是valid. 所以关键有2点:
  1. 如何有效的循环遍历matrix的所有行/列/小九宫格?
  2. 如何判断该行/列/小九宫格是有效的?

idea 1

• 判断行很容易. 但是怎么判断列/小九宫格?
• 我一开始想的是通过r/c来遍历. 同时填充出每一个char[9]的jiu来判断.
• 判断char[9]也容易. 这里使用set, 以及add(). 这个add(x)在set已经有这个x的时候会返回false.
• 代码如下:

private boolean isValid(char[] jiu) {
    Set<Character> set = new HashSet<>();
    for (char ch : jiu) {
        if (ch != '.' && !set.add(ch)) {
            return false;
        }
    }
    return true;
}

idea 2

• 并不需要填充char[9]来判断, 直接给出范围不就行了嘛?
• 这里思考一下loop怎么写.

• 判断方法如下:

  • 直接遍历r/c能取得的数 : 0->8. 由于分开行列为2个区间, 所以一个loop解决.

    • 行: (r,0) -> (r,8)
    • 列: (0,c) -> (8,c)

  • 对小九宫格的左上角遍历, 所以一共是9个点:

    • 小九宫格: (r3, c3) -> (r3+2, c3+2).

• 搞清楚算法, 就很好写了.

• 代码如下

public boolean isValidSudoku(char[][] board) {
    for (int rc = 0; rc < 9; ++rc) {
        if (!isValid(board, rc, 0, rc, 8))  return false;
        if (!isValid(board, 0, rc, 8, rc))  return false;
    }

    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < 3; ++c) {
            if (!isValid(board, r*3, c*3, r*3+2, c*3+2)) {
                return false;
            }
        }
    }
    return true;
}

private boolean isValid(char[][] board, int xs, int ys, int xe, int ye) {
    Set<Character> set = new HashSet<>();
    for (int r = xs, r < xe; ++r) {
        for (int c = ys; c < ye; ++c) {
            if (board[r][c] != '.' && !set.add(board[r][c]) {
                return false;
            }
        }
    }
    return true;
}

写后感

• 解决问题不要有成见, 例如这里思路有了, 就要想着怎么遍历. 不一定是r,c的遍历. 那就是起点/终点的遍历. 然后就想出来了.