news.

A Metaheuristic Approach to Solving Rogo

rogo_header

Puzzles are difficult. When a person attempts to solve one they require mental prowess and the love of a good challenge. Puzzles exist to baffle and deceive, while offering a sense of achievement when they are eventually defeated.

Define: Rogo

Rogo is a simple puzzle game that encapsulates a few features that are of interest to us scientists. It is the brain child of Creative Heuristics Ltd, a New Zealand based company run by Dr Nicola Ward Petty and Dr Shane Dye. More information can be found on their website.

A Rogo puzzle is a n x m grid containing empty (white), weighted (numbered) and restricted (black) squares. Given a fixed step size s and an optimal value z, find a feasible cycle of length s such that the sum of the weights it passes through is z. Where a feasible cycle does not pass through restricted squares and a move is only made vertically or horizontally. Detailed instructions are available on the Rogo website.

Example Problem

http://www.rogopuzzle.co.nz/paper-rogos/intro-rogo-1/

Solution

http://www.rogopuzzle.co.nz/paper-rogos/intro-solution-1/

 

Some problems are really hard

http://xkcd.com/287/

In computational complexity theory we make a distinction between Polynomial-time (P)  and Non-deterministic Polynomial-time (NP) problems. When a problem is P it means there is a fast (polynomial-time) way to find a solution. When a problem is NP is means there is a fast way to check if a solution is valid, but no known polynomial-time algorithm to find the solution. A NP-hard problem is at least as hard as any NP problem, but usually harder.

Rogo is a NP-hard [1], thus doing an exhaustive search of the solution space is a really bad idea. Instead, let us try a metaheuristic approach!

Metaheuristics, sounds dangerous right?

Instead of checking every possible combination, we find a smart way to only consider candidates that will most likely lead us to an optimal solution. There is a major down side to this approach, we are not guaranteed a global optimal solution. That is to say the algorithm might return the best ever solution, but it might also return a local optimal solution. On the up side, it will do so quite fast.

A metaheuristic is a more abstract form of heuristic, often taking ideas from nature and natural phenomena. For those interested in further reading, my favourite metaheuristics fall under Swarm Intelligence. For our Rogo problem we will be using the less exotic yet very powerful Tabu search.

Tabu Search

A tabu search is essentially a random search with one key difference, if no improving moves (in terms of the cost function) are available, make a decreasing move that is not in the restricted move (tabu) list. Thus for each iteration consider all possible moves that can be made from the current position and based on the above criteria, select the next move to be made.

This brings us to a very important point, how we define the moves. A move is a simple rule that states how a candidate can be generated from a given position. For example, consider a binary encoded sequence that represents items to be packed into a knapsack, 1 if the item is included and 0 if it is not. Thus a initial solution could be 000, representing an empty knapsack. If we define our move as a bit-flip operation, the following candidates would be generated from our initial solution: 100, 010, 001.

If we had a cost function max z = x1 + 2x2 + 3x3 the best move would be 001, since it increases z from 0 to 3. From 001 we would generate the candidates 101, 011. Since the move **x was used previously, it has been added to the tabu list and the candidate 000 is not considered.

Since there are no restrictions in place, the optimal solution to this problem would be to include all the items, thus 111. It is easy to see that this would eventually be reached by iteratively generating candidates and selecting the best one. As each move is selected, that move operation is added to the tabu list, thus preventing a move from being reversed and resulting in the algorithm being stuck in a local optimum.

The length of the tabu list is important and mostly problem specific. If the length is finite and the list becomes full it behaves like a FIFO queue.

Solving the problem

This solution was implemented in Python, here follows a brief summary of the core features given a Rogo puzzle grid R of size n x m,  a path length s and optimal value z. These two examples will be used to demonstrate the functionality.

http://www.rogopuzzle.co.nz/rogo/4/d16.jpg

 

http://www.rogopuzzle.co.nz/rogo/4/d22.jpg

Initial Solution: Density

Create a density matrix of size n x m and fill each Dij with a weighted value obtained from Rij and its adjacent neighbours. Use D to generate a list of candidate grids Ck of size a x b where a x b = s and the sum of all entries in Ck is >= z – u, where u is a tolerance coefficient.

Sort the Ck by density and run tabu search on each of them. Stop when an optimal solution has been found or until all candidates have been considered.

The highest density initial solution found for May 16 is:

heart_initial

Simple Move: Corners

The first and easiest move defined is the corner flip. Given a current cycle, find all corners and flip them into a new feasible position. Make the (from, to) tuple tabu. It was found that for most of the problems this move was sufficient to find the optimal solution, such as May 22. Another benefit of this move is that it does not modify the length of the cycle, thus it is trivial to generate the candidates.

fish_t1move_optimal_22mayThough for some, such as May 16, a second type of move was required. Without the additional move the search ended in a local optimum.

heart_t1move_notoptimal

Another Move: Indentation

By introducing an indentation move it allowed the algorithm to create candidates with a path form that was impossible to create using only corner flips. This move does a inward shift operation on a side of the current cycle and then introduces all possible indents to the new shifted cycle. Thus generating multiple candidates for each shifted side. The inverse operation was also required to undo an indent and to do an outward shift operation. This move has a greater computational cost, since it has to reduce the cycle length by two and then introduce the indent that increases it back to the correct length.

Using this move in conjunction with the corner flip move on May 16 results in an optimal solution.

heart_t2move_optimal

 

We Should Try That Next Time

Only a small number of problems have been tested using the current implementation. An optimal solution is found for all the problems, but there could be a problem that will not be solvable using only these two moves. When that problem arises, stay tuned for Special Move: Third time lucky.

Metaheuristics are great when faced with a difficult problem. Do note that it is an art form to identify the simple components that hide inside the complexity of your NP problem, but do not be discouraged, it is a lot of fun trying different techniques and approaches that will teach you valuable problem solving skills.

Talk to Me

Have any experience with metaheuristics? Have an idea for the third (and final?) move? Let me know with a comment below.

References

[1] Dye, Shane, and Nicola Ward Petty. “Rogo, a TSP-based Paper Puzzle: Optimization Approaches.” Information and Media Technologies 7.3 (2012): 978-985.

, , ,

No comments yet.

Leave a comment

Leave a Reply

(required)