八皇后

#include "stdio.h"
#include "stdlib.h"

#define QUEEN_COUNT 8

int resolve = 0;
int *queen;			/*记录每个皇后放置的列数,queen[0]=5表示第0个皇后放置在5列*/

void print_queen(int *queen)
{
	int i = 0;
	int j = 0;
	
	printf("----------------\n");
	for (int i = 0; i < QUEEN_COUNT; i++)
	{
		for (int j = 0; j < QUEEN_COUNT; j++)
		{
			if (queen[i] == j)
			{
				printf("1 ");
			}
			else
			{
				printf("0 ");
			}
		}
		printf("\n");
	}
}

/* 放置第q个皇后 */
/*
迭代流程(以5皇后为例)：
放置第0个皇后
	放置第1个皇后
		放置第2个皇后
			放置第3个皇后
				放置第4个皇后(成功++)
			放置第3个皇后(一直失败)
		放置第2个皇后(失败)
	放置第1个皇后
		放置第2个皇后
			放置第3个皇后
				放置第4个皇后(成功++)
......

*/
int place(int q)
{
	int i = 0;	/* 试探列 */
	int j = 0;	/* 已经放置皇后的列 */
	int k = 0;	/* 对已经放置皇后探测的游标 */
	int valid = 0;	/* 位置是否合法 */


	for (i = 0; i < QUEEN_COUNT; i++)
	{
		printf("place queen %d %d ", q, i);
		queen[q] = i;	/* 第q个皇后放在第i列,皇后下标也表示第几行 */
		valid = 1;

		/* 检测放置位置是否合法，同一行(每一行新放置,不会出现在同行)、同一列、斜对角上没有其他皇后 */
		for (k = 0; k < q; k++)
		{
			if (queen[k] == queen[q] ||				/* 第k个皇后已经放在了当前试探列上 */
				(queen[q] - queen[k]) == (q - k) ||	/* 第k个皇后放在了试探列的左斜对角 */
				(queen[k] - queen[q]) == (q - k))	/* 第k个皇后放在了试探列的右斜对角 */
			{
				valid = 0;
			}
		}

		if (valid)	/* 第q个皇后可以放在第i个位置 */
		{
			printf("success\n");
			if (q == QUEEN_COUNT - 1)	/* 已经成功放置了第q个皇后 */
			{
				resolve++;
				print_queen(queen);
				return 0;
			}
			place(q + 1);
			//每次放置最后一个皇后成功,返回0,在上一次迭代的返回点,将第q个皇后放到下一个位置i+1
		}
		else
		{
			printf("failed\n");
			//每次放置失败返回点,将第q个皇后放到下一个位置i+1
		}
	}
}

int main()
{
	queen = malloc(sizeof(int) * QUEEN_COUNT);

	place(0);	/* 从第0个(行数)皇后开始放置 */
	printf("%d\r\n", resolve);

	free(queen);

    return 0;
}