/*
 * Scramble Squares solver
 * Tim Showalter (2007?, 2010)
 *
 * This is an incomplete hack, but it works.  (I stopped writing code when I
 * found my answer.)
 *
 * This program is what happens when my folks give me puzzles for Christmas.
 * I can't stand solving these things by hand.
 *
 * The MUSIC_PUZZLE refers to a Scramble Squares [tm] brand puzzle with
 * oboes, French horns, pianos, and violins.
 *
 * The WINE_PUZZLE refers to a Scramble Squares [tm] brand puzzle.  This is
 * incomplete.
 *
 * The ONE_TOUGH_PUZZLE is a puzzle called, One Tough Puzzle [tm].  It has
 * card-suit-shaped jigsaw slots.  It is identical to Scramble Squares in
 * practice, but has no edges that do not mate.  I assume it is slightly more
 * difficult, because there is no obvious edge.  This was added later.
 * It did cause me to fix some bugs.
 *
 * This code is pretty fragile.  You'll have to edit it to add a new puzzle.
 * Define exactly one of the #defines -- add your own for a new puzzle,
 * actually.  I guess this really needs to be a command-line switch, but I
 * don't care enough to do that work.  I have my answer.
 *
 * For instance, there is one solution to One Tough Puzzle, and it is:

 0 H [       SPADE,  HEART_HOLE,   CLUB_HOLE,       SPADE] 1 A [     DIAMOND,DIAMOND_HOLE,  HEART_HOLE,       HEART] 2 B [  SPADE_HOLE,  HEART_HOLE,       SPADE,     DIAMOND]
 3 E [        CLUB,   CLUB_HOLE,DIAMOND_HOLE,     DIAMOND] 4 J [       HEART,  SPADE_HOLE,  HEART_HOLE,        CLUB] 5 F [  SPADE_HOLE,   CLUB_HOLE,       HEART,       SPADE]
 6 G [     DIAMOND,   CLUB_HOLE,   CLUB_HOLE,       HEART] 7 C [       HEART,DIAMOND_HOLE,   CLUB_HOLE,        CLUB] 8 D [  HEART_HOLE,DIAMOND_HOLE,       SPADE,     DIAMOND]

 * My piece labels are arbitrary, and are defined below.  My program outputs
 * four answers, but they are all just rotations of this one.
 *
 * Similarly, the answer to the "Music" Scramble Squares puzzle, according to this program, is:

 0 C [PIANO_BOTTOM,   HORN_BELL, VIOLIN_NECK, VIOLIN_BODY] 1 A [ VIOLIN_BODY,   OBOE_REED,PIANO_BOTTOM,   HORN_LOOP] 2 J [   HORN_BELL,    NO_MATCH,   PIANO_TOP,   OBOE_BELL]
 3 E [ VIOLIN_BODY,   HORN_LOOP,PIANO_BOTTOM,    NO_MATCH] 4 D [   PIANO_TOP,   OBOE_BELL, VIOLIN_NECK,   HORN_BELL] 5 B [PIANO_BOTTOM,   HORN_BELL, VIOLIN_BODY,   OBOE_REED]
 6 G [   PIANO_TOP,   OBOE_REED, VIOLIN_BODY,PIANO_BOTTOM] 7 H [ VIOLIN_BODY,   HORN_BELL,    NO_MATCH,   OBOE_BELL] 8 F [ VIOLIN_NECK,   PIANO_TOP,   HORN_LOOP,   HORN_LOOP]

 * Unfortunately, that one, I haven't checked.  I believe I no longer have that
 * puzzle.
 *
 * This code could use some cleanup, but it /does/ work, and that's enough to
 * save it.
 *
 * The algorithm is pretty simple, and very much unoptimized.  It's fast enough.
 */

#include <cstdio>
#include <cstdlib>

/* Define ONE of these: */
// #define MUSIC_PUZZLE 1
// #define WINE_PUZZLE
#define ONE_TOUGH_PUZZLE 1

