Algorithm - Python - おびただしい女王(条件を満たす解、再帰プロシージャーによるしらみつぶし探索)

問題解決のPythonプログラミング
原著
楽天ブックス(Kobo) Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の10章(おびただしい女王)、練習問題(パズル問題2)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3
def no_conflicts(board: list, current: int) -> bool:
    for i in range(current):
        if (board[i] == board[current]) or \
           (current - i == abs(board[current] - board[i])):
            return False
    return True


def recursive_queens(board: list, current: int, size: int) -> bool:
    if current == size:
        return True
    queen_location = board[current]
    for i in range(size):
        if queen_location == -1:
            board[current] = i
        if no_conflicts(board, current) and \
           recursive_queens(board, current + 1, size):
            return True
        if queen_location == -1:
            board[current] = -1
    return False


def print_board(board, n):
    blank = ' . '
    queen = ' Q '
    for i in range(n):
        col_index = board.index(i)
        print(f'{blank * col_index}{queen}{blank * (n - col_index - 1)}')


def queens(n: int, board: list = None) -> None:
    if board is None:
        board = [-1] * n
    recursive_queens(board, 0, n)
    print_board(board, n)


if __name__ == '__main__':
    queens(20)
    print('-' * 3 * 20)
    queens(10, board=[-1, -1, 4, -1, -1, -1, -1, 0, -1, 5])

入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))

$ ./sample2.py
 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  .  .  .  .  .  .  .  .  . 
$