It only takes one to Tango

LinkedIn has a logic game called Tango. I’ve become mildly obsessed with it. The rules of the game are simple.

• It’s played on a 6x6 grid.
• The grid must be filled with symbols (either X or Y)
• No more than 2 X or 2 Y may be next to each other, either vertically or horizontally
• Each row and column must contain the same number of X or Y
• Cells separated by an = sign must contain the same type
• Cells separated by an x sign must be of the opposite symbol
• Each puzzle has one right answer and can be solved via deduction. No guesses required.

Here’s an example of a fully filled puzzle with some pretty graphics.

Let’s model it.

It’s really easy to model the game and write a solver. So, let’s not do that. Instead, we’re going to try and generate really difficult problems. We’ll struggle with brute force since a 6x6 grid has 36 cells, and 2 values per cell. Brute force gives 2³⁶ options so that’s out of the question.

Instead, we’ll use backtracking to generate all possible solutions of laying out the symbols. We’ll ignore constraints like = and x for now. We’ll try and be a bit smarter too and only generate canonical forms of the puzzle. We’ll define canonical by setting the top left cell to a fixed value, finding all the possible rotations and using the minimal string representation. Here’s a chunk of code that does just that.

    private static char[,] Canonicalize(Tango solution)
    {
        // Extract the solution’s 6x6 arrangement
        char[,] original = new char[6, 6];
        for (int r = 0; r < 6; r++)
            for (int c = 0; c < 6; c++)
                original[r, c] = solution.GetCell(r, c);

        // Generate the 4 possible rotations
        var rotations = new List<char[,]>(4)
        {
            original,
            Rotate90(original),
            Rotate90(Rotate90(original)),
            Rotate90(Rotate90(Rotate90(original)))
        };

        return rotations
            .Select(x => (x[0, 0] == 'Y') ? 
                Flip(x) : CopyGrid(x)).MinBy(GridToString);
    }

To do the backtracking, we start from the top left and fill in a symbol. If the rules of the grid are still upheld, we repeat the process recursively until we’re done. We back-track once we’ve explored all possible symbols.

    public static IEnumerable<Tango> EnumerateSolutions(Tango tango)
    {
        return EnumerateSolutions(0, 0, tango);
    }    

    private static IEnumerable<Tango> EnumerateSolutions(
        int row, 
        int col, 
        Tango tango)
    {
        if (row == Tango.GRID_SIZE)
        {
            // Finished grid; yield a copy of the solved grid.
            var solution = new char[Tango.GRID_SIZE, Tango.GRID_SIZE];
            Array.Copy(tango.Grid, solution, tango.Grid.Length);
            yield return new Tango(solution, tango.Constraints);
            yield break;
        }

        // Compute next cell coordinates.
        int nextRow = row, nextCol = col + 1;
        if (nextCol == Tango.GRID_SIZE)
        {
            nextRow++;
            nextCol = 0;
        }

        // If cell is fixed, skip to the next.
        if (tango.IsFixed[row, col])
        {
            foreach (var sol in EnumerateSolutions(nextRow, nextCol, tango))
                yield return sol;
            yield break;
        }

        // Try both possible symbols.
        foreach (var symbol in new char[] { 'X', 'Y' })
        {
            tango.Grid[row, col] = symbol;
            // Only continue if the partial grid is still valid.
            if (tango.IsValid())
            {
                foreach (var sol in EnumerateSolutions(nextRow, nextCol, tango))
                    yield return sol;
            }
        }

        // Backtrack.
        tango.Grid[row, col] = ' ';
    }

We can find all possible solutions without constraints in a second or so. There are 1440 possible permutations of filled grids that preserve the rules (assuming I’ve written the code correctly).

I don’t know why it’s 1440, and I wish I knew enough combinatorics to work it out. Answers appreciated!

Let’s make a hard puzzle

Now that we’ve got all possible grids, let's try and make a puzzle. We’ll attack this logically. For each of the 1440 canonical forms, we’ll go through the grid, remove as many cells as we can whilst leaving one unique solution.

Here’s some code that does that. It’s not particularly sophisticated. It just keeps trying to unfix cells until it can’t.

public class PuzzleMinimizer
{
    public static Tango Minimize(Tango puzzle)
    {
        while (TrySimplifyPuzzle(puzzle, includeConstraints)) { }
        return puzzle;
    }

    private static bool TrySimplifyPuzzle(Tango puzzle)
    {
        for (int row = 0; row < 6; row++)
        {
            for (int col = 0; col < 6; col++)
            {
                if (!puzzle.IsCellFixed(row, col)) continue;

                // Try removing the fixed cell
                if (CanRemoveCell(puzzle, row, col))
                {
                    puzzle.UnfixCell(row, col);
                    return true;
                }
            }
        }
        return false;
    }

    private static bool CanRemoveCell(Tango puzzle, int row, int col)
    {
        var testPuzzle = puzzle.DeepCopy();
        testPuzzle.UnfixCell(row, col);
        return HasUniqueSolution(testPuzzle);
    }

