Queens Puzzle

Queens Puzzle

Author: Jed. Feb 17, 2025

概述

八皇后問題是一個經典的西洋棋問題，目標是在一個 8×8 的棋盤上放置 8 個皇后，使得它們彼此之間無法互相攻擊。

規則

  • 不能同行：每個皇后必須位於不同的行。
  • 不能同列：每個皇后必須位於不同的列。
  • 不能左右斜對角：每個皇后不能位於其他皇后的對角線上。

4×4 棋盤的例子

image.png

當皇后放置在 (0,0) 時，以下位置不可放置皇后：

  • 同行：(0, y)
  • 同列：(x, 0)
  • 左右斜對角：(根據公式計算)

X為規則限制不能放置皇后的座標。

image.png

而完美的4X4的解法為下:

解法1

image.png

解法2

image.png

建立4X4棋盤

解了規則與解法後接下來透過python來實現，首先先建立棋盤。

class QueensPuzzle:

    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.checkerboard = [['.' for _ in range(cols)] for _ in range(rows)]

    def print_board(self):
        for row in self.checkerboard:
            print(" ".join(row))

queens_puzzle = QueensPuzzle(4, 4)

queens_puzzle.print_board()

列印4X4棋盤。

image.png

分析與實作

擺放皇冠判斷與實作

找出不可擺放的位置，當擺放(0,0)時，可以確定0 row 與 0 col就不能擺放，避免多餘的判斷時間。

image.png

而對角線可以透過公式來計算:

左上至右下對角線值

image.png

右上至左下對角線值

image.png

計算出對角線值就能求出第0 row到第3 row所有對角座標，從0 row開始，皇后擺在(0,1)，而左右對角值計算:

  • 左上至右下對角線值

    公式: row - col = value

    解: 0 - 1 = -1

  • 右上至左下對角線值

    公式: row + col = 1

    解: 0 + 1 = 1

求出值後，接著第1 row的對角座標帶入公式:

左上至右下對角線值 = 1 - x = -1, x = 2

右上至左下對角線值 = 1 + x = 1, x = 0

座標:(1,2)與(1,0)

image.png

接著第2 row的對角座標帶入公式:

左上至右下對角線值 = 2 - x = -1, x = 3

右上至左下對角線值 = 2 + x = 1, x = -1(棋盤沒有-1，所以省略)

座標:(2,3)

image.png

接著第3 row的對角座標帶入公式:

左上至右下對角線值 = 3 - x = -1, x = 4(4超過棋盤範圍，所以省略)

右上至左下對角線值 = 3 + x = 1, x = -4(棋盤沒有-4，所以省略)

座標: 無，結果不變

image.png

程式實作部分定義三個set變數存放

  • occupied_columns: col
  • occupied_left_diagonals: 左上至右下對角線值
  • occupied_right_diagonals: 右上至左下對角線值

在QueensPuzzle實作is_valid與handle

