水玉潰しを解くスクリプトを書こうと思い立ちました。が、やたらと時間がかかります。かたっぱしから手を生成して、それをシミュレートするという力技なので、時間がかかるのは当然です。ラスト何か数手であっても数分かかったりします。何かヒューリスティックを考えないといけませんね。
def main():
pattern = [[0,4,4,0,0,0],
[0,0,0,0,0,0],
[2,0,0,0,0,0],
[3,0,0,0,0,0],
[3,0,0,0,0,0],
[0,0,0,0,0,0]]
solution, tank = solve(pattern, 13,13)
print solution, tankdef play(game, sequence=[]):
for x,y in sequence:
game.dropByUser(x,y)def solve(pattern, tank=10, limit=2):
tankMax = -1
solution = None
game = Game()
for currentLimit in xrange(1, limit+1):
print currentLimit
# for each sequence:
for seq in sequences(currentLimit):
# heuristics
if unsolvable(pattern, seq):
continue
# play game
game.init(pattern, tank)
play(game, seq)
# if solved and tank is larger than prev best,
# store tank and solution
if game.isSolved() and game.tank > tankMax:
solution = seq
tankMax = game.tank
if solution:
return solution, tankMax
return solution, tankMaxdef sequences(limit):
if limit==0:
yield []
return
for x in xrange(6):
for y in xrange(6):
for tmp in sequences(limit-1):
yield [(x,y)] + tmp
return_tmp_pattern = [[0 for x in range(6)] for y in range(6)]
def unsolvable(pattern, seq):
for y in xrange(6):
for x in xrange(6):
_tmp_pattern[y][x] = pattern[y][x]
for x,y in seq:
_tmp_pattern[y][x] += 1
if max([max(z) for z in _tmp_pattern]) < 5:
return True
else:
return False
class Game:
def __init__(self):
self.tank = 0
self.cells = {}
for y in xrange(6):
for x in xrange(6):
self.cells[x,y] = Cell(self)
self.splashes = []
self.chain = 0def init(self, pattern, tank=10):
for y in xrange(6):
for x in xrange(6):
self.cells[x,y].drop = pattern[y][x]
self.tank = tankdef dropByUser(self, x, y):
self.chain = 0
return self.drop(x, y)def drop(self, x, y):
self.tank -= 1
self.cells[x,y].growDrop()
while len(self.splashes) > 0:
s = self.splashes.pop(0)
s.move()
if s.alive:
self.splashes.append(s)def notifyCrash(self, cell):
self.chain += 1
if self.chain == 3:
self.tank += 1
self.chain = 0
for (x,y),value in self.cells.items():
if value==cell:
break
for dx,dy in [(1,0), (-1,0), (0,1), (0,-1)]:
self.splashes.append(Splash(self, x,y,dx,dy))def isSolved(self):
for c in self.cells.values():
if c.drop!=0:
return False
return Truedef __str__(self):
string = "tank: %d＼n" % self.tank
for y in xrange(6):
for x in xrange(6):
string += "%d " % self.cells[x,y].drop
string += "＼n"
return stringclass Cell:
def __init__(self, game):
self.game = game
self.drop = 0def growDrop(self):
self.drop += 1
if self.drop==5:
self.drop = 0
self.game.notifyCrash(self)class Splash:
def __init__(self, game, x, y, dx, dy):
self.x = x
self.y = y
self.dx = dx
self.dy = dy
self.game = game
self.alive = Truedef move(self):
self.x += self.dx
self.y += self.dy
if (self.x<0 or 5
self.alive = False
elif self.game.cells[self.x, self.y].drop > 0:
self.game.cells[self.x, self.y].growDrop()
self.alive = False
if __name__ == "__main__":
main()
