８クィーン・ゲームとは

８×８のチェス盤に２人で交互にクィーンを置いていき、自分の手番のときに置き場所が無いほうが負けというゲームです。すでに置かれているクィーン（自分が置いたものも含め）の利き筋に新しいクィーンを置くことはできません。
いわゆる８クィーンパズルのゲーム版というところです。

クィーンは、縦横斜めの何処へでも移動できます。将棋の飛車と角を合わせた動きになります。

出典である「ナノピコ教室¹」では、先手必勝かどうかを調べるという問題でしたが、ここでは、実際に人との対戦が出来るようにしてみました。

ちなみにあなたが後手の場合は、絶対に勝てません。先手でもちゃんと考えないとなかなか勝てません。

.NET Coreのコンソールアプリケーションとして作成していますので、MacでもWindowsでもそのまま動くはずです。

どうやって解くか

実際のこの手のゲームプログラムでは、序盤戦は定石を用いたルーチンになっていると思われますが、８クイーンゲームでは、探索手の数が少ないので、愚直に全探索をしています。枝刈りなどは行っていません。
最初の一手目はすこし時間がかかりますが、それ以降は、すぐに探索が終了します。

プログラムを単純化するために、黒石(×)をコンピュータ、白石(○)を人間に固定していますが、実際の探索をするSearchメソッドは、石の色に関係なく探索が出来るようにしてあります。

Searchメソッドでは、

自分の石をある位置に置いてみる
相手の石で Searchを呼び出す（再帰処理）つまり「ここにおいたら、次に相手はどう打つかな」を考える
結果が自分の石の勝ちならば、ここで終了（戻る）
自分の石が勝てなかったら、1に戻り別の場所を試してみる
どこに置いても勝てなかったら、相手の勝ちとして戻る。

という動きになっていて、2手先、３手先を読むのではなく、勝敗がきまるまで、ずーっと先読みを続けています。
思考型の対戦ゲームとしての基本構造を示せるという点で、８クィーンゲームはなかなか良い題材だと思います。

ソースコードにはコメントを付加していますので、詳しくはソースコードを見てください。

実行例

以下に、実行例を示します。

これは、ゲームの途中の状態。人間のプレイヤーは、2桁の数字（行と列）を入力しクィーンをの置く場所を指定します。

盤面の _ は、利き筋になってもうクィーンが置けない場所を示しています。.は、クィーンを置ける場所を示しています。

次のは、ゲームが終わった状態。僕は先手(o)でしたが、負けてしまいました(T T)

主要なクラス

Controllerクラス

このゲームを制御する実質的なメインクラスです。1回の対戦だけを扱います。基本、表示はこのクラスが受け持っています、

Gameクラス

1回の対戦を扱うクラスです。2つのプレイヤーを交互に呼び出し、ゲームを進めます。

HumanPlayer クラス

人間のプレイヤーを表すクラスです。

ComputerPlayer クラス

コンピュータープレイヤーを表すクラスです。この中に思考ルーチンが組み込まれています。

Boardクラス

盤面を表すクラスです。
このBoardクラスは他のプログラムでも利用しているBoardBase<T>から派生させていますので、すこしオーバースペックかもしれません。

`BoardBase<T>`を利用している他のプログラム

などなど。

`IOberver<T>`, `IOvervable<T>`

UIとロジックを分離するために、IOberver<T>, IOvervable<T>を実装しています。
GameクラスがIObservable<Board>を実装し、盤面の変化を購読者に通知しています。
購読者クラスは、Controllerクラスで、IObserver<Board>を実装しています。

C#のコード

Program.cs

using System;

namespace EightQueensGame
{
    class Program
    {
        static void Main(string[] args)
        {
            var controller = new Controller();
            while (true)
            {
                controller.Run();
                if (!Controller.Confirm("Try Again?"))
                    break;
            }
        }
    }
}

Controller.cs

C#のコードは、GitHubでも公開しています。

using System;
namespace EightQueensGame
{
    class Controller : IObserver<Board>
    {
        private IPlayer _player1;
        private IPlayer _player2;
        private IPlayer _winner;
        private Board _board;

        // 試合の開始
        public void Run()
        {
            DecideFirstPlayer();
            _board = new Board();
            var game = new Game(_player1, _player2, _board);
            // 購読者は自分自身
            game.Subscribe(this);
            _winner = game.Start();
        }

