Tag Archives: 数独

LeetCode Valid Sudoku

Leave a reply

36. Valid Sudoku

Determine if a 9×9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.


A partially filled sudoku which is valid.

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

Example 1:

Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

Example 2:

Input:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.
  • The given board contain only digits 1-9 and the character '.'.
  • The given board size is always 9x9.

判断一个数独棋盘是否合法，即每行每列和每个小方格内不能有’1’~’9’的重复数字。只要求检查是否合法，不要求棋盘是否可解，所以程序很简单，直接按行、列和小方格检查即可。 完整代码如下：

class Solution {
public:
    bool isValidSudoku(vector<vector<char> >& board)
    {
        int m = board.size();
        if (m != 9)
            return false;
        for (int i = 0; i < m; i++) { // 行
            int n = board[i].size();
            if (n != 9)
                return false;
            vector<int> rows(n, 0);
            for (int j = 0; j < n; j++) {
                if (board[i][j] != ‘.’) {
                    rows[board[i][j] – ‘1’]++;
                    if (rows[board[i][j] – ‘1’] > 1)
                        return false;
                }
            }
        }
        for (int j = 0; j < m; j++) { //列
            vector<int> cols(m, 0);
            for (int i = 0; i < m; i++) {
                if (board[i][j] != ‘.’) {
                    cols[board[i][j] – ‘1’]++;
                    if (cols[board[i][j] – ‘1’] > 1)
                        return false;
                }
            }
        }
        for (int i = 0; i < m; i += 3) { // 小方格
            for (int j = 0; j < m; j += 3) {
                vector<int> cubes(m, 0);
                for (int k = 0; k < m; k++) {
                    if (board[i + k / 3][j + k % 3] != ‘.’) {
                        cubes[board[i + k / 3][j + k % 3] – ‘1’]++;
                        if (cubes[board[i + k / 3][j + k % 3] – ‘1’] > 1)
                            return false;
                    }
                }
            }
        }
        return true;
    }
};

本代码提交AC，用时12MS。
上述代码不够简洁，其实可以只用一个循环把行、列、小方块判断了，参考：https://discuss.leetcode.com/topic/8241/my-short-solution-by-c-o-n2。
完整代码如下，i,j,k分别代表行号、列号、所在小方块的编号，用二维数组rows,cols,cubes标记是否重复。

class Solution {
public:
    bool isValidSudoku(vector<vector<char> >& board)
    {
        int m = 9;
        vector<vector<int> > rows(9, vector<int>(9, 0)), cols(9, vector<int>(9, 0)), cubes(9, vector<int>(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;
                    int k = i / 3 * 3 + j / 3;
                    if (rows[i][num] > 0 || cols[j][num] > 0 || cubes[k][num] > 0)
                        return false;
                    rows[i][num] = cols[j][num] = cubes[k][num] = 1;
                }
            }
        }
        return true;
    }
};

本代码提交AC，用时12MS。

二刷。也是一次循环搞定行、列、和小方块，代码如下。这里面的i,j在检查行时，i是行号，j是列号；在检查列时，i是列号，j是行号；在检查小方块时，i是9个小方块在整个board中的编号，j是小方块内部每个格子的编号，都是从左往右，从上往下开始编号。

class Solution {
public:
	bool IsRepeat(vector<int>& flag, char c) {
		if (c == '.')return false;
		int val = c - '0';
		if (flag[val] > 0)return true;
		++flag[val];
		return false;
	}
	bool isValidSudoku(vector<vector<char>>& board) {

		vector<int> row_flag(10, 0), col_flag(10, 0), box_flag(10, 0);
		for (int i = 0; i < 9; ++i) {
			fill(row_flag.begin(), row_flag.end(), 0);
			fill(col_flag.begin(), col_flag.end(), 0);
			
			for (int j = 0; j < 9; ++j) {

				int box_row_start = i / 3 * 3, box_col_start = i % 3 * 3;
				int	box_row_offset = j / 3, box_col_offset = j % 3;
				int box_row = box_row_start + box_row_offset, box_col = box_col_start + box_col_offset;

				if ((box_row == 0 && (box_col == 0 || box_col == 3 || box_col == 6)) ||
					(box_row == 3 && (box_col == 0 || box_col == 3 || box_col == 6)) ||
					(box_row == 6 && (box_col == 0 || box_col == 3 || box_col == 6)))fill(box_flag.begin(), box_flag.end(), 0); // 小方块左上角

				char rowc = board[i][j], colc = board[j][i], boxc = board[box_row][box_col];
				if (IsRepeat(row_flag, rowc) || IsRepeat(col_flag, colc) || IsRepeat(box_flag, boxc))return false;

			}
		}
		return true;
	}
};

本代码提交AC，用时12MS。