Source: InterviewBit – NQueens
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]解題：
- 首先，在開始下手處理這題目之前，一定要先知道西洋棋裡的皇后到底可以怎麼移動……Queen除了具備中國象棋中"車"的直線移動方式外，亦可進行對角線移動。因此，兩個皇后棋之間不打架的狀況就是：
在棋盤中每個皇后棋的直線路徑及對角線路徑上，均不會遭遇另一個皇后棋。
- 了解這層定義後，便可以開始先設計窮盡所有組合的暴力解了。最直觀的方式當然是窮盡所有組合並對每一種組合進行檢定，但這個做法需要先行輸出n^n種組合再一一進行檢驗，在測試時必定會遭遇TLE。那有甚麼方法可以在產出組合時減少些顯然不會通過檢驗的項目呢？
- 首先，因為我們確定在同一條直線上不應該同時出現２個皇后，因此在產出表示棋盤排列的矩陣時可以採用以下方式進行：
1. 預設棋盤是個 n 行矩陣，每行亦各有 n 個元素（也就是 n 行 * n 列） 2. 從第 0 行開始，依序將該行的第 i 個元素以皇后 Q 進行取代 3.1. 因同一列不可再出現皇后，故將該列號從 0 ~ (n-1) 的陣列中剔除 3.2. 另同一行亦不可再出現皇后，故採用遞迴繼續產出下一行的不同組合 此處須特別留意進入遞迴的列號組合應係經剔除元素更新過之陣列
如此一來就可以有效減少不少顯然無法通過檢驗的組合。筆者在一開始便是用這方式減少要另外進行對角線路徑檢驗的矩陣，再另外寫一支進行對角線路徑檢驗的程式來進行：
依據皇后棋所在的行列位置，分別檢視其四個象限的對角移動中是否會遭遇其他皇后棋。只有在所有皇后棋都不會互相遭遇的情況下這個矩陣才是有效並應將其進行輸出。但即使如此，依然在 n = 10 時發生 TLE 。那還可以再怎麼進行優化呢？ - 筆者後來另外加入幾個優化方式：
1. 直到最後輸出符合條件的矩陣前都僅使用 int 表示皇后棋位置而不採用 str 形式 如此便可以降低矩陣的位元，亦不用在進行對角線路徑檢驗前重新找出皇后棋座標 2. 在每次更新皇后棋行列座標時均執行對角線路徑測試， 如測試沒過代表也沒必要進行後續的遞迴步驟，可直接改用另一個座標值繼續進行
因為已經在遞迴過程中就執行對角線路徑檢驗，故所有可以撐到最後沒被淘汰掉的矩陣們必定全數合格可以進行輸出。
Code:
class Solution:
# @param n: integer
# @return a list of list of strings
def __init__(self):
self.nQueens = []
def puzzleChecker(self, puzzle, n):
"""Check whether there would be any other queen on their
moving paths
There's no need to check horizontal or vertical
since the situation is already considered when
defining puzzleMaker"""
def quadrant1Checker(row, col, n, Q_pos):
while row > 0 and col < n-1:
if (row-1, col+1) in Q_pos: return False
else:
row -= 1
col += 1
return True
def quadrant2Checker(row, col, n, Q_pos):
while row > 0 and col > 0:
if (row-1, col-1) in Q_pos: return False
else:
row -= 1
col -= 1
return True
def quadrant3Checker(row, col, n, Q_pos):
while row < n-1 and col > 0:
if (row+1, col-1) in Q_pos: return False
else:
row += 1
col -= 1
return True
def quadrant4Checker(row, col, n, Q_pos):
while row < n-1 and col < n-1:
if (row+1, col+1) in Q_pos: return False
else:
row += 1
col += 1
return True
Q_pos = [(row, col) for row, col in enumerate(puzzle)]
for row, col in Q_pos:
if not (quadrant1Checker(row, col, n, Q_pos) and
quadrant2Checker(row, col, n, Q_pos) and
quadrant3Checker(row, col, n, Q_pos) and
quadrant4Checker(row, col, n, Q_pos)):
return False
return True
def solveNQueens(self, n):
if n == 1: return ["Q"]
elif n <= 3: return []
def puzzleMaker(n, puzzle = [], row = 0,
col = list(range(n))):
puzzle = puzzle or []
if len(puzzle) < row+1 and row < n:
puzzle.append(0)
elif row == n:
temp = []
for i in range(n):
temp.append("."*puzzle[i] + "Q" +
"."*(n-1-puzzle[i]))
self.nQueens.append(temp)
return
for i in col:
puzzle[row] = i
puzzle = puzzle[:row+1]
if self.puzzleChecker(puzzle, n):
updated_col = col[:]
updated_col.remove(i)
puzzleMaker(n, puzzle, row+1, updated_col)
return
puzzleMaker(n, [], 0, list(range(n)))
return self.nQueens
為了比較好理解程式運作的機制，筆者將程式碼分成 puzzleMaker 及 puzzleChecker 兩個主要部分並進行設計及組合。網站提供的建議解法是直接將兩者結合在一起，但筆者自己看是覺得很難懂啦……
GitHub: GitHub
Python5566 