One Tough Puzzle Solver

onetoughpuzzle.js

/**
 * onetoughpuzzle.js
 *
 * The model and puzzle solving functionality for finding solutions to
 * the One Tough Puzzle toys distributed by Great American Puzzle Factory
 *
 * Copyright (C) 2011 Jimmy Theis
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is furnished to do
 * so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

// Constants for interlocks
var PositiveHeartInterlock = '+H';
var PositiveSpadeInterlock = '+S';
var PositiveDiamondInterlock = '+D';
var PositiveClubInterlock = '+C';
var NegativeHeartInterlock = '-H';
var NegativeSpadeInterlock = '-S';
var NegativeDiamondInterlock = '-D';
var NegativeClubInterlock = '-C';

// Aggregate list of interlocks
var interlockMatches = {}
interlockMatches[PositiveHeartInterlock] = NegativeHeartInterlock;
interlockMatches[PositiveSpadeInterlock] = NegativeSpadeInterlock;
interlockMatches[PositiveDiamondInterlock] = NegativeDiamondInterlock;
interlockMatches[PositiveClubInterlock] = NegativeClubInterlock;
interlockMatches[NegativeHeartInterlock] = PositiveHeartInterlock;
interlockMatches[NegativeSpadeInterlock] = PositiveSpadeInterlock;
interlockMatches[NegativeDiamondInterlock] = PositiveDiamondInterlock;
interlockMatches[NegativeClubInterlock] = PositiveClubInterlock;

/**
 * Model for a single puzzle piece.
 */
var Piece = function(topInterlock, rightInterlock, bottomInterlock, leftInterlock) {
    this.rotations = 0;
    this.topInterlock = topInterlock;
    this.rightInterlock = rightInterlock;
    this.bottomInterlock = bottomInterlock;
    this.leftInterlock = leftInterlock;

    /**
     * Set all of this piece's interlocks at once.
     */
    this.setInterlocks = function(topInterlock, rightInterlock, bottomInterlock, leftInterlock) {
        this.topInterlock = topInterlock;
        this.rightInterlock = rightInterlock;
        this.bottomInterlock = bottomInterlock;
        this.leftInterlock = leftInterlock;
        this.wasFlipped = false;
    }

    /**
     * Whether or not this piece has any of its interlocks set.
     */
    this.isEmpty = function() {
        return this.topInterlock == null &&
            this.rightInterlock == null &&
            this.bottomInterlock == null &&
            this.leftInterlock == null;
    };

    /**
     * Create a clockwise rotated copy of this piece without
     * affecting the original.
     */
    this.rotated = function() {
        var result = new Piece();
        result.setInterlocks(this.leftInterlock, this.topInterlock,
                this.rightInterlock, this.bottomInterlock);
        result.rotations = this.rotations + 1;
        result.wasFlipped = this.wasFlipped;
        return result;
    }

    /**
     * Create a flipped copy of this piece without affecting the original
     */
    this.flipped = function() {
        var result = new Piece();
        result.setInterlocks(this.bottomInterlock, this.rightInterlock, this.topInterlock, this.leftInterlock);
        result.rotations = this.rotations;
        result.wasFlipped = true;
        return result;
    }
}

/**
 * Model for entire puzzle "board".
 */
