Bài toán N Hậu (N Queen Problem)

Giới thiệu

Sắp xếp N quân hậu trên bàn cờ NxN sao cho không quân nào ăn được quân khác. Hậu ăn theo hàng, cột, đường chéo.

Dùng ma trận nhị phân: 1 = có hậu, 0 = trống.

Đầu vào và Đầu ra

Đầu vào: Kích thước bàn cờ (thường 8)
Đầu ra: Ma trận vị trí N hậu. 1 = vị trí hợp lệ.
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

Thuật toán

isValid(board, row, col)

Begin
  nếu có hậu bên trái cột hiện tại thì return false
  nếu có hậu đường chéo trên trái thì return false
  nếu có hậu đường chéo dưới trái thì return false
  return true
End

solveNQueen(board, col)

Begin
  nếu tất cả cột đã điền thì return true
  với mỗi hàng i của bàn cờ làm:
    nếu isValid(board, i, col) thì
      đặt hậu tại (i, col)
      nếu solveNQueen(board, col+1) thì return true
      xóa hậu tại (i, col)  // backtrack
  done
  return false
End

Ví dụ (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;
    }
  }
  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(); }

Kết quả đầu ra

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