ACM Problem: Coin-Flipping, help me identify the type of problem this is

Question

I'm practicing for the upcoming ACM programming competition in a week and I've gotten stumped on this programming problem.

The problem is as follows:

---

You have a puzzle consisting of a square grid of size 4. Each grid square holds a single coin; each coin is showing either heads (H) and tails (T). One such puzzle is shown here:

H H H H
T T T T
H T H T
T T H T

Any coin that is current showing Tails (T) can be flipped to Heads (H). However, any time we flip a coin, we must also flip the adjacent coins direct above, below and to the left and right in the same row. Thus if we flip the second coin in the second row we must also flip 4 other coins, giving us this arrangment (coins that changed are shown in bold).

H T H H
H H H T
H H H T
T T H T

If a coin is at the edge of the puzzle, so there is no coin on one side or the other, then we flip fewer coins. We do not "wrap around" to the other side. For example, if we flipped the bottom right coin of the arragnement above we would get:

H T H H
H H H T
H H H H
T T T H

Note: Only coins showing (T) tails can be selected for flipping. However, anytime we flip such a coin, adjacent coins are also flipped, regardless of their state.

The goal of the puzzle is to have all coins show heads. While it is possible for some arragnements to not have solutions, all the problems given will have solutions. The answer we are looking for is, for any given 4x4 grid of coins what is the least number of flips in order to make the grid entirely heads.

For Example the grid:
H T H H
T T T H
H T H T
H H T T

The answer to this grid is: 2 flips.

---

What I have done so far:

I'm storing our grids as two-dimensional array of booleans. Heads = true, tails = false. I have a flip(int row, int col) method that will flip the adjacent coins according the rules above and I have a isSolved() method that will determine if the puzzle is in a solved state (all heads). So we have our "mechanics" in place.

The part we are having problems with is how should we loop through, going an the least amount of times deep?

Answer 1

Your puzzle is a classic Breadth-First Search candidate. This is because you're looking for a solution with the fewest possible 'moves'.

If you knew the number of moves to the goal, then that would be ideal for a Depth-First Search.

Those Wikipedia articles contain plenty of information about the way the searches work, they even contain code samples in several languages.

Either search can be recursive, if you're sure you won't run out of stack space.

Answer 2

EDIT: I hadn't noticed that you can't use a coin as the primary move unless it's showing tails. That does indeed make order important. I'll leave this answer here, but look into writing another one as well.

No pseudo-code here, but think about this: can you ever imagine yourself flipping a coin twice? What would be the effect?

Alternative, write down some arbitrary board (literally, write it down). Set up some real world coins, and pick two arbitrary ones, X and Y. Do an "X flip", then a "Y flip" then another "X flip". Write down the result. Now reset the board to the starting version, and just do a "Y flip". Compare the results, and think about what's happened. Try it a few times, sometimes with X and Y close together, sometimes not. Become confident in your conclusion.

That line of thought should lead you to a way of determining a finite set of possible solutions. You can test all of them fairly easily.

Hope this hint wasn't too blatant - I'll keep an eye on this question to see if you need more help. It's a nice puzzle.

As for recursion: you could use recursion. Personally, I wouldn't in this case.

EDIT: Actually, on second thoughts I probably would use recursion. It could make life a lot simpler.

---

Okay, perhaps that wasn't obvious enough. Let's label the coins A-P, like this:

ABCD
EFGH
IJKL
MNOP

Flipping F will always involve the following coins changing state: BEFGJ.

Flipping J will always involve the following coins changing state: FIJKN.

What happens if you flip a coin twice? The two flips cancel each other out, no matter what other flips occur.

In other words, flipping F and then J is the same as flipping J and then F. Flipping F and then J and then F again is the same as just flipping J to start with.

So any solution isn't really a path of "flip A then F then J" - it's "flip <these coins>; don't flip <these coins>". (It's unfortunate that the word "flip" is used for both the primary coin to flip and the secondary coins which change state for a particular move, but never mind - hopefully it's clear what I mean.)

