N-クイーン問題を解く

[前回](https://qiita.com/sekishoku/items/ffb5d4c35970de3219f0)の数独に引き続きゲーム関連の問題を解いてみました。

# 初めに
　N-クイーン問題について簡単に説明します。
　N-クイーン問題とはチェスのN✕Nの盤面において、N個のクイーンがお互いを攻撃し合わないようなを置き方が何通りあるか求める問題です。クイーンの動きとしては上下左右斜めの８方向に任意のマス目(将棋の飛車と角行を合わせたようなもの)なので、それらの方向に別のクイーンを配置しないようにしなければなりません。
　基本Pythonでの実装はJupyter Notebookを使っているので最後の返り値とかは適宜printしてください。


# 基本仕様
　プログラムは以下の通りになります。
　このとき、クイーンの配置は同じ行に別のクイーンが置かれることがないことから、N要素の配列のi番目にi行目のクイーンの列数を記憶するようにしました。また、面倒くさそうだったので回転・鏡像対称のものを区別しています。再帰で実装したので、見た目が前回の数独のときと酷似しています。

## プログラム本体
``` Python3
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()で、マス目の縦の大きさ、駒の種類、配置例を表示するかを引数として取ります。

```Python3
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')
```