        // 先手を決める
        private void DecideFirstPlayer()
        {
            var b = Confirm("Are you first?");
            if (b)
            {
                _player1 = new HumanPlayer();
                _player2 = new ComputerPlayer();
            }
            else
            {
                _player1 = new ComputerPlayer();
                _player2 = new HumanPlayer();
            }
        }

        private IPlayer GetHumanPlayer() =>
             _player1 is HumanPlayer ? _player1 : _player2;

        // 盤面を表示
        private void Print(Board board)
        {
            Console.Clear();
            Console.WriteLine("  1 2 3 4 5 6 7 8 ");
            Console.WriteLine("  ----------------");
            for (int y = 1; y <= 8; y++)
            {
                Console.Write($"{y}|");
                for (int x = 1; x <= 8; x++)
                {
                    var val = board[x, y].Value;
                    if (val == '_')
                        val = '.';
                    Console.Write(val + " ");
                }
                Console.WriteLine();
            }
        }

        // 終了した 
        public void OnCompleted()
        {
            var winner = _player1.IsWin ? _player1 : _player2;
            //var human = GetHumanPlayer();
            // このゲームには引き分けはない
            if (_winner is HumanPlayer)
                Console.WriteLine("You Win");
            else
                Console.WriteLine("You Lose");
        }

        // エラー発生
        public void OnError(Exception error)
        {
            Console.WriteLine(error.Message);
        }

        // 状況変化
        public void OnNext(Board value)
        {
            Print(value);
        }

        // (y/n)の確認
        public static bool Confirm(string message)
        {
            Console.Write(message);
            var left = Console.CursorLeft;
            var top = Console.CursorTop;
            try
            {
                while (true)
                {
                    var key = Console.ReadKey();
                    if (key.KeyChar == 'y')
                        return true;
                    if (key.KeyChar == 'n')
                        return false;
                    Console.CursorLeft = left;
                    Console.CursorTop = top;
                }
            }
            finally
            {
                Console.WriteLine();
            }
        }
    }
}

Game.cs

using System;
using System.Collections.Generic;

namespace EightQueensGame
{
    public class Game : IObservable<Board>
    {
        private Board _board;
        private IPlayer _player1;
        private IPlayer _player2;

        // コンストラクタ
        public Game(IPlayer player1, IPlayer player2, Board board)
        {
            _player1 = player1;
            _player2 = player2;
            _board = board;
        }

        // Game開始
        public IPlayer Start()
        {
            IPlayer player = _player1;
            IPlayer winner = null;
            Publish(_board);
            while (true)
            {
                var index = player.GetNextHand(_board);
                if (index < 0)
                {
                    winner = Turn(player);
                    break;
                }
                _board.PutPiece(index, player.MyPiece);
                Publish(_board);
                player = Turn(player);
            }
            winner.IsWin = true;
            Complete();
            return winner;


        }

        // 次のプレイヤー
        private IPlayer Turn(IPlayer player)
        {
            return player == _player1 ? _player2 : _player1;
        }

        private List<IObserver<Board>> _observers = new List<IObserver<Board>>();

        // 終了を通知する
        private void Complete()
        {
            foreach (var observer in _observers)
            {
                observer.OnCompleted();
            }
        }

        // 状況変化を知らせるために購読者に通知する
        private void Publish(Board board)
        {
            foreach (var observer in _observers)
            {
                observer.OnNext(board);
            }
        }

        // 購読を申し込む -  observerが通知を受け取れるようになる
        public IDisposable Subscribe(IObserver<Board> observer)
        {
            _observers.Add(observer);
            return observer as IDisposable;
        }
    }
}

IPlayer.cs

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

namespace EightQueensGame
{
    public interface IPlayer
    {
        int GetNextHand(Board board);

        Piece MyPiece { get; }

        bool IsWin { get; set;  }
    }
}

HumanPlayer.cs

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

namespace EightQueensGame
{
    class HumanPlayer : IPlayer
    {
        public Piece MyPiece => Piece.White;

        public bool IsWin { get; set;  }

