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(); } } }