Solve this puzzle – @memo and dynamic programming

Here’s the situation.  You have a puzzle with 15 round coloured plates arranged in an equilateral triangle, and 14 coloured pebbles on top of them.  One plate does not have a pebble – it is called the hole.  Your goal is to rearrange the pebbles so that they are on the matching coloured plates, in the minimum number of moves possible.  For each move, you can only move one pebble in a straight line to the hole, possibly leaping over other pebbles on the way.

The question is – can you design an algorithm to calculate, for any starting board, the minimum number of moves to solve it?

In fact this describes the game Panguru, recently produced by Second Nature Games and available as a board game and online.  In Panguru, there are two pebbles and plates of each colour, and one additional legal move down the centreline of the triangle.  If my quick description is too wordy, the online game will give you a much better feel for it; there are rules available too.

Panguru Online

A dynamic programming solution, with memoization

Here’s the approach I came up with, which I implemented in python. This was informed by the excellent book Python Algorithms, Mastering Basic Algorithms in the Python Language, by Magnus Lie Hetland, which I highly recommend.

Think of all the possible moves used to solve the puzzle as a tree. Number the positions 0 to 14.  The root node of the tree is the hole position, and child nodes give the position of the pebble that is being moved. So with the hole starting at the top of the triangle (position 0), one path through the tree might be 0-3-5.  (If you think about it, the last move always tells you where the hole finishes up.)

It is easy to measure how close we are to the solved board: we just count how many pebbles have the same colour as their plates.  When we hit 14, we are done!

In fact we can turn it around.  Let’s assume we have a solution (14 matching pebbles) after m moves. How did we get here?  Clearly, we must have had 13 matching pebbles the move before. (Because you only move one pebble at a time, each move can only increase or decrease the number of matching pebbles by one, or leave the number unchanged.)

And the move before that, we must have had either 12 or 13 matching pebbles. And so on.

This sounds like induction and lends itself to a recursive solution, like this. First define the tree structure via the Node class. The core of this is the __init__ method which keeps track of the node’s parent. I’ve also added original_pos to help us later, and two extra methods to display nodes nicely on the command line (__repr__) and to make it easier to access the node’s ancestry (__getitem__).

class Node():
    def __init__(self, parent, move, num_matching):
        self.parent = parent
        self.move = move
        self.num_matching = num_matching

    def original_pos(self, pos):
        """
        Return the original position of the pebble now at position pos.
        """
        if not self.parent:
            return pos
        if pos==self.move:
            prev_pos = self.parent.move
        elif pos==self.parent.move:
            prev_pos = self.move
        else:
            prev_pos = pos
        return self.parent.original_pos(prev_pos)

    def __getitem__(self, key):
        """
        If m is a node which you think of as the last move in a sequence,
        m[-3] is the third last move as a Node.
        m[-3].move is the third last move as an integer (which position was moved)
        """
        if key>=0:
            raise IndexError, "You must index moves from the end, e.g. m[-1] for the last move."
        if key==-1:
            return self
        else:
            try:
                return self.parent[key+1]
            except TypeError:
                raise IndexError, "Out of range."

    def __repr__(self):
        return "%s%d" % ((self.parent and ("%s-" % str(self.parent)) or ""),
                         self.move)

Then the puzzle-solving approach could be implemented like this:

class Puzzle():
    def __init__(self, plates, pebbles, allowed_moves):
    """
    Set up a puzzle instance for solving.
    Args:
        plates is a string of 15 chars representing colours
            e.g. "WCBRBOGYGPCORPY"
        pebbles is the same, with "-" for the hole
            e.g. "-PCBRYOGYGBCORP"
        allowed_moves is a list s.t.
            allowed_moves[i] = list of positions that a pebble at pos i can move to
                = list of positions that can move to this position, if it is the hole
            e.g. [[1, 2, 3, 4, 5, 6, 9, 10, 12, 14],
                  [0, 2, 3, 4, 6, 8, 10, 13],
                  [0, 1, 4, 5, 7, 9, 11, 14],
                  [0, 1, 4, 5, 6, 7, 10, 12],
                  [0, 1, 2, 3, 5, 7, 8, 11, 12, 13],
                  [0, 2, 3, 4, 8, 9, 12, 14],
                  [0, 1, 3, 7, 8, 9, 10, 11],
                  [2, 3, 4, 6, 8, 9, 11, 12],
                  [1, 4, 5, 6, 7, 9, 12, 13],
                  [0, 2, 5, 6, 7, 8, 13, 14],
                  [0, 1, 3, 6, 11, 12, 13, 14],
                  [2, 4, 6, 7, 10, 12, 13, 14],
                  [0, 3, 4, 5, 7, 8, 10, 11, 13, 14],
                  [1, 4, 8, 9, 10, 11, 12, 14],
                  [0, 2, 5, 9, 10, 11, 12, 13]]
    """
        self.plates = plates
        self.pebbles = pebbles
        self.allowed_moves = allowed_moves
        self.num_pebbles = len(filter(lambda x: x not in ["-"], self.pebbles))
        self.num_matching = sum(plates[i] == pebbles[i] for i in range(len(pebbles)))
        hole_pos = self.pebbles.find('-')
        self.root = Node(None, hole_pos, self.num_matching)

    def matching_nodes(self, turn, num_matching):
        """
        Return all the series of moves (as BoardNodes with parents)
        that have 'num_matching' matching spots after 'turn' turns.
        """
        if turn==0:
            if num_matching==self.num_matching:
                return [self.root]
            else:
                return []
        result = []
        for change in (-1,0,1):
            for prev_node in self.matching_nodes(turn-1, num_matching+change):
                for move in self.allowed_moves[prev_node.move]:
                    pebble_colour = self.pebbles[prev_node.original_pos(move)]
                    # was the moved pebble on a matching plate already?
                    old_pos_match = (self.plates[move]==pebble_colour)
                    # does the prev board's hole plate match the moved pebble?
                    new_pos_match = (self.plates[prev_node.move]==pebble_colour)
                    # did the move change how many positions were matching,
                    # by exactly the number we're looking at?
                    if (old_pos_match-new_pos_match)==change:
                        result += [Node(prev_node, move, num_matching)]
        return result

