There is a game of Pentamino .

In my case, it is necessary to break the figure of 60 squares into 12 pentamino different types. Maybe someone has already solved a similar problem? No code needed. We need the names of the algorithms that you used or other useful hints.

  • would say simple STROICHKAAAA! =) everyone knows Stroichka and Tetris ... although probably they don’t understand shkolota =) - Gorets
  • @Gorets, and I, at one time, it was "Pentamino" on the box that was written) - delphist007

3 answers 3

The easiest algorithm is brute force. We prepare a 5 by 12 matrix (or 6 by 10. If 0 is written in the cell, it means no one is busy, if the number is greater than zero, it means that it belongs to the figure with the given number. And now, BALAX, we take the next figure and try to put it in each cell in four positions, if we don’t attach ourselves, we take the next one. If we’ve attached, try the next figure, if all the figures are used, there was a solution.

The way looks bad. Figures 48 (12 times 4), 60 cells. Each figure can theoretically be in any cell (theoretically). therefore, we get 48 to 60 degrees (and this is about 7 to 10 to 100). Therefore, the following improvements should be applied - do not put a new figure in such a cage that it will not have a common border with existing figures (the very first one necessarily occupies the corner cage). For the first figure there will be a maximum of 4 options, and for the subsequent ones - 10-15 (you need to sit and clarify). And this will give much less than 4 * (44 in 15) - that is, several hundred thousand. And it is already easy to sort out.

You can even a little better. Spread brute force into two parts. In the first part we try to collect the bottom 2 (3 or 4) lines. That is, do not try the options when the next figure is located above this line (if part of the figure sticks out - do not worry). And then, for each of the options found, look for a complete solution. Or even better - to find solutions where the collected areas do not intersect in figures. Accordingly, there will be a bottom and a top, and you will need to fill in the middle. If you fill no more than 3 lines, and a rectangle is 6 by 10, then there will be no overlap (this is easy to prove).

And for the rest - read the article on Habré .

PS The above is correct if we are talking about one-sided pentamino. If it is allowed to turn the figures, there will be more options.

    My version:

    1. It is necessary to have a set of source figures (12 pieces according to the condition) (otherwise the task is simplified without them =))

    2. Next, you need a condition that out of these 12 pieces it’s REALLY possible to fold a “figure of 60 squares” - what kind of figure is this?))

    3. Randomization does not work out as it should =) or think over the algorithm on a sample of suitable figures ... but so far nothing is clear = (

    • figures can be completely different)) - Natashenka
    • I think this simplifies the task, because, for example, 60/12 = 5 is possible - these are equal parts, (that is, you can hold 12 figures of equal sizes of 5 squares), we also need that they are not equal, then just change their size to 2,3,5,7,8 - and display the result ... - Gorets
    • they should be torn, I thought it was clear from the task :) Wikipedia presents 12 possible figures, from which it is necessary to assemble the final figure (submitted at the entrance). - Natasha
    • Well, in the same place on the wiki, you have the necessary algorithms ... - Gorets

    This type of task is related to dynamic profile programming. More details can be read here . I can immediately say that the method itself is quite complicated and it will be extremely difficult to understand the first time.