LoginSignup
3
2

More than 3 years have passed since last update.

@gushwell(出井 秀行)

ペントミノをC#で解く

Last updated at Posted at 2019-09-30

ペントミノとは

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

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

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

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

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

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

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

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

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

T字型だと

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

I字型だと
cs
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インスタンスを返すようにする方法もありますね。

実行例

スクリーンショット 2019-09-06 20.06.19.png

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

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

スクリーンショット 2019-09-06 20.21.15.png

ソースコード

では、すべてのソースコードを掲載します。(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();
        }
    }
}
3
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
2