八皇后 问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯 1850年提出：在8X8格的国际象棋 上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林 的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。
#include <iostream> using namespace std; const int N = 8; int a[N] = {0}; int b[N] = {0}; int c[2*N -1] = {0}; int d[N] = {0}; int e[N] = {0}; bool check_position(int row,int col) { if(true == b[col]) { return true; } if((col >= row) && (0 == d[col-row] && 0 == c[col+row])) { return false; }else if ((col < row) && (0 == e[row-col] && 0 == c[col+row])) { return false; } return true; } void Output() { int k; for(k = 0;k < N;k++) cout << a[k] <<endl; } void eight_queen() { int i,j,k; int flag = 0; for(j = 0;j < N; j++){ for(k = flag;k < N;k++) { if(!check_position(j,k)){ a[j] = k; b[k] = true; c[k+j] = true; if(k>j) { d[k-j] = true; } else if(k<j) { e[j-k] = true; } else { d[k-j] = true; e[j-k] = true; } break; } } if(k == N){ if(j < 1) { cout << "error" <<endl; return; } flag = a[j-1] + 1; b[a[j-1]] = false; c[a[j-1]+j-1] = false; if(a[j-1] > (j-1)) { d[a[j-1]-(j-1)] = false; } else if(a[j-1] < (j-1)) { e[(j-1)- a[j-1]] = false; }else { d[a[j-1]-(j-1)] = false; e[(j-1)- a[j-1]] = false; } a[j-1] = false; j = j - 2; } else { flag = 0; } } Output(); } int main(int argc,char *argv[]) { eight_queen(); return 0; }
#include <stdio.h> #include <stdlib.h> #define MAX 8 /*MAX为棋盘最大坐标*/ int queen[MAX];
/*输出所有皇后的坐标*/ void printqueen() { int i; for(i=0;i<MAX;i++) { printf("<%d,%d>,",i,queen[i]); } printf("/n"); }
/*检查当前列能否放置皇后*/ int check(int n) { int i; for(i=0;i<n;i++) { if(queen[n] == queen[i] || abs(queen[n]-queen[i]) == (n-i)) { return 0; } }
return 1; }
/*回溯尝试皇后位置，n为横坐标*/ void put(int n) { int j; for(j=0;j<MAX;j++) { queen[n] = j; if(check(n)) { if(n==MAX-1) { /*如果全部摆好，则输出所有皇后的坐标*/ printqueen(); } else { /*否则继续摆放下一个皇后*/ put(n+1); } } } }
int main(int argc,char**argv) { put(0); return 0; }