        public int GetNextHand(Board board)
        {
            if (board.CanPutPlaces().Count() == 0)
            {
                return -1;
            }
            while (true)
            {
                var line = Console.ReadLine();
                if (line.Length != 2)
                    continue;
                var y = line[0] - '0';
                var x = line[1] - '0';
                if (1 <= x && x <= 8 && 1 <= y && y <= 8)
                {
                    var index = board.ToIndex(x, y);
                    if (board.CanPut(index))
                    {
                        return index;
                    }
                }
            }
        }
    }
}

ComputerPlayer.cs

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

namespace EightQueensGame
{
    // Computerの思考を担当
    public class ComputerPlayer : IPlayer
    {
        public Piece MyPiece => Piece.Black;

        public bool IsWin { get; set; }


        private Record _record;

        // Solveで得られた最善手を返す。
        public int GetNextHand(Board board)
        {
            Solve(board);
            if (_record.Children.Count > 0)
            {
                var rec = _record.Children[0];
                return rec.Index;
            }
            else
            {
                // 勝つ手が無い。
                // 最初に見つかった置ける場所に石を置く。（かなり手抜き）
                var places = board.CanPutPlaces();
                if (places.Count() > 0)
                    return places.First();
                return -1;
            }
        }

        // 最後まで探索し、最善手を見つける
        public Piece Solve(Board board)
        {
            _record = new Record();
            _record.Root = _record;
            Piece win;
            // すべての空いている位置に対して試してみる。
            foreach (var index in board.GetVacantIndexes())
            {
                // int loc = this._board.ToLocation(index);
                _record = new Record();
                _record.Root = _record;
                // 現在のボードの状態をコピーし、コピーしたものを利用する
                var workboard = board.Clone();
                int p = index;
                if (workboard.CanPut(p))
                {
                    // 石を置いてみる
                    Record nr = Put(workboard, p, MyPiece, _record);
                    // 相手（白）の番の先読み
                    win = Search(workboard, Opponent(MyPiece), nr);
                    if (win == MyPiece)
                    {
                        // もし、Computerが勝ちならば、処理をやめて戻る。
                        return win;
                    }
                }
            }
            return Opponent(MyPiece);
        }

        // 再帰処理をし、探索する。
        // 相手がどんな手を打っても勝てる位置を探す。
        public Piece Search(Board board, Piece piece, Record rec)
        {
            // すべての置ける位置に対して処理をする
            foreach (var place in board.CanPutPlaces())
            {
                Board temp = board.Clone();
                // 石を置く。
                Record nr = Put(temp, place, piece, rec);
                // 相手の番（先読み）
                Piece win = Search(temp, Opponent(piece), nr);
                if (win == piece)
                {
                    // pieceが勝ったら戻る 
                    //（pieceの相手がどんな手を打っても pieceの勝ち)
                    // 今までの手を捨て去って、新しい手をrecに加える
                    rec.Clear();
                    rec.Add(nr);
                    return piece;
                }
                // この位置に置くと相手が勝ってしまうので、次の位置を調べる。
                // ちなみにこのゲームには引き分けはない。
            }
            // どこにも打つ場所が無い。
            // あるいは、どこに置いても勝てない。
            // つまり相手の勝ち
            return Opponent(piece);
        }

        // pieceをplaceの位置に置き、置いた石とその位置を記録する
        private Record Put(Board board, int place, Piece piece, Record rec)
        {
            // board[place] = piece;
            board.PutPiece(place, piece);
            Record nr = new Record(place);
            rec.Add(nr);
            return nr;
        }

        // 次の手番の相手の石を返す
        private Piece Opponent(Piece piece)
        {
            return piece == Piece.Black ? Piece.White : Piece.Black;
        }

        // デバッグ用
        public string Print()
        {
            _record.Root.result = "";
            _record.Print(0);
            return _record.Root.result;
        }
    }
}

Record.cs

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

namespace EightQueensGame
{
    public class Record
    {
        public Record Root;
        public int Index { get; private set; }
        public Piece Piece { get; set; }

        // Childrenには可能性のある相手の手が複数格納される
        public List<Record> Children { get; private set; }

        public Record(int loc)
        {
            Index = loc;
            Children = new List<Record>();
        }

        public Record()
        {
            Children = new List<Record>();
        }

        public void Add(Record rec)
        {
            Children.Add(rec);
            rec.Root = this.Root;
        }

        public void Clear()
        {
            Children.Clear();
        }

        public string result = "";

