chessboard-and-queens

Chessboard and Queens

CSES medium

ضع ثماني ملكات على رقعة شطرنج بحيث لا تهاجم أي ملكتين بعضهما. كل مربع إما حر (.) أو محجوز (*). يمكن وضع الملكات على المربعات الحرة فقط، لكن المربعات المحجوزة لا تمنع الهجوم بين الملكات.

أوجد عدد الطرق لوضع الملكات.

الإدخال:

ثمانية أسطر في كل منها ثمانية رموز: رقعة الشطرنج.

المخرجات:

عدد صحيح واحد — عدد الطرق.

مثال:

الإدخال:

........
........
..*.....
........
........
.....**.
...*....
........

المخرجات:

الحل

الملكتان في الصف نفسه تهاجمان بعضهما، لذلك يحتوي كل صف على ملكة واحدة بالضبط. نستخدم التراجع على الصفوف: في الصف row نجرّب كل عمود، فنضع ملكة إذا كان المربع مسموحًا، ونكمل بالصف التالي، ثم نزيل الملكة.

يكون المربع مسموحًا إذا كان حرًا ولا تهاجمه أي ملكة وُضعت قبله. نحتفظ بثلاث مصفوفات حتى يستغرق كل فحص \(O(1)\):

column_used[col] — توجد ملكة في العمود col؛
diagonal1_used[row + col] — توجد ملكة على القطر الذي تكون فيه قيمة row + col ثابتة؛
diagonal2_used[row - col + 7] — توجد ملكة على القطر الآخر، الذي تكون فيه قيمة row - col ثابتة. نضيف \(7\) حتى لا يكون الموقع سالبًا.

عندما يكون في كل الصفوف الثمانية ملكة، نكون قد وجدنا طريقة واحدة.

يستبعد التراجع كل مربع مُهاجَم، لذلك يفحص عددًا من الحالات أقل بكثير من \(8^8\) ويعمل بسرعة.

#include <iostream>
#include <string>
using namespace std;

string board[8];
bool column_used[8];
bool diagonal1_used[15];  // squares with the same row + column
bool diagonal2_used[15];  // squares with the same row - column + 7
int ways = 0;

void backtracking(int row) {
    // a queen is placed in every row
    if (row == 8) {
        ways++;
        return;
    }

    for (int col = 0; col < 8; col++) {
        if (board[row][col] == '*' || column_used[col] ||
            diagonal1_used[row + col] || diagonal2_used[row - col + 7]) {
            continue;
        }

        column_used[col] = diagonal1_used[row + col] = diagonal2_used[row - col + 7] = true;
        backtracking(row + 1);
        column_used[col] = diagonal1_used[row + col] = diagonal2_used[row - col + 7] = false;  // undo the step
    }
}

int main() {
    for (int i = 0; i < 8; i++) {
        cin >> board[i];
    }

    backtracking(0);

    cout << ways << "\n";
}