using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Threading;

namespace Bojagi
{
    public class ListCoordPair : IComparable<ListCoordPair>
    {
        List<List<int>> CoordPairs;
        public List<List<int>> GetCoordPairs()
        {
            return this.CoordPairs;
        }
        public void AddCoordPair( int row, int column )
        {
            List<int> coords = new List<int>() { row, column };
            this.CoordPairs.Add( coords );
        }
        public bool HasCoordPair( int row, int column )
        {
            foreach (List<int> CoordPair in this.CoordPairs)
            {
                if (CoordPair[ 0 ] == row && CoordPair[ 1 ] == column)
                {
                    return true;
                }
            }
            return false;
        }
        public ListCoordPair( List<List<int>> coordPairs )
        {
            this.CoordPairs = coordPairs;
        }
        public override bool Equals( object x )
        {
            ListCoordPair b = x as ListCoordPair;
            if (b.CoordPairs.Count != this.CoordPairs.Count)
            {
                return false;
            }
            foreach (List<int> coords in b.CoordPairs)
            {
                if (!this.HasCoordPair( coords[ 0 ], coords[ 1 ] ))
                {
                    return false;
                }
            }
            return true;
        }
        public override int GetHashCode()
        {
            return base.GetHashCode();
        }
        public int CompareTo( ListCoordPair b )
        {
            if (this.Equals( b ))
            {
                return 0;
            }
            return 1;
        }
    }

    public class NumberCoords : IEquatable<NumberCoords>
    {
        public int Row;
        public int Column;
        public int Number;
        public int GetRow()
        {
            return this.Row;
        }
        public int GetColumn()
        {
            return this.Column;
        }
        public int GetNumber()
        {
            return this.Number;
        }
        public NumberCoords( int row, int column, int number )
        {
            this.Row = row;
            this.Column = column;
            this.Number = number;
        }
        public bool Equals( NumberCoords otherNumberCoords )
        {
            return this.Row == otherNumberCoords.Row &&
                this.Column == otherNumberCoords.Column &&
                this.Number == otherNumberCoords.Number;
        }
        public override string ToString()
        {
            return this.Row.ToString() + this.Column.ToString() + this.Number.ToString();
        }
    }

    public class Partition : IComparable<Partition>
    {
        public int GetNumParts()
        {
            return this.Parts.Count;
        }
        List<int> Parts;
        public Partition( List<int> parts )
        {
            this.Parts = parts;
        }
        public void Print()
        {
            Console.Write( this.Parts[ 0 ] );
            for (int i = 1; i < this.Parts.Count; i++)
            {
                Console.Write( ", " + this.Parts[ i ] );
            }
            Console.WriteLine();
        }
        public List<int> GetParts()
        {
            return this.Parts;
        }
        public override bool Equals( object x )
        {
            Partition b = x as Partition;
            List<int> bParts = b.GetParts().OrderBy( i => i ).ToList();
            this.Parts = this.Parts.OrderBy( i => i ).ToList();
            if (bParts.Count != this.Parts.Count)
            {
                return false;
            }
            for (int i = 0; i < this.Parts.Count; i++)
            {
                if (this.Parts[ i ] != bParts[ i ])
                {
                    return false;
                }
            }
            return true;
        }
        public override int GetHashCode()
        {
            return base.GetHashCode();
        }
        public int CompareTo( Partition b )
        {
            if (this.Equals( b ))
            {
                return 0;
            }
            return 1;
        }
    }

