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:
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?).
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.
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!
CodePudding user response：
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.
CodePudding user response：
I think your approach is a good start.
One of the problems is that if an narrow area is created where a cell could never be covered by any of the remaining pieces, it might be that the brute force search will only discover this much later -- after having placed several pieces successfully in another area. This also means that backtracking will be inefficient, as the latest placed pieces will get alternatives first, which doesn't solve the problem.
I would therefore propose this improvement:
When deciding on the next move, first iterate all free cells and determine how many valid moves would be possible that cover that cell. This offers some 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, and give those priority.
Implementation
I have made an implementation of this in JavaScript. I'm a bit disappointed that it turned out to be so much code. 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 have a boundary (wall) around it.
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 had in mind.
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 single letters for colors. I don't know if there is an agreed encoding, but I used these colors one based on the image you included:
red, green, purple, orange, ivory, yellow, white, blue, sky, magenta, arctic, lime
The first letters of these colors uniquely define them, so they are used in the output. Asterisks 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("red", ["# # #",
"# #"]);
board.addShape("green", ["# # #",
"# - #"]);
board.addShape("purple", ["# # #",
"#"]);
board.addShape("orange", ["- # # #",
"#"]);
board.addShape("ivory", ["# #",
"- # #"]);
board.addShape("yellow", ["# # #",
"- # #"]);
board.addShape("white", ["# # #",
"#",
"#"]);
board.addShape("blue", ["- - # # #",
"- #",
"#"]);
board.addShape("sky", ["# #",
"# #"]);
board.addShape("magenta", ["# # # #",
"- #"]);
board.addShape("arctic", ["# # # #",
"#"]);
board.addShape("lime", ["- #",
"# # #",
"- - #"]);
board.solutions();
}
main();<pre></pre>
Delay: <input type="number" min="0" max="5000" step="50" value="50" >CodePudding user response：
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).