var Board = function() {
    this.contents = [new Piece(), new Piece(), new Piece(),
                     new Piece(), new Piece(), new Piece(),
                     new Piece(), new Piece(), new Piece()];

    /**
     * Whether or not this board has every space occupied by
     * a non-empty piece.
     */
    this.isFull = function() {
        for (var i = 0; i < this.contents.length; i++) {
            if (this.contents[i].isEmpty()) return false;
        }

        return true;
    }

    /**
     * How many pieces are flipped in this board
     */
    this.numberFlipped = function() {
        var result = 0;
        for (var i = 0; i < this.contents.length; i++) {
            if (this.contents[i].wasFlipped) result ++;
        }

        return result;
    }

    /**
     * The first available space that is currently occupied by
     * an empty piece.
     */
    this.nextEmptySpace = function() {
        for (var i = 0; i < this.contents.length; i++) {
            if (this.contents[i].isEmpty()) return i;
        }

        return -1;
    }

    /**
     * Whether or not a piece will connect properly with the pieces
     * adjacent to the next available space.
     */
    this.canFitNextPiece = function(piece) {
        // Piece positions:
        //   0 1 2
        //   3 4 5
        //   6 7 8
        
        // Prevent more than four pieces being flipped
        if (this.numberFlipped() >= 4 && piece.wasFlipped) {
            return false;
        }

        // Helper variable to shorten the contents array name
        var c = this.contents;

        // Interlocks adjacent to each position, ordered by interlocks adjacent to top, right, bottom, left.
        // If no piece is adjacent on a side, the interlock value is null.
        var adjacency = [
            // Top row
            [null,                 c[1].leftInterlock, c[3].topInterlock, null               ],
            [null,                 c[2].leftInterlock, c[4].topInterlock, c[0].rightInterlock],
            [null,                 null,               c[5].topInterlock, c[1].rightInterlock],

            // Middle row
            [c[0].bottomInterlock, c[4].leftInterlock, c[6].topInterlock, null               ],
            [c[1].bottomInterlock, c[5].leftInterlock, c[7].topInterlock, c[3].rightInterlock],
            [c[2].bottomInterlock, null,               c[8].topInterlock, c[4].rightInterlock],

            // Bottom row
            [c[3].bottomInterlock, c[7].leftInterlock, null,              null               ],
            [c[4].bottomInterlock, c[8].leftInterlock, null,              c[6].rightInterlock],
            [c[5].bottomInterlock, null,               null,              c[7].rightInterlock]
        ];

        if (this.isFull()) return false;

        interlocks = adjacency[this.nextEmptySpace()];

        var matches = function(pieceSide, boardSide) {
            return boardSide == null || interlockMatches[pieceSide] == boardSide;
        }

        return matches(piece.topInterlock, interlocks[0]) &&
            matches(piece.rightInterlock, interlocks[1]) &&
            matches(piece.bottomInterlock, interlocks[2]) &&
            matches(piece.leftInterlock, interlocks[3]);
    }

    /**
     * Create a copy of this board with the next available space that
     * is currently occupied by an empty piece populated with the piece
     * passed to this method.
     */
    this.withNextPiece = function(piece) {
        var result = new Board();
        result.contents = this.contents.slice(0);
        
        if (result.isFull()) return result;

        result.contents[result.nextEmptySpace()] = piece;

        return result;
    }

    /**
     * Generate a string that uniquely identifies this board
     * but is the same across all rotations of this board
     */
    this.hash = function() {
        edges = [this.contents[0].topInterlock,
                 this.contents[1].topInterlock,
                 this.contents[2].topInterlock,
                 this.contents[2].rightInterlock,
                 this.contents[5].rightInterlock,
                 this.contents[8].rightInterlock,
                 this.contents[8].bottomInterlock,
                 this.contents[7].bottomInterlock,
                 this.contents[6].bottomInterlock,
                 this.contents[6].leftInterlock,
                 this.contents[3].leftInterlock,
                 this.contents[0].leftInterlock];

        var hash = edges.join();

        for (var i = 0; i < edges.length; i++) {
            edges.push(edges.shift());

            var next = edges.join();

            if (next < hash) {
                hash = next;
            }
        }

        return hash;
    }

    /**
     * Return a text representation of this board.
     * Really only works for valid and full boards.
     */
    this.toString = function() {
        var c = this.contents;

        var f = function(psn) { return c[psn].wasFlipped ? 'F' : ' '; }

        var pos = function(st) { return st[0] == '+' ? st[1] : ' '; }
        var neg = function(st) { return st[0] == '-' ? st[1] : ' '; }

        var pt = function(psn) { return pos(c[psn].topInterlock); }
        var nt = function(psn) { return neg(c[psn].topInterlock); }

        var pr = function(psn) { return pos(c[psn].rightInterlock); }
        var nr = function(psn) { return neg(c[psn].rightInterlock); }

        var pb = function(psn) { return pos(c[psn].bottomInterlock); }
        var nb = function(psn) { return neg(c[psn].bottomInterlock); }

        var pl = function(psn) { return pos(c[psn].leftInterlock); }
        var nl = function(psn) { return neg(c[psn].leftInterlock); }

        return '     '+pt(0)+'       '+pt(1)+'       ' +pt(2)+'     \n' + 
               ' +---|---+---|---+---|---+ \n' +
               ' |   '+nt(0)+'   |   '+nt(1)+'   |   '+nt(2)+'   | \n' +
               pl(0)+'-'+nl(0)+'  '+f(0)+'  '+pl(1)+'-'+pr(0)+'  '+f(1)+'  '+pl(2)+'-'+pr(1)+'  '+f(2)+'  '+nr(2)+'-'+pr(2)+'\n' +
               ' |   '+pt(3)+'   |   '+pt(4)+'   |   '+pt(5)+'   | \n' +
               ' +---|---+---|---+---|---+ \n' + 
               ' |   '+pb(0)+'   |   '+pb(1)+'   |   '+pb(2)+'   | \n' +
               pl(3)+'-'+nl(3)+'  '+f(3)+'  '+pl(4)+'-'+pr(3)+'  '+f(4)+'  '+pl(5)+'-'+pr(4)+'  '+f(5)+'  '+nr(5)+'-'+pr(5)+'\n' +
               ' |   '+pt(6)+'   |   '+pt(7)+'   |   '+pt(8)+'   | \n' +
               ' +---|---+---|---+---|---+ \n' + 
               ' |   '+pb(3)+'   |   '+pb(4)+'   |   '+pb(5)+'   | \n' +
               pl(6)+'-'+nl(6)+'  '+f(6)+'  '+pl(7)+'-'+pr(6)+'  '+f(7)+'  '+pl(8)+'-'+pr(7)+'  '+f(8)+'  '+nr(8)+'-'+pr(8)+'\n' +
               ' |   '+nb(6)+'   |   '+nb(7)+'   |   '+nb(8)+'   | \n' +
               ' +---|---+---|---+---|---+ \n' +
               '     '+pb(6)+'       '+pb(7)+'       '+pb(8)+'      ';
    }
}

