Wow, this is great. Your code succeeds at being very efficient while being reasonnably simple and short. I did not know the ListCorrelate[] command, but it is very effective here.

Also, randomly trying the pieces is not really efficient.

Yes, I agree with this, it ts the most basic way, and the least efficient

For instance, randomly combining rotation matrices and hoping you'll eventually get all necessary rotations just doesn't feel good

I disagree with this. While it effectively uses RandomChoice[], in practice there is no randomness in the results for all pieces orientations (thanks to the large number of tries), and it is fast enough (and it needs to be done only once for a given set of pieces). I think it is a matter of taste, but for me it was a lazy way to get all possible orientations without the risk of forgetting some combination of transformations. :-)

Thank you for the notebook - many things to learn !

Well, I don't know. It would be nice to mix this basic solving with machine learning, to improve it by eliminating some tries which are obviously wrong. For example, one could imagine that the machine could learn that it is bad to leave an empty space between two neighboring pieces that cannot be filled by any piece (this is something a human does naturally when trying to solve the puzzle). On a more elaborate level the machine could learn some typical combinations of 2 or 3 pieces which gives useful shapes. But as I have no experience with machine learning, I don't see what would be the way to train the machine. If any expert has some idea about it...

I have attached the notebook version of the code (SOMA set of pieces) for convenience. It contains all the code (the pieces names are still "incorrect", but the pieces themselves are ok), and a few examples.

Attachments:

Indeed, it is nearly the same problem ! Thank you for letting me know about SOMA.

The only difference is in the pieces set, which is here:

The 4 first pieces are also present in Easy Cube, the last three are different (the total volume of the 7 pieces is the same: 27 "unit cubes", which means the two games share identical problems).

Adapting the code is very easy: only three of the piece definitions need to be changed, and the rest of the code can be used as it is. Here is for example two solutions of problem 426 (as shown in your picture) with SOMA pieces:

The difficulty of these problems is probably higher than the Easy Cubes one. For the above solution of problem A426, I made two runs, using respectively ~88000 and 75000 iterations. This probably means that there is only a very small number of different solutions, and finding the solution is more time-consuming (typically between 10 minutes to a small multiple of it ?!). So the code given here should work for all the SOMA problems, but using a more advanced method (e.g. the dancing links algorithm by D. Knuth mentionned by Sander Huisman) would be a good idea if one needs all solutions of all problems... But anyway it is nice to see that a very naive method, quickly progammed, can give solutions.

Adapted code: definition of the pieces for SOMA problems (I did not make the effort to change the pieces names... the new pieces replace the definition of PLine, PSquare and PBulky, all the rest is unchanged)

