Finds a solution for a specific 16-piece edge matching puzzle.

ChrisPuzzle.cs

/*
*  Finds a solution for a specific 16-piece edge matching puzzle.
*  Yields the following output:
*
*  Success in 827772 comparisons!
*  0: Piece 1, Rot 2
*  1: Piece 9, Rot 2
*  2: Piece 15, Rot 2
*  3: Piece 5, Rot 1
*  4: Piece 6, Rot 2
*  5: Piece 12, Rot 2
*  6: Piece 13, Rot 2
*  7: Piece 3, Rot 1
*  8: Piece 8, Rot 3
*  9: Piece 7, Rot 3
*  10: Piece 11, Rot 3
*  11: Piece 10, Rot 0
*  12: Piece 14, Rot 3
*  13: Piece 16, Rot 3
*  14: Piece 4, Rot 3
*  15: Piece 2, Rot 0
*/

using System;

namespace ChrisPuzzle
{
    class Program
    {
        // bit field values for puzzle pieces info
        const int Octagon = 1, OutArrow = 2, InArrow = 4, Cross = 8;
        const int Male = 16, Female = 32;
        
        // 2 edges match if the bitwise XOR of their edge values
        // equals Male (X)OR Female, i.e. the shape information cancels
        // out , but one piece is male and one is female
        const int MatchVal = Male ^ Female;

        // information (# of operations and # of solutions found)
        static int nops = 0;
        //static int nsols = 0;

        // Representation of the puzzle configuration.  Each piece is
        // an array of 4 integers representing the 4 edge.  Each edge
        // has a single bit set for either male or female, and a single
        // bit set for its shape.
        static int[,] puzzle = 
        {
            {Cross | Male, OutArrow | Male, Cross | Female, InArrow | Female},
            {Octagon | Male, Cross | Male, OutArrow | Female, OutArrow | Female},
            {Octagon | Male, Octagon | Male, Octagon | Female, OutArrow | Female},
            {OutArrow | Male, Octagon | Male, Octagon | Female, OutArrow | Female},
            {InArrow | Male, OutArrow | Male, OutArrow | Female, Octagon | Female},
            {Octagon | Male, InArrow | Male, Cross | Female, InArrow | Female},
            {OutArrow | Male, OutArrow | Male, Octagon | Female, InArrow | Female},
            {Octagon | Male, Cross | Male, Cross | Male, Octagon | Female},
            {Octagon | Male, InArrow | Male, Octagon | Female, Cross | Female},
            {OutArrow | Male, Octagon | Male, Octagon | Female, Cross | Female},
            {Cross | Male, OutArrow | Male, OutArrow | Female, Octagon | Female},
            {InArrow | Male, InArrow | Male, Octagon | Female, Cross | Female},
            {Octagon | Male, Cross | Male, InArrow | Female, Octagon | Female},
            {InArrow | Male, InArrow | Male, OutArrow | Female, Cross | Female},
            {InArrow | Male, Cross | Male, OutArrow | Female, InArrow | Female},
            {Octagon | Male, InArrow | Male, InArrow | Female, OutArrow | Female}
        };

        // number of rows and columns
        const int R = 4;
        const int C = 4;

        // number of pieces in the puzzle
        // (should obviously be == puzzle.Length)
        const int N = R * C;

        //
        // Returns true if edge p1 matches edge p2, otherwise false.
        // For example, if we look at the bitwise XOR operation for 2 matching edges: 
        //                                               
        // p1 = (Cross | Male)   =   24   =              0  1  1  0  0  0
        // p2 = (Cross | Female) =   40   =              1  0  1  0  0  0
        //
        // applying p1 XOR p2 we get:                    
        //                                               
        // p1 ^ p2 = (Cross | Male) ^ (Cross | Female)
        //         = Male ^ Female = 48   =              1  1  0  0  0  0
        //                                 
        static Boolean Match(int p1, int p2)
        {
            return ((p1 ^ p2) == MatchVal);
        }

        // Returns true if piece i in rotation rot fits into the
        // existing solution at position n, otherwise false.  We fill the
        // puzzle from a left -> right, top -> bottom order, so it is 
        // sufficient to check that a new piece's top and left edges match
        // what is already there
        static Boolean Match(int[] sol, int[] rots, int n, int i, int rot)
        {
            ++nops;

            // position n is in the range {0..15}
            // find column and row in the range {0..3}
            // so n = row * 4 + col
            int col = n % C;
            int row = n / R;

            // If col == 0 (i.e. we're at the left column) no need to test.
            // If not, test our left edge matches the right edge of the piece to our left
            if (col > 0 && !(Match(puzzle[i, (rot+3)%4], puzzle[sol[n-1], (rots[n-1]+1)%4])))
                return false;
            // Similarly if we're at row == 0 (i.e. top edge) no need to test.
            // If not, test our top edge matches the bottom edge of the piece above us
            else if (row > 0 && !(Match(puzzle[i, rot%4], puzzle[sol[n-4], (rots[n-4]+2)%4])))
                return false;
            // Both edges match, so return true
            else
                return true;
        }


        // program starts here
        static void Main(string[] args)
        {
            // arrays for our solution to be built

            // records which piece is in each slot
            var sol = new int[N];

            // records the rotation of each piece
            var rots = new int[N];

            // records whether we've used a piece or not
            // (so we don't use the same piece twice)
            var seen = new bool[N];

            if (IterativeSolution(sol, rots, seen, 0))
            {
                // we found a solution, print a bit of information about it
                Console.WriteLine("Success in {0} comparisons!", nops);
                for (int i = 0; i < N; ++i)
                    Console.WriteLine("{0}: Piece {1}, Rot {2}", i, sol[i]+1, rots[i]);
            }
            // Console.WriteLine(nsols);
        }

        // It's actually recursive, not iterative...
        static bool IterativeSolution(int[] sol, int[] rots, bool[] seen, int n)
        {
            // Trying to place the 17th piece can only mean we've 
            // already got 16 in place, so we've found a complete solution
            if (n == N)
                return true;

            // For each piece of the puzzle
            for (int i = 0; i < N; ++i)
            {
                // if it's been used before, skip it
                if (seen[i])
                    continue;

                // find column and row of the position
                // we're trying to fill
                int col = n % C;
                int row = n / R;

                // for each possible rotation of the chosen piece
                for (int r = 0; r < 4; ++r)
                {
                    // if it fits in the position
                    if (Match(sol, rots, n, i, r))
                    {
                        // record this piece in the solution
                        sol[n] = i;

                        // record this piece's rotation value in the solution
                        rots[n] = (int)r;

                        // record that we've seen the piece
                        seen[i] = true;

                        // recursively solve the puzzle by finding
                        // a piece that fits in the next position
                        if (IterativeSolution(sol, rots, seen, n + 1))
                            return true;

                        // If we get here, it means this solution was a dead end.
                        // Remove the piece and try again.
                        seen[i] = false;
                    }
                }
            }

            // Didn't find any solution along this path :-(
            return false;
        }
    }
}