enum symbol {
   
#if MUSIC_PUZZLE
    OBOE_REED = 1,
    OBOE_BELL = -1,
    HORN_LOOP = 2,
    HORN_BELL = -2,
    PIANO_TOP = 3,
    PIANO_BOTTOM = -3,
    VIOLIN_NECK = 4,
    VIOLIN_BODY = -4,

#elif WINE_PUZZLE
    BARREL_SIDE = 1,
    BARREL_END = -1,
    GREEN_GRAPES = 2,
    GREEN_LEAVS = -2,
    BLUE_GRAPES = 3,
    BLUE_LEAVES = -3,
    BRANCH_TRUNK = 4,
    BRANCH_LEAVES = -4,

#elif ONE_TOUGH_PUZZLE
    SPADE = 1,
    SPADE_HOLE = -1,
    HEART = 2,
    HEART_HOLE = -2,
    DIAMOND = 3,
    DIAMOND_HOLE = -3,
    CLUB = 4,
    CLUB_HOLE = -4,

#else
    no_puzzle_defined();
    
#endif
    NO_MATCH = 5                // obvious borders; they have no mate 
};

const char *symbol_to_string(symbol s)
{
    switch (s) {
#define C(X) case X: return #X; break;
# ifdef MUSIC_PUZZLE
        C(OBOE_REED);
        C(OBOE_BELL);
        C(HORN_LOOP);
        C(HORN_BELL);
        C(PIANO_TOP);
        C(PIANO_BOTTOM);
        C(VIOLIN_NECK);
        C(VIOLIN_BODY);
# elif ONE_TOUGH_PUZZLE
	C(SPADE);
	C(SPADE_HOLE);
	C(HEART);
	C(HEART_HOLE);
	C(DIAMOND);
	C(DIAMOND_HOLE);
	C(CLUB);
	C(CLUB_HOLE);
# endif
        C(NO_MATCH);
#undef C
    }
    return 0;
}

struct square
{
    //  0
    // 3 1
    //  2
     
    char id;                    // one-char id
    symbol top, right, bottom, left;
    // square() { abort(); }
    square(char c, symbol tt, symbol rr, symbol bb, symbol ll)
	 : id(c), top(tt), right(rr), bottom(bb), left(ll)
    {
	 printf("%c %2d,%2d,%2d,%2d\n", id, top, right, bottom, left);
	 printf("%c [%s,%s,%s,%s]\n",
		id,
                symbol_to_string(top),
		symbol_to_string(right),
		symbol_to_string(bottom),
		symbol_to_string(left));
    }

    void rotate()
    {
	 // printf(" in %2d,%2d,%2d,%2d\n", top, left, bottom, right);
	 symbol tmp;
	 tmp    = top;
	 top    = left;
	 left   = bottom;
	 bottom = right;
	 right  = tmp;
	 // printf("out %2d,%2d,%2d,%2d\n", top, left, bottom, right);
    }
};

const int DIM_X = 3;
const int DIM_Y = 3;
const int NSQUARES = DIM_X * DIM_Y;

static void print(square const *const *const state)
{
    for (int i = 0; i < DIM_Y; i++) {
        for (int j = 0; j < DIM_X; j++) {
            int n = i*DIM_Y + j;
            const square *const sq = state[n];
            if (sq == 0) {
                printf("-- - [--,--,--,--] ");
            } else {
// 		 printf("%2d %c [%2d,%2d,%2d,%2d] ",
//                        n, sq->id,
//                        sq->top, sq->right, sq->bottom, sq->left);
		 printf("%2d %c [%12s,%12s,%12s,%12s]",
			n, sq->id,
			symbol_to_string(sq->top),
			symbol_to_string(sq->right),
			symbol_to_string(sq->bottom),
			symbol_to_string(sq->left));
            }
        }
        printf("\n");
    }
}
 
static bool validate(square *const *const state) // array of pointers to state
{
    for (int i = 0; i < NSQUARES; i++) {
        const square *const self = state[i];
        if (self == 0) continue; // nothing to validate here yet
        const int ypos = i / DIM_Y;
        const int xpos = (i - ypos * DIM_Y) % DIM_X;
        if (xpos > 0) {
            if (self->left == NO_MATCH) return false;
            const square *left = state[i-1];
            // there is a square to the left
            if (left) {
                if (self->left != - left->right) {
                    // printf("!= square %c in slot %d has %s on the left;\n"
                    //        "   square %c in slot %d has %s on the right\n",
                    //        self->id, i,   symbol_to_string(self->left),
                    //        left->id, i-1, symbol_to_string(left->right));
                    return false;
                }
                // printf("== square %c in slot %d has %s on the left;\n"
                //        "   square %c in slot %d has %s on the right\n",
                //        self->id, i,   symbol_to_string(self->left),
                //        left->id, i-1, symbol_to_string(left->right));
            }
        }
	// printf("xpos=%d ypos=%d\n", xpos, ypos);
        if (ypos > 0) {
            if (self->top == NO_MATCH) return false;
	    const square *above = state[i-DIM_Y];
	    // there is a square above, because we assume we're
	    // searching in order
            if (above) {
                if (self->top != - above->bottom) {
                    // printf("!= square %c in slot %d has %s on the top;\n"
                    //        "   square %c in slot %d has %s on the bottom\n",
                    //        self->id, i,       symbol_to_string(self->top),
                    //        above->id, i-DIM_Y, symbol_to_string(above->bottom));
                    return false;
                }
                // printf("== square %c in slot %d has %s on the top;\n"
                //        "   square %c in slot %d has %s on the bottom\n",
                //        self->id, i,       symbol_to_string(self->top),
                //        above->id, i-DIM_Y, symbol_to_string(above->bottom));
            }
        }
    }
    return true;
}

