adria.junyent-ferreThe puzzle has six polycubes, and the aim of the game is to arrange them together to form a solid 3x3 cube. I call the polycubes tetrominos because most of them are made of 4 cubes but this is not true for all of them.
The code is structured in the following files:
| File name | Description |
| solve_tetrominos.m | This is the main script that defines the pieces and tries to find a solution. |
| generate_all_positions.m | This function generates all possible positions a piece can be placed in the 3d cube. |
| translate_x.m | This function creates a position of a piece by displacing it in the x axis. |
| translate_y.m | This function creates a position of a piece by displacing it in the y axis. |
| translate_z.m | This function creates a position of a piece by displacing it in the z axis. |
| rotate_x.m | This function creates a position by rotating a piece in the x axis. |
| rotate_y.m | This function creates a position by rotating a piece in the y axis. |
| rotate_z.m | This function creates a position by rotating a piece in the z axis. |
| plot_all_configurations.m | This function plots all positions and orientations a piece can be places inside the cube. Redundant configurations are omitted. |
| plot_all_orientations.m | This function plots all orientations of a piece. |
| plot_all_translations.m | This function plots all possible positions of a piece inside the cube. |
| plot_conf.m | This function shows a 3D representation of the position of a piece inside the cube. |
| plot_pixel.m | This function plots a "3D pixel", a single cube of a polycube. |
A zip file with all these scripts can be found in the file section of this project. The code is written in Matlab language but can be run in GNU Octave as well. The only issue is that 3D plots won't work under GNU Octave. I may spend some time implementing a different type of plot for GNU Octave in the future.
Some comments about how the algorithm works:
The main script, "solve_tetrominos" defines the set of pieces, generates all their possible positions and orientations inside the 3x3 cube and then tries to combine them together to complete the cube. Once a solution is found, the search is stopped and the program plots the assembled cube and the individual positions of each piece (see screenshot).
A cell array of tetrominos is generated in the beginning. Each element of this array is a table of cell arrays that corresponds to each individual configuration a piece can take inside the 3D cube. These configurations are 3D tables of 3x3x3 where each element is either 1 or 0, 1 meaning there's a cube of the tetromino in that position of the 3D cube and a 0 when there's nothing. The long list of configurations is generated by a script named "generate_all_positions" which applies displacements and rotations to generate all possible configurations.
Once all configurations of all pieces have been found, the algorithm starts trying to combine all pieces together avoiding overlapping. Once it succeeds combining 6 pieces without overlapping inside the 3D cube, it knows it has found a suitable solution and stops.
% clear;
% clc;
% close all;
% M=[1,2,0;0,3,0;0,4,0];
M=[1,1,0;0,1,0;0,1,0];
M(:,:,2)=[0,0,0;0,0,0;0,0,0];
M(:,:,3)=[0,0,0;0,0,0;0,0,0];
tetrominos{1}=generate_all_positions(M);
M=[1,1,1;0,1,0;0,0,0];
M(:,:,2)=[0,0,0;0,0,0;0,0,0];
M(:,:,3)=[0,0,0;0,0,0;0,0,0];
tetrominos{2}=generate_all_positions(M);
M=[1,1,1;0,1,0;0,0,0];
M(:,:,2)=[0,0,0;0,1,0;0,0,0];
M(:,:,3)=[0,0,0;0,0,0;0,0,0];
tetrominos{3}=generate_all_positions(M);
M=[1,1,0;0,1,0;0,0,0];
M(:,:,2)=[0,0,0;0,1,0;0,0,0];
M(:,:,3)=[0,0,0;0,0,0;0,0,0];
tetrominos{4}=generate_all_positions(M);
M=[1,1,1;0,1,0;0,0,0];
M(:,:,2)=[1,0,0;0,0,0;0,0,0];
M(:,:,3)=[0,0,0;0,0,0;0,0,0];
tetrominos{5}=generate_all_positions(M);
M=[1,1,0;0,1,1;0,0,0];
M(:,:,2)=[0,1,0;0,0,0;0,0,0];
M(:,:,3)=[0,0,0;0,0,0;0,0,0];
tetrominos{6}=generate_all_positions(M);
tic
found=0;
m=1;
while(m<=length(tetrominos{1})&&(~found))
temp_m=tetrominos{1}{m};
n=1;
while(n<=length(tetrominos{2})&&(~found))
temp_n=temp_m+tetrominos{2}{n};
if (sum(sum(sum((temp_n)>1)))==0)
o=1;
while(o<=length(tetrominos{3})&&(~found))
temp_o=temp_n+tetrominos{3}{o};
if (sum(sum(sum((temp_o)>1)))==0)
p=1;
while(p<=length(tetrominos{4})&&(~found))
temp_p=temp_o+tetrominos{4}{p};
if (sum(sum(sum((temp_p)>1)))==0)
q=1;
while(q<=length(tetrominos{5})&&(~found))
temp_q=temp_p+tetrominos{5}{q};
if (sum(sum(sum((temp_q)>1)))==0)
r=1;
while(r<=length(tetrominos{6})&&(~found))
temp_r=temp_q+tetrominos{6}{r};
if (sum(sum(sum((temp_r)>1)))==0)
found=1;
disp('found!');
end
r=r+1;
end
end
q=q+1;
end
end
p=p+1;
end
end
o=o+1;
end
end
n=n+1;
end
m=m+1;
end
toc
colours={'r','g','b','c','m','w'};
if(found)
m=m-1;
n=n-1;
o=o-1;
p=p-1;
q=q-1;
r=r-1;
confs=[m,n,o,p,q,r];
figure('Position',[100,100,2000,200]);
for s=1:6
subplot(1,6,s);
plot_conf(tetrominos{s}{confs(s)},colours{s});
end
figure('Position',[100,100,200,200]);
for s=1:6
plot_conf(tetrominos{s}{confs(s)},colours{s});
end
endThere are a few auxiliary functions that are used to create 3D plots of the puzzle. These use a Matlab function that allows to plot 3d polygons to plot each cube of the tetrominos as a set of 4 square faces. There are three functions that can be used to debug the algorithm that plot all orientations, translations and all possible configurations a piece can occupy inside a 3D cube (see screenshot of "plot_all_configurations".