leetcode 36. Valid Sudoku || 37. Sudoku Solver

本次题解包括

• 36. Valid Sudoku
• 37. Sudoku Solver

36. Valid Sudoku

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.

题目地址：leetcode Valid Sudoku

题目大意：给你一个数独，让你判断是否是合法的数独。合法的数度定义为：每一行和每一列的数字以及每9个宫格数字不能重复出现。

思路：

先判断行和列是否有重复的，再判断9个是否有重复的。

直观的写法:

C++

class Solution {
public:
	bool isValidSudoku(vector<vector<char>>& board) {
		for (int i = 0; i < 9; ++i) {
			vector<bool> vis(10, false);
			for (int j = 0; j < 9; ++j) {
				char c = board[i][j];
				if (c == '.') continue;
				c -= '0';
				if (vis[c]) return false;
				vis[c] = true;
			}
		}

		for (int j = 0; j < 9; ++j) {
			vector<bool> vis(10, false);
			for (int i = 0; i < 9; ++i) {
				char c = board[i][j];
				if (c == '.') continue;
				c -= '0';
				if (vis[c]) return false;
				vis[c] = true;
			}
		}

		for (int si = 0; si < 9; si += 3) {
			for (int sj = 0; sj < 9; sj += 3) {
				vector<bool> vis(10, false);
				for (int i = 0; i < 3; ++i) {
					for (int j = 0; j < 3; ++j) {
						char c = board[si + i][sj + j];
						if (c == '.') continue;
						c -= '0';
						if (vis[c]) return false;
						vis[c] = true;
					}
				}
			}
		}
		return true;
	}
};

 

更好的写法：

C++

class Solution {
public:
	bool isValidSudoku(vector<vector<char>>& board) {
		bool row_vis[9][9] = { false }, col_vis[9][9] = { false }, sub_box_vis[9][9] = { false };
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) {
				if (board[i][j] == '.') continue;
				int index = board[i][j] - '1';
				int sub_index = i / 3 * 3 + j / 3;
				if (row_vis[i][index] || col_vis[j][index] || sub_box_vis[sub_index][index])
					return false;
				row_vis[i][index] = col_vis[j][index] = sub_box_vis[sub_index][index] = true;
			}
		}
		return true;
	}
};

python

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        row_vis = [[False] * 9 for _ in range(9)]
        col_vis = [[False] * 9 for _ in range(9)]
        sub_box_vis = [[False] * 9 for _ in range(9)]

        for i in range(9):
            for j in range(9):
                if board[i][j] == '.': continue
                index = ord(board[i][j]) - ord('1')
                sub_index = i // 3 * 3 + j // 3
                if row_vis[i][index] or col_vis[j][index] or sub_box_vis[sub_index][index]:
                    return False
                row_vis[i][index] = col_vis[j][index] = sub_box_vis[sub_index][index] = True
        return True

 

---

37. Sudoku Solver

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.

A sudoku puzzle...

...and its solution numbers marked in red.

题目地址：leetcode Sudoku Solver

题目大意： 给个数独，让你输出解

思路：

C++

class Solution {
    bool dfs(int cur, vector<vector<char>> &board, bool row[][9], bool col[][9], bool grid[][9]){
        if(cur >= 81)
            return true;
        int x = cur / 9, y = cur % 9;
        if(board[x][y] != '.')
            return dfs(cur + 1, board, row, col, grid);
        for(int i = 0; i < 9; ++i){
            int k = x / 3 * 3 + y / 3;
            if(row[x][i]  col[y][i]  grid[k][i])
                continue;
            row[x][i] = col[y][i] = grid[k][i] = true;
            board[x][y] = i + '1';
            if(dfs(cur + 1, board, row, col, grid)) 
                return true;
            board[x][y] = '.';
            row[x][i] = col[y][i] = grid[k][i] = false;
        }
        return false;
    }
    
public:
    void solveSudoku(vector<vector<char>>& board) {
        bool row[9][9] = {false}, col[9][9] = {false}, grid[9][9] = {false};
        for(int i = 0; i < 9; ++i){
            for(int j = 0; j < 9; ++j){
                if(board[i][j] == '.') continue;
                int t = board[i][j] - '1', k = i / 3 * 3 + j / 3;
                row[i][t] = col[j][t] = grid[k][t] = true;
            }
        }
        dfs(0, board, row, col, grid);
    }
};

Python

class Solution(object):
    def dfs(self, cur, board, vis_row, vis_col, vis_sub_box):
        if cur == 81: return True
        x, y = cur // 9, cur % 9
        if board[x][y] != '.':
            return self.dfs(cur + 1, board, vis_row, vis_col, vis_sub_box)

        for k in range(9):
            sub_index = x // 3 * 3 + y // 3
            if vis_row[x][k] or vis_col[y][k] or vis_sub_box[sub_index][k]:
                continue

            vis_row[x][k] = vis_col[y][k] = vis_sub_box[sub_index][k] = True
            board[x][y] = chr(k + ord('1'))

            if self.dfs(cur + 1, board, vis_row, vis_col, vis_sub_box):
                return True

            board[x][y] = '.'
            vis_row[x][k] = vis_col[y][k] = vis_sub_box[sub_index][k] = False

        return False

    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        vis_row = [[False] * 9 for _ in range(9)]
        vis_col = [[False] * 9 for _ in range(9)]
        vis_sub_box = [[False] * 9 for _ in range(9)]

        for i in range(9):
            for j in range(9):
                if board[i][j] == '.': continue
                k = ord(board[i][j]) - ord('1')
                sub_index = i // 3 * 3 + j // 3
                vis_row[i][k] = vis_col[j][k] = vis_sub_box[sub_index][k] = True
        self.dfs(0, board, vis_row, vis_col, vis_sub_box)

 

本文是leetcode如下的题解

• 36. Valid Sudoku
• 37. Sudoku Solver

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/