static void search(int nsq,     // use this square from sqs
                   const square *sqs, // input squares
                   square **state) // global state list
{
    // printf("search; nsq = %d\n", nsq);
    if (nsq == NSQUARES) {
        if (validate(state)) {
            printf("answer:\n");
            print(state);
            return;
        }
    }
    
    square mytmp = sqs[nsq];
    for (int i = 0; i < NSQUARES; i++) {
        if (state[i] == 0) {
            state[i] = &mytmp;
            // try each rotation in this slot
            for (int j = 0; j < 4; j++) {
                mytmp.rotate();
                if (validate(state) == true) {
                    search(nsq+1, sqs, state);
                }
            }
            state[i] = 0;
        }
    }
}

int main()
{
#if 0
    square sqs[] = {
        // for validation purposes, this works in the trivial matrix
        // plus its four rotations
        square('A', NO_MATCH, NO_MATCH, VIOLIN_BODY, HORN_LOOP),
        square('B', NO_MATCH, HORN_BELL, PIANO_TOP, HORN_BELL),
        // square('B', NO_MATCH, NO_MATCH, NO_MATCH, NO_MATCH),
        square('C', VIOLIN_NECK, NO_MATCH, NO_MATCH, OBOE_REED),
        square('D', PIANO_BOTTOM, OBOE_BELL, NO_MATCH, OBOE_BELL),
    };
    state[0] = &sqs[0];
    state[1] = &sqs[1];
    state[2] = &sqs[2];
    state[3] = &sqs[3];
    printf ("validate 2x2: %d\n", validate(state));
#endif

    square sqs[] = {
    //  0
    // 3 1
    //  2
#if MUSIC_PUZZLE
        square('A', HORN_LOOP, VIOLIN_BODY, OBOE_REED, PIANO_BOTTOM),
        square('B', VIOLIN_BODY, OBOE_REED, PIANO_BOTTOM, HORN_BELL),
        square('C', HORN_BELL, VIOLIN_NECK, VIOLIN_BODY, PIANO_BOTTOM),
        square('D', OBOE_BELL, VIOLIN_NECK, HORN_BELL, PIANO_TOP),
        square('E', PIANO_BOTTOM, NO_MATCH, VIOLIN_BODY, HORN_LOOP),
        square('F', HORN_LOOP, HORN_LOOP, VIOLIN_NECK, PIANO_TOP),
        square('J', HORN_BELL, NO_MATCH, PIANO_TOP, OBOE_BELL),
        square('G', VIOLIN_BODY, PIANO_BOTTOM, PIANO_TOP, OBOE_REED),
        square('H', OBOE_BELL, VIOLIN_BODY, HORN_BELL, NO_MATCH),
#elif WINE_PUZZLE
        never_did_implement_this(),
#elif ONE_TOUGH_PUZZLE
	square('A', DIAMOND, DIAMOND_HOLE, HEART_HOLE, HEART),
	square('B', DIAMOND, SPADE_HOLE, HEART_HOLE, SPADE),
	square('C', HEART, DIAMOND_HOLE, CLUB_HOLE, CLUB),
	square('D', SPADE, DIAMOND, HEART_HOLE, DIAMOND_HOLE),
	square('E', CLUB, CLUB_HOLE, DIAMOND_HOLE, DIAMOND),
	square('F', HEART, SPADE, SPADE_HOLE, CLUB_HOLE),
	square('G', HEART, DIAMOND, CLUB_HOLE, CLUB_HOLE),
	square('H', SPADE, SPADE, HEART_HOLE, CLUB_HOLE),
	square('J', CLUB, HEART, SPADE_HOLE, HEART_HOLE),
#endif
    };
    square *state[NSQUARES] = {0};
    search(0, sqs, state);

    printf("(end)\n");
}