Skip to content

Instantly share code, notes, and snippets.

@peterdn
Created October 15, 2010 10:09
Show Gist options
  • Save peterdn/627951 to your computer and use it in GitHub Desktop.
Save peterdn/627951 to your computer and use it in GitHub Desktop.
Finds a solution for a specific 16-piece edge matching puzzle.
/*
* 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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment