import java.io.*;
import java.util.*;

/**
* 盤のマス等、白、黒、その他を表す
*/
enum HexPawnDefs
{
    None,       // 盤外、未定を表す
    Black,      // 黒を表す
    White,      // 白を表す
    Empty       // 空き
}


/**
* 盤のマスを示すクラス
*/
class HpPoint
{
    public int file;    // 左を0とした横方向
    public int rank;    // 下を0とした縦方向

    /**
    * コンストラクタ
    */
    public HpPoint()
    {
        file = -1;
        rank = -1;
    }

    /**
    * コンストラクタ
    *
    * @param f 横方向位置
    * @param r：縦方向位置
    */
    public HpPoint(int f, int r)
    {
        file = f;
        rank = r;
    }

    /**
    * 左右反対のHpPointを取得する
    *
    * @return 左右反対のHpPoint
    */
    public HpPoint Mirror()
    {
        HpPoint mirror = new HpPoint(this.file, this.rank);

        if (mirror.file == 0)
            mirror.file = 2;
        else if (mirror.file == 2)
            mirror.file = 0;

        return mirror;
    }

    /**
    * 文字列にする
    *
    * @param pText 文字列へのポインタ
    */
    public String ToString()
    {
        String s = "";

        s += (char)('a' + this.file);   // 左から a,b,c
        s += (char)('1' + this.rank);   // 下から 1,2,3

        return s;
    }
}

/**
* 盤面を表すクラス
*/
class HpBoard
{
    protected static int BOARD_SIZE = 3;        // 盤の大きさ

    protected HexPawnDefs[][] Squares = new HexPawnDefs[BOARD_SIZE][BOARD_SIZE];    // 盤のマス

    /**
    * コンストラクタ
    */
    public HpBoard()
    {
        // 盤の初期状態を作成する
        for (int file = 0; file < BOARD_SIZE; file++)
        {
            SetSquare(new HpPoint(file, 2), HexPawnDefs.Black); // 黒のポーン
            SetSquare(new HpPoint(file, 1), HexPawnDefs.Empty); // 空き
            SetSquare(new HpPoint(file, 0), HexPawnDefs.White); // 白のポーン
        }
    }

    /**
    * すべてのマスの位置を取得する
    *
    * @return HpPointの配列
    */
    public static HpPoint[] GetAllPoints()
    {
        ArrayList<HpPoint> list = new ArrayList<HpPoint>();

        for (int rank = 0; rank < BOARD_SIZE; rank++)
        {
            for (int file = 0; file < BOARD_SIZE; file++)
                list.add(new HpPoint(file, rank));
        }

        return list.toArray(new HpPoint[0]);
    }

    /**
    * 指定されたマスの状態を取得する
    *
    * @param pt マスの位置を表すHpPoint
    * @return マスの状態
    */
    public HexPawnDefs GetSquare(HpPoint pt)
    {
        return GetSquare(pt.file, pt.rank);
    }

    /**
    * 指定されたマスの状態を取得する
    *
    * @param file 横方向の位置
    * @param rank 縦方向の位置
    * @return マスの状態
    */
    public HexPawnDefs GetSquare(int file, int rank)
    {
        if (0 <= file && file < BOARD_SIZE
            && 0 <= rank && rank < BOARD_SIZE)
        {
            return Squares[file][rank];
        }
        else
        {
            return HexPawnDefs.None;
        }
    }

    /**
    * 指定されたマスの状態を設定する
    *
    * @param pt マスの位置を表すHpPoint
    * @param pawn マスの状態
    */
    public void SetSquare(HpPoint pt, HexPawnDefs pawn)
    {
        SetSquare(pt.file, pt.rank, pawn);
    }

    /**
    * 指定されたマスの状態を設定する
    *
    * @param file 横方向の位置
    * @param rank 縦方向の位置
    * @param pawn マスの状態
    */
    public void SetSquare(int file, int rank, HexPawnDefs pawn)
    {
        if (0 <= file && file < BOARD_SIZE
            && 0 <= rank && rank < BOARD_SIZE)
        {
            Squares[file][rank] = pawn;
        }
    }

