## 2018年12月7日金曜日

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

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

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