51. N 皇后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
vector<string> path; //某一种解法
vector< vector<string>> ans;//解法集合
//额外加2列
int board[11][11] = {0}; //放棋子的位置是 1~9 0 和 10是边界，永远是0
int boardCol[11] = {0};
string defaultString;//默认的每一行的字符串，将在回溯前初始化
//回溯三部曲
//1.确认返回类型以及参数
void backtracing(int n, int row)
{
//2.终止条件,当行数大于n时，说明n个棋子已经放完了
if(row == n + 1)
{
ans.emplace_back(path);
return;
}
//每次回溯的遍历过程
for(int column = 1; column <= n; column++)
{
//先判断这一列有没有棋子
if(boardCol[column] == 1) continue;
//判断会不会和上面的棋子同一斜线
int curRow = row ;//记录上面的行
int colLeft = column - 1;//记录左斜线的列号
int colRight = column + 1;//记录右斜线的列号
while(curRow--)
{
//如果左上方有棋子
if( colLeft > 0 && board[curRow][colLeft] == 1) break;
//如果右上方有棋子
if( colRight <= n && board[curRow][colRight] == 1) break;
//如果当前行没有冲突的棋子
colLeft--;
colRight++;
}
//如果当前行没有减到0，说明在之前有冲突的棋子，提前退出了，那么继续
if(curRow > 0) continue;
//此时这个row column是安全的，可以放置
board[row][column] = 1;//该位置标记
boardCol[column] = 1;//该行标记
string s = defaultString;
s[column - 1] = 'Q';
path.emplace_back(s);
backtracing(n, row + 1);//放下一行的棋子
board[row][column] = 0;//回溯完了，要把棋子收回
boardCol[column] = 0;
path.pop_back();
}
}
vector<vector<string>> solveNQueens(int n) {
for(int i = 0; i < n; i++)
{
defaultString += ".";
}
backtracing(n, 1);
return ans;
}
};
约束条件
同行不能有，所以是按行回溯
同列不能有，使用全局数组int boardCol[11]来判断
同一斜线不能有，这个比较麻烦，需要用循环，判断之前每一行有没有
注意
判断斜线的时候，我用的是while(curRow–)，这个过程中出现了很多问题，debug之后发现，while语句，无论curRow是否大于0，只要执行while(curRow–)这一行代码，curRow就会-1，所以初始化时，要初始化为row，这样的话while(curRow–)正好curRow就是上一行。而且在最后判断斜线上到底有无时，if(curRow > 0) 要>0不能==0，因为如果没有冲突，最后是-1.
在记录棋盘每一行的字符串时，需要一个默认的字符串defaultString，全是”.”，在每次放棋子时，再新建一个s来=defaultString，不然的话，直接用defaultString，Q会填满默认字符串变成“QQQQ”
37. 解数独
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
public:
//二维回溯 回溯三部曲
//1.确认返回类型，参数
//使用bool是因为只有一个答案，一旦发现一个答案，就返回true，不再继续回溯了
//在回溯的过程中修改board
bool backtracing(vector<vector<char>>& board)
{
//2.中止条件直接就是遍历过程，23究极合体
for(int row = 0; row < 9; row++)
{
for(int col = 0; col < 9; col++)
{
//来判断是不是可以填数，是点的话就可以填
if(board[row][col] == '.')
{
//来判断填哪个
for(int i = 1; i <= 9; i++)
{
if(isValid(row, col, i, board))//如果这个位置填这个i是合理的
{
//填上这个数
board[row][col] = i + '0';
//去回溯,遇到true了，直接返回
if(backtracing(board)) return true;
board[row][col] = '.';
}
}
//如果9个数遍历完了，都不能填，那么返回false
return false;
}
}
}
//所有格子都填满了
return true;
}
bool isValid(int row, int col, int val, vector<vector<char>>& board)
{
//判断行
for(int j = 0; j < 9; j++)
{
if(board[row][j] == val + '0') return false;
}
//判断列
for(int i = 0; i < 9; i++)
{
if(board[i][col] == val + '0') return false;
}
//判断9宫格
row = (row / 3) * 3;
col = (col / 3) * 3;
for(int i = row; i < row + 3; i++)
{
for(int j = col; j < col + 3; j++)
{
if(board[i][j] == val + '0') return false;
}
}
//判断下来，都没冲突的话就返回true
return true;
}
void solveSudoku(vector<vector<char>>& board) {
backtracing(board);
}
};
这个题目感觉挺暴力的，就一个一个挨个查，这次回溯三部曲的2和3合体了，直接在遍历的过程中来判断是否该中止
至此，回溯章节的题目终于刷完啦~
明天就要开坑贪心算法喽~