    /**
    * 盤の状態を表示する
    */
    public void Show()
    {
        System.out.println("");

        for (int rank = BOARD_SIZE - 1; rank >= 0; rank--)
        {
            System.out.print("\n   +---+---+---+");
            System.out.print("\n " + (rank + 1) + " |");

            for (int file = 0; file < BOARD_SIZE; file++)
            {
                if (GetSquare(new HpPoint(file, rank)) == HexPawnDefs.Black)
                    System.out.print(" ○|");
                else if (GetSquare(new HpPoint(file, rank)) == HexPawnDefs.White)
                    System.out.print(" ●|");
                else if ((rank % 2) == (file % 2))
                    System.out.print(":::|");
                else
                    System.out.print("   |");
            }

            if (rank == 2)
                System.out.print("      7  8  9");
            else if (rank == 1)
                System.out.print("      4  5  6");
            else if (rank == 0)
                System.out.print("      1  2  3");
        }

        System.out.print("\n   +---+---+---+");
        System.out.print("\n     a   b   c\n");
    }

    /**
    * 指定された位置のポーンが動けるかどうか
    *
    * @param pt 調べるマス
    * @return true:動ける、false:動けない
    */
    public boolean IsMoveablePawn(HpPoint pt)
    {
        int dir;            // 進む方向
        HexPawnDefs opp;    // 対戦相手の駒

        if (GetSquare(pt) == HexPawnDefs.White)
        {
            dir = 1;
            opp = HexPawnDefs.Black;
        }
        else if (GetSquare(pt) == HexPawnDefs.Black)
        {
            dir = -1;
            opp = HexPawnDefs.White;
        }
        else
        {
            return false;
        }

        if (GetSquare(pt.file, pt.rank + dir) == HexPawnDefs.Empty)
            return true;
        else if (GetSquare(pt.file - 1, pt.rank + dir) == opp)
            return true;
        else if (GetSquare(pt.file + 1, pt.rank + dir) == opp)
            return true;
        else
            return false;
    }

    /**
    * 勝敗を確認する
    *
    * @param next 次が白番か、黒番か
    * @return 勝った方の色、または、未定
    */
    public HexPawnDefs CheckFinish(HexPawnDefs next)
    {
        // ３列目に駒があるか /////////////////////////
        for (int file = 0; file < BOARD_SIZE; file++)
        {
            if (GetSquare(file, BOARD_SIZE - 1) == HexPawnDefs.White)
                return HexPawnDefs.White;
            else if (GetSquare(file, 0) == HexPawnDefs.Black)
                return HexPawnDefs.Black;
        }

        // 動ける駒の数 ///////////////////////////////
        HpPoint[] all = HpBoard.GetAllPoints();
        int cntWhite = 0;
        int cntBlack = 0;

        for( HpPoint pt : all )
        {
            if (IsMoveablePawn(pt))
            {
                if (HexPawnDefs.White == GetSquare(pt))
                    cntWhite++;
                else if (HexPawnDefs.Black == GetSquare(pt))
                    cntBlack++;
            }
        }

        if (next == HexPawnDefs.White && cntWhite == 0)
            return HexPawnDefs.Black;   // 次が白番で動かせる駒が無い
        else if (next == HexPawnDefs.Black && cntBlack == 0)
            return HexPawnDefs.White;   // 次が黒番で動かせる駒が無い

        return HexPawnDefs.Empty;   // 勝敗未定
    }
};

/**
* 盤の状態と駒の移動を表すクラス
*/
class HpBoardMove extends HpBoard
{
    protected HpPoint From = null;  // 駒の移動元
    protected HpPoint To = null;    // 駒の移動先

    /**
    * コンストラクタ
    */
    public HpBoardMove()
    {
    }

    /**
    * コンストラクタ（コピー）
    *
    * @param bdmove コピー元
    */
    public HpBoardMove(HpBoardMove bdmove)
    {
        HpPoint[] all = HpBoard.GetAllPoints();

        for (HpPoint pt : all)
            SetSquare(pt, bdmove.GetSquare(pt));

        From = bdmove.From;
        To = bdmove.To;
    }

    /**
    * 移動を設定する
    *
    * @param from 移動元
    * @param to 移動先
    */
    public void SetMove(HpPoint from, HpPoint to)
    {
        From = from;
        To = to;
    }