Each coin will either be used as a primary move or not, 0 or 1. There are 16 coins, so 2^16 possibilities. So 0 might represent "don't do anything"; 1 might represent "just A"; 2 might represent "just B"; 3 "A and B" etc.

Test each combination. If (somehow) there's more than one solution, count the number of bits in each solution to find the least number.

Implementation hint: the "current state" can be represented as a 16 bit number as well. Using a particular coin as a primary move will always XOR the current state with a fixed number (for that coin). This makes it really easy to work out the effect of any particular combination of moves.

---

Okay, here's the solution in C#. It shows how many moves were required for each solution it finds, but it doesn't keep track of which moves those were, or what the least number of moves is. That's a SMOP :)

The input is a list of which coins are showing tails to start with - so for the example in the question, you'd start the program with an argument of "BEFGJLOP". Code:

using System;

public class CoinFlip
{
    // All ints could really be ushorts, but ints are easier 
    // to work with
    static readonly int[] MoveTransitions = CalculateMoveTransitions();

    static int[] CalculateMoveTransitions()
    {
        int[] ret = new int[16];
        for (int i=0; i < 16; i++)
        {
            int row = i / 4;
            int col = i % 4;
            ret[i] = PositionToBit(row, col) +
                PositionToBit(row-1, col) +
                PositionToBit(row+1, col) +
                PositionToBit(row, col-1) +
                PositionToBit(row, col+1);
        }
        return ret;
    }

    static int PositionToBit(int row, int col)
    {
        if (row < 0 || row > 3 || col < 0 || col > 3)
        {
            // Makes edge detection easier
            return 0;
        }
        return 1 << (row * 4 + col);
    }

    static void Main(string[] args)
    {
        int initial = 0;
        foreach (char c in args[0])
        {
            initial += 1 << (c-'A');
        }
        Console.WriteLine("Initial = {0}", initial);
        ChangeState(initial, 0, 0);
    }

    static void ChangeState(int current, int nextCoin, int currentFlips)
    {
        // Reached the end. Success?
        if (nextCoin == 16)
        {
            if (current == 0)
            {
                // More work required if we want to display the solution :)
                Console.WriteLine("Found solution with {0} flips", currentFlips);
            }
        }
        else
        {
            // Don't flip this coin
            ChangeState(current, nextCoin+1, currentFlips);
            // Or do...
            ChangeState(current ^ MoveTransitions[nextCoin], nextCoin+1, currentFlips+1);
        }
    }
}

Answer 3

I would suggest a breadth first search, as someone else already mentioned.

The big secret here is to have multiple copies of the game board. Don't think of "the board."

I suggest creating a data structure that contains a representation of a board, and an ordered list of moves that got to that board from the starting position. A move is the coordinates of the center coin in a set of flips. I'll call an instance of this data structure a "state" below.

My basic algorithm would look something like this:

Create a queue.
Create a state that contains the start position and an empty list of moves.
Put this state into the queue.
Loop forever:
    Pull first state off of queue.
    For each coin showing tails on the board:
        Create a new state by flipping that coin and the appropriate others around it.
        Add the coordinates of that coin to the list of moves in the new state.
        If the new state shows all heads:
            Rejoice, you are done.
        Push the new state into the end of the queue.

If you like, you could add a limit to the length of the queue or the length of move lists, to pick a place to give up. You could also keep track of boards that you have already seen in order to detect loops. If the queue empties and you haven't found any solutions, then none exist.

Also, a few of the comments already made seem to ignore the fact that the problem only allows coins that show tails to be in the middle of a move. This means that order very much does matter. If the first move flips a coin from heads to tails, then that coin can be the center of the second move, but it could not have been the center of the first move. Similarly, if the first move flips a coin from tails to heads, then that coin cannot be the center of the second move, even though it could have been the center of the first move.