Algorithm - Python - 女王たちを一緒にするな(if文、not、continue文、インデントの段数の削減、8クイーン問題、2次元リスト、forループ、関数のデフォルト引数、continue文、繰り返しによるしらみ潰し探索、衝突検出)

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

開発環境

• macOS Mojave - Apple
• Emacs (Text Editor)
• Python 3.7 (プログラミング言語)

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の4章(女王たちを一緒にするな)、練習問題(問題3)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3
''' 問題1 '''


def no_conflicts(board, current, queen_index, n):
    for j in range(current):
        if board[queen_index][j] == 1:
            return False
    k = 1
    while queen_index - k >= 0 and current - k >= 0:
        if board[queen_index - k][current - k] == 1:
            return False
        k += 1
    k = 1
    while queen_index + k < n and current - k >= 0:
        if board[queen_index + k][current - k] == 1:
            return False
        k += 1
    return True


def print_board(board, n=4):
    def set_queen(i, j):
        if board[i][j] == 1:
            return 'Q'
        return ' '
    board_nn = [[set_queen(i, j) for j in range(n)]
                for i in range(n)]

    for row in board_nn:
        print('-' * (2 * n + 1))
        print(f'|{"|".join(row)}|')
    print('-' * (2 * n + 1))
    print()


def four_queens(n=4):
    board = [[0 for _ in range(n)]
             for _ in range(n)]
    for i in range(n):
        board[i][0] = 1
        for j in range(n):
            board[j][1] = 1
            if not no_conflicts(board, 1, j, n):
                board[j][1] = 0
                continue
            for k in range(n):
                board[k][2] = 1
                if not no_conflicts(board, 2, k, n):
                    board[k][2] = 0
                    continue
                for m in range(n):
                    board[m][3] = 1
                    if not no_conflicts(board, 3, m, n):
                        board[m][3] = 0
                        continue
                    print_board(board)
                    board[m][3] = 0
                board[k][2] = 0
            board[j][1] = 0
        board[i][0] = 0
    return


if __name__ == '__main__':
    four_queens()

入出力結果(Terminal, Jupyter(IPython))

$ ./sample3.py
---------
| | |Q| |
---------
|Q| | | |
---------
| | | |Q|
---------
| |Q| | |
---------

---------
| |Q| | |
---------
| | | |Q|
---------
|Q| | | |
---------
| | |Q| |
---------

$