ナイト(騎士)の最適配置問題とは

チェスのナイト（騎士）を以下の規則に従って配置するパズルです。

すべての空きがどれかのナイトの効き筋になっていること。複数のナイトから効いていてもかまわない。
ナイト同士は互いに効き筋にはない。
なるべく少ない数のナイトで配置する。

この３つの規則を満たすように、ナイトを配置します。
8クイーン問題のナイト(騎士)バージョンといった感じのパズルです。

解き方

この手の他のパズルと同様、バックトラックを使って探索します。

どうやって、探索数を減らすのかが、高速化の決め手になると思いますが、なかなか手ごわい問題です。3つ目の条件「なるべく少ない数のナイトで配置する。」があるので、答えがすぐに見つかるようなコードを書くことができませんでした。

いろいろと考えた結果、チェス盤を4×4の４つのブロックに区切って探索することにしました。

ひとつのブロックには、最大でも４つのKnightを配置すれば条件を満たせるはずです。なぜなら、ひとつのブロックに対し、以下のように配置すれば条件を満たせるからです。

かつ、隅の４つの箇所は、他のブロックに置いたナイトからは届かない場所ですから、一つのブロックで４つのナイトを配置した時に、隅の４つが効き筋でもなく、ナイトも置いていなかったら、条件を満たさないことになります。これで枝刈りを行っています。

なるべく少ない数のナイトを配置するという問題なので、ひとつ解がみつかると、覚えておいた最善解とを比べて、新たな最善解を記憶したら、次の解を見つけにいっています。

最後まで探査すれば、最善解が記憶されているので、その解を表示するようにしています。

これを書いていて思ったのですが、ナイトの数が記憶している解のナイトの数よりも多くなった時点で、探索を終了するようにすれば、もうすこし速くなったかもしれません。どなたか気が向いた方がいたら、チャレンジしてみてください。

C#のコード

Chessboardクラス / Pieceクラス

Chessboardクラスは、当パズルに特化したチェス盤を表すクラスです。BoardBaseクラス(後述)から派生させています。
Pieceクラスは駒クラスです。Footmarkクラスは利き筋を表しています。

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

namespace ArrangementOfKnights {

    public class Piece {
        public static readonly Piece Empty = new Piece { Value = '.' };
        public static readonly Piece Knight = new Piece { Value = 'K' };
        public char Value { get; set; }

        public override string ToString() {
            return Value.ToString();
        }

        public virtual Piece Clone() {
            return new Piece {
                Value = this.Value
            };
        }
    }

    public class Footmark : Piece {
        public int Count { get; set; }

        public Footmark() {
            Value = 'F';
        }

        public override Piece Clone() {
            return new Footmark {
                Count = this.Count,
                Value = this.Value
            };
        }
    }


    public class Chessboard : BoardBase<Piece> {
        // 移動可能な８つの方向
        private int[] _allDestinations;
        // 番兵部分を除いたすべてのインデックス(少しでも高速化するためキャッシュしておく)
        private int[] _allIndexes;

        // コンストラクタ
        public Chessboard()
            : base(8, 8) {
            _allIndexes = GetAllIndexes().ToArray();
            foreach (var p in _allIndexes)
                this[p] = Piece.Empty;
            _allDestinations = new int[] {
                ToDirection(-1, -2),
                ToDirection(+1, -2),
                ToDirection(-2, -1),
                ToDirection(+2, -1),
                ToDirection(-1, +2),
                ToDirection(+1, +2),
                ToDirection(-2, +1),
                ToDirection(+2, +1),
            };
        }

        // コピーコンストラクタ
        public Chessboard(Chessboard board) : base(board) {
            this._allIndexes = board._allIndexes.ToArray();
            this._allDestinations = board._allDestinations.ToArray();
            // ここで、深いコピーをしてしまうが、Empty, Knightは唯一一つのオブジェクトにしたい。
            foreach (var ix in board.GetAllIndexes()) {
                if (this[ix] is Footmark)
                    this[ix] = board[ix].Clone();
            }
        }

        // 指定Blockは正しい状態か。他のブロックからは届かない隅の４つが埋まっていないといけない。
        public bool IsCorrect(int[] block) {
            if (block.Skip(12).All(ix => this[ix] != Piece.Empty))
                return true;
            return false;
        }

