Optimizing a puzzle solver
Hel*_*ful 15 python algorithm optimization recursion combinatorics
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!
我认为你使用位图的方法是一个好的开始。
\n问题之一是，如果组合创建了一个狭窄的区域，其中一个单元格永远不会被任何剩余的单元格覆盖，那么暴力搜索只会在很晚之后才发现这一点——在另一个单元格中成功添加了几个单元格之后。董事会的面积。这意味着最终会有很多这样的组合组合成天文数字般的组合，而很明显，其中任何一个都无法覆盖有问题的区域。
\n深度优先
\n第一个建议是使用深度优先搜索：选择一个空闲单元，并找到所有可能占据该单元的棋子位置，并且仅找到那些。如果单元格不能被任何一块覆盖，则原路返回。如果有多种可能性，请尝试第一种，然后继续使用下一个空闲单元，......等等。当回溯到这个位置时，尝试下一个方法，一块可以覆盖该单元格，...等等。
\n使用深度优先搜索至少会提高内存效率，但也会遇到同样的问题：一些空闲单元变得不可发现，但这可能会在很晚之后才被检测到，这意味着回溯将效率低下，因为最新放置的块将获得替代品首先，这并不能解决不可覆盖的单元格问题。
\n选择空闲单元格
\n我会建议采用深度优先方法进行此改进：
\n当决定下一个“移动”时，首先迭代所有空闲单元，并为每个单元确定可能有多少个有效移动覆盖该单元。这个额外的步骤需要做一些工作，但提供了巨大的优势：
\n- \n
现在，您可以及早发现某个单元不再有希望被覆盖，因此您可以比平常更早地回溯；
\n \n您可以选择覆盖范围最少的单元格。这意味着您实际上会寻找可能很快就会遇到问题的领域，并优先考虑这些领域，目的也是尽早回溯。
\n \n
执行
\n我已经用 JavaScript 实现了这个。我对代码量如此之多感到有点失望。尽管如此，由于 JavaScript 支持大整数，摆弄这些位图变得容易一些，因此 56 个单元格的棋盘可以用一个整数表示，甚至允许额外的单元格在棋盘周围形成边界（墙）。
\n此代码片段从一个空板开始（用字符串定义，但立即转换为位图），并使用相同的字符串到位图逻辑定义 12 个形状。
\n对于每个棋子，它会找到棋盘上的所有有效位置，并进行 6 次旋转和镜像变换。我相信这就是您在实施中已经做过的事情。
\n然后它开始深度优先搜索，但使用这个额外的逻辑来选择要覆盖的“最难”的单元格。该单元格的所有可能覆盖代表递归树中的子级。
\n找到解决方案后，会将其打印出来，并引入一个小的延迟（您可以交互地更改延迟），这样浏览器就不会挂起，您可以更长时间地查看一个配置。然后它继续搜索更多。
\n打印输出将使用单个字母 (AL) 来标识您共享的图像中所示的部件。输出中的星号表示位图中存在的单元，但它们是“墙”。这些墙对于算法来说可能并不是真正必要的，但我就这样保留了它。
\n// Utility function to introduce delays between asynchronous executions\nconst delay = ms => new Promise(resolve => setTimeout(resolve, ms));\n\n// Utility function to translate an array of strings to a bitpattern (bigint)\nfunction hexaShape(lines, width) {\n let bits = 0n;\n let bit = 1n;\n for (let [i, line] of lines.entries()) {\n if (line.length > width * 2 + 1) throw `line width is ${line.length}, but expected at most ${width * 2 + 1}`;\n if (!/^([#-] )*[#-]?$/.test(line)) throw `line ${i} has invalid format`;\n for (let j = 0; j < width; j++) {\n if (line[2*j] === "#") bits |= bit;\n bit <<= 1n;\n }\n }\n return bits;\n}\n\n// For I/O handling\nconst output = document.querySelector("pre"); \nconst input = document.querySelector("input");\n\nclass Board {\n /* Constructor takes an array of strings representing lines of the board area,\n surrounded by boundaries.\n See example run for the expected format for the parameter */\n constructor(lines) {\n this.width = (lines[0].length + 1) >> 1;\n this.height = lines.length;\n this.bits = hexaShape(lines, this.width);\n if (lines[0].includes (\'-\') || lines.at(-1).includes(\'-\')) throw "board should have boundaries";\n if (lines.some(line => /^-|-$/.test(line.trim()))) throw "board should have boundaries";\n // Shapes are the pieces. One shape can have more than one actual position/transformation\n this.shapes = [];\n }\n translate(bits, translation) {\n /* Transform the positioned shape by applying the given \n translation callback to each cell. Used for mirroring and for rotating.\n Returns an array with the transformed position in all its possible locations \n on the board. */\n // Rotate 60\xc2\xb0 clockwise around the (0, 0) coordinate. \n let old = bits;\n bits = 0n;\n let bit = 1n;\n for (let row = 0; row < this.height; row++) {\n for (let col = 0; col < this.width; col++) {\n if (old & bit) bits |= 1n << BigInt(translation(row, col));\n bit <<= 1n;\n }\n }\n // Shift shape\'s cell up and left as much as possible -- which probably is an invalid position\n while ((bits & 1n) == 0n) bits >>= 1n;\n // Shift it back within the boundaries of the board and append it to the array of valid positions\n const positions = [];\n while (bits < this.bits) {\n if ((bits & this.bits) == 0) positions.push(bits);\n bits <<= 1n;\n }\n return positions;\n }\n mirror(bits) {\n return this.translate(bits, (row, col) => (row + 1) * (this.width - 1) - col)[0];\n }\n rotation(bits) {\n return this.translate(bits, (row, col) => ((row + col) * this.width) - row);\n }\n addShape(color, lines) {\n let bits = hexaShape(lines, this.width);\n if (bits == 0n) throw "empty shape";\n const positions = [];\n const unique = new Set;\n // Apply mirroring and rotation to arrive at all valid positions of this shape on the board.\n for (let mirror = 0; mirror < 2; mirror++) {\n bits = this.mirror(bits);\n for (let rotation = 0; rotation < 6; rotation++) {\n const shifts = this.rotation(bits);\n bits = shifts[0];\n if (unique.has(bits)) continue; // Skip: it\'s an already processed position\n unique.add(bits);\n positions.push(...shifts);\n }\n }\n if (positions.length == 0) throw "Could not fit shape unto empty board";\n this.shapes.push({\n color,\n positions,\n placement: 0n\n });\n }\n toString() {\n let output = "";\n let bit = 1n;\n for (let row = 0; row < this.height; row++) {\n output += " ".repeat(row);\n for (let col = 0; col < this.width; col++) {\n const shape = this.shapes.find(({placement}) => placement & bit);\n output += shape ? shape.color[0]\n : (this.bits & bit) ? "*" : " ";\n output += " ";\n bit <<= 1n;\n }\n output += "\\n";\n }\n return output;\n }\n getMoves(occupied, cell) {\n /* Return an array will all possible positions of any unused shape\n that covers the given cell */\n const moves = [];\n for (const shape of this.shapes) {\n if (shape.placement) continue;\n for (const position of shape.positions) {\n if ((cell & position) && !(position & occupied)) { // Found candidate\n moves.push([shape, position]);\n }\n }\n }\n return moves;\n }\n getCriticalCell(occupied) {\n /* This leads to optimisation: do a quick run over all free cells and \n count how many ways it can be covered. This will detect when there is a \n cell that cannot be covered. If there are no such cells, the cell with\n the least number of possible coverings is returned */\n let minCount = Infinity, \n critical = -2n;\n for (let cell = 1n; cell < occupied; cell <<= 1n) {\n if (cell & occupied) continue; // Occupied\n // Count all moves that would cover this cell \n let count = this.getMoves(occupied, cell).length;\n if (count < minCount) {\n if (!count) return -1n; // Found a cell that cannot be covered\n minCount = count;\n critical = cell;\n }\n }\n return critical;\n }\n async recur(occupied, remaining) {\n /* Depth-first search for solutions */\n if (remaining === 0) { // BINGO!!\n output.textContent = this.toString();\n await delay(+input.value);\n return;\n }\n const cell = this.getCriticalCell(occupied);\n if (cell == -1n) return; // Stuck. Need to backtrack\n for (const [shape, position] of this.getMoves(occupied, cell)) {\n shape.placement = position;\n await this.recur(occupied | position, remaining - 1);\n shape.placement = 0n;\n }\n }\n async solutions() {\n await this.recur(this.bits, this.shapes.length);\n }\n}\n\nfunction main() {\n const board = new Board([\n "# # # # # # # # # # # # # # #",\n "# # # - - - - - - - - - - - #",\n "# # - - - - - - - - - - - # #",\n "# - - - - - - - - - - - - # #",\n "# - - - - - - - - - - - # # #",\n "# - - - - - - - - - - - # # #",\n "# # # # # # # # # # # # # # #"\n ]);\n board.addShape("A", ["- - - #",\n "- - # #",\n "# #"]);\n board.addShape("B", ["- - # #",\n "# # #"]);\n board.addShape("C", ["- - - - #",\n "- - - #",\n "# # #"]);\n board.addShape("D", ["- - - #",\n "# # # #"]);\n board.addShape("E", ["- # #",\n "# # #"]);\n board.addShape("F", ["- - #",\n "# # # #"]);\n board.addShape("G", ["- # - #",\n "# # #"]);\n board.addShape("H", ["- - #",\n "- #",\n "# # #"]);\n board.addShape("I", ["- - - #",\n "# # #"]);\n board.addShape("J", ["# #",\n "- # #"]);\n board.addShape("K", ["- # #",\n "# #"]);\n board.addShape("L", ["- - #",\n "# # #"]);\n board.solutions();\n}\n\nmain();<pre></pre>\nDelay: <input type="number" min="0" max="5000" step="50" value="50" >观察结果
\n您会注意到，左侧的棋子很快从一种解决方案更改为下一种解决方案，而棋盘右侧的棋子很快就没有变化。这是因为算法认为棋盘右侧的单元格是覆盖可能性最小的单元格，因此第一个棋子的放置发生在搜索树的顶部。
\n如果您想在已经放置了一些部件的板上运行此代码（例如您共享的图像中），请像这样更改代码：
\n- \n
- 用更多的“#”字符初始化棋盘，以指示棋子已经放置的位置。 \n
- 注释掉
addPiece不再可用的部分的调用。 \n
解决方案尺寸
\n我运行了上述代码的一个变体，它只计算解决方案，并使用记忆。运行大约 25 分钟后，结果为：6,029,968 个解决方案。
\n// Utility function to introduce delays between asynchronous executions\nconst delay = ms => new Promise(resolve => setTimeout(resolve, ms));\n\n// Utility function to translate an array of strings to a bitpattern (bigint)\nfunction hexaShape(lines, width) {\n let bits = 0n;\n let bit = 1n;\n for (let [i, line] of lines.entries()) {\n if (line.length > width * 2 + 1) throw `line width is ${line.length}, but expected at most ${width * 2 + 1}`;\n if (!/^([#-] )*[#-]?$/.test(line)) throw `line ${i} has invalid format`;\n for (let j = 0; j < width; j++) {\n if (line[2*j] === "#") bits |= bit;\n bit <<= 1n;\n }\n }\n return bits;\n}\n\nconst output = document.querySelector("pre"); // For I/O handling\nlet counter = 0;\n\nclass Board {\n /* Constructor takes an array of strings representing lines of the board area,\n surrounded by boundaries.\n See example run for the expected format for the parameter */\n constructor(lines) {\n this.width = (lines[0].length + 1) >> 1;\n this.height = lines.length;\n this.bits = hexaShape(lines, this.width);\n if (lines[0].includes (\'-\') || lines.at(-1).includes(\'-\')) throw "board should have boundaries";\n if (lines.some(line => /^-|-$/.test(line.trim()))) throw "board should have boundaries";\n // Shapes are the pieces. One shape can have more than one actual position/transformation\n this.shapes = [];\n this.map = new Map;\n }\n translate(bits, translation) {\n /* Transform the positioned shape by applying the given \n translation callback to each cell. Used for mirroring and for rotating.\n Returns an array with the transformed position in all its possible locations \n on the board. */\n // Rotate 60\xc2\xb0 clockwise around the (0, 0) coordinate. \n let old = bits;\n bits = 0n;\n let bit = 1n;\n for (let row = 0; row < this.height; row++) {\n for (let col = 0; col < this.width; col++) {\n if (old & bit) bits |= 1n << BigInt(translation(row, col));\n bit <<= 1n;\n }\n }\n // Shift shape\'s cell up and left as much as possible -- which probably is an invalid position\n while ((bits & 1n) == 0n) bits >>= 1n;\n // Shift it back within the boundaries of the board and append it to the array of valid positions\n const positions = [];\n while (bits < this.bits) {\n if ((bits & this.bits) == 0) positions.push(bits);\n bits <<= 1n;\n }\n return positions;\n }\n mirror(bits) {\n return this.translate(bits, (row, col) => (row + 1) * (this.width - 1) - col)[0];\n }\n rotation(bits) {\n return this.translate(bits, (row, col) => ((row + col) * this.width) - row);\n }\n addShape(color, lines) {\n let bits = hexaShape(lines, this.width);\n if (bits == 0n) throw "empty shape";\n const positions = [];\n const unique = new Set;\n // Apply mirroring and rotation to arrive at all valid positions of this shape on the board.\n for (let mirror = 0; mirror < 2; mirror++) {\n bits = this.mirror(bits);\n for (let rotation = 0; rotation < 6; rotation++) {\n const shifts = this.rotation(bits);\n bits = shifts[0];\n if (unique.has(bits)) continue; // Skip: it\'s an already processed position\n unique.add(bits);\n positions.push(...shifts);\n }\n }\n if (positions.length == 0) throw "Could not fit shape unto empty board";\n this.shapes.push({\n id: 1n << BigInt(this.shapes.length), // Unique bit for shape\n color,\n positions,\n placement: 0n\n });\n }\n toString() {\n let output = "";\n let bit = 1n;\n for (let row = 0; row < this.height; row++) {\n output += " ".repeat(row);\n for (let col = 0; col < this.width; col++) {\n const shape = this.shapes.find(({placement}) => placement & bit);\n output += shape ? shape.color[0]\n : (this.bits & bit) ? "*" : " ";\n output += " ";\n bit <<= 1n;\n }\n output += "\\n";\n }\n return output;\n }\n getMoves(occupied, cell) {\n /* Return an array will all possible positions of any unused shape\n that covers the given cell */\n const moves = [];\n for (const shape of this.shapes) {\n if (shape.placement) continue;\n for (const position of shape.positions) {\n if ((cell & position) && !(position & occupied)) { // Found candidate\n moves.push([shape, position]);\n }\n }\n }\n return moves;\n }\n getCriticalCell(occupied) {\n /* This leads to optimisation: do a quick run over all free cells and \n count how many ways it can be covered. This will detect when there is a \n cell that cannot be covered. If there are no such cells, the cell with\n the least number of possible coverings is returned */\n let minCount = Infinity, \n critical = -2n;\n for (let cell = 1n; cell < occupied; cell <<= 1n) {\n if (cell & occupied) continue; // Occupied\n // Count all moves that would cover this cell \n let count = this.getMoves(occupied, cell).length;\n if (count < minCount) {\n if (!count) return -1n; // Found a cell that cannot be covered\n minCount = count;\n critical = cell;\n }\n }\n return critical;\n }\n async recur(occupied, remaining, usedShapes) {\n /* Depth-first search for solutions */\n if (remaining === 0) { // BINGO!!\n output.textContent = ++counter;\n if (counter % 100 == 0) await delay(0);\n return 1;\n }\n let map = this.map.get(usedShapes);\n if (!map) this.map.set(usedShapes, map = new Map);\n const memoCount = map.get(occupied);\n if (memoCount !== undefined) {\n if (memoCount) {\n counter += memoCount;\n output.textContent = counter;\n if (counter % 100 == 0) await delay(0);\n }\n return memoCount;\n }\n let count = 0;\n const cell = this.getCriticalCell(occupied);\n if (cell != -1n) {\n for (const [shape, position] of this.getMoves(occupied, cell)) {\n shape.placement = position;\n count += await this.recur(occupied | position, remaining - 1, usedShapes | shape.id);\n shape.placement = 0n;\n }\n }\n map.set(occupied, count);\n return count;\n }\n async solutions() {\n let start = performance.now();\n await this.recur(this.bits, this.shapes.length, 0n);\n console.log("all done", counter);\n console.log(performance.now() - start, "milliseconds");\n }\n}\n\nfunction main() {\n const board = new Board([\n "# # # # # # # # # # # # # # #",\n "# # # - - - - - - - - - - - #",\n "# # - - - - - - - - - - - # #",\n "# - - - - - - - - - - - - # #",\n "# - - - - - - - - - - - # # #",\n "# - - - - - - - - - - - # # #",\n "# # # # # # # # # # # # # # #"\n ]);\n board.addShape("A", ["- - - #",\n "- - # #",\n "# #"]);\n board.addShape("B", ["- - # #",\n "# # #"]);\n board.addShape("C", ["- - - - #",\n "- - - #",\n "# # #"]);\n board.addShape("D", ["- - - #",\n "# # # #"]);\n board.addShape("E", ["- # #",\n "# # #"]);\n board.addShape("F", ["- - #",\n "# # # #"]);\n board.addShape("G", ["- # - #",\n "# # #"]);\n board.addShape("H", ["- - #",\n "- #",\n "# # #"]);\n board.addShape("I", ["- - - #",\n "# # #"]);\n board.addShape("J", ["# #",\n "- # #"]);\n board.addShape("K", ["- # #",\n "# #"]);\n board.addShape("L", ["- - #",\n "# # #"]);\n \n board.solutions();\n}\n\nmain();Number of solutions found: <pre></pre>