回溯算法

八皇后问题

解题思路：

程序实现：

#include <iostream>
#include <string>
using namespace std;

int Place(int c[], int k) {
	for (int i = 0; i < k; i++) {
		if (c[k] == c[i] || abs(c[i] - c[k]) == abs(i - k)) {
			return 1;
		}
	}
	return 0;
}

void Queen(int c[], int n) {
	int k = 0;
	while (k >= 0) {
		++c[k];
    //若不满足要求就列加1
		while (c[k] < n&&Place(c, k)) {
			++c[k];
		}
		//完成
		if (c[k] < n&&k == n - 1) {
			for (int i = 0; i < n; i++) {
				cout << c[i] + 1 << " ";
			}
			cout << "\n";
		}
		//还有未摆放皇后的行
		else if (c[k] < n&&k < n - 1) {
			++k;
		}
		//都尝试摆放了但都没完成
		else {
			cout << k <<" "<< c[k] << " 回溯" << endl;
			//重置c[k]然后回溯
			c[k--] = -1;
		}
	}
}

int main() {
	int c[5];
	int n = 5;
	for (int i = 0; i < n; i++) {
		c[i] = -1;
	}
	Queen(c, n);
	system("pause");
}

2 4 回溯
3 4 回溯
2 4 回溯
1 4 回溯
2 4 1 3
3 4 回溯
2 4 回溯
1 4 回溯
3 1 4 2
3 4 回溯
2 4 回溯
1 4 回溯
3 4 回溯
2 4 回溯
2 4 回溯
1 4 回溯
0 4 回溯

k和c[k]分别代表第k行和第c[k]列

图着色问题

时间复杂度：
O(mn)，m为颜色数；n为结点数

哈密顿回路问题