/*
	Name: n皇后问题 
	Copyright: 
	Author: 巧若拙 
	Date: 24-12-14 22:04
	Description: 
	采用非递归的回溯法解决n皇后问题，为了减少计算，采用了输出对称图形的方法，这样时间可以节省一半。
	亮点是图像的输出，来自《C/C++算法手册》，很漂亮。 
*/
#include<stdio.h>
#include<stdlib.h>

#define MAX 50

int board[MAX] = {0};
long long count = 0;

void Queens(int n);//求解n皇后问题的驱动函数 
void SubQueens(int row, int n);//求解n皇后问题的子函数 
void PrintBoard(int board[], int n);
int Place(int row);
void Symmetry(int board[], int n);//输出对称解 

int main(void)
{
	int n = 6;

	printf("%d 皇后\n", n);
	Queens(n); 
	
    return 0;
}

void Queens(int n)//求解n皇后问题的驱动函数 
{
	SubQueens(0, n);
	if (n % 2 == 1)
	{
		board[0] = n / 2;
		SubQueens(1, n);
	}
}

void SubQueens(int row, int n)//求解n皇后问题的子函数 
{
	int i, top = row;
	
	for (i=0; i<n/2; i++)
	{
		board[row] = i;
		board[++top] = -1;
		while (top > row)
		{
			board[top]++;
			if (top == n)//已经到最后一行，输出解 
			{ 
				PrintBoard(board, n);
				Symmetry(board, n);//输出对称解 
				top--;//返回上一行 
			}
			else
			{
				if (board[top] < n && Place(top))//若本行满足要求，计算下一行位置 
					board[++top] = -1;
				else if (board[top] == n)//已经尝试了本行所有位置，返回上一行 
					top--;
			}
		}
	}
}

void Symmetry(int board[], int n)//输出对称解 
{
	int temp[MAX] = {0};
	int i;
	
	for (i=0; i<n; i++)
	{
		temp[i] = n - 1 - board[i];
	}
	
	PrintBoard(temp, n);
}

int Place(int row)//判断low行皇后的位置是否可行 
{
	int i;
	
	for (i=0; i<row; i++)
	{
		if (board[i] == board[row])
			return 0;
		if (board[i] > board[row] && (row - i) == (board[i] - board[row]))
			return 0;
		if (board[i] < board[row] && (row - i) == (board[row] - board[i]))
			return 0;
	}
	return 1;
}

void PrintBoard(int board[], int n)
{
	int i, j, flag = 1;
	
	printf("方案%d：\n", ++count);
	printf("  ");
	for (i=0; i<n; i++)
		printf("__");
	printf("\n");	
	
	for (i=0; i<n; i++)
	{
		printf(" |");
		for (j=0; j<n; j++)
		{
			if (j == board[i])
			{
				printf("★");
			}
			else
			{
				if (flag < 0)
					printf("  ");
				else
					printf("■");
			} 
			flag *= -1;
		}
		printf("| \n");
		flag *= -1;
	}
	printf("  ");
	for (i=0; i<n; i++)
		printf("￣");
	printf("\n");	
}

n皇后问题