09. C Pro 深度算法求解八皇后问题

本文主要是介绍09. C Pro 深度算法求解八皇后问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

有时候真的感概，撸码并Debug一天，搞得自己头昏脑胀，结果第二天才发现，原来两行代码的执行顺序错了 -_-!

方法一、二维数组

#define N 8
int a[N][N] = { 0 };
int count = 0;

int abs(int x, int y) {
　　return x >= y ? (x - y) : (y - x);
}
void dps(int x){
　　if (x == N ) {
　　　　count++;
　　　　printf("\n方案%d：\n",count);
　　　　for (int i = 0; i < N; i++) {
　　　　　　for (int j = 0; j < N; j++) 
　　　　　　　　printf("%d\t", a[i][j]==1?a[i][j]:0);
　　　　　　printf("\n");
　　　　}
　　　　return;
　　}

　　for (int k = 0; k < N; k++) {
　　　　if (a[x][k] == 0) {
　　　　　　for (int i = 0; i < N; i++) {
　　　　　　　　for (int j = 0; j < N; j++) {
　　　　　　　　　　a[x][j] -= 1;
　　　　　　　　　　a[i][k] -= 1;
　　　　　　　　　　if (abs(x, i) == abs(j, k)) a[i][j] -= 1;
　　　　　　　　}
　　　　　　}
　　　　　　a[x][k] = 1;
　　　　　　dps(x + 1);
　　　　　　for (int i = 0; i < N; i++) {
　　　　　　　　for (int j = 0; j < N; j++) {
　　　　　　　　　　a[x][j] += 1;
　　　　　　　　　　a[i][k] += 1;
　　　　　　　　　　if (abs(x, i) == abs(j, k)) a[i][j] += 1;
　　　　　　　　}
　　　　　　}
　　　　　　a[x][k] = 0;
　　　　}
　　}

　　return;
}

int main() {
　　dps(0);
　　getchar(); return 0;
}

方法二、一维数组，place函数暂时没看懂

int solution[N], j, k, count, sols;
int place(int row, int col) {
　　for (j = 0; j < row; j++) {
　　　　if (row - j == solution[row] - solution[j] || row + solution[row] == j + solution[j] || solution[j] == solution[row])
　　　　return 0;
　　}
　　return 1;
}

void backtrack(int row) {
　　count++;
　　if (N == row) {
　　　　sols++;
　　　　for (k = 0; k < N; k++)
　　　　　　printf("%d\t", solution[k]);
　　　　printf("\n\n");
　　}
　　else {
　　　　for (int i = 0; i < N; i++) {
　　　　　　solution[row] = i;
　　　　　　if (place(row, i)) backtrack(row + 1);
　　　　}
　　}
}

void queens() {
　　backtrack(0);
}

int main() {
　　queens();
　　printf("The total solutions : %d\n", sols);
　　getchar(); return 0;
}

这篇关于09. C Pro 深度算法求解八皇后问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！