iOS 和 Andriod 上有一款名为Puzzle Number 9 的游戏(我与创作者没有任何关系)。您从 3x3 网格开始，其中数字 1 到 9 随机放置在棋盘上。然后将相邻数字(追踪一条路径)组合起来，加起来为 9。路径中的最后一个节点变为 9，所有其他数字增加 1。将 9 的相同倍数组合在一起，其中结束节点变为数字的两倍并且起始节点回到一个。例如，如果您开始于

1 2 3
5 4 6
7 8 9 

你可以从 2-3-4 开始到结束

1 3 4
5 9 6
7 8 9

然后将两个9组合起来

1 3 4
5 1 6
7 8 18

游戏的目标是达到 1152。基本上它就像 2048，但没有随机元素。例如，当您用完总和为 9 的数字时游戏结束

8 7 6
5 5 5
9 1 72

我在 python 上写了一个简单的深度优先搜索，它适用于一些谜题，但我用完了其他谜题的内存:

import sys
import Queue

conf = "213 547 689"
grid1 = []
for y in conf.split():
    for x in y:
        grid1.append(int(x))

a = []
explored = set()
sol = Queue.LifoQueue()

def tostr(node):
    s = ''
    for i in range(0,9):
        s += str(node[i]) + ' '
    return s

def printsol():
    while not sol.empty():
        print sol.get()        

def same(x, y, grid):
    for n in neighbors(y):
        ng = grid[:]
        if grid[n] == x and n != y:
            if x == 576:
                printsol()
                sys.exit()
            ng[n] = 2*x
            ng[y] = 1
            sol.put(tostr(ng))
            same(2*x, n, ng)
            solve(ng, grid)
            sol.get()
            ng[n] = 1
            ng[y] = 2*x
            sol.put(tostr(ng))
            same(2*x, y, ng)
            solve(ng, grid)
            sol.get()

##succeeding functions are edited versions of Boggle solver from http://stackoverflow.com/questions/746082/how-to-find-list-of-possible-words-from-a-letter-matrix-boggle-solver
def solve(grid2, grid1):
    for i in range(0,9):
        if grid2[i] < 9 and tostr(grid2) not in explored:
            for result in extending(grid2[i], (i,), grid2):
                newgrid = grid2[:]
                y = len(result) - 1
                for j in range(0, y):
                    newgrid[result[j]] += 1
                newgrid[result[y]] = 9
                sol.put(tostr(newgrid))
                if tostr(newgrid) not in explored:
                    same(9, result[y], newgrid)
                    solve(newgrid, grid2)
                sol.get()
    explored.add(tostr(grid2))

def extending(add, path, grid2):
    if add == 9:
        yield path
    for n in neighbors(path[-1]):
        if n not in path:
            add1 = add + grid2[n]
            if add1 <= 9:
                for result in extending(add1, path + (n,), grid2):
                    yield result

def neighbors(n):
    for nx in range(max(0, n%3-1), min(n%3+2, 3)):
        for ny in range(max(0, n/3-1), min(n/3+2, 3)):
            yield ny*3+nx

sol.put(tostr(grid1))
solve(grid1, grid1)

如何提高效率？如果不是那样，什么是用于知情搜索的良好启发式方法？我正在考虑取板上数字的平均值与某个数字的绝对差，但什么是好的数字？

最佳答案

The goal of the game is to reach 1152

我已经设法做到了!这是搜索的示例输出。第一行的三个数字是:状态得分、图的深度和矩阵中的最大元素。接下来的三个是矩阵本身:

...
-577 246 576
  36  288    9 
   1    1  576 
 144   36   72 

-577 245 576
  36  288   18 
  18    1  576 
 144    9   72 

-577 249 576
   1  288    9 
   1  288  576 
   1    1    1 

-577 245 576
  36  288    1 
  18   18  576 
 144    9   72 

-577 250 576
   1    1    9 
   1  576  576 
   1    1    1 

-1153 251 1152
   1    1    9 
   1    1 1152 
   1    1    1 

-1153 251 1152
   1    1    9 
   1 1152    1 
   1    1    1 

-577 250 576
   1  576    9 
   1    1  576 
   1    1    1 

-1153 251 1152
   1    1    9 
   1    1 1152 
   1    1    1 

-1153 251 1152
   1 1152    9 
   1    1    1 
   1    1    1 
