优化的n皇后问题
/* 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 = 13;
printf("%d 皇后\n", n);
Queens(n);
return 0;
}
void Queens(int n)//求解n皇后问题的驱动函数
{
int i;
for (i=0; i<n/2; i++)
{
board[0] = i;
SubQueens(0, n);
}
if (n % 2 == 1)
{
board[0] = n / 2;
for (i=0; i<n/2-1; i++)
{
board[1] = i;
SubQueens(1, n);
}
}
}
void SubQueens(int row, int n)//求解n皇后问题的子函数
{
int i, top = row;
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");
}
[ 本帖最后由 巧若拙 于 2014-12-25 14:57 编辑 ]