N皇后问题的构造法
n*n的棋盘，放n个皇后，互不攻击
一、当n%6 != 2 或 n%6 != 3时，有一个解为：
2,4,6,8,...,n,1,3,5,7,...,n-1 (n为偶数)
2,4,6,8,...,n-1,1,3,5,7,...,n (n为奇数)
(上面序列第i个数为ai，表示在第i行ai列放一个皇后；... 省略的序列中，相邻两数以2递增。下同)
二、当n%6 == 2 或 n%6 == 3时，
(当n为偶数,k=n/2；当n为奇数,k=(n-1)/2)
k,k+2,k+4,...,n,1,2,4,...,k-2,k+3,k+5,...,n-1,1,3,5,...,k+1 (k为偶数,n为偶数)
k,k+2,k+4,...,n-1,2,4,...,k-2,k+3,k+5,...,n-2,1,3,5,...,k+1,n (k为偶数,n为奇数)
k,k+2,k+4,...,n-1,1,3,5,...,k-2,k+3,...,n,2,4,...,k+1 (k为奇数,n为偶数)
k,k+2,k+4,...,n-2,1,3,5,...,k-2,k+3,...,n-1,2,4,...,k+1,n (k为奇数,n为奇数)
凭这就可以做掉：http://acm.uva.es/p/v100/10094.html
不知道如何理论上证明?其他解还有什么规律?
问题点数：200、回复次数：18Top
1 楼whalefish2001（whale）回复于 2004-05-09 11:45:07 得分 50
我把我做的程序代码放在这里。
为了执行速度快一些，可以不要打印输出。
#include<iostream.h>
#include<conio.h>
#define N 11 //这里修改N的数目也就是N 皇后
int eg[20][20],geshu;
void print();
void eight(int js)
{
if(js>N)return;
int i,j,flag=0;
for(i=1;i<=N;i++)
{
flag=0;
eg[js][i-1]=0;
eg[js][i]=1;
for(j=1;j<=js-1;j++)
{
if(eg[j][i]==1) flag=1;
}
for(j=1;(i>j)&&(js>j);j++)
{
if(eg[js-j][i-j]==1)flag=1;
}
for(j=1;(js>j)&&(i+j<=8);j++)
{
if(eg[js-j][i+j]==1)flag=1;
}
if((js==N)&&(flag==0))print();
if(flag==0) eight(js+1);
}
for(i=1;i<=N;i++)eg[js][i]=0;
}
void print()
{
geshu+=1;
// /* 把这里的最前面的 // 去掉，不要打印输出。
int i,j;
for(i=1;i<=N;i++)
{
for(j=1;j<=N;j++)
cout<<eg[i][j]<<" ";
cout<<endl;
}
cout<<"-----------------"<<endl;
cout<<endl;
// */ // 把这里的最前面的 // 去掉，不要打印输出。
}
void main()
{
geshu=0;
eight(1);
cout<<"总共"<<N<<"皇后的个数是："<<geshu<<endl;
return ;
}
我的测试：
皇后个数 总共的排法
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 644
10 4345
11 39303
12 386703
13 XXXXXX
..........................
可能会对你们找算法有一些帮助吧。
Top
2 楼wlpwind（robin）回复于 2004-05-09 13:05:30 得分 10
与禁位排列的理论有关吧。Top
3 楼mmmcd（超超）回复于 2004-05-09 17:21:51 得分 0
<<算法艺术与信息学竞赛>>稍有提及，没有细说。Top
4 楼hell190109（）回复于 2004-05-09 18:59:30 得分 10
http://oibh.ioiforum.org/newcomer/standard/dfs/dfs01.htmTop
5 楼hell190109（）回复于 2004-05-09 18:59:59 得分 0
http://www.cnblogs.com/jebit/Top
6 楼NowCan（城市浪人）回复于 2004-05-09 19:22:44 得分 20
帖一个以前在这里看到的。
/*
皇后问题，最多算30个
方法：在每一行放一个皇后就在下面的与此皇后在一条竖线和斜线上的
格子作上标记，在下面一行再放皇后时就可很容易找到有效的格子
不用递归也不用栈
*/
#include <string.h>
#include <conio.h>
#include <stdio.h>
#include <windows.h>
#define _PRINT_ 0
#define MAX_WIDTH 30
#define FLAG_OCCUPYED 19999
int board[MAX_WIDTH][MAX_WIDTH]; //棋盘[最大列数][最大行数]
int begin[MAX_WIDTH]; //棋盘每一行开始尝试的格子的位置
int queen[MAX_WIDTH]; //每一行的皇后的位置
int n; //棋盘的实际大小(nXn)
//清空棋盘
void clearboard(void)
{
memset(board, 0, MAX_WIDTH * MAX_WIDTH * sizeof(int));
memset(begin, 0, MAX_WIDTH * sizeof(int));
memset(queen, 0, MAX_WIDTH * sizeof(int));
}
//在第ln行第col列放一皇后,并对其以下各行相关格了作上标记
void insert(int ln, int col)
{
int tcol, scol;
board[col][ln]=FLAG_OCCUPYED;
queen[ln]=col;
tcol=scol=col;
for(int k=ln + 1; k < n; k++)
{
if(!board[col][k]) //为与此皇后在一条纵线上的格子作上标记
board[col][k]=ln + 1;
if(++tcol < n && !board[tcol][k]) //为与此皇后在一条右下斜线上格子作标记
board[tcol][k]=ln + 1;
if(--scol >= 0 && !board[scol][k]) //为与此皇后在一条左下斜线上格子作标记
board[scol][k]=ln + 1;
}
begin[ln]=col;
}
//尝试第ln行失败后,删除第ln行的皇后并恢复其以下的相关格子标记为0(有效)
void erase(int ln)
{
int col, tcol, scol;
for(int i=ln + 1; i < n; i++) begin[i]=0;
col=queen[ln];
board[col][ln]=0;
tcol=scol=col;
for(int k=ln + 1; k < n; k++) //清空与此格子相关的标记
{
if(board[col][k] == ln + 1) board[col][k]=0;
if(++tcol < n && board[tcol][k] == ln + 1) board[tcol][k]=0;
if(--scol >= 0 && board[scol][k] == ln + 1) board[scol][k]=0;
}
begin[ln]++; //下一次尝试将从ln行下一格开始
}
/* */
void main(void)
{
int ln, col;
int resnum=0; //解的数目
printf("Please input board width(4-30):");
scanf("%d", &n); //输入棋盘实际大小
#if _PRINT_
FILE *f;
f=fopen("queen.txt", "w"); //打开输出文件
if(!f)
{
printf("Can not open file 'queen.txt'");
return;
}
#endif
DWORD nBegin = GetTickCount();
HANDLE hThread = GetCurrentThread();
SetThreadPriority( hThread , THREAD_PRIORITY_TIME_CRITICAL );
clearboard();
#if _PRINT_
fprintf(f, "%dX%d\n", n, n);
#endif
ln=0;
while(1)
{
bool find=false;
for(col=begin[ln]; col < n; col++)
{
if(!board[col][ln]) //如果此格子为0有效
{
insert(ln, col); //在此格子处放一皇后
find=true;
break;
}
}
if(!find) //没发现有效格子
{
if(!ln) break; //如果已经回溯到第1行,则退出
ln--; //回到上一行
erase(ln); //删除此行皇后
}
else //发现有效格子后
{
ln++; //到下一行
if(ln == n) //已经超过最后一行则说明已找到一个解, 并保存在文件
{
++resnum;
#if _PRINT_
fprintf(f, "No. %d: ", resnum);
for(int i=0; i < n; i++) fprintf(f, "%d ", queen[i] + 1);
fprintf(f, "\n");
if(resnum % 1000 == 0) printf("\rfound %d Results...", resnum);
#endif
ln--;
erase(ln); //删除最后一行的皇后,并尝试其他解
}
}
}
#if _PRINT_
fclose(f);
#endif
printf("\nTotal Results: %d\n", resnum);
printf("Time Used : %lu ms", GetTickCount() - nBegin);
#if _PRINT_
printf("Open 'queen.txt' for all results.\nPress any key exit... ");
getch();
#endif
}
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
11 2680
12 14200
13 73712
14 365596
15 2279184
16 14772512
17 ???????????
答案不同了，怎么回事？Top
7 楼mmmcd（超超）回复于 2004-05-09 21:11:48 得分 0
我晕！！！！！！！！
本贴跟回溯法没有任何关系！！！！！！！
这题：
http://acm.uva.es/p/v100/10094.html
的皇后数目最多1000个
现在要讨论的是“构造法”，O(1)时间内生成答案。Top
8 楼mmmcd（超超）回复于 2004-05-09 21:16:47 得分 0
刚开始对付“皇后问题”就用搜索，
现在用新方法，与时俱进。Top
9 楼whalefish2001（whale）回复于 2004-05-10 10:02:47 得分 50
呵呵，确实知道楼主的时间复杂度是 O(1)
不过，偶不会。
Top
10 楼mmmcd（超超）回复于 2004-06-07 09:53:08 得分 0
这里有200分
继续看Top
11 楼BaiYunfeng（Kidan）回复于 2004-06-08 17:22:56 得分 50
LRJ的书上说的是用启发式修补。速度也很快了。1000个皇后大概0.99s
这个东西只要摆出来不冲突就可以了，怎么构造都是可以的啊？Top
12 楼mmmcd（超超）回复于 2004-06-08 20:24:45 得分 0
我的直接构造用时：0.047s
http://acm.uva.es/cgi-bin/OnlineJudge?ProblemStat:10094
我也想知道启发式修补的程序是什么样的Top
13 楼mmmcd（超超）回复于 2004-06-26 11:11:21 得分 0
继续看看Top
14 楼mmmcd（超超）回复于 2004-07-20 13:25:47 得分 0
http://acm.uva.es/p/v100/10094.htmlTop
15 楼mmmcd（超超）回复于 2004-09-08 21:05:28 得分 0
这有200分
继续看看Top
16 楼NowCan（城市浪人）回复于 2004-09-09 12:28:06 得分 0
怎么你能连续回复4次？Top
17 楼ZhangYv（迎着朝阳,走向地狱）回复于 2004-09-09 21:15:49 得分 0
似乎当网络传输不太正常时可以连续回复多次。当时我学校的校园网不稳定时候，我可以无限回复...Top
18 楼zzwu（未名）回复于 2004-09-10 20:30:22 得分 10
怪事一桩.Top
