C 语言程序设计：八皇后问题求解

#include <stdio.h> #define N 8

int queen[N]; //存放已放置的皇后的列数

//检查皇后是否可以放在第row行col列 int check(int row, int col) { int i; for(i = 0; i < row; i++) { if(queen[i] == col || abs(row-i) == abs(col-queen[i])) { return 0; //不能放置 } } return 1; //可以放置 }

//递归求解 int solve(int row) { int i; if(row == N) { //已经放置完毕 return 1; } for(i = 0; i < N; i++) { if(queen[row] == -1 && check(row, i)) { //当前行未放置皇后且可以放置 queen[row] = i; if(solve(row+1)) { //递归求解下一行 return 1; } queen[row] = -1; //回溯 } else if(queen[row] == i && check(row, i)) { //当前行已放置皇后且可以放置 if(solve(row+1)) { //递归求解下一行 return 1; } } } return 0; //无解 }

int main() { int i, row, count = 0; char c; //初始化 for(i = 0; i < N; i++) { queen[i] = -1; } //输入已放置的皇后的行数 for(i = 0; i < N; i++) { scanf('%d%c', &row, &c); if(row != count+1) { //行数不连续，无解 printf('No Answer'); return 0; } if(c == '\n') { //输入结束 break; } if(row <= N && row >= 1) { //合法行数 queen[row-1] = i; //存放列数 count++; } else { //非法行数，无解 printf('No Answer'); return 0; } } //求解最后一个皇后的放置位置 if(solve(count)) { printf('%d', queen[N-1]+1); } else { printf('No Answer'); } return 0;