## 2018年12月11日火曜日

### Algorithm - Python - 中庭にタイルを敷く(欠損正方形、L字型のタイル、リスト内包表記、再帰分割統治探索)

コード(Emacs)

Python 3

```#!/usr/bin/env python3
import random

quads = [(row // 4, col // 4) for row, col in missing_tiles]
return False
return True

def is_tromino(missing_tiles: list):
for i, tile1 in enumerate(missing_tiles):
tile1_row, tile1_col = tile1
for j, tile2 in enumerate(missing_tiles):
if i == j:
continue
tile2_row, tile2_col = tile2
for k, tile3 in enumerate(missing_tiles):
if i == k or j == k:
continue
tile3_row, tile3_col = tile3
if (
tile2_row - tile1_row == 1 and tile1_col == tile2_col and
tile2_row == tile3_row and tile3_col - tile2_col == 1
) or (
tile1_row == tile2_row and tile1_col - tile2_col == 1 and
tile3_row - tile2_row == 1 and tile2_col == tile3_col
) or (
tile1_row - tile2_row == 1 and tile1_col == tile2_col and
tile2_row == tile3_row and tile2_col - tile3_col == 1
) or (
tile1_row == tile2_row and tile2_col - tile1_col == 1 and
tile2_row - tile3_row == 1 and tile2_col == tile3_col
):
return True
return False

def four_tiles_missing_yard(n: int, tiles_missing: list) -> bool:
if n <= 1:
return True
# 4つの欠損正方形が4つの異なる象限にあるか
return True
# 4つのうち3つにトロミノが当てはまるか
for i, _ in enumerate(tiles_missing):
if is_tromino(tiles_missing[:i] + tiles_missing[i + 1:]):
print('tromino')
return True
return False

def print_yard(n, missing_tiles) -> None:
for row in range(2 ** n):
for col in range(2 ** n):
if (row, col) in missing_tiles:
print(' ', end='')
else:
print('X', end='')
print()

if __name__ == '__main__':
print(four_tiles_missing_yard(3, [(0, 0), (0, 7), (7, 0), (7, 7)]))
print(four_tiles_missing_yard(3, [(0, 0), (0, 1), (1, 0), (7, 7)]))
for _ in range(10):
n = random.randrange(2, 5)
tiles = [(row, col)
for row in range(2 ** n)
for col in range(2 ** n)]
missing_tiles = random.sample(tiles, k=4)
print(n, missing_tiles)
print_yard(n, missing_tiles)
print(four_tiles_missing_yard(n, missing_tiles))
print()
```

```\$ ./sample1.py
True
tromino
True
4 [(5, 3), (10, 2), (3, 7), (12, 3)]
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXX XXXXXXXX
XXXXXXXXXXXXXXXX
XXX XXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XX XXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXX XXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
True

3 [(5, 6), (1, 7), (3, 4), (3, 2)]
XXXXXXXX
XXXXXXX
XXXXXXXX
XX X XXX
XXXXXXXX
XXXXXX X
XXXXXXXX
XXXXXXXX
False

2 [(0, 3), (2, 2), (2, 0), (3, 3)]
XXX
XXXX
X X
XXX
False

2 [(0, 0), (3, 2), (2, 0), (2, 1)]
XXX
XXXX
XX
XX X
False

2 [(3, 2), (0, 0), (1, 1), (1, 0)]
XXX
XX
XXXX
XX X
tromino
True

3 [(3, 2), (2, 1), (0, 1), (4, 1)]
X XXXXXX
XXXXXXXX
X XXXXXX
XX XXXXX
X XXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
False

2 [(1, 1), (3, 2), (3, 0), (2, 1)]
XXXX
X XX
X XX
X X
False

4 [(12, 2), (8, 3), (11, 11), (12, 15)]
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXX XXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXX XXXX
XX XXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
True

4 [(9, 0), (2, 8), (0, 1), (9, 15)]
X XXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXX XXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
True

3 [(1, 6), (4, 2), (1, 0), (7, 3)]
XXXXXXXX
XXXXX X
XXXXXXXX
XXXXXXXX
XX XXXXX
XXXXXXXX
XXXXXXXX
XXX XXXX
False

\$
```