/**
 * A representation of a board state, for solving
 */
var State = function(board, pieces) {
    this.board = board;
    this.pieces = pieces;
}

/**
 * Create a solved board given a list of 9 pieces
 */
var solvePuzzle = function(pieces) {
    // Helper function that removes the first element of an array, if there is one.
    var shortened = function(ary) { return ary.length <= 1 ? [] : ary.slice(1); }

    var board = new Board();
    var workspace = [];

    // Push initial empty board state
    workspace.push(new State(board, pieces));

    while (true) {

        // Base case that will be triggered if a solution is not found
        if (workspace.length <= 0) return null;

        // Retrieve the top state on the workspace
        var state = workspace.pop();

        var board = state.board;
        var pieces = state.pieces;

        // Base case that will be triggered when the board is filled
        if (board.isFull()) return board;

        for (var i = 0; i < pieces.length; i++) {
            // Retrieve one of the remaining pieces
            var piece = pieces[i];

            // Strip that piece out of the pices left over
            var nextPieces = pieces.slice(0, i).concat(pieces.slice(i + 1, pieces.length));

            // Generate rotations of the retrieved piece
            var piece2 = piece.rotated();
            var piece3 = piece2.rotated();
            var piece4 = piece3.rotated();

            // If any rotation of the piece fits in the next available space,
            // create the state with that piece added to the board and push
            // it onto the workspace stack
            if (board.canFitNextPiece(piece)) workspace.push(new State(board.withNextPiece(piece), nextPieces))
            if (board.canFitNextPiece(piece2)) workspace.push(new State(board.withNextPiece(piece2), nextPieces));
            if (board.canFitNextPiece(piece3)) workspace.push(new State(board.withNextPiece(piece3), nextPieces));
            if (board.canFitNextPiece(piece4)) workspace.push(new State(board.withNextPiece(piece4), nextPieces));
        }
    }
}

var findAllSolutions = function(pieces) {
    // Helper function that removes the first element of an array, if there is one.
    var shortened = function(ary) { return ary.length <= 1 ? [] : ary.slice(1); }

    var board = new Board();
    var workspace = [];

    results = [];

    // Push initial empty board state
    workspace.push(new State(board, pieces));

    while (true) {

        // Base case that will be triggered if a solution is not found
        if (workspace.length <= 0) return results;

        // Retrieve the top state on the workspace
        var state = workspace.pop();

        var board = state.board;
        var pieces = state.pieces;

        // Base case that will be triggered when the board is filled
        if (board.isFull()) results[board.hash()] = board;

        for (var i = 0; i < pieces.length; i++) {
            // Retrieve one of the remaining pieces
            var piece = pieces[i];

            // Strip that piece out of the pices left over
            var nextPieces = pieces.slice(0, i).concat(pieces.slice(i + 1, pieces.length));

            // Generate rotations of the retrieved piece
            var piece2 = piece.rotated();
            var piece3 = piece2.rotated();
            var piece4 = piece3.rotated();

            var piece5 = piece.flipped();
            var piece6 = piece5.rotated();
            var piece7 = piece6.rotated();
            var piece8 = piece7.rotated();

            // If any rotation of the piece fits in the next available space,
            // create the state with that piece added to the board and push
            // it onto the workspace stack
            if (board.canFitNextPiece(piece)) workspace.push(new State(board.withNextPiece(piece), nextPieces))
            if (board.canFitNextPiece(piece2)) workspace.push(new State(board.withNextPiece(piece2), nextPieces));
            if (board.canFitNextPiece(piece3)) workspace.push(new State(board.withNextPiece(piece3), nextPieces));
            if (board.canFitNextPiece(piece4)) workspace.push(new State(board.withNextPiece(piece4), nextPieces));

            if (board.canFitNextPiece(piece5)) workspace.push(new State(board.withNextPiece(piece5), nextPieces));
            if (board.canFitNextPiece(piece6)) workspace.push(new State(board.withNextPiece(piece6), nextPieces));
            if (board.canFitNextPiece(piece7)) workspace.push(new State(board.withNextPiece(piece7), nextPieces));
            if (board.canFitNextPiece(piece8)) workspace.push(new State(board.withNextPiece(piece8), nextPieces));
        }
    }

    return results;
}

