2018年11月17日土曜日

開発環境

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

コード(Emacs)

Python 3

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


def no_conflicts(board, current):
    for i in range(current):
        if board[i] == board[current] or \
           current - i == abs(board[current] - board[i]):
            return False
    return True


def print_board(board, n=8):
    board_nn = [[' ' for _ in range(n)]
                for _ in range(n)]
    for i, j in enumerate(board):
        board_nn[j][i] = 'Q'

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


def eight_queens(max_board_count, n=8):
    if max_board_count == 0:
        return
    board = [-1] * n
    count = 0
    for i in range(n):
        board[0] = i
        for j in range(n):
            board[1] = j
            if not no_conflicts(board, 1):
                continue
            for k in range(n):
                board[2] = k
                if not no_conflicts(board, 2):
                    continue
                for l in range(n):
                    board[3] = l
                    if not no_conflicts(board, 3):
                        continue
                    for m in range(n):
                        board[4] = m
                        if not no_conflicts(board, 4):
                            continue
                        for o in range(n):
                            board[5] = o
                            if not no_conflicts(board, 5):
                                continue
                            for p in range(n):
                                board[6] = p
                                if not no_conflicts(board, 6):
                                    continue
                                for q in range(n):
                                    board[7] = q
                                    if no_conflicts(board, 7):
                                        print_board(board)
                                        count += 1
                                        if count == max_board_count:
                                            return


if __name__ == '__main__':
    for count in range(5):
        print(f'最大{count}個の解')
        eight_queens(count)

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

$ ./sample1.py
最大0個の解
最大1個の解
-----------------
|Q| | | | | | | |
-----------------
| | | | | | |Q| |
-----------------
| | | | |Q| | | |
-----------------
| | | | | | | |Q|
-----------------
| |Q| | | | | | |
-----------------
| | | |Q| | | | |
-----------------
| | | | | |Q| | |
-----------------
| | |Q| | | | | |
-----------------

最大2個の解
-----------------
|Q| | | | | | | |
-----------------
| | | | | | |Q| |
-----------------
| | | | |Q| | | |
-----------------
| | | | | | | |Q|
-----------------
| |Q| | | | | | |
-----------------
| | | |Q| | | | |
-----------------
| | | | | |Q| | |
-----------------
| | |Q| | | | | |
-----------------

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

最大3個の解
-----------------
|Q| | | | | | | |
-----------------
| | | | | | |Q| |
-----------------
| | | | |Q| | | |
-----------------
| | | | | | | |Q|
-----------------
| |Q| | | | | | |
-----------------
| | | |Q| | | | |
-----------------
| | | | | |Q| | |
-----------------
| | |Q| | | | | |
-----------------

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

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

最大4個の解
-----------------
|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| |
-----------------
| |Q| | | | | | |
-----------------
| | | |Q| | | | |
-----------------

$

0 コメント:

コメントを投稿

関連コンテンツ