前回の数独に引き続きゲーム関連の問題を解いてみました。
初めに
N-クイーン問題について簡単に説明します。
N-クイーン問題とはチェスのN✕Nの盤面において、N個のクイーンがお互いを攻撃し合わないようなを置き方が何通りあるか求める問題です。クイーンの動きとしては上下左右斜めの８方向に任意のマス目(将棋の飛車と角行を合わせたようなもの)なので、それらの方向に別のクイーンを配置しないようにしなければなりません。
基本Pythonでの実装はJupyter Notebookを使っているので最後の返り値とかは適宜printしてください。
基本仕様
プログラムは以下の通りになります。
このとき、クイーンの配置は同じ行に別のクイーンが置かれることがないことから、N要素の配列のi番目にi行目のクイーンの列数を記憶するようにしました。また、面倒くさそうだったので回転・鏡像対称のものを区別しています。再帰で実装したので、見た目が前回の数独のときと酷似しています。
プログラム本体
def n_queen_solver(n, example=False):
place = [-1 for i in range(n)]
result = n_queen(n, place, 0, 0, example)
return result
def n_queen(n, place, iter_n, count, example):
if iter_n == n:
count += 1
# show examples of placement
if example:
print(place)
else:
for i in range(n):
if queen_placeable(place, iter_n, i):
place[iter_n] = i
count = n_queen(n, place, iter_n+1, count, example)
return count
def queen_placeable(place, iter_n, col):
for i in range(iter_n):
# queen already placed in same column
if col == place[i]:
return False
# queen already placed in diagonal direction
if col + (iter_n - i) == place[i] or col - (iter_n - i) == place[i]:
return False
return True
出力例
n_queen_solver(8): 92
合ってそうですね。nをあまり大きい数字にすると処理時間が割とかかります
(大体n=10を超えたあたりから少し間が空きはじめる)
n_queen_solver()の第２引数のexampleをTrueにすれば、配置例をズラッと並べます。
終わりに
数独のときと違って置けるかどうかの判定の実装が簡単だったので、書きやすかったですね。対称性とか考慮するとうまく工夫しないと実行時間が長くなりそうです(あまり得意ではない)。この問題はクイーン以外の駒で行う場合もありますが、配置できる駒の最大数が自明でない場合がありそうで面倒くさそうです。
追記
クイーンの他にビショップ、ルーク、ナイト、キングの場合でも解けるように拡張しました。クイーン、ルーク以外の駒だと探索が指数のオーダーになっているので７✕７の場合でも時間がかかる仕様です。
関数本体はn_chess()で、マス目の縦の大きさ、駒の種類、配置例を表示するかを引数として取ります。
import copy
def n_qr_solver(n, piece_type, example=False):
place = [-1 for i in range(n)]
result = n_qr(n, place, 0, 0, piece_type, example)
return result
def n_qr(n, place, iter_n, count, piece_type, example):
if iter_n == n:
count += 1
# show examples of placement
if example:
print(place)
else:
for i in range(n):
if qr_placeable(place, iter_n, i, piece_type):
place[iter_n] = i
count = n_qr(n, place, iter_n+1, count, piece_type, example)
return count
def qr_placeable(place, iter_n, col, piece_type):
for i in range(iter_n):
# queen or rook already placed in same column
if col == place[i]:
return False
if piece_type == "queen":
# queen already placed in diagonal direction
if col + (iter_n - i) == place[i] or col - (iter_n - i) == place[i]:
return False
return True
def bishop_placeable(n, board, row, col):
# find bishops in diagonal direction
for i in range(max(-row, -col), min(row+1, n-col)):
if i == 0:
continue
else:
if board[row-abs(i)][col+i] == 1:
return False
return True
def king_placeable(n, board, row, col):
direction = [[-1, -1], [-1, 0], [-1, 1], [0, -1]]
# find king
for d_row, d_col in direction:
row_t = row + d_row
col_t = col + d_col
if 0 <= row_t < n and 0 <= col_t < n and board[row_t][col_t] == 1:
return False
return True
def knight_placeable(n, board, row, col):
direction = [[-1, -2], [-2, -1], [-2, 1], [-1, 2]]
# find knight
for d_row, d_col in direction:
row_t = row + d_row
col_t = col + d_col
if 0 <= row_t < n and 0 <= col_t < n and board[row_t][col_t] == 1:
return False
return True
def n_bkk(n, board, row, col, count, piece_count, max_piece, judger, example_list):
# number of placeable pieces is lower than maximum
if piece_count + (n*n - row*n + col) < max_piece:
pass
elif row == n:
# found placement with more pieces
if piece_count > max_piece:
max_piece = piece_count
count = 1
example_list.clear()
else:
count += 1
board_copy = copy.deepcopy(board)
example_list.append(board_copy)
else:
if judger(n, board, row, col):
board[row][col] = 1
if col == n-1:
count, max_piece = n_bkk(n, board, row+1, 0, count, piece_count+1, max_piece, judger, example_list)
else:
count, max_piece = n_bkk(n, board, row, col+1, count, piece_count+1, max_piece, judger, example_list)
board[row][col] = 0
if col == n-1:
count, max_piece = n_bkk(n, board, row+1, 0, count, piece_count, max_piece, judger, example_list)
else:
count, max_piece = n_bkk(n, board, row, col+1, count, piece_count, max_piece, judger, example_list)
return count, max_piece
def n_bkk_solver(n, piece_type, example):
judgers = {'bishop': bishop_placeable, 'king': king_placeable, 'knight': knight_placeable}
board = [[0 for i in range(n)] for j in range(n)]
example_list = []
judger = judgers[piece_type]
result, max_piece = n_bkk(n, board, 0, 0, 0, 0, 0, judger, example_list)
if example:
print("max piece number: {}".format(max_piece))
for ex in example_list:
print(ex)
return result
def n_chess(n, piece_type, example=False):
if piece_type == "queen" or piece_type == "rook":
print(n_qr_solver(n, piece_type, example))
elif piece_type == "bishop" or piece_type == "king" or piece_type == "knight":
print(n_bkk_solver(n, piece_type, example))
else:
print('Invalid piece type')