[分享]经典问题——八皇后问题
偶然看到这个经典问题的经典解决方法。
//本方法采用回溯方法,通过函数put_chess()对自身的递归来实现。递归深度为7
#include <math.h>
#include <stdio.h>
#define MAX 8
int board[MAX]; //皇后坐标数组,MAX为行数,board[MAX]为列数
int sum=0;
void show_result();
int check_cross(int n);
void put_chess(int n);
main()
{
put_chess(0);
printf("%d",sum);
getch();
return;
}
void show_result()
{
int i;
for(i=0;i<MAX;i++)
printf("(%d,%d)",i,board[i]);
printf("\n");
sum++;
}
int check_cross(int n)
{
int i;
for(i=0;i<n;i++)
{
if(board[i]==board[n]||(n-i)==abs(board[i]-board[n]))
return 1;
}
return 0;
}
void put_chess(int n)
{
int i;
for(i=0;i<MAX;i++)
{
board[n]=i;
if(!check_cross(n))
{
if(n==MAX-1)
show_result();
else
put_chess(n+1);
}
}
}
//共92种结果