Better algorithm for determining sequence of moves needed to reach a success state in game

Question

I have been playing simple game that I have been attempting to solve recently.

The game is as follows:

There are 81 squares of different colors on a 9x9 grid. For each square, we may consider its four neighbors in the up, down, left, or right direction. If two or more neighboring squares are the same color, you have the option to click on those squares to eliminate them.

The "gap" left by the eliminated squares will be filled by the rule: the remaining squares shift down first if there are any vertical gaps, and then to the left if there are any horizontal gaps.

A success state is when you have eliminated all 81 squares. A failure state is when there are squares remaining on the board that you cannot click (i.e. no remaining square has a neighbor of the same color). A game state will refer to any intermediate state between and including when we begin with 81 squares and proceed to either a success or failure state.

My current strategy and program involve determining all possible options of a game state by running a BFS to see which squares are connected. Then, I randomly choose any valid option (we can think of options as a list of coordinates we can click on) and simulate the result until I hit a failure state or a success state.

Each sequence of random choices is recorded and stored in a list. If I hit a failure state, I backtrack a random number of steps back and continue the stimulation. If there are enough failures or dead ends, I start over entirely.

Here is my implementation of my strategy. The program works by first configuring a picture of the starting game state from the image_grid.py file, specified in the selected_image variable (pictures are stored in the imgs folder). After selecting the desired picture, one can run the refactored_game_solution.py and the program will work to determine a sequence that leads to a successful state. For instance, for the image "sample3.png", the sequence that was determined after running was:

Note that the coordinate system is (-y,x). For example, (6,6) means go down 7 spaces and to the right 7 spaces and click on this square.

I have been running into problems when there are more colors, such as 6 colors instead of 2 colors in that the program does not seem to finish solving ever.

Thus, I am wondering if there is a better way to approach this (potentially an algorithm?) than random brute-forcing and if there is a way to determine if a beginning game state is solvable.

Thanks for reading through.

Answer 1

I actually thought this was a fun game, so I wrote a quick solution that:

• defines the game so you can play it
• solves the game by building a tree of all possible moves (without duplicates)
• tells you what the minimum number of needed moves for a game is and shows you the resulting steps (for one of the possible solutions)

Edit: the first version I posted actually didn't remove empty columns and allowed 1 block moves - so I updated the answer here, same main idea though.

import random

# plays and solves http://g.fromgame.com/game/13/


