Advice for script to solve color tile matching puzzle

Question

I have a game that I'm trying to devise a script to find the solution for. I'm using python because that's what I'm most familiar with.

Here's the gist, the game is a 10 x 14 board made up of 5 different color tiles. The mechanics are you can select any group of 2 or more tiles of the same color that are touching on the horizontal or vertical axis (diagonals do not count). That group will then disappear and all the tiles above will fall down to take their place. If a column is completely empty of tiles any remaining columns of tiles to the right will move to the left to fill in the gap. You win by clearing the board and not leaving any tiles behind.

Small example of the game board, the actual one is 10 x 14

First step - Write a python script to respect the rules of the game. Fairly easy.

I map the colors of the tiles to number values and create a matrix like this:

test_game_board = [
    [2, 2, 2, 1, 1, 1, 5], 
    [2, 2, 2, 3, 3, 1, 5], 
    [3, 2, 4, 5, 3, 3, 5], 
    [3, 3, 4, 5, 5, 3, 5], 
    [1, 1, 1, 1, 1, 3, 5], 
    [1, 1, 5, 5, 1, 4, 4]]

I parse the matrix and find all consecutive tiles of the same color and create an object for every possible move currently on the board.

I then have a block of code given a certain eligible move (see later comment on logic to pick moves) to update a copy of the game board and shuffle tiles down and over where needed.

Check the board again to refresh the list of eligible moves since tiles have moved around.

If there are eligible moves left then keep on picking new moves. If no more eligible moves are found then I check the board to see if I lost or won the game. If game lost then I start over and reset to the original game board layout.

Performance of the above seems to run through 30-40 moves and complete a single attempt of the game in about 0.0350 seconds.

Second step - Picking the sequence of moves

I've tried a few approaches:

randomly picking a move each turn: Even after running the script for hours it hasn't repeated an exact sequence of moves out of several million moves attempted.
I tried weighting the moves selected by how many tiles were in each move and picking the larger ones.
Going through the possible moves sequentially. Same as the random option but this way I can see some sort of progress it's making. I've tried running this on a spare machine for a few days and it's gotten through 15 million sequences and still not very far along the unknown number of total possible moves.

So I guess my question out there to the world is if someone has any resources or ideas on how I could devise an algorithm for solving this other than my current approach of brute forcing. I can post the script on pastebin or something didn't want to bloat my post more than it already is :P

EDIT: So I've gone with the brute force sequential route. I'm picking the first move in the list of eligible moves. If that sequence of moves fails I'll start over and increment the last eligible move. So I'm working on some optimizations for the brute force method:

caching results from N set of moves in a sequence so it's faster to loop through.
if a move creates an un-winnable board skip it (ex: if a move color has a lone tile on the board)

I think if I find a few more optimizations I can get this to solve a puzzle in a reasonable amount of time :)

A friend solved this in python for a 15x9 board with 4 colors, runs in 1s. Not sure how much more would another color add, but should be doable to run in reasonable time — juvian
@juvian ooh I'd be interested in learning their approach, can you share the code/example? — user1630543

CaptainTrunky CaptainTrunky · Accepted Answer · 2017-08-04T03:27:39

It's a not a simple problem at all.) I think that this task belongs to NP-complete class, so there is no easy way of solving it.

What can you do? Try using A* search. As a heuristic, you can try picking a number of elements that could be removed by an action (I'm not sure that it's correct/optimal, you'll have to study it yourself).

There are other approaches, for example, constraint satisfaction, but I think it will be very difficult to implement a solver for your puzzle with it. However, look at Minizinc for insights. I would generate a task in the form of 'is it possible to empty current board in K steps?'. If not, increase K and run Minizinc again.

Advice for script to solve color tile matching puzzle

1 Answers