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