回溯八皇后问题，递归：
#include <stdio.h>
#include <stdlib.h>
#define max 8
int queen[max], sum=0; /* max为棋盘最大坐标 */
void show() /* 输出所有皇后的坐标 */
{
int i;
for(i = 0; i < max; i++)
{
printf((%d,%d) , i, queen[i]);
}
printf(\n);
sum++;
}
int check(int n) /* 检查当前列能否放置皇后 */
{
int i;
for(i = 0; i < n; i++) /* 检查横排和对角线上是否可以放置皇后 */
{
if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i))
{
return 1;
}
}
return 0;
}
void put(int n) /* 回溯尝试皇后位置,n为横坐标 */
{
int i;
for(i = 0; i < max; i++)
{
queen[n] = i; /* 将皇后摆到当前循环到的位置 */
if(!check(n))
{
if(n == max - 1)
{
show(); /* 如果全部摆好，则输出所有皇后的坐标 */
}
else
{
put(n + 1); /* 否则继续摆放下一个皇后 */
}
}
}
}
int main()
{
put(0); /* 从横坐标为0开始依次尝试 */
printf(%d, sum);
system(pause);
return 0;
}
非递归：#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 8
int column[N];
int chessboard[N][N]; // 棋盘数组
int layout_count; // 可行解个数统计
int place(int row);
void output(void);
void init_chessboard(void);
void display_chessboard(void);
/**
*初始化column数组
*/
void init(void) {
int i;
for(i=0; i<N; i++) {
column[i] = 0;
}
}
/**
*非递归回溯算法求n-皇后问题的函数
*/
void n_queens() {
init(); // 初始化column数组
column[0] = -1;
int row = 0;
while(row >= 0) {
column[row]++;
while(!place(row)) {
column[row]++;
}
if(column[row] < N) {
if(row == N-1) {
layout_count++;
output();
}
else {
row++;
column[row] = -1;
}
}
else {
row--;
}
}
}
/**
*判断第row行的皇后是否满足问题要求
*/
int place(int row) {
int i = 0;
while(i < row) {
if(column[i] == column[row]
|| abs(i-row) == abs(column[i]-column[row])) {
return 0;
}
i++;
}
return 1;
}
/**
*求解过程中，如果找到一个可行解，调用该函数打印输出可行解及其对应的可行棋盘布局
*/
void output(void) {
int i;
for(i=0; i<N; i++) {
printf(%3d, column[i]);
}
printf(\n\n);
display_chessboard(); // 根据一种可行解，打印显示可行棋盘布局
}
/**
*打印显示一种棋盘布局
*/
void display_chessboard(void) {
int i,j;
init_chessboard();
for(i=0; i<N; i++) {
chessboard[i][column[i]] = 1; // 将放置皇后的位置置1
}
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
printf(%3d, chessboard[i][j]);
}
printf(\n);
}
printf(\n);
}
/**
*棋盘恢复到初始状态
*将数组chessboard初始化为0
*/
void init_chessboard(void) {
int i,j;
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
chessboard[i][j] = 0;
}
}
}
int main() {
n_queens();
printf(\n%d\n, layout_count);
return 0;
}
