8 Queens Chess Problem

In chess it is possible to place eight queens on the board so that no onequeen can be taken by any other. Write a program that will determine allsuch possible arrangements for eight queens given the initial position of oneof the queens.

Do not attempt to write a program which evaluates every possible 8configuration of 8 queens placed on the board. This would require 8⁸evaluations and would bring the system to its knees. There will be areasonable 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 datasetwill be two numbers separated by a blank. The numbers represent the squareon which one of the eight queens must be positioned. A valid square will berepresented; it will not be necessary to validate the input.

To standardize our notation, assume that the upper left-most corner of theboard 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 toa 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 .Each solution willconsist of 8 numbers. Each of the 8 numbers will be the ROW coordinate forthat solution. The column coordinate will be indicated by the order in whichthe 8 numbers are printed. That is, the first number represents the ROW inwhich the queen is positioned in column 1; the second number represents theROW in which the queen is positioned in column 2, and so on.

The sample input below produces 4 solutions. The full 88 representation of each solution is shown below.

   SOLUTION 1           SOLUTION 2           SOLUTION 3           SOLUTION 41 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 00 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 00 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 10 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 00 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 00 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 00 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 00 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 describedearlier. 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.

Print a blank line between datasets.

Sample Input 

11 1

Sample Output 

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8
 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 <stdio.h>
#include <stdlib.h>
int x[8], y[8], used[8] = {};
int ax, ay, time;
int check(int a, int b, int idx) {
    int i;
    for(i = 0; i < idx; i++)
        if(abs(x[i]-a) == abs(y[i]-b))
            return 0;
    return 1;
}
void dfs(int idx) {
    if(idx == 8) {
        if(y[ay-1] == ax-1) {
            printf("%2d     ", ++time);
            int i;
            for(i = 0; i < 8; i++)
                printf(" %d", y[i]+1);
            puts("");
        }
        return;
    }
    int i;
    for(i = 0; i < 8; i++) {
        if(used[i] == 0 && check(idx, i, idx) != 0) {
            used[i] = 1;
            x[idx] = idx, y[idx] = i;
            dfs(idx+1);
            used[i] = 0;
        }
    }
}
int main() {
    int t, i, j, first = 0;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &ax, &ay);
        if(first)
            puts("");
        first = 1;
        puts("SOLN       COLUMN");
        puts(" #      1 2 3 4 5 6 7 8\n");
        time = 0;
        dfs(0);
    }
    return 0;
}