イラストロジックをだいたい解けるプログラム
#
import array
class ImageBoard:
board=
x_size=0
y_size=0
def __init__(self,xs,ys):
self.x_size=xs
self.y_size=ys
for i in range(self.y_size):
line=[0]*self.x_size
self.board.append(line)
def dump(self):
for y in range(self.y_size):
for x in range(self.x_size):
if(self.board[y][x]==0):
print("?",end="")
elif(self.board[y][x]==1): #fill
print("#",end="")
else:
print("X",end="") #space
print("")
def get_rows(self,y):
return self.board[y]
def set_rows(self,y,row):
for i in range(x_size):
if(self.board[y][i]==0):
self.board[y][i]=row[i]
def get_cols(self,x):
ret=[0]*x_size
for i in range(y_size):
ret[i]=self.board[i][x]
return ret
def set_cols(self,x,col):
for i in range(y_size):
if(self.board[i][x]==0):
self.board[i][x]=col[i]
#
# 与えられた空白の数を隙間のに割り当てる
# 隙間の数の組み合わせを作る
# 1が黒、2が白
# 例）
# □■■□□■■□■■□
# 2,1,1,2,2,1,1,2,1,1,2
#
# yield を使うともっと簡潔に書けるかも
#
# num 割り振る値の合計値
# cell_cnt 割り振る場所の数
def combination_generator(num,cell_cnt):
ans=
max_num=num-cell_cnt
if(cell_cnt==1):
ans.append([num])
elif(cell_cnt==2):
for i in range(max_num+1):
ans.append([max_num+1-i,i+1])
else:
for i in range(1,max_num+2):
ans_list=combination_generator(num-i,cell_cnt-1)
for l in ans_list:
ans.append([i]+l)
return ans
#
# 列が指定の条件を満たしているか
# 0=未定 なら何でもよい
# その他は 1,2が一致している
#
#
def check_rows(target_cells,test_cells):
flag=True
for i in range(len(target_cells)):
if(target_cells[i]>0 and target_cells[i]!=test_cells[i]):
flag=False
return flag
#
#
# 両サイドのエッジは0 ~ 最大自由度
# セルの中身は両サイドの自由度を引いた後が最大、最低が隙間の数。
#
def make_fill_pattern(target_cells,clue):
match_patterns=
cell_cnt=len(target_cells) #長さ
num_cnt =len(clue) #数字の数
num_sum =sum(clue) #リストの数字の合計
if(cell_cnt==num_sum):
match_patterns.append([1]*cell_cnt)
elif(num_sum==0):
match_patterns.append([2]*cell_cnt)
else:
space_cnt=cell_cnt-(num_sum+num_cnt-1) #調整可能な空白
vacant_cell_cnt=num_cnt-1 #隙間の数
#print(cell_cnt,num_cnt,num_sum,space_cnt,vacant_cell_cnt)
if vacant_cell_cnt==0:#途中に空白がない場合
for lc in range(space_cnt+1):
rc=space_cnt-lc
candidate=[2]*lc+[1]*num_sum+[2]*rc
if check_rows(target_cells,candidate):
match_patterns.append(candidate)
else:
for lc in range(space_cnt+1): #左右の隙間を確保
for rc in range(space_cnt-lc+1):
patterns=
usable_space_cnt=cell_cnt-lc-rc-num_sum
space_patterns=combination_generator(usable_space_cnt,vacant_cell_cnt)
for p in space_patterns:
p.extend([0]) #ループの最後対策
candidate=[]
for m in clue:
candidate.extend([1]*m)
candidate.extend([2]*p.pop(0))
candidate=[2]*lc+candidate+[2]*rc #比較候補
if check_rows(target_cells,candidate):
match_patterns.append(candidate)
return match_patterns
#
# 1次元配列のtarget_cellsに対して、clue(ヒント)を満たす候補をすべて求めて比較
#候補が1つしかなければ決定
#全てセルで同じ結果になるのであれば、そのセルは決定
#縦のセルは1次元で横にして渡す
#
def think_by_line(target_cells,clue):
cell_cnt=len(target_cells)
if target_cells.count(0)==0:
return [0]*cell_cnt #この列は決定している
patterns=make_fill_pattern(target_cells,clue)
if len(patterns)==1:
fill_ptn=patterns[0]
else:
fill_ptn=[0]*cell_cnt
for p in patterns:
for i in range(cell_cnt):
if(fill_ptn[i]==0):
fill_ptn[i]=p[i]
elif(fill_ptn[i]!=p[i]):
fill_ptn[i]=3
for i in range(cell_cnt):
if( (target_cells[i]>0 and target_cells[i]!=fill_ptn[i]) or fill_ptn[i]==3):
fill_ptn[i]=0
return fill_ptn
#
# パズルを解く本体 上から下まで横一列を解いた後、左から右に縦1列を解く
# 一通りやって、変更したセルがなくなったら終了
# 30x30でも5回ぐらいで解ける
#
def solve_main(x_size,y_size,max_challenge):
for i in range(max_challenge):
chg=0
print( "%d times try "%(i+1))
for y in range(y_size):
line=ib.get_rows(y)
ret=think_by_line(line,row_clue[y])
ib.set_rows(y,ret)
chg += len(ret)-ret.count(0)
for x in range(0,x_size):
line=ib.get_cols(x)
ret=think_by_line(line,col_clue[x])
ib.set_cols(x,ret)
chg += len(ret)-ret.count(0)
if(chg==0):
return True
return False
if __name__ == "__main__":
#問題をここに書く
col_clue=[[2],[4],[6],[8],[8],[6],[4],[2]]
row_clue=[[2],[4],[6],[8],[8],[6],[4],[2]]
max_challenge=8
x_size=len(col_clue)
y_size=len(row_clue)
print(x_size,y_size)
ib=ImageBoard(x_size,y_size)
if(solve_main(x_size,y_size,max_challenge)):
print("Solved")
else:
print("Give Up!")
ib.dump()