class QueensPuzzle:
        ...
        def is_valid(self, row, col, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
            if col in occupied_columns or (row - col) in occupied_left_diagonals or (row + col) in occupied_right_diagonals:
                return False
            return True

        def handle(self):
            def backtrack(row, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
                for col in range(self.cols):
                    if self.is_valid(row, col, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
                        self.checkerboard[row][col] = 'Q'
                        self.print_board()
                        print('-' * 20)
                        occupied_columns.add(col)
                        occupied_left_diagonals.add(row - col)
                        occupied_right_diagonals.add(row + col)

            backtrack(0, set(), set(), set())

queens_puzzle.handle()

執行後結果

image.png

但結果不如預期，會發現迴圈是由左往右但row永遠不變，因為我們從外面傳入0。

backtrack(0, set(), set(), set())

遞迴

所以這邊需要實作遞迴，每當擺放皇后時，row就要+1直到等於邊界為止。

backtrack(row +1,
          occupied_columns=occupied_columns,
          occupied_left_diagonals=occupied_left_diagonals,
          occupied_right_diagonals=occupied_right_diagonals)

執行後的結果

image.png

但是這邊又遇到問題，看圖中列印第三個棋盤時，怎麼會有皇后在旁邊?這是因為當遞迴2 row時，因為皇后無法擺放在2 row任何地方。

image.png

因此 2 row 的遞迴結束會返回至1 row，而1 row執行到(1,2)座標將繼續執行

image.png

而剛好只記錄col，並沒有紀錄row，且對角值都剛好沒匹配，所以會導致(1,3)驗證通過

image.png

回溯實作

前面提到無法放置Q時，我們需要將上個row的 Q 回溯，將原本(1,2)以及判斷的變數值都刪除，並尋找下一個符合規則的座標，因此將會是(1,3)。

image.png

backtrack

def backtrack(row, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
    for col in range(self.cols):
        if self.is_valid(row, col, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
            ....
            backtrack(row + 1,
                      occupied_columns=occupied_columns,
                      occupied_left_diagonals=occupied_left_diagonals,
                      occupied_right_diagonals=occupied_right_diagonals)
                        self.checkerboard[row][col] = '.'
                        occupied_columns.remove(col)
                        occupied_left_diagonals.remove(row - col)
                        occupied_right_diagonals.remove(row + col)

打印結果

Q . . .
. . . .
. . . .
. . . .
--------------------
Q . . .
. . Q .
. . . .
. . . .
--------------------
Q . . .
. . . Q
. . . .
. . . .
--------------------
Q . . .
. . . Q
. Q . .
. . . .
--------------------
. Q . .
. . . .
. . . .
. . . .
--------------------
. Q . .
. . . Q
. . . .
. . . .
--------------------
. Q . .
. . . Q
Q . . .
. . . .
--------------------
. Q . .
. . . Q
Q . . .
. . Q .
--------------------
. . Q .
. . . .
. . . .
. . . .
--------------------
. . Q .
Q . . .
. . . .
. . . .
--------------------
. . Q .
Q . . .
. . . Q
. . . .
--------------------
. . Q .
Q . . .
. . . Q
. Q . .
--------------------
. . . Q
. . . .
. . . .
. . . .
--------------------
. . . Q
Q . . .
. . . .
. . . .
--------------------
. . . Q
Q . . .
. . Q .
. . . .
--------------------
. . . Q
. Q . .
. . . .
. . . .
--------------------

Process finished with exit code 0

最後定義一個list來存放這些解答，以及判斷當目前col達到棋盤定義範圍就代表已經有解答了，因為有最佳解才會一直row+1直到與棋盤邊界相等

class QueensPuzzle:

    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.checkerboard = [['.' for _ in range(cols)] for _ in range(rows)]
        self.solutions = [] # 定義list

    ...
    def handle(self):
        def backtrack(row, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
            if row == self.rows: # 判斷是否找尋到解答
                self.solutions.append(["".join(r) for r in self.checkerboard])
                return

      #實作解答打印方法
      def print_solve(self):
        print(f"共{len(self.solutions)}個解答")
        for solution in self.solutions:
            for row in solution:
                print(row)
            print()

完整程式碼

class QueensPuzzle:

    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        self.checkerboard = [['.' for _ in range(cols)] for _ in range(rows)]
        self.solutions = []

    def is_valid(self, row, col, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
        if col in occupied_columns or (row - col) in occupied_left_diagonals or (row + col) in occupied_right_diagonals:
            return False
        return True

    def print_solve(self):
        print(f"共{len(self.solutions)}個解答")
        for solution in self.solutions:
            for row in solution:
                print(row)
            print()

    def handle(self):
        def backtrack(row, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
            if row == self.rows:
                self.solutions.append(["".join(r) for r in self.checkerboard])
                return

            for col in range(self.cols):
                if self.is_valid(row, col, occupied_columns, occupied_left_diagonals, occupied_right_diagonals):
                    self.checkerboard[row][col] = 'Q'
                    occupied_columns.add(col)
                    occupied_left_diagonals.add(row - col)
                    occupied_right_diagonals.add(row + col)
                    backtrack(row + 1,
                              occupied_columns=occupied_columns,
                              occupied_left_diagonals=occupied_left_diagonals,
                              occupied_right_diagonals=occupied_right_diagonals)
                    self.checkerboard[row][col] = '.'
                    occupied_columns.remove(col)
                    occupied_left_diagonals.remove(row - col)
                    occupied_right_diagonals.remove(row + col)

        backtrack(0, set(), set(), set())

    def print_board(self):
        for row in self.checkerboard:
            print(" ".join(row))

queens_puzzle = QueensPuzzle(4, 4)

queens_puzzle.handle()
queens_puzzle.print_solve()

總結

  • 核心思想：通過回溯算法嘗試所有可能的皇后位置，並排除不符合規則的位置來提高效率。
  • 關鍵點：
    • 使用集合記錄列和對角線的佔用情況。
    • 遞迴嘗試每一行的每個位置，並在無法放置時回溯。