ZeroJudge D324: 8 Queens Chess Problem

UVa 00750 – 8 Queens Chess Problem

On a chessboard, you can place 8 queens so that none of them conflict with each other (meaning no queen can attack another). Given the position of one queen, please write a program to output all possible arrangements where this condition holds.

Sample Input(s)Sample Output(s)
The first line of input contains an integer, indicating how many sets of test data will follow.
Each test case is on one line. Each line contains 2 integers representing the position where one of the queens must be placed. To standardize the chessboard, we define the top-left corner as position (1, 1). For example, in the diagram below, the black square's position is (4, 6), representing the 4th row (ROW) and the 6th column (COLUMN).		For each test case, first output a header. Then, for each solution, output one line where only the row positions are given. The column positions are represented by the order of the 8 numbers. For example, in the first test case of the Sample Output: The first solution's 8 queens' positions are (1, 1), (5, 2), (8, 3), (6, 4), (3, 5), (7, 6), (2, 7), (4, 8).
If there is more than one solution, please sort them in ascending order based on lexicographical order. Additionally, output a blank line between test cases. Please refer to the Sample Output for guidance.
1
1 1		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
ZeroJudge D324 Sample Test Case

Thought Process

Use the DFS (Depth-First Search) method to test whether each row can be a valid position. Store the positions of the already placed queens in an array. Each time you place a new queen, check the positions in the array to see if the new queen would be attacked.

Sample Code－ZeroJudge D324: 8 Queens Chess Problem

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<pair<int, int>>queen;
vector<vector<pair<int, int>>>ans;

int horizontal[10] = {};
int y, x;


void DFS(const int row, vector<pair<int, int>>v, int *hor) {
    if (row == y) {
        DFS(row+1, v, hor);
        return;
    }
    if (row == 9) {
        ans.push_back(v);
        return;
    }
    for (int i = 1; i<=8; i++) {
        if (hor[i] != 0) continue;
        bool isOK = true;
        for (int j = 0; j<v.size(); j++) {
            //cout << row << " " << i << " " << v[j].first << " " << v[j].second << endl;
            if (v[j].first == i || abs(row-v[j].second) == abs(i-v[j].first)) {
                isOK = false;
                break;
            }
        }
        if(isOK) {
            v.push_back(make_pair(i, row));
            hor[i]++;
            DFS(row+1, v, hor);
            hor[i]--;
            v.pop_back();
        }
        //break;
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for (int i = 0; i<T; i++) {
        queen.clear();
        ans.clear();
        cin >> y >> x;
        queen.push_back(make_pair(x, y));
        for (int j = 1; j<=8; j++) horizontal[j] = 0;
        horizontal[x]++;
        DFS(1, queen, horizontal);
        cout << "SOLN       COLUMN\n #      1 2 3 4 5 6 7 8\n\n";
        vector<vector<int>>output;
        for (int j = 0; j<ans.size(); j++) {
            sort(ans[j].begin(), ans[j].end());
            vector<int>tmp;
            for (int k = 0; k<8; k++) tmp.push_back(ans[j][k].second);
            output.push_back(tmp);
        }
        sort(output.begin(), output.end());
        for (int j = 0; j<output.size(); j++) {
            cout << j+1 << "      ";
            for (int k = 0; k<8; k++) {
                cout << output[j][k] << " ";
            }
            cout << "\n";
        }
        cout << "\n";
    }
}

//ZeroJudge D324
//Dr. SeanXD
Tags

Related Posts

Comments