    public class Board : IComparable<Board>, IEquatable<Board>
    {
        int[][] Numbers;
        int Rows;
        int Columns;
        List<NumberCoords> NumberCoords;
        NumberCoords[] SortedNumberCoords;
        string Representation;
        public override string ToString()
        {
            return Representation;
        }
        public int GetRows() { return this.Rows; }
        public int GetColumns() { return this.Columns; }
        public List<NumberCoords> GetNumberCoords()
        {
            return this.NumberCoords.ToList();
        }
        public int GetNum( int row, int column )
        {
            return this.Numbers[ row ][ column ];
        }
        public void PrintBoard()
        {
            for (int i = 0; i < this.Rows; i++)
            {
                for (int j = 0; j < this.Columns; j++)
                {
                    Console.Write( this.Numbers[ i ][ j ] );
                }
                Console.WriteLine();
            }
        }
        public void PrintBoard( Solution solution )
        {
            for (int i = 0; i < this.Rows; i++)
            {
                for (int j = 0; j < this.Columns; j++)
                {
                    Console.Write( this.Numbers[ i ][ j ] );
                    if (solution.GetFilled( i, j ))
                    {
                        Console.Write( "f " );
                    }
                    else
                    {
                        Console.Write( "e " );
                    }
                }
                Console.WriteLine();
            }
        }
        public List<Solution> Solve()
        {
            Solution solution = new Solution( this.Rows, this.Columns );
            List<Solution> solutions = new List<Solution>() { solution };
            while (solutions[ 0 ].MinInt() == 0)
            {
                solutions = this.FillABox( solutions );
                if (solutions.Count == 0)
                {
                    break;
                }
            }
            return solutions;
        }
        public List<Solution> FillABox( List<Solution> curSolutions )
        {
            List<Solution> newSolutions = new List<Solution>();
            foreach (Solution solution in curSolutions)
            {
                bool filled = false;
                for (int i = 0; i < this.Rows; i++)
                {
                    for (int j = 0; j < this.Columns; j++)
                    {
                        int num = this.Numbers[ i ][ j ];
                        if (!solution.GetFilled( i, j ) && num > 0)
                        {
                            //try to fill this box
                            List<List<int>> FactorPairs = Program.GetFactorPairs( num );
                            foreach (List<int> pair in FactorPairs)
                            {
                                List<Solution> newSols = solution.FillBox( i, j, pair[ 0 ], pair[ 1 ], this );
                                foreach (Solution newSol in newSols)
                                {
                                    newSolutions.Add( newSol );
                                }
                            }
                            filled = true;
                        }
                        if (filled)
                        {
                            break;
                        }
                    }
                    if (filled)
                    {
                        break;
                    }
                }
            }
            newSolutions = newSolutions.Distinct().ToList();
            return newSolutions;
        }
        public Board( int rows, int columns, List<NumberCoords> numberCoords )
        {
            this.NumberCoords = numberCoords;
            //this.SortedNumberCoords = .ToArray();
            this.Representation = string.Join( ",", numberCoords.OrderBy( x => x.Row ).ThenBy( x => x.Column ).ThenBy( x => x.Number ).Select( x => x.ToString() ) );
            this.Numbers = new int[ rows ][];
            this.Rows = rows;
            this.Columns = columns;
            for (int i = 0; i < this.Rows; i++)
            {
                this.Numbers[ i ] = new int[ columns ];
            }
            foreach (NumberCoords coord in numberCoords)
            {
                this.Numbers[ coord.GetRow() ][ coord.GetColumn() ] = coord.GetNumber();
            }
        }
        internal bool HasNumber( int i, int j )
        {
            return this.Numbers[ i ][ j ] != 0;
        }
        public int CompareTo( Board other )
        {
            if (this.Equals( other ))
            {
                return 0;
            }
            return 1;
        }
        public override bool Equals( object obj )
        {
            var otherBoard = obj as Board;
            if (otherBoard == null)
            {
                return false;
            }
            return this.Equals( otherBoard );
        }
        public override int GetHashCode()
        {
            return this.Representation.GetHashCode();
        }
        public bool Equals( Board otherBoard )
        {
            return this.Representation == otherBoard.Representation;
            //if(this.SortedNumberCoords.Length != otherBoard.SortedNumberCoords.Length)
            //{
            //    return false;
            //}
            //for (int i = 0; i < this.SortedNumberCoords.Length; i++)
            //{
            //    if(!this.SortedNumberCoords[i].Equals(otherBoard.SortedNumberCoords[i]))
            //    {
            //        return false;
            //    }
            //}
            //return true;

            //if (this.Rows != otherBoard.Rows)
            //{
            //    return false;
            //}
            //if (this.Columns != otherBoard.Columns)
            //{
            //    return false;
            //}
            //for (int i = 0; i < this.Rows; i++)
            //{
            //    for (int j = 0; j < this.Columns; j++)
            //    {
            //        if (this.Numbers[i][j] != otherBoard.Numbers[i][j])
            //        {
            //            return false;
            //        }
            //    }
            //}
            //return true;
        }
    }