The interesting recursion here is going on in the matching_nodes method.  It just implements the idea that the solutions that have, say, 10 matching positions at turn 10, must have had either 9,10 or 11 matching positions at turn 9. It then works back to turn 0, at which point we know how many matching positions there were.

On top of this, we need a further method which finds the right question to ask. It could start by saying – give me all the solutions after 0 moves. If there are none, find all the solutions after 1 move. And keep trying until you find some solutions, e.g.:

    def optimal_moves(self, stop_at=20):
        """
        Return a tuple (fewest possible number of moves, [optimal moves for this board]).
        """
        num = 0
        result = []
        while not result and num<=stop_at:
            result = self.matching_nodes(num, self.num_pebbles)
            num += 1
        return (num, result)

The code above will work, but it will be slow and inefficient, because matching_nodes will often recurse through territory it has already covered. And that’s where Hetland’s memo decorator comes to the rescue. (This is only a few lines of code which you can find by searching at Google books.) This will cache the results of the decorated method, so that it does not need to be recalculated.  To use it, simply apply @memo to the def matching_nodes line, like so:

@memo
def matching_nodes(self, turn, num_matching):

And that’s it!

You can see this code in action when you ask for a hint in the online game. Each time you press the hint button, the javascript sends off an ajax query which triggers the server to run the above code on the player’s board, and return which moves would come next if the player plays optimally.

In fact, to get around annoying ever-expanding memory problems on the server, I’m running this asynchronously using Celery and Redis (as covered in an earlier blog post), and restarting the celery worker after every request.  But that’s another story…

I hope that has been of interest, and please let me know if you have any comments or improvements.

  

