Nテトリス問題とは？

さっき俺が名付けた問題です。Nクイーン問題をパクりました。
(↓Nクイーン問題って何？って人はこれ見たら分かると思う)
N-queens - とうきょうこうぎょう

いわゆる、あの落ちものゲーのテトリスで使われる正方形が集まってできた物体、ミノっていう名前なんですけど、あれは全部で7種類あるんすよね。
こういうやつ↓

で、このミノを構成しているブロックって4つですよね。

このブロックの数が5とか6の時はどんな形があって、何通りあるんやろって思ったんで、考えてみました。

やりたいこと

Nに自然数を代入して、実行するとブロック数がN個のミノの形を全て求めて、その形と個数を出力できればOK。
※縦長に出力するものとする。
※回転させて一致する図形はいずれか1つのみ出力するものとする。
表にまとめるとこんな感じ。

引数	ミノの形状(省略)	ミノの種類の個数
1		$1$
2		$1$
3		$2$
4		$7$
5		$18$
6		$60$
7		$196$
8		$704$
9		$2,500$
10		$9,189$
…		…

というわけで、こんな感じで実装してみました。

実装

Program.cs

using System.Diagnostics;

namespace CreatingMino {
    internal class Program {
        
        //ブロック数1のミノ。
        static Mino firstMino = new Mino(new List<int[]> { new int[] { 0, 0 } });

        //全ての結果を保持する。
        static List<Mino> minoList = new List<Mino> { firstMino };

        //ブロックが(i + 1)個のミノを保持する。
        static List<Mino> nextMinoList = new List<Mino> { };

        //出力するミノを保持する。
        static List<Mino> printMinoList = new List<Mino> { };

        //今回の使用ブロック数。
        const int N = 5;

        static void Main(string[] args) {

            var sw = Stopwatch.StartNew();

            CreateMino(minoList);

            //ブロック数がNのミノのみ出力する。
            foreach(var mino in minoList) {
                if(mino.Blocks.Count() == N) {
                    printMinoList.Add(mino);
                }
            }

            Mino.PrintMino(printMinoList);

            sw.Stop();

            Console.WriteLine("経過時間: " + sw.ElapsedMilliseconds + " ms");

        }

        //ブロック数がi個の全てのミノの形状と、その個数を求める。
        private static void CreateMino(List<Mino> oMinoList) {

            nextMinoList = new List<Mino>();

            foreach(var oMino in oMinoList) {
                var testBlocks = new List<int[]>();

                //ブロックの外側に1マス分の空のブロックを追加し、枠を作る。
                foreach(var block in oMino.Blocks) {
                    testBlocks.Add(new int[] { block[0] + 1, block[1] + 1 });
                }

                //AddMino()をtestBlocksに対して行うと反復処理が行えなくなるので、
                //"testBlocks"の中身を"tmpBlocks"にコピーしておく。
                var tmpBlocks = testBlocks.Select(b => b.ToArray()).ToList();
                var newBlock = new int[2];
                var settable = true;

                //上→右→下→左の順に、ブロックの隣に新たなブロックを置けるか確認する。
                foreach(var tBlock in testBlocks) {
                    foreach(var direction in Mino.directionMap.Keys) {
                        //tBlockの1つ上、右、下、左隣の座標を求める。
                        newBlock = Mino.GetNewBlock(tBlock, direction);

                        //tmpBlockに、既にブロックが置かれていなければ、その形状をminoListに追加する。
                        foreach(var block in testBlocks) {
                            if(block[0] == newBlock[0] && block[1] == newBlock[1]) {
                                settable = false;
                            }
                        }
                        if(settable == true) {
                            AddMino(tmpBlocks, newBlock);
                            tmpBlocks.Remove(newBlock);
                        }
                        settable = true;
                    }
                }
            }

            minoList.AddRange(nextMinoList);

            //i個のブロックのミノを使用して(i + 1)個のミノを生成して、
            //それをN個まで繰り返した後、処理が終了する。
            if(nextMinoList.First().Blocks.Count() < N) { CreateMino(nextMinoList); }
        }

