Search code examples
algorithmvb6heuristics

Hungarian Rings Puzzle

I'm having a hard time finding an admissible heuristic for the Hungarian Rings puzzle. I'm planing on using IDA* algorithm to solve and am writing the program in Visual Basic. All I am lacking is how to implement the actual solving of the puzzle. I've implemented both the left and right rings into their own arrays and have functions that rotate each ring clockwise and counterclockwise. I'm not asking for code, just somewhere to get started is all.

Here is the 2 ring arrays:

Dim leftRing(19) As Integer 
' leftRing(16) is bottom intersection and leftRing(19) is top intersection
Dim rightRing(19) As Integer
' rightRing(4) is top intersection and rightRing(19) is bottom intersection

In the arrays, I store the following as the values for each color: Red value = 1 Yellow = 2 Blue = 3 and Black = 4

Solution

  • I suggest counting "errors" in each ring separately - how many balls need to be replaced to make the ring solved (1 9-color, 1 10-color, one lone ball from a 9-color). At most two balls can be fixed using a rotation, then another rotation is needed to fix another two. Compute the distance of each ring individually = 2n-1 where n is half the amount of bad positions and take the larger of them. You can iterate over all twenty positions when looking for one that has the least amount of errors, but I suppose there's a better way to compute this metric (apart from simple pruning).

    Update: The discussion with Gareth Reed points to the following heuristic:

    For each ring separately, count:

    1. the number of color changes. The target amount is three color changes per ring, and at most four color changes may be eliminated at a time. Credits go to Gareth for this metric.
    2. the count of different colors, neglecting their position. There should be: 10 balls of one 10-color, 9 balls of one 9-color and one ball of the other 9-color. At most 2 colors can be changed at a time.

    The second heuristic can be split into three parts:

    1. there should be 10 10-balls and 10 9-balls. Balls over ten need to be replaced.
    2. there should be only one color of 10-balls. Balls of the minor color need to be replaced.
    3. there should be only one ball of a 9-color. Other balls of the color need to be replaced. If all are the same color, and 9-color is not deficient, one additional ball need to be replaced.

    Take the larger of both estimates. Note that you will need to alternate the rings, so 2n-1 moves are actually needed for n replacements. If both estimates are equal, or the larger one is for the latest moved ring, add an additional one. One of the rings will not be improved by the first move.

    Prune all moves that rotate the same ring twice (assuming a move metric that allows large rotations). These have already been explored.

    This should avoid all large local minima.