...

如您所见，为了获得 1152 的分数，您必须深入探索。还要考虑到分支因子非常大，您会发现问题具有挑战性。您必须完成 ~250 步才能获得 1152 的分数。假设您每次移动需要 10 秒，您将玩 40 分钟!!!

我所做的是为每个节点/状态关联一个分数，在探索期间我只保留前 1000 个节点/状态。这确保我们只探索相关节点。 所以剩下的就是设计评分函数/启发式方法。这是我尝试过的评分功能:

• 矩阵中的最大元素
• 节点深度
• 矩阵中元素的总和
• score 表示有多少元素可以被 9 整除，相邻元素也可以被 9 整除
• 矩阵中不同元素的数量
• 9以上矩阵中不同元素的个数
• 2以下矩阵中不同元素的数量
• score 表示有多少元素可以被 9 整除，相邻元素也可以被 9 整除并且它的两倍小

使用简单的启发式方法，您可以构建更复杂的方法。我最终得到的是启发式方法，它只是上述列表中第一个和最后一个的总和。选择更具限制性的启发式算法会使搜索变得困惑。这是代码(python 3):

import random
from queue import PriorityQueue


dx = [0,  0, -1, -1, -1,  1, 1, 1]
dy = [-1, 1, -1,  0,  1, -1, 0, 1]


class State:
    def __init__(self, a, depth):
        self.depth = depth
        if len(a) == 9:
            self.a = (tuple(a[:3]), tuple(a[3:6]), tuple(a[6:]))
        if len(a) == 3:
            self.a = tuple(map(tuple, a))

    @staticmethod
    def check(i):
        return 0 <= i < 3

    def get_9_moves(self):
        ans = []
        for i in range(3):
            for j in range(3):
                if self.a[i][j] % 9 == 0:

                    for k in range(len(dx)):
                        ni, nj = i + dx[k], j + dy[k]
                        if State.check(ni) and State.check(nj):
                            if self.a[ni][nj] % 9 == 0 and \
                               self.a[i][j] == self.a[ni][nj]:
                                ans.append(((i, j), (ni, nj)))
        return ans

    def get_sum_moves_rec(self, i, j, cur_sum, cur_cells, ans):
        if cur_sum > 9:
            return
        if cur_sum == 9 and len(cur_cells) > 1:
            ans.append(tuple(cur_cells))
        for k in range(len(dx)):
            ni, nj = i + dx[k], j + dy[k]
            pair = (ni, nj)
            if self.check(ni) and self.check(nj) and pair not in cur_cells:
                cur_cells.append(pair)
                self.get_sum_moves_rec(ni, nj, cur_sum + self.a[ni][nj],  cur_cells, ans)
                cur_cells.pop()

    def get_sum_moves(self):
        ans = []
        for i in range(3):
            for j in range(3):
                self.get_sum_moves_rec(i, j, self.a[i][j], [(i, j)], ans)
        return ans

    def get_neighbours(self):
        neighbours = []
        moves = self.get_sum_moves()
        for move in moves:
            a = list(map(list, self.a))
            for i in range(len(move)):
                x, y = move[i]
                if i == len(move)-1:
                    a[x][y] = 9
                else:
                    a[x][y] += 1
            neighbours.append(State(a, self.depth+1))
        moves = self.get_9_moves()
        for move in moves:
            a = list(map(list, self.a))
            a[move[0][0]][move[0][1]] = 1
            a[move[1][0]][move[1][1]] *= 2
            neighbours.append(State(a, self.depth+1))
        return neighbours

    def get_value(self):
        return max(map(max, self.a))

    # 576
    def get_score0(self):
        return -self.get_value()

    def get_score1(self):
        ans = 0
        for i in range(3):
            for j in range(3):
                if self.a[i][j] % 9 == 0:
                    ans += 1
        return ans

    # 36
    def get_score2(self):
        ans = 0
        for i in range(3):
            for j in range(3):
                if self.a[i][j] < 9:
                    ans += 1
        return ans

    # achieves 1152 but rather slow
    def get_score3(self):
        return -self.depth

    # 36
    def get_score4(self):
        ans = 0
        for i in range(3):
            for j in range(3):
                if self.a[i][j] == 1:
                    ans += 1
        return ans

    # 288
    def get_score5(self):
        return -sum(map(sum, self.a))

    def get_score6(self):
        t = []
        for i in range(3):
            for j in range(3):
                if self.a[i][j] % 9 == 0:
                    t.append((self.a[i][j], (i, j)))
        t.sort(reverse=True)
        ans = 0
        for i in range(len(t) - 1):
            pairi = t[i][1]
            pairj = t[i+1][1]

            if abs(pairi[0]-pairj[0]) <= 1 and abs(pairi[1]-pairj[1]) <= 1:
                ans += 1
            break
        return -ans

    def get_score7(self):
        t = []
        for i in range(3):
            for j in range(3):
                if self.a[i][j] % 9 == 0:
                    t.append(self.a[i][j])
        t.sort(reverse=True)
        ans = 0
        for i in range(len(t) - 1):

            if t[i] // t[i+1] == 2:
                ans += 1
            break
        return -ans

    def get_score8(self):
        t = []
        for e in self.a:
            t.extend(e)
        return len(list(filter(lambda x: x >= 9,t)))

    def get_score9(self):
        t = []
        for e in self.a:
            t.extend(e)
        return len(list(filter(lambda x: x <= 2,t)))

    def get_score10(self):
        t = []
        for e in self.a:
            t.extend(e)
        return len(set(filter(lambda x: x >= 9,t)))



    def get_score_mix(self):
        # achieves 1152
        return self.get_score0() + self.get_score6()

    def __repr__(self):
        ans = ''
        for i in range(3):
            for j in range(3):
                ans += '{0:4d} '.format(self.a[i][j])
            ans += '\n'
        return ans

    def __hash__(self):
        return  hash(self.a)

    def __lt__(self, other):
        # hash(self) < hash(other)
        pass