Pieces Definitions
In[2]:= PTriangle = {{0, 0, 0}, {0, 1, 0}, {1, 0, 0}};
In[3]:= PSquare = {{0, 0, 0}, {0, 0, 1}, {1, 0, 0}, {1, -1, 0}};
In[4]:= PLine = {{0, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, 1, 1}};
In[5]:= PL = {{0, 0, 0}, {0, 1, 0}, {1, 0, 0}, {2, 0, 0}};
In[6]:= PPodium = {{0, 0, 0}, {0, 1, 0}, {-1, 0, 0}, {1, 0, 0}};
In[7]:= PSnake = {{0, 0, 0}, {0, 1, 0}, {1, 0, 0}, {-1, 1, 0}};
In[8]:= PBulky = {{0, 0, 0}, {1, 0, 0}, {0, -1, 0}, {0, 0, 1}};
In[9]:= (* Rotation by angle \[Pi]/2 matrix*)
In[10]:= Mrotz = {{0, 1, 0}, {-1, 0, 0}, {0, 0, 1}};
In[11]:= Mrotx = {{1, 0, 0}, {0, 0, 1}, {0, -1, 0}};
In[12]:= Mrotx = {{0, 0, -1}, {0, 1, 0}, {1, 0, 0}};
In[13]:= (* Reflection  matrix *)
In[14]:= Mrefx = {{-1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
In[15]:= Mrefy = {{1, 0, 0}, {0, -1, 0}, {0, 0, 1}};
In[16]:= Mrefz = {{1, 0, 0}, {0, 1, 0}, {0, 0, -1}};
In[17]:= MUnit = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
In[18]:= (*Operators which peform a given number of rotation, and of \
reflection*)
In[19]:= RotatePiecex[piece_, n_] := Nest[Mrotx.# &, #, n] & /@ piece
In[20]:= RotatePiecey[piece_, n_] := Nest[Mrotx.# &, #, n] & /@ piece
In[21]:= RotatePiecez[piece_, n_] := Nest[Mrotz.# &, #, n] & /@ piece
In[22]:= ReflectPiecex[piece_, n_] := 
 If[n == 0, (MUnit.#) & /@ piece, (Mrefx.#) & /@ piece]
In[23]:= ReflectPiecey[piece_, n_] := 
 If[n == 0, (MUnit.#) & /@ piece, (Mrefy.#) & /@ piece]
In[24]:= ReflectPiecez[piece_, n_] := 
 If[n == 0, (MUnit.#) & /@ piece, (Mrefz.#) & /@ piece]
Each piece with all the possible orientations
In[25]:= MakeAllPieces[piece_] := 
 DeleteDuplicates@
  Table[Module[{Rota, Rotb, Rotc, Refa, Refb, Refc, na, nb, nc, ma, 
     mb, mc},
    Rota = RandomChoice[{RotatePiecex, RotatePiecey, RotatePiecez}];
    Rotb = RandomChoice[{RotatePiecex, RotatePiecey, RotatePiecez}]; 
    Rotc = RandomChoice[{RotatePiecex, RotatePiecey, RotatePiecez}];
    Refa = RandomChoice[{ReflectPiecex, ReflectPiecey, ReflectPiecez}];
    Refb = RandomChoice[{ReflectPiecex, ReflectPiecey, ReflectPiecez}];
    Refc = RandomChoice[{ReflectPiecex, ReflectPiecey, ReflectPiecez}];
    na = RandomInteger[{0, 3}]; nb = RandomInteger[{0, 3}]; 
    nc = RandomInteger[{0, 3}];
    ma = RandomInteger[{0, 1}]; mb = RandomInteger[{0, 1}]; 
    mc = RandomInteger[{0, 1}];
    Refc[Rotc[Refb[Rotb[ Refa[Rota[piece, na], ma], nb], mb], nc], 
     mc]], {i, 1, 2000}]
In[26]:= PTriangleAll = MakeAllPieces[PTriangle]; Length@PTriangleAll
Out[26]= 24
In[27]:= PSquareAll = MakeAllPieces[PSquare]; Length@PSquareAll
Out[27]= 48
In[28]:= PLineAll = MakeAllPieces[PLine]; Length@PLineAll
Out[28]= 48
In[29]:= PLAll = MakeAllPieces[PL]; Length@PLAll
Out[29]= 24
In[30]:= PPodiumAll = MakeAllPieces[PPodium]; Length@PPodiumAll
Out[30]= 24
In[31]:= PSnakeAll = MakeAllPieces[PSnake]; Length@PSnakeAll
Out[31]= 24
In[32]:= PBulkyAll = MakeAllPieces[PBulky]; Length@PBulkyAll
Out[32]= 48
In[33]:= tPieces = {PBulkyAll, PLAll, PPodiumAll, PSnakeAll, PSquareAll, 
   PLineAll, PTriangleAll};
In[34]:= tPiecesNames = {"Bu", "Ll", "Po", "Sn", "Sq", "Li", "Tr"};

Example of use on problem A

Solve problem A426 
In[71]:= coordA426 = 
 Join[Table[{0, j, 0}, {j, -3, 2}], Table[{1, j, 0}, {j, -3, 2}], 
  Table[{-1, j, 0}, {j, -3, 2}],
  Table[{0, j, 1}, {j, -1, 2}], Table[{-1, j, 1}, {j, -1, 2}], 
  Table[{-1, j, 2}, {j, 2, 2}]]
Out[71]= {{0, -3, 0}, {0, -2, 0}, {0, -1, 0}, {0, 0, 0}, {0, 1, 0}, {0, 2, 
  0}, {1, -3, 0}, {1, -2, 0}, {1, -1, 0}, {1, 0, 0}, {1, 1, 0}, {1, 2,
   0}, {-1, -3, 0}, {-1, -2, 0}, {-1, -1, 0}, {-1, 0, 0}, {-1, 1, 
  0}, {-1, 2, 0}, {0, -1, 1}, {0, 0, 1}, {0, 1, 1}, {0, 2, 
  1}, {-1, -1, 1}, {-1, 0, 1}, {-1, 1, 1}, {-1, 2, 1}, {-1, 2, 2}}
In[72]:= TheGridA426 = GridDefine[coordA426];
In[73]:= Plus @@ Flatten[ 1 - TheGridA426]
Out[73]= 27

In[75]:= SolgridA426ex1 = SolveGridBare[TheGridA426];
During evaluation of In[75]:= 88530
In[78]:= PlotGrid3D[SolgridA426ex1, All]

- another post of yours has been selected for the Staff Picks group, congratulations !

We are happy to see you at the top of the "Featured Contributor" board. Thank you for your wonderful contributions, and please keep them coming!

Thank you for the info ! I did not know the dancing links algorithm. Having a look at the wikipedia page about it, it seems very interesting (and way more powerful than my basic algorithm). I have matter to study here.