    public class Solution : IComparable<Solution>
    {
        List<List<int>> Filled;
        int Rows;
        int Columns;
        public override bool Equals( object x )
        {
            Solution b = x as Solution;
            if (b.Rows != this.Rows || b.Columns != this.Columns)
            {
                return false;
            }
            for (int i = 0; i < this.Rows; i++)
            {
                for (int j = 0; j < this.Columns; j++)
                {
                    if (b.Filled[ i ][ j ] != this.Filled[ i ][ j ])
                    {
                        return false;
                    }
                }
            }
            return true;
        }
        public override int GetHashCode()
        {
            return base.GetHashCode();
        }
        public int CompareTo( Solution b )
        {
            if (this.Equals( b ))
            {
                return 0;
            }
            return 1;
        }
        public void Fill( int row, int column, int toFill )
        {
            this.Filled[ row ][ column ] = toFill;
        }
        public bool GetFilled( int row, int column )
        {
            return (this.Filled[ row ][ column ] > 0);
        }
        public List<Solution> FillBox( int row, int column, int rowDim, int columnDim, Board board )
        {
            List<Solution> solutions = new List<Solution>();
            for (int deltaX = -rowDim + 1; deltaX <= 0; deltaX++)
            {
                for (int deltaY = -columnDim + 1; deltaY <= 0; deltaY++)
                {
                    //make an identical solution to this
                    Solution solution = new Solution( this.Rows, this.Columns );
                    for (int i = 0; i < this.Rows; i++)
                    {
                        for (int j = 0; j < this.Columns; j++)
                        {
                            solution.Fill( i, j, this.Filled[ i ][ j ] );
                        }
                    }
                    int toFill = solution.MaxInt() + 1;
                    bool validSolution = true;
                    for (int i = row + deltaX; i < row + deltaX + rowDim; i++)
                    {
                        if (i >= 0 && i < this.Rows)
                        {
                            for (int j = column + deltaY; j < column + deltaY + columnDim; j++)
                            {
                                if (j >= 0 && j < this.Columns)
                                {
                                    if (this.Filled[ i ][ j ] > 0 || (board.GetNum( i, j ) > 0 && i != row && j != column))
                                    {
                                        validSolution = false;
                                        break;
                                    }
                                    else
                                    {
                                        solution.Fill( i, j, toFill );
                                    }
                                }
                                else
                                {
                                    validSolution = false;
                                    break;
                                }
                            }
                        }
                        else
                        {
                            validSolution = false;
                        }
                        if (!validSolution)
                        {
                            break;
                        }
                    }
                    if (validSolution)
                    {
                        solutions.Add( solution );
                    }
                }
            }
            return solutions;
        }
        public int MaxInt()
        {
            int max = 0;
            for (int i = 0; i < this.Rows; i++)
            {
                for (int j = 0; j < this.Columns; j++)
                {
                    if (this.Filled[ i ][ j ] > max)
                    {
                        max = this.Filled[ i ][ j ];
                    }
                }
            }
            return max;
        }
        public int MinInt()
        {
            int min = 1000;
            for (int i = 0; i < this.Rows; i++)
            {
                for (int j = 0; j < this.Columns; j++)
                {
                    if (this.Filled[ i ][ j ] < min)
                    {
                        min = this.Filled[ i ][ j ];
                    }
                }
            }
            return min;
        }
        public Solution( int rows, int columns )
        {
            this.Rows = rows;
            this.Columns = columns;
            this.Filled = new List<List<int>>();
            for (int i = 0; i < this.Rows; i++)
            {
                List<int> row = new List<int>();
                for (int j = 0; j < this.Columns; j++)
                {
                    row.Add( 0 );
                }
                this.Filled.Add( row );
            }
        }
    }



    public class Program
    {
        private static Stopwatch sw = new Stopwatch();