6 thoughts on “Solve this puzzle – @memo and dynamic programming”

  1. I like this problem. I am curious as to the ‘span’ of the game – what’s the hardest Panguru problem (i.e. largest number of minimum moves)?

    Some thoughts on how to brute-force solve this (at the expense of, in the words of George Webster, “dynamiting the trout stream”, using computers to solve a recreational mathematical problem):

    There are 15! / (2^7) different positions for the markers (holding a given position of the plates constant).

    We could assign a dense ID to each position as follows:

    1) The hole can be in 1 of 15 different positions, and thus is numbered from 0..14. Take an accumulator and assign it this number (a = hole_pos).

    2) Our first colour is arbitrarily chosen – we have 14×13/2 different configurations, having taken one position away for the hole and allowing /2 as we don’t care about which order the two markers are placed. Find a dense encoding for the 91 different choices of this color, then stick this value into our accumulator:

    a += first_color_encoding * 15

    3) Repeat this procedure for each of the colors, although the final color isn’t very interesting, as it’s completely determined by the positions of the previous color.

    a += second_color_encoding * (15*91)

    Each time we would have to multiply our encoded value by all the total different possibilities of the lower-order values.

    Now we have a procedure to encode a game board into a dense ID. A series of divides/mod operations can reverse the procedure, going from a ID -> game board.

    (note – encoding the individual pairs of positions – e.g. (14*13)/2 positions for the first color – isn’t trivial but isn’t that hard)

    Given the dense IDs, we could work out from the start position and simply BFS the game to death. You’d need a data structure that can hold all 15!/(2^7) positions, but this is feasible. You probably only need a few bits at each position (a move count + a “last move” field to allow us to trace the move back).

    This means about 10.2 billion positions so the important question here is: is this feasible? We would need to sweep this huge structure repeatedly, and each time we find a position at our current BFS level, we need to expand out the positions next moves, which, unfortunately, isn’t straightforward, as we have to load our data structure to see whether there’s already a better move at that position. So we’re going to have 300+ cycle latencies to main memory to do this.

    This could be pipelined – we could prefetch all destinations of our current position (or current set of positions) so we’re not waiting around 300 cycles every single time we want to update a position.

    Other possibly required optimizations would be to make that giant torrent of integer divide and modulo operations that need to be done to go from a dense id into a series of positions into divide-by-constant operations – which can be done via integer multiply (the compiler will get this automatically). Divides are expensive and if you have to do 7 of them every time you want to translate a dense id into a game board life will be awkward.

    Note: there is probably a much smarter way of doing this. :-)

  2. Hi I love the game and the puzzle+level+high score board layout of your app!

    May I ask how you can achieve doing the high score+level+unlock mechanism in django? I would really like to implement something similar with a scrabble game (I have the working game in javascript already).
    Could you share your code/templates privately? Or can we working something out together it will be great.

    * also I find out a url hack can bypass the lock without stars/paying, please check (I Don’t Pay).

    Thank you.

    1. Hi Anzel,

      Great to hear you like it, thanks!

      For the number of stars each player has on the leaderboard, my current implementation actually calculates this on the fly every time, based on the games played. I save the best number of turns/stars made by each user on each board in a PlayedGame object (and delete old games if they are not as good as the latest game). The leaderboard API (view) code is simply:

      from django.views.generic import View
      ....class LeaderboardApi(JSONViewMixin, View):
      ...."Return the JSON representation of the leaderboard"
      ....def get(self, request, *args, **kwargs):
      ........if 'board' in kwargs:
      ............played = PlayedGame.objects.filter(board__id=kwargs['board'])
      ........if 'subseries' in kwargs:
      ............played = PlayedGame.objects.filter(board__subseries_id=kwargs['subseries'])
      ........if 'series' in kwargs:
      ............played = PlayedGame.objects.filter(board__subseries__series_id=kwargs['series'])
      ........lb = played.values('user__username').annotate(stars=Sum('stars')).order_by('-stars')[:20]
      ........lb = [{ 'name':e['user__username'].title(),
      ................'stars':e['stars'],
      ..............} for e in lb if e['user__username']]
      ........return self.json_response(lb)

      An earlier version updated a separate total after each game, so no on-the-fly calculation is required; if I have performance issues one day I may return to that approach. I recalculate it and re-serve every time you change screen in the game, which cannot be optimal! Also, there’s no pagination on the leaderboard yet; one day I’d like to add that. And finally, the medals each player has earned are saved at the time of earning, so they can be picked up in a simple query. I have written a “management” command that re-calculates these comprehensively in case I add or remove a class of medals.

      Then there’s the access the player has – which I have not fully implemented, as you worked out (the URL scheme is not too cryptic, is it?!). My plan is each user will have an access level in their user profile, which says which “camps” they can access. This is updated after every played game. Then the API call to show the subseries in a “camp” will only serve them up if you have the right access. I will let the front-end control access to particular subseries (“RED” etc) within a camp, but in theory that could be API-controlled too.

      Does that help? Happy to provide more info if you want. Also, if you have a better way, I’d love to know! And let me know where I can play your game when it’s ready…

      1. Great write up and thanks for sharing the info!
        I have read your previous posts as well so I guess you’re using django-cms framework? Mine starts with Mezzanine because I need the integration with cartridge OTB.

        Alright here is my thought and idea to implement the game:
        Page to hold custom content category (say Puzzles) >> grid layout for (Puzzle) probably in 5 difficulties to choose from >> Easy level is Free to play and the rest needs either (Full membership) or Pay to unlock.
        You need to sign up a free account to start playing (let say, have 10 Lives to begin with), every time you lose will deduct the live (similar to candy xrush anyway).
        when you win 10-15 games in Easy Level you can unlock the next level; and the AI strength becomes stronger.
        You pay to add “Lives”.
        I will need a global ranking system in place and the usual “highest score” + “number of bingos” etc.

        And yes I am going to extend the UserProfile to store all the new parameters, and probably need to tweak a lot on the cartridge models/view to make this work together.

        But hey, thanks for your tip on that leaderBoard and I will come back to you if I need help or the scrabble game is published :)

        Best regards.

        1. Hi Anzel,
          Sounds good! I am using Django-CMS for the Second Nature Games website, but all the Panguru screens are handled by the client using Angular; Django is only providing the API. By the way, in case you haven’t come across it, you may want to take a look at Meteor too – although you can’t use Python with Meteor.
          cheers

          1. Hi Arthur,

            It’s been a while, the site prototype was done about a week ago, serving a leaderboard using restframework – and do Ajax call whenever page refreshes.
            I looked at both Angular & Ember however I gave up cause I didn’t want to confuse myself with the similar double curly brackets lol. But I do realise how convenient with these Js framework, so thanks for the advice.

            Meanwhile CEO changed his mind and now the site will be embedded into another site as a backend and will allow anonymous game too… Meaning I have to rewrite part of the since I have things built with registered user in mind and to update user scores/level during the game… And page view permission etc.

            Look forward to your new django post, pretty inspiring :)

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>