ปัญหา N Queen (N Queen Problem)

บทนำ

จัดวาง N ตัวหลาน (Queens) บนกระดานหมากรุก N×N ให้ไม่มีตัวใดกินกันได้ หมายถึง ไม่มีสองตัวอยู่แถวเดียว คอลัมน์เดียว หรือแนวทแยงเดียวกัน

แสดงผลเป็นเมทริกซ์ไบนารี 1 = วางหลาน, 0 = ว่าง

อินพุตและเอาต์พุต

Input: ขนาดกระดาน (ปกติ 8x8)
Output: เมทริกซ์ตำแหน่งหลาน 1=วางหลาน 0=ว่าง
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0

อัลกอริทึม

isValid(board, row, col)

Input: กระดาน, แถว, คอลัมน์
Output: True ถ้าวางหลานที่ (row,col) ถูกต้อง

Begin
    if มีหลานทางซ้ายในแถวเดียวกัน return false
    if มีหลานแนวทแยงซ้ายบน return false
    if มีหลานแนวทแยงซ้ายล่าง return false
    return true
End

solveNQueen(board, col)

Input: กระดาน, คอลัมน์ที่กำลังวาง
Output: เมทริกซ์ตำแหน่งหลาน

Begin
    if คอลัมน์ครบทุกตัว return true
    for แต่ละแถวของกระดาน do
        if isValid(board, row, col) then
            วางหลานที่ (row, col)
            if solveNQueen(board, col+1) return true
            นำหลานออก (backtrack)
    done
    return false
End

ตัวอย่างโค้ด (C++)

#include<iostream>
using namespace std;
#define N 8

void printBoard(int board[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) cout << board[i][j] << " ";
        cout << endl;
    }
}

bool isValid(int board[N][N], int row, int col) {
    for (int i = 0; i < col; i++) if (board[row][i]) return false;
    for (int i=row, j=col; i>=0 && j>=0; i--, j--) if (board[i][j]) return false;
    for (int i=row, j=col; j>=0 && i= N) return true;
    for (int i = 0; i < N; i++) {
        if (isValid(board, i, col)) {
            board[i][col] = 1;
            if (solveNQueen(board, col + 1)) return true;
            board[i][col] = 0;  // backtrack
        }
    }
    return false;
}

bool checkSolution() {
    int board[N][N] = {};
    if (!solveNQueen(board, 0)) { cout << "Solution does not exist"; return false; }
    printBoard(board); return true;
}

int main() { checkSolution(); }

ผลลัพธ์

1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0