ペントミノをC#で解く

ペントミノとは

12個の形の違ったピースを四角の枠にぴっちりとはめ込むパズルで、子供の頃、皆さんもきっとやったことのあるパズルだと思います。

詳しくは、Wikipediaのページペントミノを参照してください。

ここでは、５×12の長方形に収めることにします。ほかにも、6x10、4x15、 3x20 の長方形に収めるパターンもあります。

どうやって解くか（まずはデータの持ち方を考える）

この手のプログラムでは、ピースデータをどのように表現するかで、作成するプログラムコードは大きく変わってきます。

ここでは、ひとつのピースをchar型の２次元配列として表現しています。

ピースがあるところには、ピースの形を顕わす文字を入れています。空白文字の部分は、ピースが無いことを示しています。

例えば、Ｌ 字型のピースでは、

new char[,] {
    { 'L',' ' },
    { 'L',' ' },
    { 'L',' ' },
    { 'L','L' },
}),

T字型だと

new char[,] {
     { 'T','T','T' },
     { ' ','T',' ' },
     { ' ','T',' ' },
}),

I字型だと

new char[,] {
    { 'I','I','I','I','I' },
}),

このように保持します。
この配列は、Pieceクラス内に保持するものとします。

このようにしているのは、このプログラムは、コンソールアプリとして作成しているので、配列の内容をそのまま出力すれば、ピースの形がわかるようにするためです。

そのため、WPFやWindowsFormsでグラフィカルに表示する場合は、ピース毎に配列の要素の文字を変える必要はありません。

これを、以下のようにして、12個のピースをリストに格納します。

