八皇后是一道很具典型性的题目。它的基本要求是这样的:在一个8*8的矩阵上面放置8个物体,一个矩阵点只允许放置一个物体,任意两个点不能在一行上,也不能在一列上,不能在一条左斜线上,当然也不能在一条右斜线上。
算法思路:
(1)在第n行探测某列(从0开始)是否可以放置皇后
(2)如果没有可以位置可以放置皇后,返回探测其他列是否可以放置(遍历0~7列)
(3)如果可以放置皇后。此时再判断是否已经是最后一行,如果是,打印输结果;
反之继续对下一行进行探测 row+1
(4) 0~7列探测完后,回溯到上一行row-1,即回到(1)
如果棋盘为3X3,思路如下图所示:
#include <stdio.h> #include <math.h> #include <stdlib.h> #include <stdbool.h> #define N 8 int a[N]; //a[i]为第i行皇后所在列 void show_answers() { static num = 0; int i =0, j = 0; printf("the %d answers:\n", ++num); for(i=0; i<N; i++) { for(j=0; j<N; j++) { if(a[i] == j) printf("1 "); else printf("0 "); } printf("\n"); } } //函数实现的前提在于之前所有点的位置都已经保存了 //注意随着递归返回,位置也会随之改变,好好理解这种妙处 bool check_pos(int rows) { bool ret = true; int i = 0; for(i=0; i<rows; i++) { if(a[i] == a[rows] || fabs(rows - i) == fabs(a[rows] - a[i])) { ret = false; break; } } return ret; } void eight_queens(int rows) { int cols = 0; for(cols=0; cols<N; cols++) { a[rows] = cols; if(check_pos(rows)) { if(rows == N-1) show_answers(); else eight_queens(rows+1); }//不合法则探测下一列 }//所有列探测完后返回上一行,即回溯,相对来讲rows-1 } int main (void) { eight_queens(0); return 0; }