    /**
    * 駒の移動が有効であるかどうかを調べる
    *
    * @return true:有効、false:無効
    */
    public boolean IsValidMove()
    {
        int df = To.file - From.file;
        int dr = To.rank - From.rank;

        if (GetSquare(From) == HexPawnDefs.White)
        {
            if (GetSquare(To) == HexPawnDefs.Empty && df == 0 && dr == 1)
                return true;
            else if (GetSquare(To) == HexPawnDefs.Black && (df == 1 || df == -1) && dr == 1)
                return true;
        }
        else if (GetSquare(From) == HexPawnDefs.Black)
        {
            if (GetSquare(To) == HexPawnDefs.Empty && df == 0 && dr == -1)
                return true;
            else if (GetSquare(To) == HexPawnDefs.White && (df == 1 || df == -1) && dr == -1)
                return true;
        }

        return false;
    }

    /**
    * 同じかどうか比較する
    *
    * @param bdmove 比較先
    * @return true:同じ
    */
    public boolean TestEqual(HpBoardMove bdmove)
    {
        HpPoint[] all = HpBoard.GetAllPoints();

        for (HpPoint pt : all)
        {
            if (this.GetSquare(pt) != bdmove.GetSquare(pt))
                return false;
        }

        if (this.From.file != bdmove.From.file || this.From.rank != bdmove.From.rank
            || this.To.file != bdmove.To.file || this.To.rank != bdmove.To.rank)
            return false;

        return true;
    }

    /**
    * 駒を移動する
    */
    public void MovePawn()
    {
        SetSquare(To, GetSquare(From));
        SetSquare(From, HexPawnDefs.Empty);
    }

    /**
    * 左右反対の状態を作成する
    *
    * @return 左右反対のHpBoardMove
    */
    public HpBoardMove MakeMirror()
    {
        HpBoardMove mirror = new HpBoardMove();

        mirror.SetMove(From.Mirror(), To.Mirror());

        HpPoint[] all = HpBoard.GetAllPoints();

        for (HpPoint pt : all)
            mirror.SetSquare(pt, GetSquare(pt.Mirror()));

        return mirror;
    }
};


/**
* ゲームを実現するクラス
*/
class HexPawn
{
    private ArrayList<HpBoardMove> DefeatList = new ArrayList<HpBoardMove>(); // 負けの状態リスト
    private Random  RandObj = new Random();     // 乱数オブジェクト

    private HexPawnDefs PlayerColor = HexPawnDefs.White;    // プレイヤーの色
    private HexPawnDefs MatchBoxColor = HexPawnDefs.Black;  // マッチ箱の色

    /**
    * 負けの状態リストに存在するかどうか
    *
    * @param bdmove 盤の状態と駒の移動
    * @return true:存在する
    */
    public boolean ExistDefeatList(HpBoardMove bdmove)
    {
        HpBoardMove mirror = bdmove.MakeMirror();

        for (HpBoardMove defeat : DefeatList)
        {
            if (defeat.TestEqual(bdmove))
                return true;

            if (defeat.TestEqual(mirror))
                return true;
        }

        return false;
    }

    /**
    * マッチ箱の番
    *
    * @param bdmove 現在の盤の状態
    * @return true 打った false リザイン
    */
    public boolean MatchBoxTurn(HpBoardMove bdmove)
    {
        // すべてのマスの位置を取得する
        HpPoint[] allsq = HpBoard.GetAllPoints();

        // ランダムに打つよう、配列の順番を変更する
        for (int i = 0; i < 20; i++)
        {
            // 任意の２つのマスの配列内の順番を入れ替える
            int p = RandObj.nextInt(allsq.length);
            int q = RandObj.nextInt(allsq.length);

            if (p != q)
            {
                HpPoint t = allsq[p];
                allsq[p] = allsq[q];
                allsq[q] = t;
            }
        }

        // 有効な手を探索する
        for (HpPoint from : allsq)
        {
            if (bdmove.GetSquare(from) != MatchBoxColor)
                continue;   // 手番の駒が無ければ次へ

            for (HpPoint to : allsq)
            {
                bdmove.SetMove(from, to);

                // 有効な手であり、負けの手に含まれていなければOK!
                if (bdmove.IsValidMove() && !ExistDefeatList(bdmove))
                {
                    System.out.print("\nマッチ箱： " + from.ToString() + " を " + to.ToString() + " へ");
                    return true;
                }
            }
        }

        System.out.print("\nリザインします。");

        return false;   // リザイン
    }

