Gặp lỗi trong chương trình in ra 7 quân hậu thích hợp trên bàn cờ 8x8 từ 1 vị trí có sẵn cho trước

Mình đã update lại điều kiện if (col == x) trong hàm solveNQueenB() lại để tránh error, nhưng lỗi ở trên vẫn còn!

#include <iostream>
#include <vector>
#include <string>
#define N 8

using namespace std;

int y, x;

bool isSafe(const vector<string> &board, int row, int col)
{
    /* Check this row on left side */
    for (int i = 0; i < col; ++i) {
        if (board[row][i] == 'w') return false;
    }
    /* Check upper diagonal on left side */
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
        if (board[i][j] == 'w') return false;
    }
    /* Check lower diagonal on left side */
    for (int i = row + 1, j = col - 1; i < N && j >= 0; ++i, --j) {
        if (board[i][j] == 'w') return false;
    }
    return true;
}
// Place all the kings suitably before col x
bool SolveNQueenB(vector<string> &board, int col = 0)
{
    // Solution found!
    if (col == x) {
        if (isSafe(board, y, x)) {
            board[y][x] = 'w';
            return true;
        }
        return false;
    }
    for (int i = 0; i < N; ++i) {
        // Found a square for queen[i][col]
        if (isSafe(board, i, col)) {
            board[i][col] = 'w';
            if (SolveNQueenB(board, col + 1))
                return true;
            board[i][col] = '.'; // backtrack
        }
    }
    return false;
}
// Place all the kings suitably after col x
bool SolveNQueenA(vector<string> &board, int col = x + 1)
{
    // Solution found!
    if (col == N) {
        return true;
    }
    for (int i = 0; i < N; ++i) {
        // Found a square for queen[i][col]
        if (isSafe(board, i, col)) {
            board[i][col] = 'w';
            if (SolveNQueenA(board, col + 1))
                return true;
            board[i][col] = '.'; // backtrack
        }
    }
    return false;
}

int main()
{
    // print all solutions to N-Queen problem.
    vector<string> board(N);
    for (int i = 0; i < N; ++i)
        board[i].resize(N, '.');
    cin >> y >> x;
    --y; --x; // set to the right indexes
    SolveNQueenB(board);
    SolveNQueenA(board);
    for (int i = 0; i < N; ++i) {
        cout << board[i] << endl;
    }
    return 0;
}

Test với một số input mà x > 1 thì có vẻ hàm solveNQueenA() không chạy?

Mình có thử test đoạn code trên hết 64 trường hợp thì:

• Các TH mà x = 1 thì code cho ra kết quả đúng.
• Các TH mà x = 2 thì code chỉ chạy đúng ở (y; x) = (1; 2); (2; 2); (5; 2); (6; 2); (7; 2).
• Các TH mà x = 3 thì code chạy sai hết.
• Các TH mà x = 4 thì code cũng chạy sai hết.
• Các TH mà x = 5 thì code chỉ chạy đúng ở mỗi test (y; x) = 1 5
• Các TH mà x = 6 thì code chỉ chạy đúng ở mỗi test (y; x) = 1 6
• Các TH mà x = 7 thì code chạy đúng ở 2 tests (y; x) = (2; 7); (8; 7)
• Các TH mà x = 8 thì code chạy đúng hết.

Có ai có phát hiện gì không nhỉ?

À, mình đã tìm ra bug rồi.
Việc chia 2 hàm để solve những cột bên trái cột x và solve những cột bên phải cột x riêng đã dẫn tới bug, cụ thể là có nhiều hơn 1 TH các queens được đặt vào những cột bên trái cột x và một vài trong số đó có thể làm bài toán vô nghiệm. Vậy nên phải giải bài toán trong cùng 1 hàm để tránh trường hợp bài toán chỉ xét TH vô nghiệm mà ko xét những TH có nghiệm khác.

#include <iostream>
#include <vector>
#include <string>
#define N 8

using namespace std;

int y, x;

bool isSafe(const vector<string> &board, int row, int col)
{
    /* Check this row on left side */
    for (int i = 0; i < col; ++i) {
        if (board[row][i] == 'w') return false;
    }
    /* Check upper diagonal on left side */
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
        if (board[i][j] == 'w') return false;
    }
    /* Check lower diagonal on left side */
    for (int i = row + 1, j = col - 1; i < N && j >= 0; ++i, --j) {
        if (board[i][j] == 'w') return false;
    }
    return true;
}

bool SolveNQueen(vector<string> &board, int col = 0)
{
    // Solution found!
    if (col == x) {
        if (isSafe(board, y, x)) {
            board[y][x] = 'w';
            if (SolveNQueen(board, col + 1))
                return true;
        }
        return false;
    }
    if (col == N) return true;
    for (int i = 0; i < N; ++i) {
        // Found a square for queen[i][col]
        if (isSafe(board, i, col)) {
            board[i][col] = 'w';
            if (SolveNQueen(board, col + 1))
                return true;
            board[i][col] = '.'; // backtrack
        }
    }
    return false;
}

int main()
{
    // print all solutions to N-Queen problem.
    vector<string> board(N);
    for (int i = 0; i < N; ++i)
        board[i].resize(N, '.');
    cin >> y >> x;
    --y; --x; // set to the right indexes
    board[y][x] = 'w';
    SolveNQueen(board);
    for (int i = 0; i < N; ++i) {
        cout << board[i] << endl;
    }
    return 0;
}

ACCEPTED!
Cảm ơn mọi người đã pay attention to.

Cảm ơn mọi người đã pay attention to.

tính ra cả bài viết có mỗi 3 comment của ông mà

nice try @minhcanhtu

This post was flagged by the community and is temporarily hidden.