How to make an efficient solver for Puzzle Number 9

Question

There's this game on iOS and Andriod called Puzzle Number 9 (I'm in no way affiliated with the creators). You start with a 3x3 grid where the numbers 1 to 9 are placed randomly on the board. Then you combine adjacent numbers (trace a path) to add up to 9. The final node in the path becomes a 9 and all the other numbers increase by 1. You combine the same multiples of 9 together where the end node becomes twice the number and the starting node goes back to one. For example, if you start with

1 2 3
5 4 6
7 8 9 

you can start with 2-3-4 and end up with

1 3 4
5 9 6
7 8 9

and then combine the two 9's

1 3 4
5 1 6
7 8 18

The goal of the game is to reach 1152. Basically it's like 2048 but without stochastic elements. The game ends when you run out of numbers that will sum to 9, for example

8 7 6
5 5 5
9 1 72

I wrote a simple depth-first search on python it works for some puzzles but I run out of memory for other puzzles:

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)

How do you make this more efficient? If not that, what would be a good heuristic for an informed search? I was thinking of taking the absolute difference of the average of the numbers on the board from a certain number but what would be a good number?

Answer 1

The goal of the game is to reach 1152

I've managed to do it! Here is a sample output of the search. On the first row the three numbers are: score of the state, the depth of the graph, and the maximum element from the matrix. On the next three is the matrix itself:

...
-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 
...

As you can see in order to get score 1152 you have to explore pretty deep. Take also into account that the branching factor is very big and you could see that the problem is challenging. You have to do ~250 moves in order to get the score 1152. Assuming that it takes you 10 seconds per move you'll be playing the game for 40min!!!

What I did was I associated a score for each node/state and during the exploration I only kept the top 1000 nodes/states. This ensures that we explore only relevant nodes. So what was left was engineering the score functions/heuristics. Here what score functions I've tried:

• maximal element from the matrix
• depth of the node
• sum of the elements in the matrix
• score which tells for how many elements divisible by 9 the is neighboring element which is also divisible by 9
• number of distinct elements in the matrix
• number of distinct elements in the matrix above 9
• number of distinct elements in the matrix below 2
• score which tells for how many elements divisible by 9 the is neighboring element which is also divisible by 9 and its twice smaller

Using simple heuristics you could build up more complex. What I ended up with is the heuristics which is a sum of only the first and the last in the above-mentioned list. Picking more restrictive heuristics messes up the search. Here's the code (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)

---

What's next?

Since the procedure is not very performant ( it takes ~ 1 min to find the answer) one could try to find better heuristics which would be useful for the search. It seems that they should be very loose trying to model the requirement otherwise they would mess up the search.