    private static bool IsValidPosition(int row, int col) =>
        row >= 0 && row < 6 && col >= 0 && col < 6;

    private static bool HasUniqueSolution(Tango puzzle) =>
        TangoSolver.EnumerateSolutions(puzzle).Take(2).Count() == 1;
}

We can run this on all of our 1440 full solutions, and we find that we need no more than 11 cells (out of 36) for any of the Tango puzzles.

Here is the hardest puzzle of the lot, which only has six cells set and has a single unique solution.

. . . . . .

. . . . . .

. . . X . .

. Y Y . . .

. . Y . . .

. . . . X X

But this still isn’t very pleasant as a puzzle. It’s quite boring, and it’s not hard. Give it a try!

Let’s make a harder problem

We’ll use the same back-tracking approach that we used before, but now we’ll give the ability to add a constraint too. If we can’t remove a cell, we’ll try and add a constraint between the cell we’re on and any of the immediate neighbours.

public class PuzzleMinimizer
{
    public static Tango Minimize(Tango puzzle, bool includeConstraints)
    {
        while (TrySimplifyPuzzle(puzzle, includeConstraints)) { }
        return puzzle;
    }

    private static bool TrySimplifyPuzzle(Tango puzzle, bool includeConstraints)
    {
        for (int row = 0; row < 6; row++)
        {
            for (int col = 0; col < 6; col++)
            {
                if (!puzzle.IsCellFixed(row, col)) continue;

                // Try removing the fixed cell
                if (CanRemoveCell(puzzle, row, col))
                {
                    puzzle.UnfixCell(row, col);
                    return true;
                }

                // Try replacing with a constraint
                if (includeConstraints && TryReplaceWithConstraint(puzzle, row, col))
                {
                    return true;
                }
            }
        }
        return false;
    }

    private static bool CanRemoveCell(Tango puzzle, int row, int col)
    {
        var testPuzzle = puzzle.DeepCopy();
        testPuzzle.UnfixCell(row, col);
        return HasUniqueSolution(testPuzzle);
    }

    private static bool TryReplaceWithConstraint(Tango puzzle, int row, int col)
    {
        var adjacentCells = GetAdjacentFixedCells(puzzle, row, col);
        var constraintTypes = new[] { Tango.ConstraintType.Same, Tango.ConstraintType.Different };

        foreach (var (r2, c2) in adjacentCells)
        {
            foreach (var constraintType in constraintTypes)
            {
                var testPuzzle = puzzle.DeepCopy();
                testPuzzle.UnfixCell(row, col);
                testPuzzle.AddConstraint(row, col, r2, c2, constraintType);

                if (HasUniqueSolution(testPuzzle))
                {
                    puzzle.UnfixCell(row, col);
                    puzzle.AddConstraint(row, col, r2, c2, constraintType);
                    return true;
                }
            }
        }
        return false;
    }

    private static IEnumerable<(int row, int col)> GetAdjacentFixedCells(Tango puzzle, int row, int col)
    {
        var directions = new[] { (-1, 0), (1, 0), (0, -1), (0, 1) };
        
        return directions
            .Select(d => (row: row + d.Item1, col: col + d.Item2))
            .Where(pos => IsValidPosition(pos.row, pos.col) && puzzle.IsCellFixed(pos.row, pos.col));
    }

    private static bool IsValidPosition(int row, int col) =>
        row >= 0 && row < 6 && col >= 0 && col < 6;

    private static bool HasUniqueSolution(Tango puzzle) =>
        TangoSolver.EnumerateSolutions(puzzle).Take(2).Count() == 1;
}

This allows us to reduce every single possible solution to a grid with just a single symbol set! This makes intuitive sense to me as an = symbol forces a second cell to be set (and so on). Given the symmetry aspect of the grid, one symbol is obviously the minimum that can be set.

But what about the minimum number of constraints?

Finally, the hardest problem?

What do we define as the hardest problem? Let’s iterate over all possible grids and find the minimum number of symbols and constraints that are set.

        var possibleSolutions = TangoSolver.GetMinimalSolutions(new Tango());              
        
        var hardestGrid = possibleSolutions.MinBy(x => 
            {
                var minPuzzle = PuzzleMinimizer.Minimize(x, true);
                return minPuzzle.CellsSet() + minPuzzle.ConstraintsSet();
            }
        );

This isn’t a fully exhaustive search. We’re only considering if an = or x removes constraints locally. I haven’t convinced myself yet that there isn’t a constraint you could put elsewhere in the grid to remove ambiguity.

Here is the hardest Tango puzzle I could find. It has six elements (five constraints and a single symbol).

. . . . . .

. . . . . .

. . . . . .
    =
. . . . . .
      = x
. . . . . .
          =
. . . . .=X

It’s pretty hard!

But is it the hardest problem? I don’t know. My code is here. Suggestions for improvement welcome.

So, here’s your challenge — can you find a Tango puzzle harder than this?