Optimizing a puzzle solver

Question

Over the holidays, I was gifted a game called "Kanoodle Extreme". The details of the game are somewhat important, but I think I've managed to abstract them away. The 2D variant of the game (which is what I'm focusing on) has a number of pieces that can be flipped/rotated/etc. A given puzzle will give you a certain amount of a hex-grid board to cover, and a certain number of pieces with which to cover it. See the picture below for a quick visual, I think that explains most of it.

(Image attribution: screenshotted from the amazon listing)

Here is the full manual for the game, including rules, board configurations, and pieces (manufactorer's site).

For convenience, here's the collection of pieces (individual problems may include a subset of these pieces):

Here is an example of a few board configurations (shown pieces are fixed - the open spaces must be filled with the remaining pieces):

It's an interesting game, but I decided I didn't just want to solve a puzzle, I wanted to solve all the puzzles. I did this not because it would be easy, but because I thought it would be easy. As it turns out, a brute-force/recursive approach is pretty simple. It's also hilariously inefficient.

What have I done so far? Well, I'll happily post code but I've got quite a bit of it. Essentially, I started with a few assumptions:

1. It doesn't matter if I place piece 1, then 2, then 3... or 3, then 1, then 2... since every piece must be placed, the ordering doesn't matter (well, matter much: I think placing bigger pieces first might be more efficient since there are fewer options?).

2. In the worst case, solving for all possible solutions to puzzle is no slower than solving for a single solution. This is where I'm not confident: I guess on average the single solution could probably be early-exited sooner, but I think in the worst case they're equivalent.

3. I don't THINK there's a clean algebraic way to solve this - I don't know if that classifies it as NP-complete or what, but I think some amount of combinatorics must be explored to find solutions. This is my least-confident assumption.

My approach to solving so far:

For each piece given, I find all possible locations/orientations of said piece on the game board. I code each piece/location on the board as a bitmap (where each bit represents a location on the board, and 0 means unoccupied while 1 means occupied). Now for each piece I have a collection of some 20-200 ints (depending on the size of the board) that represent technically-valid placements, though not all are optimal. (I think there's some room to trim down unlikely orientations here).

I store all these ints in a map, as a list associated with a key that represents the index of the piece in question. Starting at piece index 0, I loop through all possible iterations (keyed by the index of that iteration in the list of all possible iterations for that piece), and loop through all possible iterations of the next piece. I take the two ints and bitwise-& them together: if I get a "0" out, it means that there is no overlap between the pieces so they COULD be placed together.

I store all the valid combos from piece 0-1 (for instance, piece 0 iteration index 5 is compatible with piece 1 iterations 1-3, 6, 35-39, and 42). How I store that is likely irrelevant, but I currently store it as a nested list: index 5 of the list would contain another list that held [1, 2, 3, 6, 35, 36, 37, 38, 39, 42].

I do this for piece 0-1, 0-2, 0-3... 1-2, 1-3... 2-3... every combination of pieces. I then start finding 3-sequence combos: Iterate through the list of valid piece 0->1 lists, and for each piece 1 index (so 1, 2, 3, 6, 35, 36... from the example above), find the compatibility list from piece 1->2 for that index. This will give me a sequence of lists. For each item in this sequence, I filter it by taking the intersection with the compatibility list for piece 0->2 for the selected piece 0 iteration.

This gives me a collection of "3-lists". I find all 3-lists ((0, 1, 2), (1, 2, 3), (2, 3, 4)), and repeat the process of filtering to get 4-lists: ((0, 1, 2, 3), (1, 2, 3 4)). Repeat to get 5-lists. If I have only 5 pieces, the 5 list represents all solutions. If I have more than n pieces, repeat until I have an n-list.

This approach DOES work, and I don't THINK I'm duplicating many (if any) calculations, but the combinatorics get so large that it takes too long or - when I have 8 or 9 pieces - takes up 30+ GB of ram, then crashes.

The ultimate question: how can I solve this problem (searching for ALL solutions for a given puzzle) more efficiently?

Sub-questions: Optimizations to my algorithmic approach? Optimizations to the calculations performed (I used ints and bitwise operations and then set intersections because I thought they'd be fast)? Rejections of my assumptions that might result in faster solutions?

Thanks!

Salesmanship

I know this doesn’t relate to the algorithm and more to the hardware side but have you considered rewriting this in cython or a faster language? – Improvident

It's an exact cover problem. – Electromagnetism

Depending on the shape you calculate up to 12 mirrored/rotated solutions where you could have calculated 1 and then applied transformations. Also contradicting as fast as possible (e.g. if you cut off an area of 7 there will be no solution) or placing restricted pieces first (e.g. change from putting pieces in order to first cover a corner and then go along the edge always touching the previous piece, like this the choices are usually very restricted because you don't want gaps) might help. – Bodiless

Listen to @DavidEisenstat (always a good idea!) If you follow references to exact cover you'll find very similar problems being solved on computers in the 1950s and early 60s. – Teena

Do you have some concrete shapes and boards for which your current approach is problematic in terms of running time? – Belenbelesprit

@DavidEisenstat I figured this was a solved problem, but I didn't know the terminology! I'll dig into that! – Salesmanship

@Improvident That's a good call, but I imagine I'd still have some challenges with memory usage (at least, with my current approach). – Salesmanship

@Bodiless I definitely have SOME inefficiency there, but when I convert the piece into a bitmap I check my list of bitmaps to make sure it's not in there already, so we're at least avoiding exact duplicates. That said, the overall board might still end up flipped/mirrored, so we're probably computing 4x the solutions necessary. – Salesmanship

@PaulHankin Will do, and knowing that it was solved in the 50s 60s suggests that my approach is... less than optimal, haha, since it can't run on modern hardware. – Salesmanship

@Belenbelesprit 5 and 6 pieces it's borderline instant, 7 it's slow, 8 it's 10ish minutes, and 9 never finishes. – Salesmanship

@Salesmanship it is 12 because it is possible to have 6-way rotation symmetry (because they are hexagons) and each of those solutions can be mirrored, so 2*6 = 12. In practice it is probably more like 4 (2-way rotation symmetry and mirroring) because the board doesn't have space for big 6-way rotation symmetry shapes. – Bodiless

Sorry, I don't know which pieces you refer to. Can you please give a very concrete input (the actual piece shapes and board size) for which the performance is unacceptable? I don't know the game, so please specify the shapes structure and the board shape. An image is nice, but it is not precise enough -- at least not for me. – Belenbelesprit

Is the grid always a "square" of hex tiles? Or can it form some other, perhaps asymmetric "blob" shapes? – Mceachern

@DillonDavis At the end of the board it's tapered, but the my abstraction (sets of ints) should remove any of the challenges of the physical board shape (unless you think the abstraction isn't optimal). – Salesmanship

I think board geometry is important- it imposes a planar restriction of the composition of each set (representing a piece + rotation). It shouldn't change the asymptotic time complexity, but it probably will permit real-time performance optimizations. – Mceachern

I found a manual online that shows off the pieces, the board, all the puzzle configurations, and explains the 3 kinds of puzzles in greater detail. I'll try to edit the question with an image of the pieces and a board or two, but there's more than 100 problems, so I cannot upload them all. Link: educationalinsights.com/amfile/file/download/file/202/product/… – Mceachern

@Belenbelesprit see my edit - I've included context from the manufacturer's game manual – Mceachern

A straightforward brute-force approach would run in O(n) memory. Briefly, you do not form all lists of length k before going to length k+1. Instead, you have one (1) list all the time, and try all possible ways of adding an element to it, using backtracking. – Sensillum

@n.m. There's the speed/memory tradeoff, for sure. On larger boards, I've seen pieces have upwards of 200 valid placements. Assuming a round 100 each, that means with 9 pieces you have 100^9 = 1e18 possibilities, so to solve that in even a week would take 1.6 trillion combinations/second. I'm hoping for more like "a few seconds". For the record, I have got a pure bruteforce/backtracking approach working, but this question is about optimizing. – Salesmanship

"On larger boards": which board sizes are those? Do you mean the one with 56 cells, for placing 12 pieces? – Belenbelesprit

"Larger" meaning 9+ pieces to place, so typically 40+ cells, will cause memory issues on my machine (30+GB usage). – Salesmanship

I don't see any speed/memory tradeoff in your implementation. You use more memory for sure, but how does it translate to more speed? – Sensillum

@n.m. A naive backtracking approach would recompute a lot of possibilities, for instance: piece 0 configuration 0 might check to see p1o0 and p2o0 and find that they're not compatible. Then, when I check piece 0 configuration 1, I might recompute that for p1o0 and p2o0. By using vectorized operations (set intersections), I'm both parallelizing (speedup) and removing redundant calculations (speedup). I can get a timeit of the naive approach vs my approach for 5, 6, 7 pieces, it's pretty significant. – Salesmanship

Checking all placements of all pieces would be too naïve indeed, you need to reject unviable candidates early. How about checking those that cover the leftmost topmost uncovered cell? You can precompute placements to find candidates quickly, and you will be able to reject a lot of dead end positions early on. (Basically the same idea as @Belenbelesprit is using). – Sensillum

I guess you have so far ignored @DavidEisenstat 's comment: you should note this (nearly) exact problem is described (with solution by none other than Donald Knuth) here: en.wikipedia.org/wiki/Exact_cover#Pentomino_tiling Would be fun to implement the dancing link solution, give it a go! Alternatively you can use existing software to solve this: en.wikipedia.org/wiki/Dancing_Links#External_links – Soupandfish

Answer 1

I think your approach with bitmaps is a good start.

One of the problems is that if a narrow area is created by a combination, where a cell could never be covered by any of the remaining pieces, the brute force search will only discover this much later -- after having added several pieces successfully in another area of the board. This means that eventually there are a lot of such combinations being combined in astronomically more combinations, while it is already clear that the problematic area cannot be covered by any of them.

Depth-first

The first suggestion is to use a depth-first search: select a free cell, and find all possible piece positions that would occupy that cell, and only those. If the cell cannot be covered by any piece, then backtrack. If there are multiple possibilities, try the first one, and continue with a next free cell, ...etc. When backtracking to this position, try the next way a piece can cover that cell, ...etc.

Using a depth first search will at least be more memory efficient, but will also have the same problem: some free cells become uncoverable, but this may be detected much later, meaning that backtracking will be inefficient, as the latest placed pieces will get alternatives first, which doesn't solve the uncoverable-cell problem.

Choose free cell

I would propose this improvement on a depth-first approach:

When deciding on the next "move", first iterate all free cells and for each of those cells determine how many valid moves would be possible that cover that cell. This extra step represents some work, but offers huge advantages:

• Now you will detect early when there is a cell that has no more hope of getting covered, so you can backtrack earlier than you would normally do;

• You can select the cell that has the fewest possible coverings. This means you actually look for areas where you might run into problems soon, and give those priority, again with the aim to backtrack early.

Implementation

I have made an implementation of this in JavaScript. I'm a bit disappointed that it turned out to be so much code. Still, the fiddling with these bitmaps was made a bit easier as JavaScript supports big integers, and so the board of 56 cells could be represented with one integer, even allowing for extra cells to make a boundary (wall) around the board.

This snippet starts with an empty board (defined with strings, but immediately converted to a bitmap), and defines the 12 shapes using the same string-to-bitmap logic.

For each piece it finds all valid positions on the board, with its 6 rotations and mirror transformation. I believe this is what you already did in your implementation.

Then it starts the depth-first search, but with this extra logic to select the "most difficult" cell to cover. All possible coverings for that cell represent the children in the recursion tree.

When a solution is found, it is printed, and a small delay is introduced (you can alter the delay interactively) so the browser does not hang and you can have a longer look at one configuration. Then it continues the search for more.

The printed output will use the single letters (A-L) to identify the pieces as depicted in the image you have shared. Asterisks in the output denote cells that exist in the bitmap, but are "walls". These walls might not all be really necessary for the algorithm, but I just left it like that.

// Utility function to introduce delays between asynchronous executions
const delay = ms => new Promise(resolve => setTimeout(resolve, ms));

// Utility function to translate an array of strings to a bitpattern (bigint)
function hexaShape(lines, width) {
    let bits = 0n;
    let bit = 1n;
    for (let [i, line] of lines.entries()) {
        if (line.length > width * 2 + 1) throw `line width is ${line.length}, but expected at most ${width * 2 + 1}`;
        if (!/^([#-] )*[#-]?$/.test(line)) throw `line ${i} has invalid format`;
        for (let j = 0; j < width; j++) {
            if (line[2*j] === "#") bits |= bit;
            bit <<= 1n;
        }
    }
    return bits;
}

// For I/O handling
const output = document.querySelector("pre"); 
const input = document.querySelector("input");

class Board  {
    /* Constructor takes an array of strings representing lines of the board area,
       surrounded by boundaries.
       See example run for the expected format for the parameter */
    constructor(lines) {
        this.width = (lines[0].length + 1) >> 1;
        this.height = lines.length;
        this.bits = hexaShape(lines, this.width);
        if (lines[0].includes ('-') || lines.at(-1).includes('-')) throw "board should have boundaries";
        if (lines.some(line => /^-|-$/.test(line.trim()))) throw "board should have boundaries";
        // Shapes are the pieces. One shape can have more than one actual position/transformation
        this.shapes = [];
    }
    translate(bits, translation) {
        /* Transform the positioned shape by applying the given 
           translation callback to each cell. Used for mirroring and for rotating.
           Returns an array with the transformed position in all its possible locations 
           on the board. */
        // Rotate 60° clockwise around the (0, 0) coordinate. 
        let old = bits;
        bits = 0n;
        let bit = 1n;
        for (let row = 0; row < this.height; row++) {
            for (let col = 0; col < this.width; col++) {
                if (old & bit) bits |= 1n << BigInt(translation(row, col));
                bit <<= 1n;
            }
        }
        // Shift shape's cell up and left as much as possible -- which probably is an invalid position
        while ((bits & 1n) == 0n) bits >>= 1n;
        // Shift it back within the boundaries of the board and append it to the array of valid positions
        const positions = [];
        while (bits < this.bits) {
            if ((bits & this.bits) == 0) positions.push(bits);
            bits <<= 1n;
        }
        return positions;
    }
    mirror(bits) {
        return this.translate(bits, (row, col) => (row + 1) * (this.width - 1) - col)[0];
    }
    rotation(bits) {
        return this.translate(bits, (row, col) => ((row + col) * this.width) - row);
    }
    addShape(color, lines) {
        let bits = hexaShape(lines, this.width);
        if (bits == 0n) throw "empty shape";
        const positions = [];
        const unique = new Set;
        // Apply mirroring and rotation to arrive at all valid positions of this shape on the board.
        for (let mirror = 0; mirror < 2; mirror++) {
            bits = this.mirror(bits);
            for (let rotation = 0; rotation < 6; rotation++) {
                const shifts = this.rotation(bits);
                bits = shifts[0];
                if (unique.has(bits)) continue; // Skip: it's an already processed position
                unique.add(bits);
                positions.push(...shifts);
            }
        }
        if (positions.length == 0) throw "Could not fit shape unto empty board";
        this.shapes.push({
            color,
            positions,
            placement: 0n
        });
    }
    toString() {
        let output = "";
        let bit = 1n;
        for (let row = 0; row < this.height; row++) {
            output += " ".repeat(row);
            for (let col = 0; col < this.width; col++) {
                const shape = this.shapes.find(({placement}) => placement & bit);
                output += shape ? shape.color[0]
                        : (this.bits & bit) ? "*" : " ";
                output += " ";
                bit <<= 1n;
            }
            output += "\n";
        }
        return output;
    }
    getMoves(occupied, cell) {
        /* Return an array will all possible positions of any unused shape
           that covers the given cell */
        const moves = [];
        for (const shape of this.shapes) {
            if (shape.placement) continue;
            for (const position of shape.positions) {
                if ((cell & position) && !(position & occupied)) { // Found candidate
                    moves.push([shape, position]);
                }
            }
        }
        return moves;
    }
    getCriticalCell(occupied) {
        /* This leads to optimisation: do a quick run over all free cells and 
           count how many ways it can be covered. This will detect when there is a 
           cell that cannot be covered. If there are no such cells, the cell with
           the least number of possible coverings is returned */
        let minCount = Infinity, 
            critical = -2n;
        for (let cell = 1n; cell < occupied; cell <<= 1n) {
            if (cell & occupied) continue; // Occupied
            // Count all moves that would cover this cell                
            let count = this.getMoves(occupied, cell).length;
            if (count < minCount) {
                if (!count) return -1n; // Found a cell that cannot be covered
                minCount = count;
                critical = cell;
            }
        }
        return critical;
    }
    async recur(occupied, remaining) {
        /* Depth-first search for solutions */
        if (remaining === 0) { // BINGO!!
            output.textContent = this.toString();
            await delay(+input.value);
            return;
        }
        const cell = this.getCriticalCell(occupied);
        if (cell == -1n) return; // Stuck. Need to backtrack
        for (const [shape, position] of this.getMoves(occupied, cell)) {
            shape.placement = position;
            await this.recur(occupied | position, remaining - 1);
            shape.placement = 0n;
        }
    }
    async solutions() {
        await this.recur(this.bits, this.shapes.length);
    }
}

function main() {
    const board = new Board([
       "# # # # # # # # # # # # # # #",
        "# # # - - - - - - - - - - - #",
         "# # - - - - - - - - - - - # #",
          "# - - - - - - - - - - - - # #",
           "# - - - - - - - - - - - # # #",
            "# - - - - - - - - - - - # # #",
             "# # # # # # # # # # # # # # #"
    ]);
    board.addShape("A", ["- - - #",
                          "- - # #",
                           "# #"]);
    board.addShape("B", ["- - # #",
                          "# # #"]);
    board.addShape("C", ["- - - - #",
                          "- - - #",
                           "# # #"]);
    board.addShape("D", ["- - - #",
                          "# # # #"]);
    board.addShape("E", ["- # #",
                          "# # #"]);
    board.addShape("F", ["- - #",
                          "# # # #"]);
    board.addShape("G", ["- # - #",
                          "# # #"]);
    board.addShape("H", ["- - #",
                          "- #",
                           "# # #"]);
    board.addShape("I", ["- - - #",
                          "# # #"]);
    board.addShape("J", ["# #",
                          "- # #"]);
    board.addShape("K", ["- # #",
                          "# #"]);
    board.addShape("L", ["- - #",
                          "# # #"]);
    board.solutions();
}

main();

<pre></pre>
Delay: <input type="number" min="0" max="5000" step="50" value="50" >

Observations

You'll notice that the pieces at the left side quickly change from one solution to the next, while on the right side of the board there is no change soon. This is because the algorithm decided that the cells at the right of the board were the ones with the least possibilities for covering, so there the very first piece placements happened -- at the top of the search tree.

If you want to run this code on boards where some pieces were already placed (like in the images you shared), then change the code like this:

• Initialise the board with more '#' characters to indicate where pieces were already placed.
• Comment out the calls of addPiece of the pieces that are no longer available.

Solution size

I ran a variant of the above code that only counts solutions, and uses memoization. After some 25 minutes running time, the result was: 6,029,968 solutions.

// Utility function to introduce delays between asynchronous executions
const delay = ms => new Promise(resolve => setTimeout(resolve, ms));

// Utility function to translate an array of strings to a bitpattern (bigint)
function hexaShape(lines, width) {
    let bits = 0n;
    let bit = 1n;
    for (let [i, line] of lines.entries()) {
        if (line.length > width * 2 + 1) throw `line width is ${line.length}, but expected at most ${width * 2 + 1}`;
        if (!/^([#-] )*[#-]?$/.test(line)) throw `line ${i} has invalid format`;
        for (let j = 0; j < width; j++) {
            if (line[2*j] === "#") bits |= bit;
            bit <<= 1n;
        }
    }
    return bits;
}

const output = document.querySelector("pre"); // For I/O handling
let counter = 0;

class Board  {
    /* Constructor takes an array of strings representing lines of the board area,
       surrounded by boundaries.
       See example run for the expected format for the parameter */
    constructor(lines) {
        this.width = (lines[0].length + 1) >> 1;
        this.height = lines.length;
        this.bits = hexaShape(lines, this.width);
        if (lines[0].includes ('-') || lines.at(-1).includes('-')) throw "board should have boundaries";
        if (lines.some(line => /^-|-$/.test(line.trim()))) throw "board should have boundaries";
        // Shapes are the pieces. One shape can have more than one actual position/transformation
        this.shapes = [];
        this.map = new Map;
    }
    translate(bits, translation) {
        /* Transform the positioned shape by applying the given 
           translation callback to each cell. Used for mirroring and for rotating.
           Returns an array with the transformed position in all its possible locations 
           on the board. */
        // Rotate 60° clockwise around the (0, 0) coordinate. 
        let old = bits;
        bits = 0n;
        let bit = 1n;
        for (let row = 0; row < this.height; row++) {
            for (let col = 0; col < this.width; col++) {
                if (old & bit) bits |= 1n << BigInt(translation(row, col));
                bit <<= 1n;
            }
        }
        // Shift shape's cell up and left as much as possible -- which probably is an invalid position
        while ((bits & 1n) == 0n) bits >>= 1n;
        // Shift it back within the boundaries of the board and append it to the array of valid positions
        const positions = [];
        while (bits < this.bits) {
            if ((bits & this.bits) == 0) positions.push(bits);
            bits <<= 1n;
        }
        return positions;
    }
    mirror(bits) {
        return this.translate(bits, (row, col) => (row + 1) * (this.width - 1) - col)[0];
    }
    rotation(bits) {
        return this.translate(bits, (row, col) => ((row + col) * this.width) - row);
    }
    addShape(color, lines) {
        let bits = hexaShape(lines, this.width);
        if (bits == 0n) throw "empty shape";
        const positions = [];
        const unique = new Set;
        // Apply mirroring and rotation to arrive at all valid positions of this shape on the board.
        for (let mirror = 0; mirror < 2; mirror++) {
            bits = this.mirror(bits);
            for (let rotation = 0; rotation < 6; rotation++) {
                const shifts = this.rotation(bits);
                bits = shifts[0];
                if (unique.has(bits)) continue; // Skip: it's an already processed position
                unique.add(bits);
                positions.push(...shifts);
            }
        }
        if (positions.length == 0) throw "Could not fit shape unto empty board";
        this.shapes.push({
            id: 1n << BigInt(this.shapes.length), // Unique bit for shape
            color,
            positions,
            placement: 0n
        });
    }
    toString() {
        let output = "";
        let bit = 1n;
        for (let row = 0; row < this.height; row++) {
            output += " ".repeat(row);
            for (let col = 0; col < this.width; col++) {
                const shape = this.shapes.find(({placement}) => placement & bit);
                output += shape ? shape.color[0]
                        : (this.bits & bit) ? "*" : " ";
                output += " ";
                bit <<= 1n;
            }
            output += "\n";
        }
        return output;
    }
    getMoves(occupied, cell) {
        /* Return an array will all possible positions of any unused shape
           that covers the given cell */
        const moves = [];
        for (const shape of this.shapes) {
            if (shape.placement) continue;
            for (const position of shape.positions) {
                if ((cell & position) && !(position & occupied)) { // Found candidate
                    moves.push([shape, position]);
                }
            }
        }
        return moves;
    }
    getCriticalCell(occupied) {
        /* This leads to optimisation: do a quick run over all free cells and 
           count how many ways it can be covered. This will detect when there is a 
           cell that cannot be covered. If there are no such cells, the cell with
           the least number of possible coverings is returned */
        let minCount = Infinity, 
            critical = -2n;
        for (let cell = 1n; cell < occupied; cell <<= 1n) {
            if (cell & occupied) continue; // Occupied
            // Count all moves that would cover this cell                
            let count = this.getMoves(occupied, cell).length;
            if (count < minCount) {
                if (!count) return -1n; // Found a cell that cannot be covered
                minCount = count;
                critical = cell;
            }
        }
        return critical;
    }
    async recur(occupied, remaining, usedShapes) {
        /* Depth-first search for solutions */
        if (remaining === 0) { // BINGO!!
            output.textContent = ++counter;
            if (counter % 100 == 0) await delay(0);
            return 1;
        }
        let map = this.map.get(usedShapes);
        if (!map) this.map.set(usedShapes, map = new Map);
        const memoCount = map.get(occupied);
        if (memoCount !== undefined) {
            if (memoCount) {
                counter += memoCount;
                output.textContent = counter;
                if (counter % 100 == 0) await delay(0);
            }
            return memoCount;
        }
        let count = 0;
        const cell = this.getCriticalCell(occupied);
        if (cell != -1n) {
            for (const [shape, position] of this.getMoves(occupied, cell)) {
                shape.placement = position;
                count += await this.recur(occupied | position, remaining - 1, usedShapes | shape.id);
                shape.placement = 0n;
            }
        }
        map.set(occupied, count);
        return count;
    }
    async solutions() {
        let start = performance.now();
        await this.recur(this.bits, this.shapes.length, 0n);
        console.log("all done", counter);
        console.log(performance.now() - start, "milliseconds");
    }
}

function main() {
    const board = new Board([
       "# # # # # # # # # # # # # # #",
        "# # # - - - - - - - - - - - #",
         "# # - - - - - - - - - - - # #",
          "# - - - - - - - - - - - - # #",
           "# - - - - - - - - - - - # # #",
            "# - - - - - - - - - - - # # #",
             "# # # # # # # # # # # # # # #"
    ]);
    board.addShape("A", ["- - - #",
                          "- - # #",
                           "# #"]);
    board.addShape("B", ["- - # #",
                          "# # #"]);
    board.addShape("C", ["- - - - #",
                          "- - - #",
                           "# # #"]);
    board.addShape("D", ["- - - #",
                          "# # # #"]);
    board.addShape("E", ["- # #",
                          "# # #"]);
    board.addShape("F", ["- - #",
                          "# # # #"]);
    board.addShape("G", ["- # - #",
                          "# # #"]);
    board.addShape("H", ["- - #",
                          "- #",
                           "# # #"]);
    board.addShape("I", ["- - - #",
                          "# # #"]);
    board.addShape("J", ["# #",
                          "- # #"]);
    board.addShape("K", ["- # #",
                          "# #"]);
    board.addShape("L", ["- - #",
                          "# # #"]);
    
    board.solutions();
}

main();

Number of solutions found: <pre></pre>

Belenbelesprit

Answer 2

One quick way to implement an efficient algorithm for this problem is to encode this as an instance of SAT, and then apply an off-the-shelf SAT solver. I find Z3py very convenient for rapid implementation.

Basically, you have boolean variables x_{p,l,o}, where x_{p,l,o} is true if piece p is placed at position l in orientation o. Then, all of the rules of the game can be translated into boolean conditions on these variables (i.e., clauses). You can take the conjunction of all of those conditions, and then use a SAT solver to search for a satisfying assignment.

SAT solvers are very good at solving this kind of problem, as long as the number of variables is not too large.

I don't recommend you manually implement your own algorithm based on backtracking etc. In some sense you can think of SAT solvers as basically a systematic way of implementing backtracking, but they have many well-tuned optimizations that make it run faster.

Amalgam

I've not used SAT solvers before, but I'm looking at the documentation now. How many variables/conditions is considered "too large"? With 9+ pieces, you have 40+ board spaces, and that can easily be 100 possible locations per piece, meaning we'd have 900 booleans with that approach. Would framing it as exact cover using sets of ints be better? – Salesmanship

@Helpful, there is no set boundary for how many is too large. You have to try it and see. Intuitively I expect a SAT solver might work, but the only way to know is to try it. It doesn't take that long to code it up -- I suggest you give it a try. Exact cover is also reasonable as well, but you would then have to implement your own exact cover algorithm, which might in principle yield a better algorithm but also might in practice be more implementation work than using an off-the-shelf SAT solver. See revised answer about backtracking. – Amalgam

Answer 3

My take is that you essentially apply a breadth-first search, storing in memory all positions with k pieces before going to k+1 pieces. Instead, a depth-first search would be much more viable: it would not store anything except the current state of the board and some auxiliary info, like which pieces are already placed.

My approach would perhaps be recursion. Consider the current state of the board. Find the first (top-down, left-to-right) uncovered square of the grid. Try to cover it with all remaining pieces using all their possible shifts, flips, and rotations. For the ones that fit, run the recursion with the new state.

Such recursion won't visit any intermediate state more than once, since the squares are covered in fixed order, and if the search paths differ in covering any one square, they arrive at different states. Still, sure the solution is exponential.

To speed it up by a factor, track the position of the last covered square, so you have to search from there instead of from the start, and also track which pieces are still missing. Also, store the board as a bit mask. Precompute masks for all possible shifts, flips, and rotations of all pieces, to quickly check whether a piece fits, and to quickly change the state back and forth (xor).

To speed it up exponentially, figure out how to break early from some branches of the search that are clearly unviable (for example, an isolated empty square appearing on the board).

Kneehigh