        //適切な形状であれば、ミノを生成しリストに追加する。
        private static void AddMino(List<int[]> blocks, int[] nBlock) {
            blocks.Add(nBlock);

            var blocksWithNoSpace = RemoveSpaces(blocks);

            var height = blocksWithNoSpace.Max(y => y[0]) - blocksWithNoSpace.Min(y => y[0]) + 1;
            var width = blocksWithNoSpace.Max(x => x[1]) - blocksWithNoSpace.Min(x => x[1]) + 1;

            //縦より横の長さの方が長い場合
            if(height < width) {
                //形状を時計回りに90°回転させて、長さを(縦)≥(横)にする。
                var tmpBlocks = new List<int[]>();
                foreach(var block in blocksWithNoSpace) {
                    tmpBlocks.Add(new int[] { block[1], height - block[0] });
                }
                blocksWithNoSpace = RemoveSpaces(tmpBlocks);
                (height, width) = (width, height);
            }

            //既に生成されているミノと比較して、重複がない場合のみミノを生成し、リストに追加する。
            if(CheckNoDuplication(blocksWithNoSpace, height, width)) {
                nextMinoList.Add(new Mino(blocksWithNoSpace));
            };
        }

        //CreateMino()で加えられた外枠を取り除き、隙間を取り除いた形状にして返す。
        private static List<int[]> RemoveSpaces(List<int[]> blocks) {
            blocks = blocks.OrderBy(y => y[0]).ThenBy(x => x[1]).ToList();

            //xMin(各座標の中で最小のx座標の値)を算出し、左端に何マスの隙間があるか計算する。 yMin(最小のy座標の値)も同様。
            var xMin = blocks.Min(x => x[1]);
            var yMin = blocks.Min(y => y[0]);

            var blocksWithNoSpace = new List<int[]>();

            foreach(var block in blocks) {
                blocksWithNoSpace.Add(new int[] { block[0] - yMin, block[1] - xMin });
            }

            return blocksWithNoSpace;
        }

        //重複しているミノの生成を防ぐ。
        //与えられた形状に重複が無かった場合、trueを返す。
        private static bool CheckNoDuplication(List<int[]> blocks, int height, int width) {
            bool sameFlg;
            foreach(var mino in nextMinoList) {
                //縦と横の長さが同じ場合のみ重複をチェックする。
                if(height == mino.Height && width == mino.Width) {
                    //同じかどうか比較
                    var rBlocks = blocks.Select(b => b.ToArray()).ToList();
                    var tmpBlocks = new List<int[]>();
                    for(var i = 0; i < 4; i++) {
                        var differ = i % 2 == 0 ? height : width;
                        //tmpBlocksに、rBlocksを90°回転させた座標を代入して、チェックを行う。
                        foreach(var rBlock in rBlocks) {
                            tmpBlocks.Add(new int[] { rBlock[1], differ - 1 - rBlock[0] });
                        }
                        tmpBlocks = tmpBlocks.OrderBy(y => y[0]).ThenBy(x => x[1]).ToList();
                        rBlocks = tmpBlocks.Select(b => b.ToArray()).ToList();
                        sameFlg = true;
                        //全ての座標が一致していた場合、重複していると判定される。
                        for(var j = 0; j < mino.Blocks.Count; j++) {
                            if(!Enumerable.SequenceEqual(tmpBlocks[j], mino.Blocks[j])) { sameFlg = false; }
                        }
                        if(sameFlg) { return false; }
                        tmpBlocks.Clear();
                    }
                }
            }
            return true;
        }
    }
}

mino.cs

using System.Text;

namespace CreatingMino {
    public class Mino {
        //ミノの形状を表現するクラス。Blocksには各ブロックの位置をxy平面上の格子点に対応付け、その座標(y座標, x座標)が入る。
        //原点の座標は(0, 0)とし、xは正の方向に、yは負の方向に進む。
        //Heightにはその形状の縦の長さ、Widthには横の長さが入る。
        //
        // 　0  1  … x
        //0　■  ■
        //1　■ 　
        //2　■
        //:
        //y
        //このような形状のデータは、[ {"Blocks" : "{0, 0}, {0, 1}, {1, 0}, {2, 0}", "Height" : "3", "Width" : "2"} ]となる。

        //ブロックの座標
        public List<int[]> Blocks { get; }
        //ミノの高さ
        public int Height => CalcHeight();
        //ミノの長さ
        public int Width => CalcWidth();

        public Mino(List<int[]> blocks) {
            Blocks = blocks;
        }

