First you use flood fill to break up the problem into filling continuous regions of lego bricks. Then for each of those you can use a dfs with memoization you wish. The flood fill is trivial so I will not describe it farther.
Make sure to follow a right hand rule while expanding the search tree to not repeat states.
For each piece in the sorted list, try to place as many as you can in the plate:
Raster a 2D image of your design looking for regions of the image with uniform color, the shape of the current piece and free studs for each stud that the piece will use.
If the color of the region found do not exist for that particular piece, ignore an continue searching.
If the color exists: tag the studs used by that pieces and increment a counter for that kind of piece and that color.
Step 2 will be done once for squared pieces, twice for rectangular pieces (once vertical and once horizontal) and 4 times for corner pieces.
Iterate to 2 until the plate is full or no more type of pieces are available.
Once arrived to the end you will have the number of pieces of each kind and each color that you needed with a minimum cost.
If cost by stubs can change by color, then the original sorted list must include not only the type of piece by also the color.
FindBestCostToFillInRemainingArea()
{
- find next empty square
- if no empty square, return 0
- for each piece type available
- if it's legal to place the piece with upper-left corner on the empty square
- place the piece
- total cost = cost to place this piece + FindBestCostToFillInRemainingArea()
- remove the piece
return the cheapest "total cost" found
}
Karl's approach is basically sound, but could use some more details. It will find the optimal cost solution, but will be too slow for certain inputs. Large open areas especially will have too many possibilities to search through naively.
So, the algorithm fills in a given area. It is recursive (DFS):
FindBestCostToFillInRemainingArea()
{
- find next empty square
- if no empty square, return 0
- for each piece type available
- if it's legal to place the piece with upper-left corner on the empty square
- place the piece
- total cost = cost to place this piece + FindBestCostToFillInRemainingArea()
- remove the piece
return the cheapest "total cost" found
}
Once we figure out the cheapest way to fill a sub-area, we'll cache the result. To very efficiently identify a sub-area, we'll use a 64-bit integer using Zobrist hashing. Warning: hash collisions may cause incorrect results. Once our routine returns, we can reconstruct the optimal solution based on our cached values.
Optimizing: In the example, 41936 nodes (recursive calls) are explored (searching for empty square top-to-bottom). However, if we search for empty squares left-to-right, ~900,000 nodes are explored.
For large open areas: I'd suggest finding the most cost-efficient piece and filling in a lot of the open area with that piece as a pre-process step. Another technique is to divide your image into a few regions, and optimize each region separately.
Good luck! I'll be unavailable until March 26th, so hopefully I didn't miss anything!
对于可能的零件数组（包括每种颜色的单个零件），每个零件至少制作 n 个副本，其中 n = max（每种颜色的板号/零件号）。因此，最多n块可以按面积覆盖整个棋盘的所有颜色。
现在我们有一个巨大的可能的棋子集合，这是有限的，因为可以保证这个集合的一个子集将完全填满棋盘。
那么它就变成了一个子集问题，即NP-Complete。
解决子集问题
For each unused piece in the set
For each possible rotation (e.g. for a square only 1, for a rectangle piece 2, for an elbow piece 4)
For each possible position in the *remaining* open places on board matching the color and rotation of the piece
- Put down the piece
- Mark the piece as used from the set
- Recursively decent on the board (with already some pieces filled)
For an array of possible pieces (include single pieces of each color), make at least n duplicates of each piece, where n = max(board#/piece# of each color). Therefore, at most n of that piece can cover all of the entire board's colors by area.
Now we have a huge collection of possible pieces, bounded because it is guaranteed that a subset of this collection will completely fill the board.
Then it becomes a subset problem, which is NP-Complete.
Solving the subset problem
For each unused piece in the set
For each possible rotation (e.g. for a square only 1, for a rectangle piece 2, for an elbow piece 4)
For each possible position in the *remaining* open places on board matching the color and rotation of the piece
- Put down the piece
- Mark the piece as used from the set
- Recursively decent on the board (with already some pieces filled)
Optimizations
Obviously being an O(2^n) algorithm, pruning of the search tree early is of utmost importance. Optimizations must be done early to avoid long-running. n is a very large number; just consider a 48x48 board -- you have 48x48xc (where c = number of colors) just for single pieces alone.
Therefore, 99% of the search tree must be pruned from the first few hundred plies in order for this algorithm to complete in any time. For example, keep a tally of the lowest cost solution found so far, and just stop searching all lower plies and backtrack whenever the current cost plus (the number of empty board positions x lowest average cost for each color) > current lowest cost solution.
For example, further optimize by always favoring the largest pieces (or the lowest average-cost pieces) first, so as to reduce the baseline lowest cost solution as quickly as possible and to prune as many future cases as possible.
Finding the cheapest
Calculate cost of each solution, find the cheapest!
Comments
This algorithm is generic. It does not assume a piece is of the same color (you can have multi-colored pieces!). It does not assume that a large piece is cheaper than the sum of smaller pieces. It doesn't really assume anything.
If some assumptions can be made, then this information can be used to further prune the search tree as early as possible. For example, when using only single-colored pieces, you can prune large sections of the board (with the wrong colors) and prune large number of pieces in the set (of the wrong color).
Suggestion
Do not try to do 48x48 at once. Try it on something small, say, 8x8, with a reasonably small set of pieces. Then increase number of pieces and board size progressively. I really have no idea how long the program will take -- but would love for somebody to tell me!
发布评论
评论（4）
首先，您使用洪水填充将问题分解为填充乐高积木的连续区域。然后，对于其中的每一个，您都可以使用具有所需记忆功能的 dfs。洪水填充是微不足道的，所以我不会进一步描述它。
确保在扩展搜索树时遵循右手法则，以免重复状态。
First you use flood fill to break up the problem into filling continuous regions of lego bricks. Then for each of those you can use a dfs with memoization you wish. The flood fill is trivial so I will not describe it farther.
Make sure to follow a right hand rule while expanding the search tree to not repeat states.
我的解决方案是：
一旦到达终点，您将以最低的成本获得所需的每种类型和每种颜色的件数。
如果按存根的成本可以按颜色改变，则原始排序列表必须不仅包括件的类型还包括颜色。
My solution will be:
Once arrived to the end you will have the number of pieces of each kind and each color that you needed with a minimum cost.
If cost by stubs can change by color, then the original sorted list must include not only the type of piece by also the color.
Karl 的方法基本上是合理的，但可以使用更多细节。它将找到最佳成本解决方案，但对于某些输入来说速度太慢。特别是大的开放区域将有太多的可能性来天真地搜索。
无论如何，我在这里用 C++ 进行了快速实现： http://pastebin.com/S6FpuBMc
它解决了填充空白（句点）的问题，有 4 种不同类型的砖块：
因此，算法会填充给定区域。它是递归的（DFS）：
一旦我们找出填充子区域的最便宜的方法，我们将缓存结果。为了非常有效地识别子区域，我们将使用 Zobrist 哈希来使用 64 位整数。警告：哈希冲突可能会导致错误的结果。一旦我们的例程返回，我们就可以根据缓存的值重建最佳解决方案。
优化：
在示例中，探索了 41936 个节点（递归调用）（从上到下搜索空方块）。然而，如果我们从左到右搜索空方块，则会探索约 900,000 个节点。
对于大型开放区域：我建议找到最具成本效益的部件，并用该部件填充大量开放区域作为预处理步骤。另一种技术是将图像划分为几个区域，然后分别优化每个区域。
祝你好运！我将在 3 月 26 日之前无法联系，所以希望我没有错过任何事情！
Karl's approach is basically sound, but could use some more details. It will find the optimal cost solution, but will be too slow for certain inputs. Large open areas especially will have too many possibilities to search through naively.
Anyways, I made a quick implementation in C++ here: http://pastebin.com/S6FpuBMc
It solves filling in the empty space (periods), with 4 different kinds of bricks:
So, the algorithm fills in a given area. It is recursive (DFS):
Once we figure out the cheapest way to fill a sub-area, we'll cache the result. To very efficiently identify a sub-area, we'll use a 64-bit integer using Zobrist hashing. Warning: hash collisions may cause incorrect results. Once our routine returns, we can reconstruct the optimal solution based on our cached values.
Optimizing:
In the example, 41936 nodes (recursive calls) are explored (searching for empty square top-to-bottom). However, if we search for empty squares left-to-right, ~900,000 nodes are explored.
For large open areas: I'd suggest finding the most cost-efficient piece and filling in a lot of the open area with that piece as a pre-process step. Another technique is to divide your image into a few regions, and optimize each region separately.
Good luck! I'll be unavailable until March 26th, so hopefully I didn't miss anything!
步骤
第 1 步：迭代所有解决方案。
第 2 步：找到最便宜的解决方案。
创建零件清单
对于可能的零件数组（包括每种颜色的单个零件），每个零件至少制作 n 个副本，其中 n = max（每种颜色的板号/零件号）。因此，最多n块可以按面积覆盖整个棋盘的所有颜色。
现在我们有一个巨大的可能的棋子集合，这是有限的，因为可以保证这个集合的一个子集将完全填满棋盘。
那么它就变成了一个子集问题，即NP-Complete。
解决子集问题
优化
显然，作为 O(2^n) 算法，尽早修剪搜索树至关重要。必须尽早进行优化以避免长时间运行。 n是一个非常大的数；只需考虑一块 48x48 的板 - 您有 48x48xc （其中 c = 颜色数）仅用于单块。
因此，为了使该算法能够随时完成，必须从前几百层中修剪掉 99% 的搜索树。例如，记录迄今为止找到的最低成本解决方案，只要当前成本加上（空板位置的数量 x 每种颜色的最低平均成本）> ，就停止搜索所有较低层并回溯。当前成本最低的解决方案。
例如，通过始终首先优先考虑最大的部分（或平均成本最低的部分）来进一步优化，以便尽快减少基线最低成本解决方案并修剪尽可能多的未来案例。
寻找最便宜的
计算每个解决方案的成本，找到最便宜的！
注释
该算法是通用的。它并不假设一件作品具有相同的颜色（您可以拥有多种颜色的作品！）。它并不假设大件比小件的总和更便宜。它并没有真正假设任何事情。
如果可以做出一些假设，那么该信息可以用于尽早进一步修剪搜索树。例如，当仅使用单色棋子时，您可以修剪棋盘的大部分（颜色错误）并修剪集合中的大量棋子（颜色错误）。
建议
不要尝试一次做 48x48。尝试在一些小东西上尝试，例如 8x8，并使用一组相当小的组件。然后逐渐增加件数和板尺寸。我真的不知道该计划需要多长时间——但希望有人告诉我！
Steps
Step 1: Iterate through all solutions.
Step 2: Find the cheapest solution.
Create pieces inventory
For an array of possible pieces (include single pieces of each color), make at least n duplicates of each piece, where n = max(board#/piece# of each color). Therefore, at most n of that piece can cover all of the entire board's colors by area.
Now we have a huge collection of possible pieces, bounded because it is guaranteed that a subset of this collection will completely fill the board.
Then it becomes a subset problem, which is NP-Complete.
Solving the subset problem
Optimizations
Obviously being an O(2^n) algorithm, pruning of the search tree early is of utmost importance. Optimizations must be done early to avoid long-running. n is a very large number; just consider a 48x48 board -- you have 48x48xc (where c = number of colors) just for single pieces alone.
Therefore, 99% of the search tree must be pruned from the first few hundred plies in order for this algorithm to complete in any time. For example, keep a tally of the lowest cost solution found so far, and just stop searching all lower plies and backtrack whenever the current cost plus (the number of empty board positions x lowest average cost for each color) > current lowest cost solution.
For example, further optimize by always favoring the largest pieces (or the lowest average-cost pieces) first, so as to reduce the baseline lowest cost solution as quickly as possible and to prune as many future cases as possible.
Finding the cheapest
Calculate cost of each solution, find the cheapest!
Comments
This algorithm is generic. It does not assume a piece is of the same color (you can have multi-colored pieces!). It does not assume that a large piece is cheaper than the sum of smaller pieces. It doesn't really assume anything.
If some assumptions can be made, then this information can be used to further prune the search tree as early as possible. For example, when using only single-colored pieces, you can prune large sections of the board (with the wrong colors) and prune large number of pieces in the set (of the wrong color).
Suggestion
Do not try to do 48x48 at once. Try it on something small, say, 8x8, with a reasonably small set of pieces. Then increase number of pieces and board size progressively. I really have no idea how long the program will take -- but would love for somebody to tell me!