onetoughpuzzletests.js

/**
 * onetoughpuzzletests.js
 *
 * Unit tests for toughpuzzle.js
 *
 * Dependencies:
 *  - jQuery with $ bound
 *  - qUnit
 *  - onetoughpuzzle.js
 *
 * Copyright (C) 2011 Jimmy Theis
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is furnished to do
 * so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */


$(document).ready(function() {

    module('Piece Model');

    test('Constructor property setting', function() {
        var piece = new Piece();
        piece.setInterlocks(PositiveHeartInterlock, NegativeHeartInterlock,
            NegativeSpadeInterlock,PositiveClubInterlock);

        equal(piece.topInterlock, PositiveHeartInterlock, 'Top interlock is correct');
        equal(piece.rightInterlock, NegativeHeartInterlock, 'Right interlock is correct');
        equal(piece.bottomInterlock, NegativeSpadeInterlock, 'Bottom interlock is correct');
        equal(piece.leftInterlock, PositiveClubInterlock, 'Left interlock is correct');
    });

    test('Rotation', function() {
        var piece = new Piece();
        piece.setInterlocks(PositiveHeartInterlock, NegativeHeartInterlock,
            NegativeSpadeInterlock,PositiveClubInterlock);

        var rotated = piece.rotated();

        equal(rotated.topInterlock, piece.leftInterlock, 'Left interlock rotated to top');
        equal(rotated.rightInterlock, piece.topInterlock, 'Top interlock rotated to right');
        equal(rotated.bottomInterlock, piece.rightInterlock, 'Right interlock rotated to bottom');
        equal(rotated.leftInterlock, piece.bottomInterlock, 'Bottom interlock rotated to left');
    });

    test('Rotation count', function() {
        var piece = new Piece();

        equal(piece.rotations, 0, 'Original piece has no rotations');

        piece = piece.rotated();

        equal(piece.rotations, 1, 'Single rotation counted');

        piece = piece.rotated();

        equal(piece.rotations, 2, 'Second rotation counted');

        piece = piece.rotated();
        piece = piece.rotated();
        piece = piece.rotated();

        equal(piece.rotations, 5, 'More than four rotations counted')
    });

    test('Emptiness detection', function() {
        var piece = new Piece();

        ok(piece.isEmpty(), 'Original piece is empty');

        piece.setInterlocks(PositiveHeartInterlock, NegativeHeartInterlock,
            NegativeSpadeInterlock,PositiveClubInterlock);

        ok(!piece.isEmpty(), 'Modified piece is not empty');
    });

    module('Board Model');

    test('Fullness detection', function() {
        var board = new Board();

        ok(!board.isFull(), 'New board is not full');

        board.contents[0].topInterlock = PositiveHeartInterlock;
        board.contents[1].topInterlock = PositiveHeartInterlock;
        board.contents[2].topInterlock = PositiveHeartInterlock;
        board.contents[3].topInterlock = PositiveHeartInterlock;
        board.contents[4].topInterlock = PositiveHeartInterlock;
        board.contents[5].topInterlock = PositiveHeartInterlock;
        board.contents[6].topInterlock = PositiveHeartInterlock;
        board.contents[7].topInterlock = PositiveHeartInterlock;

        ok(!board.isFull(), 'Mostly full board is not full');

        board.contents[8].topInterlock = PositiveHeartInterlock;

        ok(board.isFull(), 'Full board is full');
    });

    test('Next empty space', function() {
        var board = new Board();

        equal(board.nextEmptySpace(), 0, 'First empty space is correct');

        board.contents[0].topInterlock = PositiveHeartInterlock;

        equal(board.nextEmptySpace(), 1, 'Second empty space is correct');

        board.contents[1].topInterlock = PositiveHeartInterlock;
        board.contents[2].topInterlock = PositiveHeartInterlock;
        board.contents[3].topInterlock = PositiveHeartInterlock;
        board.contents[4].topInterlock = PositiveHeartInterlock;
        board.contents[5].topInterlock = PositiveHeartInterlock;
        board.contents[6].topInterlock = PositiveHeartInterlock;
        board.contents[7].topInterlock = PositiveHeartInterlock;

        equal(board.nextEmptySpace(), 8, 'Last empty space is correct');

        board.contents[8].topInterlock = PositiveHeartInterlock;

        equal(board.nextEmptySpace(), -1, 'Board is full');
    });

    test('Next piece insertion', function() {
        var board = new Board();
        var piece = new Piece();
        piece.setInterlocks(PositiveHeartInterlock, NegativeHeartInterlock,
            NegativeSpadeInterlock,PositiveClubInterlock);

        ok(board.contents[0].isEmpty(), 'Board is empty');

        var newBoard = board.withNextPiece(piece);

        ok(board.contents[0].isEmpty(), 'Original board is still empty');

        ok(!newBoard.contents[0].isEmpty(), 'New board is not empty');
    });

    test('Hashing', function() {
        var piece1 = new Piece('+H', '+H', '+H', '+H');
        var piece2 = new Piece('+D', '+D', '+D', '+D');

        var board1 = new Board();
        board1.contents = [piece1, piece1, piece1, piece1, piece1, piece1, piece2, piece2, piece2];

        var board2 = new Board();
        board2.contents = [piece2, piece2, piece2, piece1, piece1, piece1, piece1, piece1, piece1];

        var board3 = new Board();
        board3.contents = [piece1, piece1, piece2, piece1, piece1, piece2, piece1, piece1, piece2];

        equal(board1.hash(), board3.hash(), 'Single rotated hashes match');
        equal(board1.hash(), board2.hash(), 'Double rotated hashes match');
    });

    test('Basic fit checking', function() {
        var board = new Board();
        var piece1 = new Piece();
        var piece2 = new Piece();

        // Piece 1:
        //       S
        //   +---|---+
        //   |       |
        //  S-      H-
        //   |       |
        //   +---|---+
        //       S

        piece1.setInterlocks(PositiveSpadeInterlock, NegativeHeartInterlock,
            PositiveSpadeInterlock, PositiveSpadeInterlock);

        // Piece 2:
        //       C
        //   +---|---+
        //   |       |
        //  C-       -C
        //   |       |
        //   +---|---+
        //       H

        piece2.setInterlocks(PositiveClubInterlock, PositiveClubInterlock,
                PositiveHeartInterlock, PositiveClubInterlock);

        ok(board.canFitNextPiece(piece1), 'Empty board accepts any piece');

        board = board.withNextPiece(piece1);

        ok(!board.canFitNextPiece(piece2), 'Board denies second piece');

        ok(board.canFitNextPiece(piece2.rotated()), 'Board accepts rotated second piece');
    });
    
    test('Advanced fit checking', function() {
        var board = new Board();
        var piece = new Piece();
        piece.setInterlocks(PositiveSpadeInterlock, NegativeClubInterlock,
            NegativeSpadeInterlock, PositiveClubInterlock);

        // Piece:
        //      S
        //  +---|---+
        //  |       |
        // C-      C-
        //  |   S   |
        //  +---|---+
        //
        // Invalid rotated form:
        //       C
        //   +---|---+
        //   |       |
        //   -S      -S
        //   |   C   |
        //   +---|---+

        ok(board.canFitNextPiece(piece), 'Empty board accepts any piece');
        board = board.withNextPiece(piece);

        ok(!board.canFitNextPiece(piece.rotated()), 'Board denies rotated second piece');
        ok(board.canFitNextPiece(piece), 'Board accepts second piece');
        board = board.withNextPiece(piece);

        ok(!board.canFitNextPiece(piece.rotated()), 'Board denies rotated third piece');
        ok(board.canFitNextPiece(piece), 'Board accepts third piece');
        board = board.withNextPiece(piece);

        ok(!board.canFitNextPiece(piece.rotated()), 'Board denies rotated fourth piece');
        ok(board.canFitNextPiece(piece), 'Board accepts fourth piece');
        board = board.withNextPiece(piece);

        ok(!board.canFitNextPiece(piece.rotated()), 'Board denies rotated fifth piece');
        ok(board.canFitNextPiece(piece), 'Board accepts fifth piece');
        board = board.withNextPiece(piece);

        ok(!board.canFitNextPiece(piece.rotated()), 'Board denies rotated sixth piece');
        ok(board.canFitNextPiece(piece), 'Board accepts sixth piece');
        board = board.withNextPiece(piece);

        ok(!board.canFitNextPiece(piece.rotated()), 'Board denies rotated seventh piece');
        ok(board.canFitNextPiece(piece), 'Board accepts seventh piece');
        board = board.withNextPiece(piece);

        ok(!board.canFitNextPiece(piece.rotated()), 'Board denies rotated eighth piece');
        ok(board.canFitNextPiece(piece), 'Board accepts eighth piece');
        board = board.withNextPiece(piece);

        ok(!board.canFitNextPiece(piece.rotated()), 'Board denies rotated ninth piece');
        ok(board.canFitNextPiece(piece), 'Board accepts ninth piece');
    });

    module('Solving');

    test('Very basic solving', function() {
        var piece = new Piece();
        piece.setInterlocks(PositiveSpadeInterlock, NegativeClubInterlock,
            NegativeSpadeInterlock, PositiveClubInterlock);
        var pieces = [piece, piece, piece, piece, piece, piece, piece, piece, piece];

        var board = solvePuzzle(pieces, function() {}, function(b) {});
        ok(board.isFull(), 'Puzzle is full');
    });

    test('End rotation solving', function() {
        var piece = new Piece();
        piece.setInterlocks(PositiveSpadeInterlock, NegativeClubInterlock,
            NegativeSpadeInterlock, PositiveClubInterlock);

        var pieces = [piece, piece, piece, piece, piece, piece, piece, piece, piece.rotated()];

        var board = solvePuzzle(pieces);
        ok(board != null && board.isFull(), 'Puzzle is full');
    });

    test('Early rotations solving', function() {
        var piece = new Piece();
        piece.setInterlocks(PositiveSpadeInterlock, NegativeClubInterlock,
            NegativeSpadeInterlock, PositiveClubInterlock);

        var pieces = [piece.rotated(), piece, piece, piece, piece, piece, piece, piece, piece];

        var board = solvePuzzle(pieces);
        ok(board != null && board.isFull(), 'Puzzle is full');
    });

    test('Complex solving', function() {
        var side = new Piece();
        side.setInterlocks(PositiveSpadeInterlock, PositiveClubInterlock,
            NegativeHeartInterlock, PositiveClubInterlock);

        //      S
        //  +---|---+
        //  |       |
        // C-       -C
        //  |   H   |
        //  +---|---+
        //    

        var corner = new Piece();
        corner.setInterlocks(PositiveSpadeInterlock, PositiveSpadeInterlock,
            NegativeClubInterlock, NegativeClubInterlock);

        //      S
        //  +---|---+
        //  |       |
        //  -C      -S
        //  |   C   |
        //  +---|---+
        //

        var center = new Piece();
        center.setInterlocks(PositiveHeartInterlock, PositiveHeartInterlock,
                PositiveHeartInterlock, PositiveHeartInterlock);

        //      H
        //  +---|---+
        //  |       |
        // H-       -H
        //  |       |
        //  +---|---+
        //      H

        var pieces = [corner, corner, corner, corner, side, side, side, side, center];

        var board = solvePuzzle(pieces);
        ok(board != null && board.isFull(), 'Puzzle is full');

        pieces = [corner, side, center, corner, side, side, side, corner, corner];

        var newBoard = solvePuzzle(pieces);
        ok(newBoard != null && newBoard.isFull(), 'Puzzle is full');
        equal('\n' + board.toString(), '\n' + newBoard.toString(), 'Solutions are the same');
    });

    test('Official solving', function() {
        var piece1 = new Piece();
        piece1.setInterlocks('+C', '+D', '-D', '-C');

        var piece2 = new Piece();
        piece2.setInterlocks('+D', '+S', '-D', '-H');

        var piece3 = new Piece();
        piece3.setInterlocks('+H', '+C', '-H', '-S');

        var piece4 = new Piece();
        piece4.setInterlocks('+D', '+H', '-C', '-C');

        var piece5 = new Piece();
        piece5.setInterlocks('+H', '+C', '-C', '-D');

        var piece6 = new Piece();
        piece6.setInterlocks('+S', '+S', '-C', '-H');

        var piece7 = new Piece();
        piece7.setInterlocks('+D', '+H', '-H', '-D');

        var piece8 = new Piece();
        piece8.setInterlocks('+S', '+H', '-C', '-S');

        var piece9 = new Piece();
        piece9.setInterlocks('+D', '+S', '-H', '-S');

        var pieces = [piece1, piece2, piece3, piece4, piece5, piece6, piece7, piece8, piece9];

        var board = solvePuzzle(pieces);

        ok(board.isFull(), 'Puzzle is full');
        equal('\n' + board.toString(), '\n' + board.toString(), 'Display puzzle');
    });
});

