N皇后问题(搜索C语言版)
用数组int x[N]表示棋盘状态,例如x[0]=1表示第0行皇后放在第1列。
皇后k在第k行第x[k]列:(k,x[k])
测试方法:测试皇后k在第k行第x[k]列时,是否与前面已放置好的皇后j相攻击。
x[j]== x[k] 时,两皇后在同一列上;
abs(k-j)==abs(x[j]-x[k]) 时,两皇后在同一斜线上。
两种情况两皇后都可相互攻击
#include <stdio.h>
#define N 4
int x[N], sols;
/* 放置皇后到位置(row,col),若成功返回1,失败返回0 */
int place(int row)
{
int j;
for (j=0;j<row;j++) /* j代表行 */
{
if(row-x[row]==j-x[j]||row+x[row]==j+x[j]||x[j]==x[row])
return 0;
}
return 1;
}
void backtrack(int row)
{ int k;
if ( N == row )
{ sols++; // 解的结果加1
for( k=0 ; k<N ; k++ )
printf("(%d,%d) ", x[k]+1,k+1);
printf("\n");
}
else
{ int i;
for( i=0 ; i<N ; i++ )
{
x[row] = i;
if( place(row) )
backtrack(row + 1);
}
}
}
int main( )
{
backtrack(0);
printf("Total Solutions: %d\n", sols);
return 0;
}
代码中是4皇后,运行结果: