爱站程序员基地链接 UVA750 【8 Queens Chess Problem】
题目描述：
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.
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
输入描述：
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 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.
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.
输入样例：
11 1
输出样例：
SOLN COLUMN# 1 2 3 4 5 6 7 81 1 5 8 6 3 7 2 42 1 6 8 3 7 4 2 53 1 7 4 6 8 2 5 34 1 7 5 8 2 4 6 3
题意:
给你两值row，cal
在棋盘上放8个互相攻击不到的皇后
在第row列cal行一定要有一个皇后
数据范围：
询问次数不超过20，每格价值不超过100
思路：
8皇后问题的应用
用一个二维数组来存储每种情况皇后的摆放位置
P[i][j]表示方式 i 中第 j 行皇后的列位置
用递归来完成p数组
代码：
#include <cstdio>using namespace std;int P[1000][9]; //方式 i 中第 j 行皇后的列位置为 P[i][j]int tmp[9]; //当前方式中第 i 行皇后的列位置为 tmp[i]int n = 0; //方式数初始化bool col[8] = {0}, left[15] = {0}, right[15] = {0}; //所有列和左右对角线未被选中void fun(int r){if(r == 8){for(int i = 0;i < 8;i++)P[n][i] = tmp[i];n++;return;}for(int c = 0;c < 8;c++){int ld = c+r;int rd = (c-r)+7;if(!col[c]&&!left[ld]&&!right[rd]){col[c] = left[ld] = right[rd] = 1;tmp[r] = c;fun(r+1);col[c] = left[ld] = right[rd] = 0;}}}int main(){fun(0);int Case;scanf(\"%d\",&Case);while(Case--){int row,col;//确定皇后的行和列；scanf(\"%d %d\",&row,&col);printf(\"SOLN COLUMN\\n\");printf(\" # 1 2 3 4 5 6 7 8\\n\\n\");int k = 1;for(int i = 0;i < n;i++){if(P[i][col-1] == row-1){printf(\"%2d \",k++);for(int j = 0;j < 8;j++)printf(\" %d\",P[i][j]+1);printf(\"\\n\");}}if(Case) printf(\"\\n\"); //注意格式和low与col别搞反了}return 0;}
