using System;

using System.Collections.Generic;

​

namespace TicTacToeCombos

{

    public class Program

    {

        public static void Main(string[] args)

        {

            Console.WriteLine($"Total number of distinct games: {Play(Board.Empty)}");

        }

​

        // Recursive function that returns the number of legal permutations remaining given the provided Board.

        static int Play(Board board)

        {

            if (board.IsFinished)

            {

                return 1;

            }

            int numGames = 0;

            foreach (Board b in board.NextBoards())

            {

                numGames += Play(b);

            }

​

            return numGames;

        }

    }

​

    public enum Piece

    {

        Empty,

        X,

        O

    }

​

    public struct Position

    {

        public int x;

        public int y;

    }

​

    public class Board

    {

        // The current pieces placed on the 3x3 board

        private readonly Piece[,] m_pieces = new Piece[3, 3];

​

        // Which player's turn it is

        private readonly Piece m_nextPiece;

​

        // The number of pieces already placed.  Used for determining if the game is over because all 9 pieces have 

        // been placed.

        private readonly int m_piecesPlaced;

​

        // Whether the game has been won yet

        public readonly bool IsFinished;

​

        private Board(Piece[,] pieces, Piece nextPiece, int piecesPlayed) 

        { 

            m_pieces = pieces;

            m_nextPiece = nextPiece;

            m_piecesPlaced = piecesPlayed;

            IsFinished = GetIsFinished();

        }

​

        public static readonly Board Empty = new Board(new Piece[3, 3], Piece.X, 0);

​

        // Adds a piece to the current board and returns the new state

        public Board Next(Position pos, Piece piece)

        {

            int x = pos.x;

            int y = pos.y;

​

            Piece[,] next = new Piece[3,3];

            for (int i = 0; i < 3; i++)

            {

                for (int j = 0; j < 3; j++)

                {

                    next[i, j] = m_pieces[i, j];

                }

            }

​

            if (m_pieces[x, y] != Piece.Empty)

            {

                throw new ArgumentException();

            }

​

            next[x, y] = piece;

​

            return new Board(next, piece == Piece.X ? Piece.O : Piece.X, m_piecesPlaced + 1);

        }

​

        // Enumerates all legal next moves (i.e. moves where a piece is not already placed)

        // In the case that the game is finished, either because a player won or because the board is full, returns no 

        // items

        public IEnumerable<Position> PossibleNextMoves()

        {

            if (IsFinished)

            {

                yield break;

            }

​

            foreach (Position pos in AllPositions())

            {

                if (m_pieces[pos.x, pos.y] == Piece.Empty)

                {

                    yield return pos;

                }

            }

        }

​

        // Enumerates the resulting board from all possible next moves

        public IEnumerable<Board> NextBoards()

        {

            if (IsFinished)

            {

                yield break;

            }

​

            foreach (Position pos in PossibleNextMoves())

            {

                yield return Next(pos, m_nextPiece);

            }

        }

​

        // Determines whether the game has been won by either player

        private bool GetIsFinished()

        {

            if (m_piecesPlaced == 9)

            {

                return true;

            }

​

            Piece piece;

            // horizontals and verticals

            for (int i = 0; i < 3; i++)

            {

                piece = m_pieces[0, i];

                if (piece != Piece.Empty && m_pieces[1, i] == piece && m_pieces[2, i] == piece)

                {

                    return true;

                }

​

                piece = m_pieces[i, 0];

                if (piece != Piece.Empty && m_pieces[i, 1] == piece && m_pieces[i, 2] == piece)

                {

                    return true;

                }

            }

​

            // diagonal \

            piece = m_pieces[0, 0];

            if (piece != Piece.Empty && m_pieces[1, 1] == piece && m_pieces[2, 2] == piece)

            {

                return true;

            }

​

            // diagonal /

            piece = m_pieces[0, 2];

            return piece != Piece.Empty && m_pieces[1, 1] == piece && m_pieces[2, 0] == piece;

        }

​

        // Helper method for enumerating all 9 positions

        private static IEnumerable<Position> AllPositions()

        {

            for (int x = 0; x < 3; x++)

            {

                for (int y = 0; y < 3; y++)

                {

                    yield return new Position { x = x, y = y };

                }

            }

        }

    }

}

​