        // 騎士の数がオーバーしたか
        public bool IsOver(int[] block) {
            if (block.Count(ix => this[ix] == Piece.Knight) > 4)
                return true;
            return false;
        }

        // 正解にたどり着いたか
        public bool IsFinish() {
            return _allIndexes.All(index => this[index] != Piece.Empty);
        }

        // now位置からの移動可能な場所(index)を返す
        public IEnumerable<int> Destinations(int now) {
            return _allDestinations.Select(n => n + now).Where(n => IsOnBoard(n));
        }

        // 利き筋には、Footmarkを配置する
        public void Put(int place) {
            this[place] = Piece.Knight;
            foreach (var dest in Destinations(place)) {
                var fm = this[dest] as Footmark;
                if (fm == null)
                    this[dest] = new Footmark() { Count = 1 };
                else
                    fm.Count++;
            }
        }

        // 駒(騎士)を取り去る
        public int Clear(int place) {
            int count = 0;
            this[place] = Piece.Empty;
            foreach (var dest in Destinations(place)) {
                var fm = this[dest] as Footmark; // fm が null なら PGミス
                if (fm.Count <= 1) {
                    count++;
                    this[dest] = Piece.Empty;
                } else
                    fm.Count--;
            }
            return count;
        }

        // 騎士が移動可能な場所の数
        public int MovableCount(int place) {
            return Destinations(place).Count(ix => this[ix] == Piece.Empty);
        }

        // ４つのブロックの座標(インデックス）を設定。
        // ここだけが番兵の存在に依存している。かなり力業だが...
        // 4隅(4マス)の座標は、各配列の最後に格納する。
        private static int[] _blockA = new int[] { 28, 29, 40, 41, 50, 51, 52, 53, 62, 63, 64, 65, 26, 27, 38, 39, };
        private static int[] _blockB = new int[] { 30, 31, 42, 43, 54, 55, 56, 57, 66, 67, 68, 69, 32, 33, 44, 45, };
        private static int[] _blockC = new int[] { 74, 75, 76, 77, 86, 87, 88, 89, 100, 101, 112, 113, 98, 99, 110, 111, };
        private static int[] _blockD = new int[] { 78, 79, 80, 81, 90, 91, 92, 93, 102, 103, 114, 115, 104, 105, 116, 117, };

        public int[] BlockA() {
            return _blockA;
        }

        public int[] BlockB() {
            return _blockB;
        }

        public int[] BlockC() {
            return _blockC;
        }

        public int[] BlockD() {
            return _blockD;
        }

        public int[] NextBlock(int[] block) {
            if (block == BlockA())
                return BlockB();
            if (block == BlockB())
                return BlockC();
            if (block == BlockC())
                return BlockD();
            return null;
        }

        public void Print() {
            for (int y = 1; y <= YSize; y++) {
                for (int x = 1; x <= XSize; x++) {
                    Footmark fm = this[x, y] as Footmark;
                    if (fm != null)
                        Console.Write("{0} ", fm.Count);
                    else
                        Console.Write("{0} ", this[x, y].Value);
                }
                Console.WriteLine("");
            }
            Console.WriteLine();
        }
    }
}

Solverクラス

問題を解くクラス。盤面操作の面倒なところはChessbBoardクラスに隠蔽されています。
それでも結構複雑なコードになってますので、コメント付けておきました。

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

namespace ArrangeKnightApp {
    public class Solver {
        public Chessboard Solve(Chessboard board) {
            _Solve(board, 0, 0, board.BlockA());
            return _answer;
        }

        private int _mincount = 64;
        private Chessboard _answer;

