So I am trying to write a program that, given a set of polycubes, produces the set of arrangements of the polycubes that form a 3x3x3 cube. (This is a simple form of the problem; I hope perhaps to eventually be able to produce arrangements for any shape.)
As a particular example we have the Soma cube:
After some research I have found that this problem can be reduced into an exact cover problem as follows:
Create a matrix that has one column for each puzzle piece and one column for each 'space' in the board. (So in the case of the 3x3x3 cube we would have 27 columns for the spaces in the board.) Then produce for each possible orientation of a piece inside the 3x3x3 cube a row which contains information about the piece chosen and its position inside the 3x3x3 cube.
So if you consider a particular row for an image of a piece, it will have a 1 in the column corresponding to that piece and a 1 in each of the columns corresponding to the spaces it fills.
In this way, finding an arrangement of the pieces to create a 3x3x3 cube instead becomes finding a subset of the rows such that every column in the submatrix contains exactly one '1'.
The issue I have is 'easily' generating all the rows of the matrix such that all possible arrangements of a piece are produced. That is, given a list of points that represent the relative position of each block in a polycube (for example [(0, 0, 0), (1, 0, 0), (2, 0, 0), (0, 1, 0)] represents the T-shaped tetronimo) how can I produce the rows of the matrix as described above which relate to this piece?
A better explanation on how the problem is reduced to the exact cover problem and how to then solve this at http://ift.tt/1FIKs7t .
Aucun commentaire:
Enregistrer un commentaire