## 2018年11月17日土曜日

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

コード(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)
```

```\$ ./sample1.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| | | | |
-----------------
| | | | | |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| | | | | | |
-----------------
| | | | |Q| | | |
-----------------
| | |Q| | | | | |
-----------------

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

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

\$
```