        // ４つに区切って探索する。
        // ひとつのブロックには、最大でも４つのKnightを配置すれば条件を満たせるはず。
        private void _Solve(Chessboard board, int level, int nowpos, int[] block) {
            if (board.IsOver(block))
                return;
            if (board.IsCorrect(block)) {
                // 現在のブロックが正しいので、次のブロックを求める
                int[] nextblock = board.NextBlock(block);
                if (nextblock != null) {
                    // 次のブロックの解を求める
                    _Solve(board, level, nowpos, nextblock);
                } else {
                    // すべてのブロックを処理し終わったので、解が見つかったか調べる
                    if (board.IsFinish()) {
                        // Levelの値と置いた騎士の数は一致する。置いた騎士の数が少ないほうがより良い解。
                        if (_mincount > level) {
                            // より良い解が見つかったので、解を覚える。
                            _answer = new Chessboard(board);
                            // _answer.Print();  // デバッグ用 暫定解を表示
                            _mincount = level;
                        }
                    }
                }
                return;
            }

            if (level + 1 >= _mincount)
                //  現在の最良解よりも悪いものなので、この探索は途中で打ち切る
                return;

            // 現在のブロックのそれぞれに対し、騎士が置けるかを調べる
            var list = block.Where(ix => board[ix] == Piece.Empty).ToList();
            foreach (int pos in list) {
                if (Array.IndexOf(block, pos) > Array.IndexOf(block, nowpos)) {
                    // 直前に置いた騎士の位置よりもインデックスが小さいなら既に試してあるので、
                    // インデックスが大きい場合に、新たに騎士をおいて、次の探索に行く。
                    board.Put(pos);
                    _Solve(board, level + 1, pos, block);
                    // pos位置での試しは終わったので、次の探索ができるようにするためクリアする。
                    board.Clear(pos);
                }
            }
        }
    }
}

Programクラス

using System;

namespace ArrangeKnightApp {
    class Program {
        static void Main(string[] args) {
            var board = new Chessboard();
            var solver = new Solver();
            var answer = solver.Solve(board);
            answer.Print();
        }
    }
}

実行結果

Kが騎士を配置した場所、数値はその場所へ移動できる騎士の数を表しています。

K 1 K 2 1 1 1 1
1 1 3 1 1 K 1 1
K 2 1 2 K K 1 1
K 1 3 2 2 1 3 1
1 3 1 2 2 3 1 K
1 1 K K 2 1 2 K
1 1 K 1 1 3 1 1
1 1 1 1 2 K 1 K

さすがにすべてを1にする配置方法はないみたいです。
キャラクタベースなので、どこに騎士を配置したかが判りにくいので、数字を'.'に手で置き換えてみました。

K . K . . . . .
. . . . . K . . 
K . . . K K . .
K . . . . . . .
. . . . . . . K
. . K K . . . K
. . K . . . . .
. . . . . K . K

対象性のある綺麗な形でした。

BoardBaseクラス

このBoardBaseクラスは、「騎士巡回問題」などで利用したものと同じものです。

前述のBoardクラスの基底クラスです。X × Y の盤面を表し、基本的な操作を定義しています。これは似たようなパズルでも再利用できるような汎用的な機能に絞っています。このBoardBaseクラスは、コンソールアプリに依存しない作りにしています。UWP、WinFormsでもそのまま使えると思います。

このBoardBaseを継承して、当パズル専用のBoardクラスを定義します。

内部では1次元配列を使っていますが、インデクサを定義して、1次元配列、2次元配列としても扱えるようにしています。
ただし、すべてのメソッドで１次元対応と２次元対応のものを用意するのは面倒なので、どちらか一方にしています。まあこれは好み以外の何物でもありません。

１次元のインデックスによるアクセスができるようにしている理由は、一重ループで処理が書けるので、コードが簡潔になるからです。LINQのコードも書きやすくなります。

2次元配列として見た場合の、X座標、Y座標は、0 からではなく、1から始まります。
つまり、board[1,1] は、いちばん左上を示し、8×8の盤ならば、board[8,8]が右下を示すことになります。

なお、盤の周りには番兵用の領域を用意しています。これにより範囲外かどうかの判断を簡単に出来るようにしています。ナイト(騎士)の動きに対応できるよう、番兵は二重にしています。¹

派生クラスや派生クラスを利用するクラスが、できるだけこの番兵の存在に依存しないように、ToDirectionという関数を定義し、X方向、Y方向のペアで表す移動方向(ベクトル)をインデックスで表す方向に変換するようにしています。

上の図は 4×4の盤を表しています。グレー部分が番兵が置いてある盤の周囲で、水色部分が実際の盤です。
盤面上の数値は、１次元配列のインデックスを表しています。

