Previously, I wrote about an algorithm which I constructed with the goal of being able to generate all the possible Minos of size N. My algorithm effectively involved starting from one block, and moving choosing left, forward, and right recursively until the desired count of blocks was reached.

Somehow, I thought this solved my problem. It did not. Not even close. In fact, in hindsight, it’s flaw was obvious, because it meant that there couldn’t be “branches”. So for example the algorithm can generate all regular tetris pieces for size N- Except for the T piece. The T piece isn’t possible because it cannot be represented with a contiguous set of blocks in the same way.

So it was back to the drawing board again. The Snake algorithm was out. I toyed with the idea of having the snake “branch out”, but ran into issues of tracking the correct number of remaining blocks as multiple “snakes” tried to grow out.

This led me to the thinking that all pieces with N blocks are just all possible combinations of all pieces with N-1 blocks, with an added block stapled to every possible location adjacent to those blocks. This gave me a starting point for a new algorithm, which after a lot of thinking, I’ve decided to call the “GetPieces_New” function for the moment.

Like the “snake” algorithm, this one is recursive.

• If the size requested is 1, yield a single block Mino and return.
• Otherwise, recursively iterate on all pieces of Size N-1
• With each piece, iterate over every block, and staple one block to the free adjacent sides and yield the result.

One of the benefits of the snake Algorithm is that any representable Mino can be reduced to a Trinary number, consisting of the L,R, and Forward indicators being the place values. This “new” algorithm should, conceptually, allow something similar- as there is a predictable sequence. However, I’ve not explored this, because I ended up not using that aspect of the snake-algorithm generated Minos either.

The results can be “shuffled” by introducing a random element by both randomizing the order that the blocks are processed and randomizing the order that the adjacent blocks are processed- This, too, is somewhat similar to the approach done by the Snake algorithm for the same thing.

 public static IEnumerable<List<NominoPoint>> GetPieces_New(int BlockCount, NominoPieceGenerationFlags GenerationFlags = NominoPieceGenerationFlags.Flag_None, IRandomizer rgen = null)
 {
     if (BlockCount == 1)
     {
         //End case. block count of 1 is just, well, one block.
         yield return new List<NominoPoint>() { new NominoPoint(0, 0, null) };
     }
     else
     {
         //for all other counts, grab all pieces from the N-1...
         var LowerSet = FilterRotations(GetPieces_New(BlockCount - 1, GenerationFlags, rgen), null);

         foreach (var Npiece in LowerSet)
         {
             //first let's create a HashSet of the x/y tuples.
             HashSet<(int, int)> Positions = new HashSet<(int, int)>();
             foreach (var block in Npiece)
             {
                 Positions.Add((block.X, block.Y));
             }
             //now, iterate through each block in the piece.
             (int x, int y)[] OffsetsArray = new (int x, int y)[] { (-1, 0), (0, 1), (1, 0), (0, -1) };

             var iteratelist = (GenerationFlags == NominoPieceGenerationFlags.Flag_Randomize) ?RandomHelpers.Static.Shuffle(Npiece, rgen): Npiece;
             foreach (var block in iteratelist)
             {
                 //if set to randomize, randomize the offset order for this block's sub piece choices.
                 if (GenerationFlags == NominoPieceGenerationFlags.Flag_Randomize) OffsetsArray = RandomHelpers.Static.Shuffle(OffsetsArray, rgen).ToArray();
                 foreach (var offsetuse in OffsetsArray)
                 {
                     int useX = block.X + offsetuse.x;
                     int useY = block.Y + offsetuse.y;
                     //check if this coordinate is in the Positions hash
                     if (!Positions.Contains((useX, useY)))
                     {
                         NominoPoint Append = new NominoPoint(useX, useY);
                         //yield the lowerset with this point stapled on.
                         yield return Npiece.Concat(new[] { Append }).ToList();
                     }
                 }
             }
         }

     }
 }

In this implementation: FilterRotations is the method, also used by the snake generator, which prevents the sequence from yielding the same mino as one that has already been yielded with a different rotation. Without this the same Minos will show up more than once in the results, but just with different rotations. This code also uses some separate helper methods for the Shuffle, though the context should provide indications of how that works.
When processing each of the N-1 result Minos to add blocks to it, it will go through the blocks and record the coordinates in a HashSet; this way it can (hopefully quickly at high N values) evaluate whether the proposed block to add already exists in the Mino and therefore would not actually add an additional block to the piece.

This algorithm successfully generates all the valid Minos of size N, and by being an iterator method, and with the addition of the random processing, it allows this algorithm to be deployed to simply generate a random Mino with N blocks as well, which is similar to how I ended up using the routine with my snaking algorithm as well. This makes the function, excepting the snake routines added recursion information that it passes down the stack, pretty much a drop-in replacement where I’m using the previous one.

Have something to say about this post? Comment!