        // デバッグ用
        public void Print(int indent)
        {
            if (Piece == Piece.Black || Piece == Piece.White)
            {
                string s = string.Format("{0} {1}\n", new string(' ', indent), Index.ToString());
                this.Root.result += s;
            }
            foreach (var x in Children)
                x.Print(indent + 1);
        }
    }
}

Board.cs

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

namespace EightQueensGame
{
    // 石を表すクラス
    public class Piece
    {
        public static Piece White = new Piece { Value = 'O' };
        public static Piece Black = new Piece { Value = 'X' };
        public static Piece Empty = new Piece { Value = '.' };
        public static Piece Forbid = new Piece { Value = '-' };

        public char Value { get; set; }
    }

    // 盤面クラス
    public class Board : BoardBase<Piece>
    {

        // 少しでも速くするためにキャッシュしておく
        private IEnumerable<int> AllIndexes = null;

        public Board()
            : base(8, 8)
        {
            AllIndexes = GetAllIndexes();
            foreach (var ix in AllIndexes)
                this[ix] = Piece.Empty;
        }

        // オブジェクト複製用
        public Board(Board board)
            : base(board)
        {
            AllIndexes = GetAllIndexes();
        }


        public Board Clone()
        {
            return new Board(this);
        }

        // 石を置く
        public void PutPiece(int index, Piece piece)
        {
            this[index] = piece;
            if (piece == Piece.Forbid || piece == Piece.Empty)
                return;
            // Queenが動けるところにはマークをつける
            foreach (var i in Courses(index))
                if (this[i] == Piece.Empty)
                    this[i] = Piece.Forbid;
        }

        // 空いている位置を列挙する
        internal IEnumerable<int> GetVacantIndexes()
        {
            return AllIndexes.Where(x => this[x] == Piece.Empty);
        }

        // 置けるか？
        public bool CanPut(int place)
        {
            return this[place] == Piece.Empty;
        }

        // 置ける位置だけを列挙
        public IEnumerable<int> CanPutPlaces()
        {
            return AllIndexes.Where(ix => CanPut(ix));
        }

        // nowを通る 縦横斜めのすべての位置を列挙
        public IEnumerable<int> Courses(int now)
        {
            return Virtical(now)
                .Concat(Horizontal(now))
                .Concat(SlantL(now))
                .Concat(SlantR(now)).Distinct();
        }

        private int Up => ToDirection(0, -1);
        private int Down => ToDirection(0, 1);
        private int Left => ToDirection(-1, 0);
        private int Right => ToDirection(1, 0);
        private int UpperLeft => ToDirection(-1, -1);
        private int UpperRight => ToDirection(1, -1);
        private int LowerLeft => ToDirection(1, -1);
        private int LowerRight => ToDirection(1, 1);

        // 縦の位置を列挙
        public IEnumerable<int> Virtical(int now)
        {
            var (x, y) = ToLocation(now);
            return this.EnumerateIndexes(x, y, Up)
                       .Skip(1)
                       .Concat(this.EnumerateIndexes(x, y, Down));
        }

        // 横の位置を列挙
        public IEnumerable<int> Horizontal(int now)
        {
            var (x, y) = ToLocation(now);
            return this.EnumerateIndexes(x, y, Left)
                       .Skip(1)
                       .Concat(this.EnumerateIndexes(x, y, Right));
        }

        // 右上がり斜線
        public IEnumerable<int> SlantR(int now)
        {
            var (x, y) = ToLocation(now);
            return this.EnumerateIndexes(x, y, UpperRight)
                       .Skip(1)
                       .Concat(this.EnumerateIndexes(x, y, LowerLeft));
        }

        // 左上がりの斜線
        public IEnumerable<int> SlantL(int now)
        {
            var (x, y) = ToLocation(now);
            return this.EnumerateIndexes(x, y, UpperLeft)
                       .Skip(1)
                       .Concat(this.EnumerateIndexes(x, y, LowerRight));
        }

    }
}

BpardBase.cs

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

namespace EightQueensGame
{
    // 汎用の盤面クラス
    // 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
        {
            get { return _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)
        {
            //if (0 <= index && index < BoardLength)
            return this[index] != null;
            //return false;
        }

        // 全ての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));

    }
}

『ナノピコ教室―プログラミング問題集』共立出版 (1990/03) ↩