八皇后问题

虽然八皇后问题很早就知道，但是也没有自己实现过，上周用C实现了一下，发现有很多算法还可以进一步优化的。

基本的思路是这样：
1，创建一个长度为8的数组（queens），每一项表示棋盘上每一行皇后在的位置（0-7）。-1表示还没有开始算这一行，或这一行找不到可以放置皇后的位置；
2，先将第一行的第一个位置放上皇后（queens[0] = 0），然后依次寻找下一行可以放置的位置；
3，如果找不到位置，则返回上一行寻找下一个可用的位置；
4，如果已经找到最后一行，则输出当前的布局，然后再返回上一行寻找下一个可以用的位置；
5，如果已经回到第一行，没有找到下一个可以用的位置，程序退出。

一共找到92个。和问题的标准答案吻合。

最粗糙的第一版代码附上：

[code lang="c"]
#include
#include

#define LINE 8

void printChess(int *queens);
int checkLine(int *queens, int checkLine);

int
main(void)
{
int queens[] = {0, -1, -1, -1, -1, -1, -1, -1};
int thisLine = 1;
while(1)
{
queens[thisLine] = checkLine(queens, thisLine);
if(queens[thisLine] == -1)
{
thisLine -= 1;
if(thisLine < 0)
{
break;
}
}
else if(thisLine == (LINE - 1))
{
printChess(queens);
queens[thisLine] = -1;
thisLine -= 1;
}
else
{
thisLine += 1;
}
}
return EXIT_SUCCESS;
}

int
checkLine(int *queens, int checkLine)
{
int i;
int startNum = *(queens + checkLine);
for(i = startNum + 1 ; i < LINE ; i += 1)
{
int getValue = 0;
int targetLine = checkLine;
while(--targetLine >= 0)
{
int step = checkLine - targetLine;
int target = *(queens + targetLine);
if((target == i) || (target == i - step) || (target == i + step))
{
break;
}
else
{
getValue += 1;
}
}
if(getValue == checkLine)
{
return i;
}
}
return -1;
}

void
printChess(int *queens)
{
static int count = 0;
printf("nOutput %d:n", ++count);

int i, j;
for(i = 0 ; i < LINE ; i += 1)
{
for(j = 0 ; j < LINE ; j += 1)
{
printf("%c ", (j == queens[i] ? 'Q' : '*'));
}
printf("%s", "n");
}
}
[/code]