        //ミノの高さを求める。
        private int CalcHeight() {
            return Blocks.Max(y => y[0]) - Blocks.Min(y => y[0]) + 1;
        }

        //ミノの長さを求める。
        private int CalcWidth() {
            return Blocks.Max(x => x[1]) - Blocks.Min(x => x[1]) + 1;
        }

        //ブロックを追加する方向
        public static Dictionary<String, int[]> directionMap = new Dictionary<String, int[]>() {
            {"above", new int[]{ -1,  0 } },
            {"right", new int[]{  0,  1 } },
            {"below", new int[]{  1,  0 } },
            {"left" , new int[]{  0, -1 } }
        };

        //ブロックを1つ追加する。
        public static int[] GetNewBlock(int[] blocks, string direction) {
            return new int[] { blocks[0] + directionMap[direction][0], blocks[1] + directionMap[direction][1] };
        }

        //ミノを出力する。(N ≥ 9ではスクロールしきれず全パターンを表示できない。)
        public static void PrintMino(List<Mino> minoList) {

            var sbAllMinos = new StringBuilder();

            foreach(var mino in minoList) {

                //各ミノの縦×横の長さの、空文字が連続した文字列を生成する。
                var sbMino = new StringBuilder(new string('　', mino.Height * mino.Width));

                //blockの座標から、何文字目を「■」に変換するかを求める。
                var target = 0;
                foreach(var block in mino.Blocks) {
                    target = block[0] * mino.Width + block[1];
                    sbMino.Remove(target, 1).Insert(target, "■");
                }
                //各行末ごとに改行する。
                for(var i = mino.Height; i > 0; i--) {
                    target = i * mino.Width;
                    sbMino.Insert(target, "\n");
                }
                sbAllMinos.Append(sbMino.Append("\n"));
            }
            sbAllMinos.Append("ブロック数 " + minoList.Last().Blocks.Count() + " の時 : " + minoList.Count() + "個\n");
            Console.WriteLine(sbAllMinos.ToString());
        }
    }
}

流れはこんな感じです。
N=iのときのミノがM種類あったとして、まず1種類目のミノの1つ目のブロックを選びます。そのブロックの上、右、下、左にブロックが無ければブロックを置きます。その形状を4回時計回りに90度回転させて、既に生成された形状と被らなければ、新たなミノとして扱います。
それを、i個目のブロックまで、M種類目のミノまで行って、N=i+1のときのミノを求める、みたいなことをしています。

↓N=3のミノを元に、N=4のミノを求めるときにやっていることです。

アルゴリズムに関してはこれ以上いいのが思いつかなかったです。もっと無駄なく調べ切れる方法があるんやろうな…
ちなみに、かかった時間はこんな感じでした。

N	計算時間(ms)
1	22
2	19
3	20
4	23
5	26
6	80
7	396
8	2,745
9	31,725
10	479,806
…	…
これ作った後、座標の管理をPoint型にするように作り直しました(ListではなくList)が、時間が余計に掛かったので捨てました。

ブロック数がNのときミノは何種類ある？

ところで、コードを完成させた後、ブロック数がNのときミノの種類は何通りあるんやろ、という所が気になりました。
いわゆる、ブロック数がNの時のミノの種類の個数をM(N)としたとき、それがどんな式になるんやろうという疑問です。想像もつかんけど。

N	M(N)(ミノの種類の個数)
1	$1$
2	$1$
3	$2$
4	$7$
5	$18$
6	$60$
7	$196$
8	$704$
9	$2,500$
10	$9,189$
…	…

これ見て、思いました。諦めよう。
とはいうものの、流石にちょっと考えました。

…ちょっと用事思い出したのでこの辺にしときます。
というわけで、分かった方は俺にこっそり耳元で教えてください。
一応、ブロック数がNの時、長辺、短辺が最短のミノの長さが、長辺が$\lceil \sqrt{n} \rceil$、短辺が$\lceil\frac{n}{\lceil\sqrt{n}\rceil}\rceil$ってことは分かりました。

おまけ

この記事を書いてて知ったんですけど、この形状にはテトロミノっていう名称があったらしい。これ書かんと一生知らんかったと思う。
参照
[テトロミノ - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%AA%E3%82%AA%E3%83%9F%E3%83%8E