37.解数独
编写一个程序，通过填充空格来解决数独问题。数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。示例 1：
输入：board = [
[“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”]
]
输出：[
[“5”,”3”,”4”,”6”,”7”,”8”,”9”,”1”,”2”],
[“6”,”7”,”2”,”1”,”9”,”5”,”3”,”4”,”8”],
[“1”,”9”,”8”,”3”,”4”,”2”,”5”,”6”,”7”],
[“8”,”5”,”9”,”7”,”6”,”1”,”4”,”2”,”3”],
[“4”,”2”,”6”,”8”,”5”,”3”,”7”,”9”,”1”],
[“7”,”1”,”3”,”9”,”2”,”4”,”8”,”5”,”6”],
[“9”,”6”,”1”,”5”,”3”,”7”,”2”,”8”,”4”],
[“2”,”8”,”7”,”4”,”1”,”9”,”6”,”3”,”5”],
[“3”,”4”,”5”,”2”,”8”,”6”,”1”,”7”,”9”]
] 解释：输入的数独如上图所示，唯一有效的解决方案如所示：
分析:
1.对每个位置进行穷举放置操作, 并回溯操作, 直到满足判断条件
2.判断每个位置是否能放入, 需要同时满足满足数独的三个条件, 同行同列的比较容易判断是否有重复
3.对于判断九宫格里面是否有重复, 假设我们当前的位置是 (i,j), 我们首先要找到当前存在在哪个九宫格里面, 也就是需要找到当前所处于的九宫格的左上角的坐标, 所有左上角的横坐标是 (0,3,6) 集合, 所有左上角的纵坐标是 (0,3,6) 集合
假设当前位置是 (1,4), 它的左上角是 (0,3), 大九宫格是 (0,1), 可以对横坐标/3 找到处于是大九宫格的哪一行, 纵坐标/3找到处于大九宫格的哪一列; 然后再对大九宫格的坐标乘以3得到它的左上角(0,3)
4.因此对于 (i,j) 来说, 左上角的坐标为 (i / 3 3, j / 3 3)
5.dfs 有个需要处理的地方是, 需要手动确认递归结束的条件是完成了数独的状态, 结束递归, 不然搜索会跳出不来; 一种避免手去更改递归状态的方法, 最好将 dfs 设计成带 bool 返回值标记是否找到结果
// 改写 dfs 为 bool 返回值标记是否找到了可行解的写法
class Solution {
public:
bool check(int i, int j, vector<vector<char>>& board) {
for (int r = 0; r < 9; ++r) {
if (i != r && board[i][j] == board[r][j]) {
return false;
}
}
for (int c = 0; c < 9; ++c) {
if (j != c && board[i][j] == board[i][c]) {
return false;
}
}
int startRow = (i / 3) * 3;
int startCol = (j / 3) * 3;
for (int r = startRow; r < startRow+3; ++r) {
for (int c = startCol; c < startCol+3; ++c) {
if ((i != r || j != c) && board[i][j] == board[r][c])
return false;
}
}
return true;
}
bool dfs(int r, int c, vector<vector<char>>& board) {
if (r >= 9) {
return true;
}
if (c >= 9) {
return dfs(r+1, 0, board);
}
if (board[r][c] == '.') {
for (int i = 1; i <= 9; ++i) {
board[r][c] = (char) (i + '0');
if (check(r, c, board)) {
if (dfs(r, c+1, board)) {
return true;
}
}
board[r][c] = '.';
}
} else {
return dfs(r, c+1, board);
}
return false;
}
void solveSudoku(vector<vector<char>>& board) {
if (board.empty() || board[0].empty())
return;
dfs(0, 0, board);
return;
}
};
原始 void 返回值的写法: 需要增加 finished 标签
// 原始 void 返回值的写法: 需要增加finished标签
class Solution {
public:
bool finished = false;
bool check(int i, int j, vector<vector<char>>& board) {
for (int r = 0; r < 9; ++r) {
if (i != r && board[i][j] == board[r][j]) {
return false;
}
}
for (int c = 0; c < 9; ++c) {
if (j != c && board[i][j] == board[i][c]) {
return false;
}
}
int startRow = (i / 3) * 3;
int startCol = (j / 3) * 3;
for (int r = startRow; r < startRow+3; ++r) {
for (int c = startCol; c < startCol+3; ++c) {
if ((i != r || j != c) && board[i][j] == board[r][c])
return false;
}
}
return true;
}
void dfs(int r, int c, vector<vector<char>>& board) {
if (r >= 9) {
finished = true;
return;
}
if (c >= 9) {
dfs(r+1, 0, board);
return;
}
if (board[r][c] == '.') {
for (int i = 1; i <= 9; ++i) {
board[r][c] = (char) (i + '0');
if (check(r, c, board)) {
dfs(r, c+1, board);
if (finished)
return;
}
board[r][c] = '.';
}
} else {
dfs(r, c+1, board);
}
return;
}
void solveSudoku(vector<vector<char>>& board) {
if (board.empty() || board[0].empty())
return;
dfs(0, 0, board);
return;
}
};
51.N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例 1：输入：n = 4 输出：[
[“.Q..”,”…Q”,”Q…”,”..Q.”],
[“..Q.”,”Q…”,”…Q”,”.Q..”]
] 解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：输入：n = 1 输出：[
[“Q”]
]
分析:
1.初始化一个默认的棋盘, 因为根据规则, 每行至多放 1 个皇后, 所以在 dfs 放置的时候, 对 [行] 这个维度进行 dfs(row), 放完了直接进入下一行; dfs(row) 的内部, 对所有的列的位置 (row, col) 进行模拟放置并回溯
2.放置的时候, 需要检查放置的位置 [i,j] 是满足合法性的, 因此需要在放置之前先检查放置是合法的, 写一个 checkLegality()
3.checkLegality() 需要依次检查面的行之前不能放过, 左上方之前不能放过, 右上方之前不能放过
class Solution {
private:
vector<vector<string>> ans;
public:
bool checkLegality(int r, int c, int n, vector<string>& board) {
// 上面的行之前不能放过
for (int i = 0; i < r; ++i) {
if (board[i][c] == 'Q') {
return false;
}
}
// 左上方之前不能放过
for (int i = r-1, j = c-1; i >= 0 && j >= 0; --i, --j) {
if (board[i][j] == 'Q') {
return false;
}
}
// 右上方之前不能放过
for (int i = r-1, j = c+1; i >= 0 && j < n; --i, ++j) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
void dfs(int row, int n, vector<string>& board) {
if (row == n) {
ans.push_back(board);
return;
}
for (int col = 0; col < n; ++col) {
if (checkLegality(row, col, n, board)) {
board[row][col] = 'Q';
dfs(row+1, n, board);
board[row][col] = '.';
}
}
return;
}
vector<vector<string>> solveNQueens(int n) {
vector<string> board(n, string(n, '.'));
dfs(0, n, board);
return ans;
}
};
52.N皇后II
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。示例 1：输入：n = 4 输出：2 解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：输入：n = 1 输出：1
分析:
1.基于皇后 dfs 回溯方法, 我们得到了 N 皇后的数量.
class Solution {
private:
vector<vector<string>> res;
int count = 0;
public:
bool isValid(int row, int col, int n, vector<string>& board) {
for (int i = 0; i < row; ++i) {
if (board[i][col] == 'Q') {
return false;
}
}
for (int i = row-1, j = col-1; i >= 0 && j >= 0; --i, --j) {
if (board[i][j] == 'Q') {
return false;
}
}
for (int i = row-1, j = col+1; i >= 0 && j < n; --i, ++j) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
void backtracking(int row, int n, vector<string>& board) {
if (row == n) {
++count;
return;
}
for (int col = 0; col < n; ++col) {
if (isValid(row, col, n, board)) {
board[row][col] = 'Q';
backtracking(row+1, n, board);
board[row][col] = '.';
}
}
return;
}
int totalNQueens(int n) {
vector<string> board(n, string(n, '.'));
backtracking(0, n, board);
return count;
}
};
转载请注明来源, from goldandrabbit.github.io