    /**
    * キーボードから入力し、駒の位置に変換する
    *
    * @param strGuide 入力ガイド文字列
    * @return 駒の位置
    */
    HpPoint InputSquarePoint(String strGuide) throws IOException
    {
        BufferedReader br = new BufferedReader(
                                new InputStreamReader( System.in ) );

        for (; ; )
        {
            System.out.print(strGuide);    // 入力ガイドの表示

            String line = br.readLine();

            if( line.length() == 0 )
                continue;

            switch ( line.charAt(0) )
            {
                case '7':
                    return new HpPoint(0, 2);
                case '8':
                    return new HpPoint(1, 2);
                case '9':
                    return new HpPoint(2, 2);
                case '4':
                    return new HpPoint(0, 1);
                case '5':
                    return new HpPoint(1, 1);
                case '6':
                    return new HpPoint(2, 1);
                case '1':
                    return new HpPoint(0, 0);
                case '2':
                    return new HpPoint(1, 0);
                case '3':
                    return new HpPoint(2, 0);
            }
        }
    }

    /**
    * プレイヤーの番
    *
    * @param bdmove 現在の盤の状態
    */
    public void PlayerTurn(HpBoardMove bdmove) throws IOException
    {
        HpPoint from, to;

        for (; ; )
        {
            from = InputSquarePoint("\n駒を選んでください(1～9)：");

            if (PlayerColor == bdmove.GetSquare(from) && bdmove.IsMoveablePawn(from))
                break;
            else
                System.out.print("\n動かせる駒がありません");
        }

        for (; ; )
        {
            to = InputSquarePoint("\nどこに動かしますか？(1～9)：");

            bdmove.SetMove(from, to);

            if (bdmove.IsValidMove())
                break;
            else
                System.out.print("\nそこには動かせません");
        }
    }

    /**
    * １ゲーム、プレイする
    */
    public void Play() throws IOException
    {
        HpBoardMove board = new HpBoardMove();  // 現在の盤の状態
        HpBoardMove lastMatchBoxMove = null;   // マッチ箱の最後の手
        HexPawnDefs winner = HexPawnDefs.None;  // 勝者
        HexPawnDefs turn = HexPawnDefs.White;   // 現在の番（白番から始める）

        board.Show();

        while (winner != HexPawnDefs.White && winner != HexPawnDefs.Black)
        {
            if (turn == PlayerColor)
            {
                PlayerTurn(board);
            }
            else
            {
                if (MatchBoxTurn(board))
                {
                    lastMatchBoxMove = new HpBoardMove(board);
                }
                else
                {
                    // リザインした場合
                    winner = PlayerColor;
                    break;
                }
            }

            // 駒を移動
            board.MovePawn();

            // 盤面を表示
            board.Show();

            // 次のターンへ
            if (turn == HexPawnDefs.Black)
                turn = HexPawnDefs.White;
            else
                turn = HexPawnDefs.Black;

            winner = board.CheckFinish(turn);
        }

        if (winner == HexPawnDefs.White)
            System.out.print("\n白の勝ちです。\n");
        else if (winner == HexPawnDefs.Black)
            System.out.print("\n黒の勝ちです。\n");

        if (winner != MatchBoxColor && lastMatchBoxMove != null)
            DefeatList.add(lastMatchBoxMove);
    }

    /**
    *   main
    */
    public static void main( String[] args ) throws IOException
    {
        String  reply;  // ユーザー入力を受け取る変数
        char    q;

        HexPawn game = new HexPawn();

        do
        {
            game.Play();    // １ゲーム、プレイする

            System.out.print("終了する場合は'Q'、続ける場合は他のキーを押してください");

            BufferedReader br = new BufferedReader(
                                    new InputStreamReader( System.in ) );

            reply = br.readLine();

            if( reply.length() > 0 )
                q = reply.charAt(0);
            else
                q = 0;

        } while (q != 'q' && q != 'Q');

    }
}