        public static List<List<int>> GetFactorPairs( int n )
        {
            List<List<int>> Pairs = new List<List<int>>();
            for (int i = 1; i <= Math.Sqrt( n ); i++)
            {
                List<int> factorPair = new List<int>();
                if (n % i == 0)
                {
                    factorPair.Add( i );
                    factorPair.Add( n / i );
                    Pairs.Add( factorPair );
                }
            }
            List<List<int>> revPairs = new List<List<int>>();
            foreach (List<int> pair in Pairs)
            {
                if (pair[ 0 ] != pair[ 1 ])
                {
                    List<int> revPair = new List<int>();
                    revPair.Add( pair[ 1 ] );
                    revPair.Add( pair[ 0 ] );
                    revPairs.Add( revPair );
                }
            }
            foreach (List<int> pair in revPairs)
            {
                Pairs.Add( pair );
            }
            return Pairs;
        }
        public static List<Partition> GenerateParts( int n )
        {
            List<Partition> Partitions = new List<Partition>();
            if (n == 1)
            {
                List<int> part = new List<int>() { 1 };
                Partition partition = new Partition( part );
                Partitions.Add( partition );
                return Partitions;
            }
            for (int i = 0; i < Math.Pow( 2, n - 1 ); i++)
            {
                List<int> Parts = new List<int>();
                int currentPart = 1;
                for (int b = 0; b < n - 1; b++)
                {
                    bool bit = (i & (1 << b)) > 0;
                    if (bit)
                    {
                        Parts.Add( currentPart );
                        currentPart = 1;
                    }
                    else
                    {
                        currentPart++;
                    }
                }
                Parts.Add( currentPart );
                Partition Partition = new Partition( Parts );
                if (!Partitions.Contains( Partition ))
                {
                    Partitions.Add( Partition );
                }
            }
            return Partitions;
        }

        public static List<Board> GenerateBojagiBoards( int rows, int columns )
        {
            List<Board> boards = new List<Board>();
            int N = rows * columns;

            var partitionGenerationStopWatch = new Stopwatch();
            partitionGenerationStopWatch.Start();
            List<Partition> partitions = GenerateParts( N );
            partitionGenerationStopWatch.Stop();

            Console.WriteLine( $"{partitionGenerationStopWatch.Elapsed.TotalSeconds} to generate {partitions.Count} partitions" );

            //partitions = partitions.Take(1).ToList();


            Stopwatch generateBoardsStopWatch = new Stopwatch();
            generateBoardsStopWatch.Start();

            boards = partitions
                            .AsParallel()
                            .SelectMany( p => GetDistinctBoardsForPartition( rows, columns, p, partitions ) ).ToList();

            generateBoardsStopWatch.Stop();
            Console.WriteLine( $"{generateBoardsStopWatch.Elapsed.TotalSeconds} seconds to generate {boards.Count} distinct boards" );

            return boards;
        }

        private static IEnumerable<Board> GetDistinctBoardsForPartition( int rows, int columns, Partition p, List<Partition> partitions )
        {
            var parts = p.GetParts().OrderBy( n => n ).ToList();

            //Stopwatch partitionStopWatch = new Stopwatch();
            //partitionStopWatch.Start();

            var boardsForPartition = GetBoardsForPartition( rows, columns, p.GetParts().OrderBy( n => n ).ToList(), true );

            var distinctBoards = boardsForPartition.Distinct();
            //Console.WriteLine($"{boardsForPartition.Count()} total boards and {distinctBoards.Count()} distinct boards for partition {partitions.IndexOf(p)} of {partitions.Count}. Length of {p.GetParts().Count}, values are ( {string.Join(",", p.GetParts())} )");

            return distinctBoards;
        }