class Game:
    def __init__(self, width, height, colours=2):
        self.width = width
        self.height = height
        self.colours = colours
        self.board = [[0 for __ in range(width)] for __ in range(height)]

    def generate(self, seed=0):
        # very naive way to generate a board,
        # heavily biased towards horizontal runs, not really important
        random.seed(seed)
        self.board = []
        while len(self.board) < self.width * self.height:
            self.board.extend([random.randint(0, self.colours)] * random.randint(1, self.width // 2))
        self.board = [self.board[i*self.width:(i+1)*self.width] for i in range(self.height)]
        self.drop()

    def drop(self):
        # simply gravity, keeps dropping blocks until they are all at the 'bottom'
        dropped = True
        while dropped:
            dropped = False
            for lower, above in zip(reversed(self.board), list(reversed(self.board))[1:]):
                for i in range(len(lower)):
                    if lower[i] == 0 and above[i] != 0:
                        lower[i] = above[i]
                        above[i] = 0
                        dropped = True
        # move columns to the left, leaving no empties
        rc = [i for i, c in enumerate(self.board[-1]) if c == 0]
        self.board = [[c for i, c in enumerate(line) if i not in rc] + [0 for __ in range(len(rc))] for line in self.board]

    def copy(self):
        # returns a completely new copy of this game
        game = self.__class__(self.width, self.height, self.colours)
        game.board = [line.copy() for line in self.board]
        return game

    def print(self):
        for line in self.board:
            print(''.join(map(str,line)))

    def get_move(self, start_x, start_y):
        # returns all the pairs x, y that would be removed if the block at x, y is removed
        if self.board[start_y][start_x] == 0:
            return []

        colour = self.board[start_y][start_x]
        queue = [(start_x, start_y)]
        result = {(start_x, start_y)}

        def add(a, b):
            if (a, b) not in result and self.board[b][a] == colour:
                result.add((a, b))
                queue.append((a, b))

        while queue:
            x, y = queue.pop(0)
            if x+1 < self.width:
                add(x+1, y)
            if y+1 < self.height:
                add(x, y+1)
            if x-1 >= 0:
                add(x-1, y)
            if y-1 >= 0:
                add(x, y-1)

        return result

    def get_all_moves(self):
        # finds a set of all possible moves (as tuples of moves that are all the same move)
        moves = set()
        for y in range(self.height):
            for x in range(self.width):
                if self.board[y][x] > 0 and not any((x, y) in m for m in moves):
                    m = self.get_move(x, y)
                    # only moves of more than one block are valid
                    if len(m) > 1:
                        moves.add(tuple(m))
        return moves

    def make_move(self, move):
        for x, y in move:
            self.board[y][x] = 0
        self.drop()

    def check_won(self):
        # returns whether the game has been completed assumes all positive colours
        return sum(sum(line) for line in self.board) == 0

    def play(self):
        # trivial if there's nothing on the board, win in 0 moves, 1 path, empty moves
        if self.check_won():
            return 0, 1, {}
        # otherwise play all possible moves until conclusion
        moves = {}
        size = self.width * self.height
        min_d = size  # worst case as many moves as squares
        total = 0
        for move in self.get_all_moves():
            next_state = self.copy()
            next_state.make_move(move)
            d, n, rest = next_state.play()
            # only save the move if there's a way to win the game after this move
            if d < size:
                moves[(move[0], d)] = rest
                total += n
                min_d = min(min_d, d+1)
        return min_d, total, moves


def main():
    g = Game(4, 5)
    g.generate(seed=1)
    print('Start of the game:')
    g.print()
    min_moves, paths, moves = g.play()

    if min_moves == g.width * g.height:
        print('Game cannot be won!')
    else:
        g_copy = g.copy()
        print(f'The first winning play in {min_moves} moves, out of {paths} possible different games:')
        options = moves
        n = min_moves
        x, y = 0, 0
        next_options = {}
        while n > 0:
            for ((x, y), c), next_options in options.items():
                if c == n:
                    break
            print(f'Make move {(x, y)}:')
            g_copy.make_move(g_copy.get_move(x, y))
            g_copy.print()
            n -= 1
            options = next_options


if __name__ == '__main__':
    main()

This plays the game with a tiny board of 4x5, and the output:

Start of the game:
0101
0111
1122
1121
2211
The first winning play in 3 moves, out of 11 possible different games:
Make move (2, 3):
0100
0101
1101
1111
2211
Make move (2, 4):
0000
0000
0000
0000
2200
Make move (0, 4):
0000
0000
0000
0000
0000

Note that it numbers the board from top-left to lower-right, so 0,0 is top-left and 4,5 is lower-right in this example. The random seed is set, so you get the same result every time you run, though not necessarily the same game on every computer, this depends on the implementation of random - you could add a .save() and .load() function if you need more repeatability.

Note that the answer to your question is really just the play method together with the get_move and get_all_moves methods - which show how to build a tree of possible moves, depth-first with backtracking (using recursion - so limiting the board size through recursion depth, it would doable but a little less readable without recursion).

Also note that after this line: min_moves, paths, moves = g.play(), moves contains the full tree of all possible moves, given the game g, played to conclusion. It's worth having a look in a debugger to see what's actually generated - it's too big to print here.

To see how many solutions of each length there are:

        from collections import defaultdict
        counts = defaultdict(int)
        def count(ms, n):
            for m, k in ms:
                if k == 0:
                    counts[n] += 1
                else:
                    count(ms[(m, k)], n+1)
        count(moves, 0)
        print(counts)

For this example:

defaultdict(<class 'int'>, {2: 7, 3: 4})