// 利用するピースデータ
public static  IList<Piece> PieceList = new List<Piece> {
    new Piece(
        new char[,] {
            { ' ','X',' ' },
            { 'X','X','X' },
            { ' ','X',' ' },
    }),
    new Piece(
        new char[,] {
            { ' ','F','F' },
            { 'F','F',' ' },
            { ' ','F',' ' },
    }),
    
	...
			

ピースを回転、反転させる

実際のパズルと同じようにピースは、回転や反転ができるようにします。

Peiceクラスに、R90, Mirror, AllCandidates というメソッドを定義しています。その抜粋を示します。これらはprivateメソッドとしています。

実際には、Pieceを利用するクラスは、AllSeries というプロパティを利用して、回転や反転したピースすべてを列挙しています。

public class Piece {
	// 一つのピースの配列の空白以外の場所の位置を記憶
    public IList<Point> Points { get; private set; }

	// 回転、反転させた全てのパターンを列挙（コンストラクタで設定）
    public IList<Piece> AllSeries { get; private set; }

	// 	ピースのサイズ
    public int YSize { get; set; }  
    public int XSize { get; set; }

	// ピースの形を示す文字
    public char Char { get; private set; }

    // 右に90度回転
    public Piece R90() {
        return new Piece {
            Char = this.Char,
            Points = Points.Select(pt => new Point { 
            		X = pt.Y, Y = this.XSize - pt.X - 1 
            	})
              .OrderBy(pt => pt.Value).ToList(),
            XSize = this.YSize,
            YSize = this.XSize,
        };
    }

    // 左右に反転
    public Piece Mirror() {
        return new Piece {
            Char = this.Char,
            Points = Points.Select(pt => new Point { 
            		X = pt.X, Y = this.YSize - pt.Y - 1 
            	})
              .OrderBy(pt => pt.Value).ToList(),
            XSize = this.XSize,
            YSize = this.YSize,
        };
    }

    // 回転、反転の８つのピースを得る （左右対称なら４つ）
    private IEnumerable<Piece> AllCandidates() {
        yield return this;
        Piece r1 = this;
        for (int j = 0; j < 3; j++) {
            r1 = r1.R90();
            yield return r1;
        }
        var mirror = this.Mirror();
        if (!_pieceComparer.Equals(this, mirror)) {
            yield return mirror;
            for (int j = 0; j < 3; j++) {
                mirror = mirror.R90();
                yield return mirror;
            }
        }
    }
}

なお、一つのピースは、回転／反転させることで、最大で８つの置き方が存在します。
回転／反転後に、重ね合わせて同じ形になる場合は、それを除外するようにしています。

アルゴリズムは

ピースのデータ構造が決まれば、あとは、再起的な処理でピースを箱にはめていき、すべてのピースが箱に収まるまで試行を繰り返すことになります。

もちろん、ピースが箱に入らなくなった時点で試行を中止し、別の置き方を試します。
この部分は、他のパズルと同様に、深さ優先の探索で再帰的に処理しています。

以下に、探索をしてるSolveメソッドを抜粋します。
長方形の枠のサイズは、このメソッドの引数で渡すようになっているので、ここを変えれば、3x20 などの解も求めることができます。
このメソッドの中で、いろんなメソッドを呼び出していますが、その詳細は、この記事の最後に載せるソースコードを見てください。

解が一つ求まったら、処理を終了しています。

public bool Solve(int xSize, int ySize) {
    _board = new Board(xSize, ySize);
    return Solve(Piece.PieceList);
}

// 解を求める （再帰メソッド）
private bool Solve(IEnumerable<Piece> pieceList) {
    // 最初のピースを取り出す
    var piece = pieceList.FirstOrDefault();              
    if (piece == null)
        // すべてのペースを使い切った(つまり成功)
        return true;
    // ピースを回転、反転させたものを取り出し試していく。
    foreach (var curr in piece.AllSeries) {
        // すべての位置を順に取り出す、そこにcurrを置いていく
        foreach (var topleft in _board.AllPoints) { 
            // 取り出した位置(左上)にピースを置いてみる
            if (Put(topleft, curr)) {  
                if (CountEmpty().Any(n => n % 5 != 0)) {
                    // 5で割り切れない空き領域があれば、そこにピースははめ込むことができない。
                    // 枝刈り処理 これ以上試しても仕方が無いので、次を試す。
                    Remove(topleft, curr);
                    continue;
                }
                var newlist = pieceList.Where(o => o.Char != curr.Char).ToList();
                // 置けたら残りのピースで同じことを繰り返す
                if (Solve(newlist) == true)
                    // 成功したら処理を終える
                    return true;
                // 状態を戻して、次を試す
                Remove(topleft, curr);       
            }
        }
    }
    return false;
}

もう少し工夫すれば、全ての解を得るように変更することも可能だと思います。

このコードだと、IObservableとIObserver 使うのが良いかな。

戻り値をIEnumerable<Board>として、yield return 使って、複製したBoardインスタンスを返すようにする方法もありますね。

実行例

画面上の日時は、探索開始時刻と探索終了時刻です。

別のサイズでも実行してみました

ソースコード

では、すべてのソースコードを掲載します。(GitHubでも公開しています)

ソースコードにはコメントを書いておきましたので、詳しくはそちらを見てください。

Point.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PentominoApp {
    public struct Point {
        public int X { get; set; }
        public int Y { get; set; }

        // 上下左右の位置を列挙
        public IEnumerable<Point> GetAroundPoints() {
            yield return new Point { X = this.X, Y = this.Y + 1 };
            yield return new Point { X = this.X + 1, Y = this.Y };
            yield return new Point { X = this.X - 1, Y = this.Y };
            yield return new Point { X = this.X, Y = this.Y - 1 };
        }

        // BoardにPieceを置く際に利用する。
        public Point Add(Point pt) {
            return new Point {
                X = X + pt.X,
                Y = Y + pt.Y
            };
        }

        public override int GetHashCode() {
            return Value;
        }

        public int Value {
            get { return X + Y * 100; }
        }
    }

}

Piece.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PentominoApp {

    public class Piece {
        public IList<Point> Points { get; private set; }

        public IList<Piece> AllSeries { get; private set; }

        public int YSize { get; set; }
        public int XSize { get; set; }

        public char Char { get; private set; }

        private Piece() {

        }

        public Piece(char[,] piece) {
            YSize = piece.GetUpperBound(1) + 1;
            XSize = piece.GetUpperBound(0) + 1;
            Points = GetAllPoints().Where(pt => piece[pt.X, pt.Y] != ' ')
                                        .OrderBy(pt => pt.Value).ToList();
            var first = Points[0];
            Char = piece[first.X, first.Y];
            AllSeries = this.AllCandidates().Distinct(_pieceComparer).ToList();
        }

        // 右に90度回転
        public Piece R90() {
            return new Piece {
                Char = this.Char,
                Points = Points.Select(pt => new Point { X = pt.Y, Y = this.XSize - pt.X - 1 })
                                         .OrderBy(pt => pt.Value).ToList(),
                XSize = this.YSize,
                YSize = this.XSize,
            };
        }

        // 左右に反転
        public Piece Mirror() {
            return new Piece {
                Char = this.Char,
                Points = Points.Select(pt => new Point { X = pt.X, Y = this.YSize - pt.Y - 1 })
                                         .OrderBy(pt => pt.Value).ToList(),
                XSize = this.XSize,
                YSize = this.YSize,
            };
        }

        // ピースの全ての位置を列挙する
        private IEnumerable<Point> GetAllPoints() {
            for (int xx = 0; xx < this.XSize; xx++) {
                for (int yy = 0; yy < this.YSize; yy++) {
                    yield return new Point { X = xx, Y = yy };
                }
            }
        }

        // 回転、反転の８つのピースを得る （左右対称なら４つ）
        private IEnumerable<Piece> AllCandidates() {
            yield return this;
            Piece r1 = this;
            for (int j = 0; j < 3; j++) {
                r1 = r1.R90();
                yield return r1;
            }
            var mirror = this.Mirror();
            if (!_pieceComparer.Equals(this, mirror)) {
                yield return mirror;
                for (int j = 0; j < 3; j++) {
                    mirror = mirror.R90();
                    yield return mirror;
                }
            }
        }

        private static PieceComparer _pieceComparer = new PieceComparer();

        // 利用するピースデータ
        public static  IList<Piece> PieceList = new List<Piece> {
            new Piece(
                new char[,] {
                    { ' ','X',' ' },
                    { 'X','X','X' },
                    { ' ','X',' ' },
            }),
            new Piece(
                new char[,] {
                    { ' ','F','F' },
                    { 'F','F',' ' },
                    { ' ','F',' ' },
            }),
            new Piece(
                new char[,] {
                    { 'I','I','I','I','I' },
                }),
            new Piece(
                new char[,] {
                    { 'L',' ' },
                    { 'L',' ' },
                    { 'L',' ' },
                    { 'L','L' },
                }),
            new Piece(
                new char[,] {
                    { 'N',' ' },
                    { 'N',' ' },
                    { 'N','N' },
                    { ' ','N' },
            }),
            new Piece(
                new char[,] {
                    { 'P','P' },
                    { 'P','P' },
                    { 'P',' ' },
            }),
            new Piece(
                new char[,] {
                    { 'T','T','T' },
                    { ' ','T',' ' },
                    { ' ','T',' ' },
            }),
            new Piece(
                new char[,] {
                    { 'U',' ','U' },
                    { 'U','U','U' },
            }),
            new Piece(
                new char[,] {
                    { 'V',' ',' ' },
                    { 'V',' ',' ' },
                    { 'V','V','V' },
            }),
            new Piece(
                new char[,] {
                    { 'W',' ',' ' },
                    { 'W','W',' ' },
                    { ' ','W','W' },
            }),
            new Piece(
                new char[,] {
                    { ' ','Y' },
                    { 'Y','Y' },
                    { ' ','Y' },
                    { ' ','Y' },
            }),
            new Piece(
                new char[,] {
                    { 'Z','Z',' ' },
                    { ' ','Z',' ' },
                    { ' ','Z','Z' },
            }),
        };
    }
}

Board.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PentominoApp {
    public class Board {
        private char[,] _box;
        int _xSize;
        int _ySize;

        // コンストラクタ
        private Board(Board board) {
            this._xSize = board._xSize;
            this._ySize = board._ySize;
            this._box = board._box.Clone() as char[,];
        }

        // コンストラクタ
        public Board(int xmax, int ymax) {
            _box = new char[xmax + 2, ymax + 2];
            _xSize = xmax + 2;
            _ySize = ymax + 2;

            foreach (var pt in GetPointsIncludeFrame()) {
                if (IsValidPoint(pt))
                    this[pt] = ' ';
                else
                    this[pt] = '*';
            }
        }

        // 枠も含めてすべての位置を列挙する
        private IEnumerable<Point> GetPointsIncludeFrame() {
            for (int yy = 0; yy < this._ySize; yy++) {
                for (int xx = 0; xx < this._xSize; xx++) {
                    yield return new Point { X = xx, Y = yy };
                }
            }
        }

        private List<Point> _AllValidPoint = null;

        // 枠を除いた位置を列挙する
        public IEnumerable<Point> AllPoints {
            get {
                if (_AllValidPoint == null) {
                    var list = new List<Point>();
                    for (int yy = 1; yy < this._ySize - 1; yy++) {
                        for (int xx = 1; xx < this._xSize - 1; xx++) {
                            list.Add(new Point { X = xx, Y = yy });
                        }
                    }
                    _AllValidPoint = list.OrderBy(pt => pt.X + pt.Y).ToList();
                }
                return _AllValidPoint;
            }
        }      


        // インデクサ
        public char this[Point pt] {
            get { return _box[pt.X, pt.Y]; }
            set { _box[pt.X, pt.Y] = value; }
        }

        // Boardの内容をプリントする
        public void Print() {
            var ystr = new string(Enumerable.Repeat('-', _xSize-2).ToArray());
            Console.WriteLine($"+{ystr}+");
            for (int y = 1; y < _ySize - 1; y++) {
                Console.Write("|");
                for (int x = 1; x < _xSize - 1; x++) {
                    Console.Write(_box[x, y]);
                }
                Console.WriteLine("|");
            }
            Console.WriteLine($"+{ystr}+");
        }

        // 複製をつくる
        public Board Clone() {
            return new Board(this);
        }

        // 有効な位置か （枠ならばfalse)
        internal bool IsValidPoint(Point point) {
            return ((1 <= point.X && point.X < _xSize - 1) &&
                    (1 <= point.Y && point.Y < _ySize - 1));
        }

        // Boardの内容を変更してしまうので注意。元の状態に戻すのは呼び出す側の責務とする。
        // Pointのの位置に注目した時に、いくつの空白があるかをカウントする。pointも含める。
        // 再帰的に処理をしている。
        internal int CountEmpty(Point point) {
            if (this[point] != ' ')
                return 0;
            this[point] = '#';
            int count = 1;
            foreach (var pt in point.GetAroundPoints()) {
                if (this[pt] == ' ') {
                    count += CountEmpty(pt);
                }
            }
            return count;
        }
    }
}

PieceComparer.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PentominoApp {
    // 2つのピースを比較するクラス
    public class PieceComparer : IEqualityComparer<Piece> {
        public bool Equals(Piece a, Piece b) {
            return a.Points.SequenceEqual(b.Points);
        }

        public int GetHashCode(Piece obj) {
            return obj.Points.Aggregate(0, (hc, pt) => hc ^ pt.GetHashCode());
        }
    }
}

Pentomino.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;


namespace PentominoApp {

    public class Pentomino {
        private Board _board;

        // 問題を解く
        public bool Solve(int xSize, int ySize) {
            _board = new Board(xSize, ySize);
            return Solve(Piece.PieceList);
        }

        // 解を求める （再帰メソッド）
        private bool Solve(IEnumerable<Piece> pieceList) {
            // 最初のピースを取り出す
            var piece = pieceList.FirstOrDefault();              
            if (piece == null)
                // すべてのペースを使い切った(つまり成功)
                return true;
            // ピースを回転、反転させたものを取り出し試していく。。
            foreach (var curr in piece.AllSeries) {
                // すべての位置を順に取り出す、そこにcurrを置いていく
                foreach (var topleft in _board.AllPoints) { 
                    // 取り出した位置(左上)にピースを置いてみる
                    if (Put(topleft, curr)) {  
                        if (CountEmpty().Any(n => n % 5 != 0)) {
                            // 5で割り切れない空き領域があれば、そこにピースははめ込むことができない。
                            // 枝刈り処理 これ以上試しても仕方が無いので、次を試す。
                            Remove(topleft, curr);
                            continue;
                        }
                        var newlist = pieceList.Where(o => o.Char != curr.Char).ToList();
                        // 置けたら残りのピースで同じことを繰り返す
                        if (Solve(newlist) == true)
                            // 成功したら処理を終える
                            return true;
                        // 状態を戻して、次を試す
                        Remove(topleft, curr);       
                    }
                }
            }
            return false;
        }

        // ピースをBoardから取り除く
        private void Remove(Point topleft, Piece piece) {
            foreach (var pt in piece.Points) {
                var point = topleft.Add(pt);
                _board[point] = ' ';
            }
        }

        // ピースを指定位置に置く
        public bool Put(Point basePlace, Piece piece) {
            List<Point> save = new List<Point>();
            foreach (var pt in piece.Points) {
                var point = basePlace.Add(pt);
                
                if (_board.IsValidPoint(point) &&  _board[point] == ' ') {
                    _board[point] = piece.Char;
                    save.Add(point);
                } else {
                    // やっぱり置けなかったので、元に戻す。
                    foreach (var p in save)
                        _board[p] = ' ';
                    return false;
                }
            }
            return true;
        }

        // プリント
        public void Print() {
            _board.Print();
        }

        // 空いている領域の面積を列挙する。
        private IEnumerable<int> CountEmpty() {
            var bclone = _board.Clone();
            var pts = bclone.AllPoints
                          .Where(pt => bclone[pt] == ' ').ToArray();
            return pts.Select(pt => bclone.CountEmpty(pt))
                      .Where(cnt => cnt > 0);
        }
    }
}

Program.cs

using System;

namespace PentominoApp {
    class Program {
        static void Main(string[] args) {
            Pentomino solver = new Pentomino();
            Console.WriteLine(DateTime.Now);
            solver.Solve(12, 5);
            Console.WriteLine(DateTime.Now);
            solver.Print();
            Console.ReadLine();
        }
    }
}