BoardBaseクラスはジェネリッククラスにしていて、そのパラメータの型は、盤面上に置けるクラスの型です。

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

namespace Puzzle {
    // 汎用の盤面クラス
    // Tは、盤面に置けるオブジェクトの型。参照型でnew()ができれば何でも良い。
    public abstract class BoardBase<T> where T : class, new() {
        private T[] _pieces;

        // 盤の行数（縦方向）
        public int YSize { get; private set; }

        // 盤のカラム数（横方向）
        public int XSize { get; private set; }

        // 番兵も含めた幅のサイズ
        private int OuterWidth => XSize + 4;

        private int OuterHeight => XSize + 4;

        // コンストラクタ
        public BoardBase(int xsize, int ysize) {
            this.YSize = ysize;
            this.XSize = xsize;

            _pieces = new T[OuterWidth * OuterHeight];

            // 盤データの初期化 - 盤の周りはnull(番兵)をセットしておく
            ClearAll();
        }

        // コピー用コンストラクタ
        public BoardBase(BoardBase<T> board) {
            XSize = board.XSize;
            YSize = board.YSize;
            this._pieces = board._pieces.ToArray();
        }

        // 番兵も含めたボード配列の長さ
        public int BoardLength => _pieces.Length;


        // インデクサ (x,y)の位置の要素へアクセスする
        public T this[int index] {
            get { return _pieces[index]; }
            set { _pieces[index] = value; }
        }

        // インデクサ (x,y)の位置の要素へアクセスする
        public T this[int x, int y] {
            get { return this[ToIndex(x, y)]; }
            set { this[ToIndex(x, y)] = value; }
        }

        // Location から _coinのIndexを求める
        public int ToIndex(int x, int y) => x + 1 + (y + 1) * OuterWidth;

        // IndexからLocationを求める (ToIndexの逆演算)
        public (int, int) ToLocation(int index) 
            => (index % OuterWidth - 1, index / OuterWidth - 1);


        public int ToDirection(int dx, int dy) => dy * OuterWidth + dx;

        // 本来のボード上の位置(index)かどうかを調べる
        public virtual bool IsOnBoard(int index) => this[index] != null;


        // 全てのPieceをクリアする
        public virtual void ClearAll() {
            for (int index = 0; index < BoardLength; index++)
                this[index] = null;       // 番兵
            foreach (var index in GetAllIndexes())
                this[index] = new T();　　// 初期値
        }

        // 盤上のすべての位置(index)を列挙する
        public virtual IEnumerable<int> GetAllIndexes() {
            for (int y = 1; y <= this.YSize; y++) {
                for (int x = 1; x <= this.XSize; x++) {
                    yield return ToIndex(x, y);
                }
            }
        }

        // (x,y)からdirection方向の位置を列挙する　(x,y)含む
        public virtual IEnumerable<int> EnumerateIndexes(int x, int y, int direction) {
            for (int index = ToIndex(x, y); IsOnBoard(index); index += direction)
                yield return index;
        }

        // (x,y)から右(水平)の位置を列挙する　(x,y)含む
        public virtual IEnumerable<int> Horizontal(int x, int y)
            => EnumerateIndexes(x, y, ToDirection(1, 0));

        // (x,y)から下(垂直)の位置を列挙する　(x,y)含む
        public virtual IEnumerable<int> Virtical(int x, int y)
            => EnumerateIndexes(x, y, ToDirection(0, 1));

        // (x,y)から右斜め下(45度)の位置を列挙する　(x,y)含む
        public virtual IEnumerable<int> SlantR(int x, int y)
            => EnumerateIndexes(x, y, ToDirection(1, 1));

        // (x,y)から左斜め下(45度)の位置を列挙する　(x,y)含む
        public virtual IEnumerable<int> SlantL(int x, int y)
            => EnumerateIndexes(x, y, ToDirection(-1, 1));

    }
}

この記事は、Gushwell's C# Programming Pageで公開したものを大幅に加筆・修正したものです。

当初は一重の番兵でしたが、albireoさんのコメント（アドバイス）により、二重の番兵に変更しました。 ↩