        // 3x2
        // 2,2,2
        public static IEnumerable<Board> GetBoardsForPartition( int rows, int columns, List<int> numbersForThisBoard, bool tryDedupe )
        {
            var boards = new List<Board>();

            if (numbersForThisBoard.Count == (rows * columns) && numbersForThisBoard.All( n => n == 1 ))
            {
                var coordsForSimpleBoard = new List<NumberCoords>();
                for (int i = 0; i < rows; i++)
                {
                    for (int j = 0; j < columns; j++)
                    {
                        coordsForSimpleBoard.Add( new NumberCoords( i, j, 1 ) );
                    }
                }
                return new List<Board>() { new Board( rows, columns, coordsForSimpleBoard ) };
            }

            int firstNumber = numbersForThisBoard.First();
            var remainingNumbers = numbersForThisBoard.GetRange( 1, numbersForThisBoard.Count - 1 );
            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < columns; j++)
                {
                    boards.AddRange( GetBoardsForPartition( rows, columns, new List<NumberCoords>() { new NumberCoords( i, j, firstNumber ) }, remainingNumbers, 0, 0, tryDedupe ) );
                }
            }

            // filter out partial boards
            //var nonPartialBoards = boards.Where(board => board.GetNumberCoords().Sum(coord => coord.GetNumber()) == (rows * columns)).ToList();            

            return boards;
        }

        public static IEnumerable<Board> GetBoardsForPartition( int rows, int columns, List<NumberCoords> coords, IEnumerable<int> numbersForThisBoard, int startingRow, int startingColumn, bool tryDedupe )
        {
            if (!numbersForThisBoard.Any())
            {
                yield return new Board( rows, columns, coords );
                yield break;
            }

            var boards = new List<Board>();
            var firstNumber = numbersForThisBoard.First();

            var currentNumberBlock = coords.Last().Number;

            int yieldCount = 0;
            var remainingNumbers = numbersForThisBoard.Skip( 1 );
            for (int i = startingRow; i < rows; i++)
            {
                for (int j = startingColumn; j < columns; j++)
                {
                    if (!coords.Any( x => x.Row == i && x.Column == j ))
                    {
                        var newCoords = coords.ToList();
                        newCoords.Add( new NumberCoords( i, j, firstNumber ) );

                        var nextStartRow = 0;
                        var nextStartColumn = 0;
                        var nextNumber = remainingNumbers.FirstOrDefault();
                        if (nextNumber == firstNumber && tryDedupe)
                        {
                            nextStartRow = i;
                            nextStartColumn = j;
                        }

                        foreach (var board in GetBoardsForPartition( rows, columns, newCoords, remainingNumbers, nextStartRow, nextStartColumn, tryDedupe ))
                        {
                            yield return board;
                            yieldCount++;
                        }
                    }
                }
                startingColumn = 0;
            }
        }

        public static void PrintBojagiBoardsWithUniqueSolution( int rows, int columns )
        {
            List<Board> boards = GenerateBojagiBoards( rows, columns );
            foreach (Board board in boards)
            {
                if (board.Solve().Count == 1)
                {
                    board.PrintBoard();
                    Console.WriteLine();
                }
            }
        }
        public static int CountBojagiBoardsWithUniqueSolution( int rows, int columns )
        {
            List<Board> boards = GenerateBojagiBoards( rows, columns );

            Stopwatch solveBoards = new Stopwatch();
            solveBoards.Start();

            int count = boards.AsParallel().Count( b => b.Solve().Count == 1 );
            //foreach (Board board in boards)
            //{
            //    if (board.Solve().Count == 1)
            //    {
            //        count++;
            //    }
            //}

            solveBoards.Stop();
            Console.WriteLine( $"{solveBoards.Elapsed.TotalSeconds} seconds to solve {boards.Count} boards" );

            return count;
        }



        static void Main( string[] args )
        {
            sw.Start();

            var desiredNumbers = new List<Tuple<int, int>>()
            {
                new Tuple<int, int>(2, 4),
                new Tuple<int, int>(2, 5),
                new Tuple<int, int>(3, 3),
                new Tuple<int, int>(2, 6),
                new Tuple<int, int>(3, 4),
            };

            foreach (var desiredNumber in desiredNumbers)
            {
                int row = desiredNumber.Item1;
                int column = desiredNumber.Item2;
                Console.WriteLine( $"Bojagi({row},{column})..." );
                var bojagiNumber = CountBojagiBoardsWithUniqueSolution( row, column );
                Console.WriteLine( $"Bojagi({row},{column}) = {bojagiNumber}" );

                Console.WriteLine( "----------------------" );
            }

            Console.ReadKey();
        }
    }
}