playground.html

<!DOCTYPE html>
<!--
    playground.html

    Interactive "One Tough Puzzle" solver

    Copyright (C) 2011 Jimmy Theis

    Permission is hereby granted, free of charge, to any person obtaining a copy of
    this software and associated documentation files (the "Software"), to deal in
    the Software without restriction, including without limitation the rights to
    use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
    of the Software, and to permit persons to whom the Software is furnished to do
    so, subject to the following conditions:
    
    The above copyright notice and this permission notice shall be included in all
    copies or substantial portions of the Software.
    
    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
    SOFTWARE. 
-->
<html>
    <head>
        <style type="text/css">
            select.top {
                display: inline-block;
                position:relative;
                left:25px;
                top:-8px;
            }
            
            select.right {
                display: inline-block;
                position:relative;
                left:70px;
                top:-5px;
            }
            select.bottom {
                display: inline-block;
                position:relative;
                left:25px; 
                top:20px;
            }
            select.left {
                display: inline-block;
                position:relative;
                left:-15px; 
                top: 15px;
            }
            
            .row {
                display: block;
            }
            
            .piece {
                display: inline-block;
                background-color: #800;
                width: 100px;
                height: 100px;
                margin: 20px 10px 10px 30px;
            }
        </style>
        <script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.7.1/jquery.min.js"></script>
        <script type="text/javascript" src="onetoughpuzzle.js"></script>
        <script type="text/javascript">
            $(document).ready(function() {
                var pieces = function() {
                    var piece1 = new Piece($('#1t').val(), $('#1r').val(), $('#1b').val(), $('#1l').val());
                    var piece2 = new Piece($('#2t').val(), $('#2r').val(), $('#2b').val(), $('#2l').val());
                    var piece3 = new Piece($('#3t').val(), $('#3r').val(), $('#3b').val(), $('#3l').val());
                    var piece4 = new Piece($('#4t').val(), $('#4r').val(), $('#4b').val(), $('#4l').val());
                    var piece5 = new Piece($('#5t').val(), $('#5r').val(), $('#5b').val(), $('#5l').val());
                    var piece6 = new Piece($('#6t').val(), $('#6r').val(), $('#6b').val(), $('#6l').val());
                    var piece7 = new Piece($('#7t').val(), $('#7r').val(), $('#7b').val(), $('#7l').val());
                    var piece8 = new Piece($('#8t').val(), $('#8r').val(), $('#8b').val(), $('#8l').val());
                    var piece9 = new Piece($('#9t').val(), $('#9r').val(), $('#9b').val(), $('#9l').val());
                    return [piece1, piece2, piece3, piece4, piece5, piece6, piece7, piece8, piece9];
                }

                $('button#solve').click(function() {
                    var board = solvePuzzle(pieces());

                    if (board === null) {
                        $('#solution').text("No solution found.\nMake sure you entered all pieces correctly.");
                    } else {
                        $('#solution').text(board.toString());
                    }
                });

                $('button#solveall').click(function() {
                    var boards = findAllSolutions(pieces());
                    var total = 0;
                    var answer = '';

                    for (key in boards) {
                        total ++;
                        answer += '\n' + boards[key].toString();
                    }

                    $('#solution').text('Found ' + total + ' solutions:' + answer);
                });
             });
        </script>
    </head>
    <body>
        <div class="row">
            <div class="piece">
                <select id="1t" class="top">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D" selected="selected">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="1l" class="left">
                    <option value="+H">+H</option>
                    <option value="+C" selected="selected">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="1r" class="right">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D" selected="selected">-D</option>
                </select>
                <select id="1b" class="bottom">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C" selected="selected">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
            </div>
            <div class="piece">
                <select id="2t" class="top">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S" selected="selected">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="2l" class="left">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D" selected="selected">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="2r" class="right">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D" selected="selected">-D</option>
                </select>
                <select id="2b" class="bottom">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H" selected="selected">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
            </div>
            <div class="piece">
                <select id="3t" class="top">
                    <option value="+H">+H</option>
                    <option value="+C" selected="selected">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="3l" class="left">
                    <option value="+H" selected="selected">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="3r" class="right">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H" selected="selected">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="3b" class="bottom">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S" selected="selected">-S</option>
                    <option value="-D">-D</option>
                </select>
            </div>
        </div>
        <div class="row">
            <div class="piece">
                <select id="4t" class="top">
                    <option value="+H" selected="selected">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="4l" class="left">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D" selected="selected">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="4r" class="right">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C" selected="selected">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="4b" class="bottom">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C" selected="selected">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
            </div>
            <div class="piece">
                <select id="5t" class="top">
                    <option value="+H">+H</option>
                    <option value="+C" selected="selected">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="5l" class="left">
                    <option value="+H" selected="selected">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="5r" class="right">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C" selected="selected">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="5b" class="bottom">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D" selected="selected">-D</option>
                </select>
            </div>
            <div class="piece">
                <select id="6t" class="top">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S" selected="selected">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="6l" class="left">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S" selected="selected">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="6r" class="right">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C" selected="selected">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="6b" class="bottom">
                    <option value="+H" selected="selected">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H" selected="selected">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
            </div>
        </div>
        <div class="row">
            <div class="piece">
                <select id="7t" class="top">
                    <option value="+H" selected="selected">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="7l" class="left">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D" selected="selected">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="7r" class="right">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H" selected="selected">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="7b" class="bottom">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D" selected="selected">-D</option>
                </select>
            </div>
            <div class="piece">
                <select id="8t" class="top">
                    <option value="+H" selected="selected">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="8l" class="left">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S" selected="selected">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="8r" class="right">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C" selected="selected">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="8b" class="bottom">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S" selected="selected">-S</option>
                    <option value="-D">-D</option>
                </select>
            </div>
            <div class="piece">
                <select id="9t" class="top">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S" selected="selected">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="9l" class="left">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D" selected="selected">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="9r" class="right">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H" selected="selected">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S">-S</option>
                    <option value="-D">-D</option>
                </select>
                <select id="9b" class="bottom">
                    <option value="+H">+H</option>
                    <option value="+C">+C</option>
                    <option value="+S">+S</option>
                    <option value="+D">+D</option>
                    <option value="-H">-H</option>
                    <option value="-C">-C</option>
                    <option value="-S" selected="selected">-S</option>
                    <option value="-D">-D</option>
                </select>
            </div>
        </div>
        
        <button id="solve" type="button">Solve</button>
        <button id="solveall" type="button">Find Solutions With Flipped Pieces</button>
        
        <pre id="solution">
           
 +---|---+---|---+---|---+ 
 |       |       |       | 
 -       -       -       - 
 |       |       |       | 
 +---|---+---|---+---|---+ 
 |       |       |       | 
 -       -       -       - 
 |       |       |       | 
 +---|---+---|---+---|---+ 
 |       |       |       | 
 -       -       -       - 
 |       |       |       | 
 +---|---+---|---+---|---+ 
        </pre>
    </body>
