首先，題目要窮舉，可以先想看看DFS。
創建一個array，用來儲存結果。(其實不創建也可以XDD)
創建一個used列表，用來記錄哪個column已經被使用過了。
|
#假設要放置3個queen，1個castle
q_num = 3 c_num = 1 array_size = q_num + c_num array = [ |
一個4*4的矩陣，array[row][col]，array[0]到array[3]，剛好就是DFS的第layer:0~3。
接下來，就想想每一層要做的事情。
1. 每一個column，都只能使用一次。(例如: layer 0使用col 1，那麼layer 1就不能再使用col 1。)
2. 在每一層內，每一個column，都要嘗試放置皇后以及城堡。
3. 放置前，檢查該column有無使用過，該種類旗子的數量是否大於0。
4. 放置城堡時，需再檢查斜線處有無皇后。
5. 放置皇后時，需再檢查斜線處有無皇后或城堡。
(放置皇后時，需要再多檢查斜線有無城堡，以免把已經放置的城堡吃掉)
為了要快速檢查斜線處有無城堡或皇后，我把已經放置的城堡或皇后，儲存到list內。每次放置棋子時，都要把座標append進去，移除的時候也要remove。
檢查的時候，就使用x+y和x-y來檢查。如果值相等，表示有在同一斜線上。
|
q_site = [[x, y], [x, y]...]
c_site = [[x, y], [x, y]...]
#傳入x, y，檢查斜線上有無皇后，如果有，回傳False。
def check_q(x:int, y:int):
for i,j in q_site:
if (x+y==i+j) or (x-y==i-j):
return False
return True
#檢查斜線上有無城堡
def check_c(x:int, y:int):
for i,j in c_site:
if (x+y==i+j) or (x-y==i-j):
return False
return True
|
接下來，想想看進出下一層前後的步驟。
進入下一層之前，要把該種類旗子數量q_num或c_num減1，把該欄位標註為used，把該座標加入到q_site = []或c_site = []裡面。修改array(非必要)。
然後dfs(layer+1, q_num, c_num)。
出來之後，再把旗子數量加回來，把used標記取消，把座標從q_site = []或c_site = []裡面移除。如果有改array，再改回來。
成功抵達最後一層後。
把計數+1，然後return。
如果想要知道有哪些組合，也可以把array給print出來。
以下是完整程式碼:
|
#輸入皇后和城堡的數量
q_num, c_num = map(int,input().split())
#初始化棋盤矩陣
array_size = q_num + c_num
array = [[" " for _ in range(array_size)] for _ in range(array_size)] #創建矩陣
used = [False for _ in range(array_size)]
q_site = []
c_site = []
result_count = 0
#檢查斜線上有無皇后
def check_q(x:int, y:int):
for i,j in q_site:
if (x+y==i+j) or (x-y==i-j):
return False
return True
#檢查斜線上有無城堡
def check_c(x:int, y:int):
for i,j in c_site:
if (x+y==i+j) or (x-y==i-j):
return False
return True
def dfs(layer, q_num, c_num):
global result_count
if layer == array_size:
result_count += 1
#print(*array, sep="\n")
#print("------------------")
return
for col in range(array_size):
#放置皇后時，斜線上必須沒有城堡、沒有皇后
if (not used[col]) and (q_num > 0) and check_q(layer, col) and check_c(layer, col):
array[layer][col] = "q"
used[col] = True
q_site.append([layer, col])
#進入下層
dfs(layer+1, q_num-1, c_num)
#回到原處
used[col] = False
array[layer][col] = " "
q_site.remove([layer, col])
#放置城堡時，斜線上必須沒有皇后
if (not used[col]) and (c_num > 0) and check_q(layer, col):
array[layer][col] = "c"
used[col] = True
c_site.append([layer, col])
dfs(layer+1, q_num, c_num-1)
used[col] = False
array[layer][col] = " "
c_site.remove([layer, col])
dfs(0,q_num,c_num)
print(result_count)
|
#print(*array, sep="\n")和#print("------------------")如果取消註解的話，可以看到結果的棋盤。所有程式碼之中，有array的，都是選配，沒有使用也不影響答案。