Vexed 是一款流行的益智游戏，有许多版本可用（其中一些是 GPL 自由软件）。非常适合小屏设备；版本可用于 Android、iOS 等。我在 PalmOS 平台上发现了它。
只是为了好玩，我想写一个求解器来解决 Vexed 级别。
Vexed 是一款方块滑动益智游戏。简而言之，以下是规则：
0）每个级别都是一个正方形网格，以不可通行的边界为界。在任何关卡中都会有一些实心方块，它们是无法通过的。有一些不同颜色的块；这些可以放在底部边框上，放在实心方块上，或者放在其他块（不同颜色）上。大多数级别是 8x8 或更小。
1) 你唯一能做的就是向左或向右滑动一个方块。每走一格算作一次移动。
2）有重力。如果在你滑动一个方块后，它不再停留在一个实心方块或另一个方块上，它会下落，直到它停留在另一个方块、一个实心方块或底部边框上。请注意，您永远无法再次抬起它。
3) 任何时候两个或多个相同颜色的方块接触，它们就会消失。请注意，链是可能的：如果支撑块消失，则支撑在其上的块会掉落，这可能导致更多相同颜色的块接触并因此消失。
4）目标是使所有块在最少的移动次数内消失。每个级别都有一个“标准分数”，它告诉您最少的移动次数。（在最初的 PalmOS 游戏中，“标准分数”不一定是最低的，但在我最近玩的 Android 版本中，它是最低的。）
以下是包含 PalmOS 版本游戏源代码的 SourceForge 项目：
http://sourceforge.net/projects/vexed/
我是一位经验丰富的软件开发人员，但我还没有在 AI 方面做过任何工作（寻路、解决问题等），所以我正在寻找建议，让我指出正确的方向。
目前，我可以看到我要追求的两个基本策略：
0) 只需编写一个蛮力求解器，可能是为了速度而用 C 语言，它会遍历每场比赛的所有可能解决方案，并返回所有解决方案的列表，最好的一个在前。这是一种合理的方法，还是可能的移动总数会使这太慢？我认为不存在任何大于 10x10 的关卡。
1) 学习一些 AI-ish 算法，并以聪明的方式应用它们来解决问题，可能使用 Python。
请注意，PalmOS Vexed 的源代码包括一个求解器。根据作者的说法，“求解器使用带有剪枝启发式的 A* 来寻找解决方案。”
http://www.scottlu.com/Content/Vexed.html
因此，我可以采用的一种策略是研究 A* 算法，然后研究现有求解器的 C++ 代码并尝试从中学习。
我将用 Python 和 C 标记对此进行标记，但如果您认为我应该使用其他东西，请进行销售宣传，我会考虑的！
这是来自“Variety 25 Pack”的一个级别的 ASCII 艺术；48级，“黑魔王”。我能够解决大多数关卡，但这个关卡让我很烦恼。这个级别的标准杆分数是 25 步，但我还没有解决它！
__________
|## g####|
|## # b##|
|## # p##|
|#g ###|
|bp ###|
|p# p g |
==========
在这张图片中，边框是下划线、竖线和等号字符。填充方块是“#”。空位是空格字符。彩色块是“g”（绿色）、“b”（蓝色）和“p”（紫色）。
顺便说一句，我可能会将求解器的输入文件格式设置为关卡的 ASCII 艺术，就像这样，但没有繁琐的线条边框字符。
感谢您的任何建议！
编辑：
我已经接受了一个答案。感谢给我答案的人。
这是一个半蛮力求解器。它没有使用 A*，但它正在削减无利可图的短枝。
它读入一个带有关卡数据的简单文本文件。字母是块，“_”（下划线）是空格，“#”是填充空格。
#!/usr/bin/env python
#
# Solve levels from the game Vexed.
from collections import Counter
import sys
level_blocks = set(chr(x) for x in range(ord('a'), ord('z')+1))
level_other = set(['_', '#'])
level_valid = set().union(level_blocks, level_other)
def prn_err(s='\n'):
sys.stderr.write(s)
sys.stderr.flush()
def validate_llc(llc):
if len(llc) == 0:
raise ValueError, "need at least one row of level data"
w = len(llc[0])
if w < 2:
raise ValueError, "level data not wide enough"
for i, row in enumerate(llc):
if len(row) != w:
s = "level data: row %d is different length than row 0"
raise ValueError, s % i
for j, ch in enumerate(row):
if ch not in level_valid:
s = "char '%c' at (%d, %d) is invalid" % (ch, i, j)
raise ValueError, s
class Info(object):
pass
info = Info()
info.width = 0
info.height = 0
info.spaces = set()
info.boom_blocks = set()
info.best_solution = 9999999999
info.title = "unknown"
class Level(object):
"""
Hold the state of a level at a particular move. self.parent points
to the previous state, from a previous move, so the solver builds a
tree representing the moves being considered. When you reach a solution
(a state where there are no more blocks) you can walk up the tree
back to the root, and you have the chain of moves that leads to that
solution."""
def __init__(self, x):
if isinstance(x, Level):
self.blocks = dict(x.blocks)
self.colors = dict(x.colors)
self.parent = x
self.s_move = ''
self.rank = x.rank + 1
else:
if isinstance(x, basestring):
# allow to init from a one-line "data" string
# example: "___;___;r_r"
x = x.split(';')
# build llc: list of rows, each row a list of characters
llc = [[ch for ch in row.strip()] for row in x]
llc.reverse()
info.width = len(llc[0])
info.height = len(llc)
validate_llc(llc)
# Use llc data to figure out the level, and build self.blocks
# and info.spaces. self.blocks is a dict mapping a coordinate
# tuple to a block color; info.spaces is just a set of
# coordinate tuples.
self.blocks = {}
for y in range(info.height):
for x in range(info.width):
loc = (x, y)
c = llc[y][x]
if c == '_':
# it's a space
info.spaces.add(loc)
elif c in level_blocks:
# it's a block (and the block is in a space)
self.blocks[loc] = c
info.spaces.add(loc)
else:
# must be a solid square
assert(c == '#')
# colors: map each block color onto a count of blocks.
self.colors = Counter(self.blocks.values())
# parent: points to the level instance that holds the state
# previous to the state of this level instance.
self.parent = None
# s_move: a string used when printing out the moves of a solution
self.s_move = 'initial state:'
# rank: 0 == initial state, +1 for each move
self.rank = 0
self.validate()
print "Solving:", info.title
print
sys.stdout.flush()
if self._update():
print "level wasn't stable! after updating:\n%s\n" % str(self)
def lone_color(self):
return any(count == 1 for count in self.colors.values())
def is_solved(self):
return sum(self.colors.values()) == 0
def validate(self):
if info.height == 0:
raise ValueError, "need at least one row of level data"
if info.width < 2:
raise ValueError, "level data not wide enough"
if self.lone_color():
raise ValueError, "cannot have just one of any block color"
for x, y in info.spaces:
if not 0 <= x < info.width or not 0 <= y < info.height:
raise ValueError, "Bad space coordinate: " + str(loc)
for x, y in self.blocks:
if not 0 <= x < info.width or not 0 <= y < info.height:
raise ValueError, "Bad block coordinate: " + str(loc)
if any(count < 0 for count in self.colors.values()):
raise ValueError, "cannot have negative color count!"
colors = Counter(self.blocks.values())
for k0 in [key for key in self.colors if self.colors[key] == 0]:
del(self.colors[k0]) # remove all keys whose value is 0
if colors != self.colors:
raise ValueError, "self.colors invalid!\n" + str(self.colors)
def _look(self, loc):
"""
return color at location 'loc', or '_' if empty, or '#' for a solid sqaure.
A bad loc does not raise an error; it just returns '#'.
"""
if loc in self.blocks:
return self.blocks[loc]
elif loc in info.spaces:
return '_'
else:
return '#'
def _lookxy(self, x, y):
loc = x, y
return self._look(loc)
def _board_mesg(self, mesg, loc):
x, y = loc
return "%s %c(%d,%d)" % (mesg, self._look(loc), x, y)
def _blocked(self, x, y):
return self._lookxy(x, y) != '_'
def _s_row(self, y):
return ''.join(self._lookxy(x, y) for x in xrange(info.width))
def data(self, ch_join=';'):
return ch_join.join(self._s_row(y)
for y in xrange(info.height - 1, -1, -1))
# make repr() actually print a representation
def __repr__(self):
return type(self).__name__ + "(%s)" % self.data()
# make str() work
def __str__(self):
return self.data('\n')
def _move_block(self, loc_new, loc_old):
self.blocks[loc_new] = self.blocks[loc_old]
del(self.blocks[loc_old])
def _explode_block(self, loc):
if loc in info.boom_blocks:
return
info.boom_blocks.add(loc)
color = self.blocks[loc]
self.colors[color] -= 1
def _try_move(self, loc, d):
x, y = loc
if not d in ('<', '>'):
raise ValueError, "d value '%c' invalid, must be '<' or '>'" % d
if d == '<':
x_m = (x - 1)
else:
x_m = (x + 1)
y_m = y
loc_m = (x_m, y_m)
if self._blocked(x_m, y_m):
return None # blocked, so can't move there
# Not blocked. Let's try the move!
# Make a duplicate level...
m = Level(self)
# ...try the move, and see if anything falls or explodes...
m._move_block(loc_m, loc)
m._update()
if m.lone_color():
# Whoops, we have only one block of some color. That means
# no solution can be found by considering this board.
return None
# finish the update
m.s_move = self._board_mesg("move:", loc) + ' ' + d
m.parent = self
return m
def _falls(self, loc):
x, y = loc
# blocks fall if they can, and only explode when at rest.
# gravity loop: block falls until it comes to rest
if self._blocked(x, y - 1):
return False # it is already at rest
while not self._blocked(x, y - 1):
# block is free to fall so fall one step
y -= 1
loc_m = (x, y)
self._move_block(loc_m, loc)
return True # block fell to new location
def _explodes(self, loc):
x, y = loc
exploded = False
color = self._look(loc)
# look left, right, up, and down for blocks of same color
for e_loc in [(x-1, y), (x+1, y), (x, y-1)]:
if e_loc in self.blocks and self.blocks[e_loc] == color:
self._explode_block(e_loc)
exploded = True
if exploded:
self._explode_block(loc)
return exploded
def _update(self):
c = 0
while True:
# TRICKY: sum() works on functions that return a bool!
# As you might expect, True sums as 1 and False as 0.
f = sum(self._falls(loc) for loc in self.blocks)
e = sum(self._explodes(loc) for loc in self.blocks)
for loc in info.boom_blocks:
del(self.blocks[loc])
info.boom_blocks.clear()
c += f + e
if (f + e) == 0:
# no blocks fell or exploded; board is stable, update is done
break
return c
def print_moves(self):
lst = [self]
a = self
while a.parent:
a = a.parent
lst.append(a)
lst.reverse()
for i, a in enumerate(lst):
if i:
print "Move %d of %d" % (i, len(lst) - 1)
print a.s_move
print a
print
def solve(self):
c = 0
seen = set()
solutions = []
seen.add(self.data())
q = []
if self.is_solved():
solutions.append(self)
else:
q.append(self)
while q:
a = q.pop(0)
# Show dots while solver is 'thinking' to give a progress
# indicator. Dots are written to stderr so they will not be
# captured if you redirect stdout to save the solution.
c += 1
if c % 100 == 0:
prn_err('.')
if a.rank > info.best_solution:
# We cannot beat or even match the best solution.
# No need to think any more about this possibility.
# Just prune this whole branch of the solution tree!
continue
for loc in a.blocks:
for d in ('<', '>'):
m = a._try_move(loc, d)
if not m or m.data() in seen:
continue
if m.is_solved():
if info.best_solution > a.rank:
print "\nnew best solution: %d moves" % m.rank
info.best_solution = a.rank
else:
print "\nfound another solution: %d moves" % m.rank
solutions.append(m)
else:
seen.add(m.data())
q.append(m)
print
print "Considered %d different board configurations." % c
print
solutions.sort(key=lambda a: a.rank)
for n, a in enumerate(solutions):
print "solution %d): %d moves" % (n, a.rank)
a.print_moves()
if not solutions:
print "no solutions found!"
def load_vex_file(fname):
with open(fname, "rt") as f:
s = f.next().strip()
if s != "Vexed level":
raise ValueError, "%s: not a Vexed level file" % fname
s = f.next().strip()
if not s.startswith("title:"):
raise ValueError, "%s: missing title" % fname
info.title = s[6:].lstrip() # remove "title:"
for s in f:
if s.strip() == "--":
break
return Level(f)
if __name__ == "__main__":
if len(sys.argv) == 1:
print "Usage vexed_solver <vexed_level_file.vex>"
sys.exit(1)
fname = sys.argv[1]
level = load_vex_file(fname)
level.solve()
这是一个示例级别文件：
Vexed level
title: 25-48, "Dark Lord"
--
##_f####
##_#_c##
##_#_p##
#f___###
cp___###
p#_p_f__
在我的电脑上，考虑到 14252 种不同的板配置，它几乎在 10 秒内就解决了“黑魔王”。我用 Python 2.x 而不是 Python 3 编写的，因为我想用 PyPy 试试这个，看看它有多快。
接下来我应该努力将 A* 应用于此。我想我可以制定一个指标，例如“将橙色块移向另一个橙色块而不是移开”并尝试将其计算在内。但我确实希望所有解决方案都能弹出，所以也许我已经完成了。（如果有三个解决方案都是最小移动数，我想看到所有三个。）
欢迎对这个 Python 程序发表评论。我写得很开心！
编辑：我确实用 PyPy 试过这个，但直到现在我才更新这个。在我使用 PyPy 的计算机上，求解器可以使用 CPython 在 10 秒内解决“黑魔王”关卡；PyPy 下降到 4 秒。很酷的部分是我可以看到JIT 启动时的加速：这个程序在工作时打印点，在 PyPy 下我可以看到点开始变慢，然后只是加速。PyPy 很漂亮。