はじめに
縦横に仕切られたマス目を塗りつぶしてイラストを完成させる、お絵かきロジックというパズルがあります。詳しい説明はWikipediaに任せますので、ここでは簡単な説明を。縦横の各列に注目したとき、連続して塗りつぶすマス目が何個あるかという情報がヒントとして与えられます。ヒントをもとに「このマス目は必ず塗りつぶして良い」「このマス目は必ず塗りつぶされない」ということを徐々に確定させていくことで、イラストの全体像があぶりだされるというパズルです。
先日、興味本位でお絵かきロジックを解くプログラムを書いてみました。内容はGoogle Colabを使ってこちらから公開しています。この記事では、プログラムの内容を簡単に解説しようと思います。
まずは、この記事で出てくる用語の定義を少しだけしておきます。
- ボード マス目の集合。
- ヒント 塗りつぶされるマス目の数を表す数字。
パズルの入力・表示
このプログラムでは、パズルの入力から解の導出までを１つのクラスとして実装しています。なお、各マス目の状態は３通りの文字で表しています。
-
'w'マス目の中身が確定していない状態(white)。 -
'b'マス目が塗りつぶされた状態(black)。 -
'c'マス目が塗りつぶされないことが確定した状態(cross)。
内容は以下の通りです。
import copy
import time
import numpy as np
class IllustLogic:
def __init__(self, size, sample=False):
self.size = size
self.board = np.full([size, size], 'w')
self.str_w = '.'
self.str_c = '-'
self.str_b = 'o'
if sample:
self.hint_row = [[1], [1], [5], [1], [1]]
self.hint_col = [[1], [3], [1, 1, 1], [1], [1]]
else:
print('Input row numbers (split with spaces):')
self.hint_row = self.input_hint()
print('Input column numbers (split with spaces):')
self.hint_col = self.input_hint()
def input_hint(self):
ans = list()
for i in range(self.size):
hint_i = list(map(int, input().split()))
sum_i = sum(hint_i) + len(hint_i) - 1
if sum_i > self.size:
raise(Exception('Input numbers are too large.'))
ans.append(hint_i)
return ans
def convert_board_to_str(self):
board_str = copy.copy(self.board)
np.place(board_str, board_str == 'w', self.str_w)
np.place(board_str, board_str == 'c', self.str_c)
np.place(board_str, board_str == 'b', self.str_b)
ans = ''
ans += '+' + '-' * (self.size * 2) + '\n'
for i in range(self.size):
ans += '| ' + ' '.join(board_str[i, :]) + '\n'
return ans
def convert_hint_to_str(self, hint):
ans = '\n'.join([' '.join(map(str, h)) for h in hint])
return(ans)
def __str__(self):
ans = 'Board:\n'
ans += self.convert_board_to_str()
ans += '\n\nRow hints:\n'
ans += self.convert_hint_to_str(self.hint_row)
ans += '\n\nColumn hints:\n'
ans += self.convert_hint_to_str(self.hint_col)
return ans
# (後略)
パズルを入力するには、まずパズルが縦横いくつのマス目で構成されているかを
sizeとして指定します。
il1 = IllustLogic(size=5)
すると、標準入力が可能になりますので、ヒントである数字をスペース区切りで入力していきます。別の列のヒントを入力する際は改行を入れます。順番は、横方向のヒントの一番上の数字から下に向かって順に入力し、そのあとに縦方向のヒントの一番左の数字から右に向かって順に入力します。
> Input row numbers (split with spaces):
> 1
> 1
> 5
> 1
> 1
> Input column numbers (split with spaces):
> 1
> 3
> 1 1 1
> 1
> 1
入力したパズルをprint()すると、ボードの状態とヒントの一覧が表示されます。
まだどのマス目も中身が確定していない状態ですので、.で表示されています。
print(il1)
> Board:
> +----------
> | . . . . .
> | . . . . .
> | . . . . .
> | . . . . .
> | . . . . .
>
>
> Row hints:
> 1
> 1
> 5
> 1
> 1
>
> Column hints:
> 1
> 3
> 1 1 1
> 1
> 1
答えの導出方法
パズルを解くアルゴリズムは、以下の４段階で構成されています。
- 列ごとにマス目の塗りつぶし方をすべて列挙する
- 塗りつぶされる／されないことが確定したマス目の状態をボードに反映させる
- 各列で列挙されたマス目のパターンから、ボードの状態と矛盾するものを除去する
- 2-3を繰り返し、ボードの状態が変化しなくなったら終了
このプログラムはIllustLogicクラス内の関数で以下のように実装されています。
class IllustLogic:
#（中略）
def solve(self, does_print=True):
# 段階１
# 列ごとにマス目の塗りつぶし方をすべて列挙する
all_row_pattern = [self.create_all_pattern(h) for h in self.hint_row]
all_col_pattern = [self.create_all_pattern(h) for h in self.hint_col]
n_iter = 0
while True:
n_iter += 1
board_prev = copy.copy(self.board)
# 段階２－１
# 塗りつぶされる／されないことが確定したマス目を特定する
all_row_fixed = [self.find_intersect(p) for p in all_row_pattern]
all_col_fixed = [self.find_intersect(p) for p in all_col_pattern]
board_fixed_row = np.array(all_row_fixed)
board_fixed_col = np.array(all_col_fixed).transpose()
# 段階２－２
# 塗りつぶされる／されないことが確定したマス目をボードに反映する
new_board = copy.copy(board_fixed_row)
new_board[new_board == 'w'] = board_fixed_col[new_board == 'w']
self.board = copy.copy(new_board)
# 段階４
# ボードの状態が変化しなくなったら終了
if np.array_equal(self.board, board_prev):
print('Finished!')
return
# 途中経過を表示
if does_print:
print(f'iter={n_iter}')
print(self.convert_board_to_str())
# 段階３
# 各列で列挙されたマス目のパターンから、ボードの状態と矛盾するものを除去する
for i in range(self.size):
all_row_pattern[i] = [
p for p in all_row_pattern[i]
if self.compare_pattern(board=list(self.board[i, :]), pattern=p)]
all_col_pattern[i] = [
p for p in all_col_pattern[i]
if self.compare_pattern(board=list(self.board[:, i]), pattern=p)]
列ごとにマス目の塗りつぶし方をすべて列挙する手順１は、IllustLogicクラス内の以下の関数で実装されています。
class IllustLogic:
#（中略）
def combn_cell_pattern(self, n_cell, n_gap):
if n_cell == 0:
return [[0] * n_gap]
if n_gap == 1:
return [[n_cell]]
ans = []
for n_cell_next in range(n_cell + 1):
prev_ans = self.combn_cell_pattern(n_cell_next, n_gap - 1)
ans += [[n_cell - n_cell_next] + ans_i for ans_i in prev_ans]
return ans
def combn_cross_cell(self, hint):
n_cell = self.size - sum(hint) - len(hint) + 1
n_gap = len(hint) + 1
return self.combn_cell_pattern(n_cell, n_gap)
def create_all_pattern(self, hint):
n_cross = self.combn_cross_cell(hint)
ans = []
for i in range(len(n_cross)):
ans_i = []
for j in range(len(n_cross[i]) - 1):
if j > 0:
ans_i += ['c']
ans_i += ['c'] * n_cross[i][j]
ans_i += ['b'] * hint [j]
ans_i += ['c'] * n_cross[i][-1]
ans.append(ans_i)
return ans
マスを塗りつぶすパターンを列挙する関数は、次の考え方で実装されています。例えば一辺が15マスのパズルで、ある列のヒントが(3, 1, 2)であったとき、その列には塗りつぶすマスと塗りつぶさないマスが以下の配置で並びます。
- ０個以上 の 塗りつぶさないマス
- ３個 の 塗りつぶすマス
- １個以上 の 塗りつぶさないマス
- １個 の 塗りつぶすマス
- １個以上 の 塗りつぶさないマス
- ２個 の 塗りつぶすマス
- ０個以上 の 塗りつぶさないマス
この時、まだ配置が決まっていない７マス (=15－3－1－1－1－2) を、４か所の塗りつぶさないマスの塊に振り分ける方法を列挙すると、可能な全てのマスの配置が分かります。この列挙はcombn_cell_pattern関数として実装されています。この関数は再帰的な構造をしており、本来は動的計画法などで効率化できるはずですが、今回の場合は計算にさほど時間がかからないこともあり、そのままにしておきました。引数のn_cellとn_gapはそれぞれ、振り分けるマスの数と、振り分けられる場所の数に対応しています。
combn_cross_cell関数は、ある列のヒントの情報をcombn_cell_pattern関数の引数に変換しています。また、create_all_pattern関数は、以上で得られた結果を、実際にありうるマス目の並びのリストに変換します。
段階２ではまず、段階１で得られたありうるマス目の並びを全て比較し、塗りつぶされる／されないことが確定したマス目をfind_intersect関数で特定します。その後、塗りつぶされる／されないことが確定したマス目をボードに書き込んでいます。
class IllustLogic:
#（中略）
def find_intersect(self, pattern):
fixed_pat = ['w'] * self.size
for i in range(self.size):
pat_i = [p[i] for p in pattern]
uniq_pat_i = list(set(pat_i))
if len(uniq_pat_i) == 1:
fixed_pat[i] = uniq_pat_i[0]
return fixed_pat
段階３では、段階２で書き込まれたボードと、リストアップされているマス目の並びをcompare_pattern関数で比較し、矛盾するものは排除します。
class IllustLogic:
#（中略）
def compare_pattern(self, board, pattern):
pattern0 = ['w' if b == 'w' else p for b, p in zip(board, pattern)]
return board == pattern0
実際に解かせると
実際にパズルを解かせてみると、このように出力されます。.は状態が確定していないマス、oは塗りつぶされたマス、-は塗りつぶされないことが確定したマスを表しています。手順２が行われるごとにボードの状態が出力され、徐々に絵が確定していく様が分かります。
Creating all patterns...
Drawing board...
iter=1
+----------
| . . o . .
| . . - . .
| o o o o o
| . . - . .
| . . o . .
iter=2
+----------
| - - o - -
| - . - - -
| o o o o o
| - . - - -
| - - o - -
iter=3
+----------
| - - o - -
| - o - - -
| o o o o o
| - o - - -
| - - o - -
Finished!
試しに30マス×30マスのパズルを解かせてみたところ、難易度の高いものでも５分程で答えを表示することができました。当実装方法には改善点も多くありますが、一つの基礎的な解き方を提示できたとは思います。なお、当コードはいかなる用途でも自由に活用して頂いて構いません。もしプログラミングの勉強に活用して頂けたり、より効率的な解法を提示して頂ければ嬉しいです。