（0）预备知识
C语言复习---二维数组和二级指针的关系：没关系，别瞎想（重点）
（一）问题描述
要在8*8的国际象棋棋盘中放8个皇后，使任意两个皇后都不能互相吃掉。规则是皇后能吃掉同一行、同一列、同一对角线的棋子。如下图即是两种方案：
（二）递归代码实现
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #define ERROR 0 #define OK 1 typedef int Status; int count = 0; /* int *chess[8] 代表棋盘，chess代表每一行指针 int row是当前行 int col是当前列 上面确定了一个位置 */ Status noDanger(int(*chess)[8], int row, int col) { int i = 0; int r, c; //先判断当前列 for (i = 0; i < 8; i++) if (chess[i][col] != 0) return ERROR; //再将当前行设置为-1 for (i = 0; i < 8; i++) if (chess[row][i] != 0) return ERROR; //再将斜行列设置为-1，分为4个方向， //左上：行列减一， r = row; c = col; while (r >= 0 && c >= 0) { if (chess[r][c] != 0) return ERROR; r--; c--; } //右上：行减一列加一， r = row; c = col; while (r >= 0 && c < 8) { if (chess[r][c] != 0) return ERROR; r--; c++; } //左下：行加一列减一， r = row; c = col; while (r < 8 && c >= 0) { if (chess[r][c] != 0) return ERROR; r++; c--; } //右下：行加一列加一， r = row; c = col; while (r < 8 && c < 8) { if (chess[r][c] != 0) return ERROR; r++; c++; } return OK; } /* int *chess[8] 代表棋盘，chess代表每一行指针 int row是当前行 int col是当前总列数 */ void EightQueen(int(*chess)[8], int row, int cols) { int chess2[8][8]; int i, j; for (i = 0; i < 8;i++) for (j = 0; j < 8;j++) chess2[i][j] = chess[i][j]; //row==8是递归结束条件 if (row==8) //从0-7就判断完毕，到第九行是不存在的，说明已经找到所有的位置，可以打印了 { printf("the number of %d ways ", count + 1); for (i = 0; i < 8;i++) { for (j = 0; j < 8; j++) printf("%d ", *(*(chess2 + i) + j)); printf(" "); } printf(" "); count++; //获取的正确方案加一 } else { //判断当前行的每一列是否有效 for (j=0;j<cols;j++) { if (noDanger(chess, row, j)) //若是这个位置不危险，可以存放皇后 { for (i = 0; i < 8;i++) { *(*(chess2 + row) + i) = 0; //将这一行设为0 } *(*(chess2 + row) + j) = 9; //当前存放皇后的位置设置为9 //进行递归,继续向下 EightQueen(chess2, row + 1, cols); } } } } int main() { int chess[8][8] = { 0 }; EightQueen(chess, 0, 8); printf("end "); system("pause"); return 0; }
递归函数EightQueen
void EightQueen(int(*chess)[8], int row, int cols) { int chess2[8][8]; //由于可以走到的方案太多，我们最好使用一个临时变量去存储原来棋盘位置，不然每次保存现场也是释放消耗时间空间的 int i, j; for (i = 0; i < 8;i++) for (j = 0; j < 8;j++) chess2[i][j] = chess[i][j]; //row==8是递归结束条件 if (row==8) //从0-7就判断完毕，到第九行是不存在的，说明已经找到所有的位置，可以打印了 { printf("the number of %d ways ", count + 1); for (i = 0; i < 8;i++) { for (j = 0; j < 8; j++) printf("%d ", *(*(chess2 + i) + j)); printf(" "); } printf(" "); count++; //获取的正确方案加一 } else { //判断当前行的每一列是否有效 for (j=0;j<cols;j++) //我们在参数中，获取了应该操作的行数，现在我们应该对列进行循环，判断该行中列的正确与否 { if (noDanger(chess, row, j)) //若是这个位置不危险，可以存放皇后 //虽然我们大多使用的是临时棋盘chess2,但在这里我们需要使用到参数传递过来的上级棋盘，因为我们在判断合法位置后，会修改临时棋盘，导致临时棋盘该位置被填充，变为不合法。不会再进入循环 { for (i = 0; i < 8;i++) { *(*(chess2 + row) + i) = 0; //将这一行设为0 //我们在这里修改了临时棋盘，所以我们在上面判断位置合法性，不要使用临时棋盘，而是使用上级棋盘chess } *(*(chess2 + row) + j) = 9; //当前存放皇后的位置设置为9 //进行递归,继续向下 EightQueen(chess2, row + 1, cols); //继续递归，传入临时棋盘 } } } }
位置合法性noDanger
我们需要对该位置的行，列，斜行列进行判断，其中斜线上我们需要判断左上，右上，左下，右下四个方向
Status noDanger(int(*chess)[8], int row, int col) { int i = 0; int r, c; //先判断当前列 for (i = 0; i < 8; i++) if (chess[i][col] != 0) return ERROR; //再将当前行设置为-1 for (i = 0; i < 8; i++) if (chess[row][i] != 0) return ERROR; //再将斜行列设置为-1，分为4个方向， //左上：行列减一， r = row; c = col; while (r >= 0 && c >= 0) { if (chess[r][c] != 0) return ERROR; r--; c--; } //右上：行减一列加一， r = row; c = col; while (r >= 0 && c < 8) { if (chess[r][c] != 0) return ERROR; r--; c++; } //左下：行加一列减一， r = row; c = col; while (r < 8 && c >= 0) { if (chess[r][c] != 0) return ERROR; r++; c--; } //右下：行加一列加一， r = row; c = col; while (r < 8 && c < 8) { if (chess[r][c] != 0) return ERROR; r++; c++; } return OK; }
