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

minhcanhtu · September 16, 2018, 1:40am

Xin chào mọi người. Mình có đang giải 1 problem sau: http://ntucoder.net/Problem/Details/115
Về phần in ra solution của bài toán N-Queen thì mình đã tìm hiểu trước ở trang Geeksforgeeks: https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/
Vì thế, mình đã tùy biến đoạn code lại để đáp ứng được yêu cầu của đề bài như sau: https://ideone.com/U1BE2N

#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) {
        board[y][x] = 'w';
        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 (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;
}

Ý tưởng của thuật toán mình làm là sẽ solve phần bàn cờ nằm bên trái tọa độ cho sẵn (y; x), sau đó sẽ solve phần bàn cờ bên phải toạn độ cho sẵn (y; x) (do đặc thù hàm kiểm tra isSafe() của đoạn code chỉ kiểm tra từ vị trí column đang xét về phía bên trái nên mình sẽ làm từ bên trái sang bên phải).
Đoạn code nhìn có vẻ ổn định nhưng khi chạy với bộ input 3 2 thì lại sinh lỗi, cụ thể là chỉ in được Queen ở phần bên trái tọa độ (y; x), còn phần bên phải không in được (như trong link IDEone). Mình vẫn phân vân chưa biết lỗi ở chỗ nào, nhờ mọi người giúp đỡ ạ!
Xin cảm ơn.

P/S: Codeblocks của mình bị lỗi gì ấy nên không thể debug được :((
Edit: Hmmm mình nghi có thể do hàm isSafe() chạy không đúng dẫn đến không in ra được w ở các col tiếp theo, nhưng vẫn chưa thấy lỗi chỗ nào!

minhcanhtu · September 16, 2018, 3:23am

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?

minhcanhtu · September 16, 2018, 7:12am

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ỉ?

minhcanhtu · September 16, 2018, 7:34am

À, 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.

phamdat2 · September 16, 2018, 3:08pm

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

james2012 · September 17, 2018, 1:45pm

nice try @minhcanhtu