</html>

tests.html

<!DOCTYPE html>
<!--
    tests.html
    
    Unit tests for onetoughpuzzle.js
    
    Copyright (C) 2011 Jimmy Theis
    
    Permission is hereby granted, free of charge, to any person obtaining a copy of
    this software and associated documentation files (the "Software"), to deal in
    the Software without restriction, including without limitation the rights to
    use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
    of the Software, and to permit persons to whom the Software is furnished to do
    so, subject to the following conditions:
    
    The above copyright notice and this permission notice shall be included in all
    copies or substantial portions of the Software.
    
    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
    SOFTWARE.
-->
<html>
    <head>
        <title>One Tough Puzzle Solver Tests</title>
        <link rel="stylesheet" href="http://code.jquery.com/qunit/qunit-git.css" type="text/css" media="screen"/>
        <script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.7.1/jquery.min.js"></script>
        <script type="text/javascript" src="http://code.jquery.com/qunit/qunit-git.js"></script>
        <script type="text/javascript" src="onetoughpuzzle.js"></script>
        <script type="text/javascript" src="onetoughpuzzletests.js"></script>
    </head>
    <body>
        <h1 id="qunit-header">One Tough Puzzle Solver Tests</h1>
        <h2 id="qunit-banner"></h2>
        <div id="qunit-testrunner-toolbar"></div>
        <h2 id="qunit-userAgent"></h2>
        <ol id="qunit-tests"></ol>
    </body>
</html>