第一百题 UVAa750 8 Queens Chess Problem 目之所及 皆是遗憾
终于写够一百道题啦，怎么也没想过他是这样来临的，在一个阳光明媚的冬日，写完第九十九题之后还是非常激动的，不知道第一百题做什么好，ACM群里不知怎么的就讨论起了八皇后问题（好像还是因为我发了一个非常奇怪的问题求解答）我犹豫了三分钟之后，算了，干脆写个八皇后问题吧，这题很熟悉，但是现在却已经都忘记了题目是什么样子的，又翻了出来。。。。
In chess it is possible to place eight queens on the board so that no one queen can be taken by any
other. Write a program that will determine all such possible arrangements for eight queens given the
initial position of one of the queens.
Do not attempt to write a program which evaluates every possible 8 configuration of 8 queens placed
on the board. This would require 88
evaluations and would bring the system to its knees. There will
be a reasonable run time constraint placed on your program.
Input
The first line of the input contains the number of datasets,
and it’s followed by a blank line.
Each dataset contains a pair of positive integers separated
by a single space. The numbers represent the square on which
one of the eight queens must be positioned. A valid square
will be represented; it will not be necessary to validate the
input.
To standardize our notation, assume that the upper leftmost corner of the board is position (1,1). Rows run horizontally and the top row is row 1. Columns are vertical and
column 1 is the left-most column. Any reference to a square
is by row then column; thus square (4,6) means row 4, column
6.
Each dataset is separated by a blank line.
Output
Output for each dataset will consist of a one-line-per-solution representation.
Each solution will be sequentially numbered 1 . . . N. Each solution will consist of 8 numbers. Each
of the 8 numbers will be the ROW coordinate for that solution. The column coordinate will be indicated
by the order in which the 8 numbers are printed. That is, the first number represents the ROW in
which the queen is positioned in column 1; the second number represents the ROW in which the queen
is positioned in column 2, and so on.
Notes:
The sample input below produces 4 solutions. The full 8×8 representation of each solution is shown
below.
DO NOT SUBMIT THE BOARD MATRICES AS PART OF YOUR SOLUTION!
SOLUTION 1 SOLUTION 2 SOLUTION 3 SOLUTION 4
1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0
Submit only the one-line, 8 digit representation of each solution as described earlier. Solution #1
below indicates that there is a queen at Row 1, Column 1; Row 5, Column 2; Row 8, Column 3; Row
6, Column 4; Row 3,Column 5; … Row 4, Column 8.
Include the two lines of column headings as shown below in the sample output and print the
solutions in lexicographical order.
Sample Input
1
1 1
Sample Output
SOLN COLUMN
1 1 5 8 6 3 7 2 4
2 1 6 8 3 7 4 2 5
3 1 7 4 6 8 2 5 3
4 1 7 5 8 2 4 6 3
#include
#include
#include
using namespace std;
int r,c,col[10],Ans;
bool vis[3][30];
void DFS(int cur) {
if(cur == 9) {
Ans ++;
printf("%2d ",Ans);
for(int i=1; i<=8; i++) printf(" %d",col[i]);
printf("\n");
return ;
}
if(cur == c) { DFS(cur + 1); return; }
for(int i=1; i<=8; i++) {
if(!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + 8]) {
col[cur] = i;
vis[0][i] = vis[1][cur + i] = vis[2][cur - i + 8] = true;
DFS(cur + 1);
vis[0][i] = vis[1][cur + i] = vis[2][cur - i + 8]=false;
}
}
}
int main(int argc,char* agrv[]) {
int T; scanf("%d",&T);
while(T--) {
scanf("%d%d",&r,&c);
Ans = 0;
memset(vis,0,sizeof(vis));
col[c] = r;
vis[0][r] = vis[1][r + c] = vis[2][c - r + 8] = true;
printf("SOLN COLUMN\n # 1 2 3 4 5 6 7 8\n\n");
DFS(1);
if(T) printf("\n");
}
return 0;
}
作者：当春风吹过时光、吹过记忆
