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 

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 

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;
}

您可能以下文章有趣

[UVA][矩形集] 870 - Intersecting Rectangles

[UVA][人系列] 133 - The Dole Queue

[UVA][greedy] 12428 - Enemy at the Gates

[UVA][IDA*][Faster] 10181 - 15-Puzzle Problem