## 2018年11月18日日曜日

### 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(location=[-1, 4, -1, -1, -1, -1, -1, 0], n=8):
# 生成してから比較
board = [-1] * n
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):
is_equal = True
for i, col in enumerate(location):
if col != -1 and col != board[i]:
is_equal = False
break
if is_equal:
print_board(board)

if __name__ == '__main__':
import random
indices = range(8)
locs = range(-1, 8)
eight_queens()
for _ in range(5):
location = [-1] * 8
i, j = random.choices(indices, k=2)
location[i], location[j] = random.choices(locs, k=2)
print(location)
eight_queens(location)
for _ in range(5):
location = [-1] * 8
i, j, k = [random.randrange(8) for _ in range(3)]
location[i] = random.randrange(8)
location[j] = random.randrange(8)
location[k] = random.randrange(8)
print(location)
eight_queens(location)
```

```\$ ./sample2.py
-----------------
| | | | | | | |Q|
-----------------
| | |Q| | | | | |
-----------------
|Q| | | | | | | |
-----------------
| | | | | |Q| | |
-----------------
| |Q| | | | | | |
-----------------
| | | | |Q| | | |
-----------------
| | | | | | |Q| |
-----------------
| | | |Q| | | | |
-----------------

[4, -1, 5, -1, -1, -1, -1, -1]
-----------------
| | | |Q| | | | |
-----------------
| |Q| | | | | | |
-----------------
| | | | | | | |Q|
-----------------
| | | | | |Q| | |
-----------------
|Q| | | | | | | |
-----------------
| | |Q| | | | | |
-----------------
| | | | |Q| | | |
-----------------
| | | | | | |Q| |
-----------------

[-1, -1, -1, 3, -1, 5, -1, -1]
[5, -1, -1, -1, -1, -1, -1, 5]
[-1, -1, -1, 6, 2, -1, -1, -1]
-----------------
| | | | | | | |Q|
-----------------
| |Q| | | | | | |
-----------------
| | | | |Q| | | |
-----------------
| | |Q| | | | | |
-----------------
|Q| | | | | | | |
-----------------
| | | | | | |Q| |
-----------------
| | | |Q| | | | |
-----------------
| | | | | |Q| | |
-----------------

[-1, -1, 2, -1, -1, -1, 4, -1]
[-1, 6, -1, 1, -1, -1, -1, 0]
[-1, -1, -1, 0, 0, -1, -1, -1]
[7, -1, -1, 1, -1, -1, -1, -1]
[-1, -1, -1, 2, -1, -1, -1, 0]
-----------------
| | | | | | | |Q|
-----------------
| |Q| | | | | | |
-----------------
| | | |Q| | | | |
-----------------
|Q| | | | | | | |
-----------------
| | | | | | |Q| |
-----------------
| | | | |Q| | | |
-----------------
| | |Q| | | | | |
-----------------
| | | | | |Q| | |
-----------------

[4, -1, -1, -1, -1, 1, 0, -1]
\$
```