class Solver:

    @staticmethod
    def strategy1(s):
        visited = set()
        while True:
            # print(s)
            neighbours = s.get_neighbours()
            if len(neighbours) == 0:
                break
            ns = None
            for i in range(30):
                ns = random.choice(neighbours)
                if not ns in visited:
                    s = ns
                    break
            if ns is None:
                break
        print(s.get_value())

    @staticmethod
    def strategy2(s):
        visited = set()
        max_depth = 6
        max_value = 0
        calls = 0

        def dfs(state, depth):
            # print(state)
            nonlocal max_value, calls

            calls += 1
            if depth > max_depth:
                return
            if state in visited:
                return
            visited.add(state)
            max_value = max(max_value, s.get_value())

            for new_state in state.get_neighbours():
                dfs(new_state, depth + 1)

        dfs(s, 0)
        print(max_value)
        print(calls)

    @staticmethod
    def strategy3(s):

        visited = set()
        pq = PriorityQueue(maxsize=1000)
        pq.put((0, s))
        visited.add(s)
        max_value = 0

        while not pq.empty():
            score, state = pq.get()
            # print(' score0  score1  score2  score3  score4  score5  score6  score7  score8  score9 score10')
            # print('{0:7d} {1:7d} {2:7d} {3:7d} {4:7d} {5:7d} {6:7d} {7:7d} {8:7d} {9:7d} {10:7d}'.format(state.get_score0(), state.get_score1(), state.get_score2(),
            #                                                                                              state.get_score3(), state.get_score4(), state.get_score5(),
            #                                                                                              state.get_score6(), state.get_score7(), state.get_score8(),
            #                                                                                              state.get_score9(), state.get_score10()))
            print(score, state.depth, state.get_value())
            print(state)
            max_value = max(max_value, state.get_value())

            for new_state in state.get_neighbours():
                # print(random.randint(0, 10))
                if new_state not in visited:
                    visited.add(new_state)
                    pq._put((new_state.get_score_mix(), new_state))
        print(max_value)


start = list(range(1, 10))
random.shuffle(start)
s = State(start, 0)
Solver.strategy3(s)
# s  = State([1,    1,   18, 18,   18,   36, 18 ,  18,    2  ], 0)
# print(s)
#
# for n in s.get_neighbours():
#     print(n)

下一步是什么？

由于该过程的性能不是很好(找到答案大约需要 1 分钟)，因此可以尝试找到对搜索有用的更好的启发式方法。看起来他们应该非常宽松地尝试对需求建模，否则他们会搞砸搜索。

关于python - 如何为第 9 题制作一个高效的解算器，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33035471/