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!

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>

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.