using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
//const int ZentaiSquareHaba = 5;
const int ZentaiSquareHaba = 23;
const int UB = ZentaiSquareHaba - 1;
struct JyoutaiDef
{
internal char[,] BanArr;
internal int Level;
internal int AreaSum;
}
//平方数の配列(正方形の面積の配列)
static int[] HeihouSuuArr = Enumerable.Range(1, ZentaiSquareHaba - 1).
Select(X => X * X).ToArray();
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
//反復深化深さ優先探索で解く
for (int Depth = 2; Depth <= ZentaiSquareHaba * ZentaiSquareHaba; Depth++) {
Console.WriteLine("深さ制限={0}で探索中。経過時間={1}", Depth, sw.Elapsed);
List<Char[,]> AnswerBanArrLog = ExecDFS(Depth);
if (AnswerBanArrLog.Count == 0) continue;
//回転解を除外
RemoveKaiten(AnswerBanArrLog);
//解を出力
int AnswerCnt = 0;
foreach (char[,] AnyBanArr in AnswerBanArrLog) {
Console.WriteLine("解{0}(正方形の個数={1})経過時間={2}",
++AnswerCnt, Depth, sw.Elapsed);
PrintAnswer(AnyBanArr);
}
break;
}
}
//深さ制限を引数として深さ優先探索を行う
static List<Char[,]> ExecDFS(int pDepthMax)
{
var WillReturnCharArrList = new List<char[,]>();
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.BanArr = new char[UB + 1, UB + 1];
for (int X = 0; X <= UB; X++)
for (int Y = 0; Y <= UB; Y++)
WillPush.BanArr[X, Y] = ' ';
WillPush.Level = 0;
WillPush.AreaSum = 0;
stk.Push(WillPush);
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
int CurrX, CurrY;
SearchWillFillSpace(Popped.BanArr, out CurrX, out CurrY);
//クリア判定
if (CurrX == -1 && CurrY == -1) {
WillReturnCharArrList.Add(Popped.BanArr);
continue;
}
//残りの面積
int RestArea = ZentaiSquareHaba * ZentaiSquareHaba - Popped.AreaSum;
//残りの面積が正方形1つで可能の場合
if (Array.IndexOf<int>(HeihouSuuArr, RestArea) >= 0) {
//レベル制限
if (Popped.Level >= pDepthMax) continue;
}
//残りの面積が正方形2つ以上の場合(下限値枝切り)
else if (Popped.Level + 1 >= pDepthMax) continue;
//正方形を配置する経路のPush処理
for (int I = 1; I <= ZentaiSquareHaba - 1; I++) {
//左右対称の解の除外で
//最初のPushで配置する正方形の一辺は、
//全体の正方形の半分以下の長さとする
if (CurrX == 0 && CurrY == 0) {
if (ZentaiSquareHaba / 2 < I) break;
}
//左右対称の解の除外で
//左上の正方形の一辺の長さ <= 右上の正方形の一辺の長さ とする
if (CurrY == 0 && CurrX + I - 1 == UB) {
if (StrToDec(Popped.BanArr[0, 0]) > I) break;
}
//回転解の除外で
//右上の正方形の一辺の長さ <= 左下の正方形の一辺の長さ とする
if (CurrX == 0 && CurrY + I - 1 == UB) {
if (StrToDec(Popped.BanArr[UB, 0]) > I) break;
}
//正方形を配置できなかったらBreak;
if (CanFillSquare(I, CurrX, CurrY, Popped.BanArr) == false)
break;
WillPush.Level = Popped.Level + 1;
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
WillPush.AreaSum = Popped.AreaSum + I * I;
for (int X = CurrX; X <= CurrX + I - 1; X++) {
for (int Y = CurrY; Y <= CurrY + I - 1; Y++) {
WillPush.BanArr[X, Y] = DecToStr(I);
}
}
stk.Push(WillPush);
}
}
return WillReturnCharArrList;
}
//char型を10進数に変換
static int StrToDec(char pStr)
{
if (pStr == ' ') return 0;
if ('A' <= pStr) return 10 + pStr - 'A';
return (int)(pStr - '0');
}
//10進数をchar型に変換
static char DecToStr(int pInt)
{
if (pInt < 10) return (char)((int)'1' + pInt - 1);
return (char)((int)'A' + pInt - 10);
}
//正方形を埋める座標を探す。なかったら-1を返す
static void SearchWillFillSpace(char[,] pBanArr, out int pX, out int pY)
{
pX = pY = -1;
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if (pBanArr[X, Y] == ' ') {
pX = X; pY = Y; return;
}
}
}
}
//マス目に正方形を埋めれるか
static bool CanFillSquare(int pFillSquareHaba, int pTargetX, int pTargetY, char[,] pBanArr)
{
if (pTargetX + pFillSquareHaba - 1 > UB) return false;
if (pTargetY + pFillSquareHaba - 1 > UB) return false;
for (int X = pTargetX; X <= pTargetX + pFillSquareHaba - 1; X++) {
for (int Y = pTargetY; Y <= pTargetY + pFillSquareHaba - 1; Y++) {
if (pBanArr[X, Y] != ' ') return false;
}
}
return true;
}
//回転解を除外
static void RemoveKaiten(List<char[,]> pTargetList)
{
Predicate<int> IsExist = (pCurrInd) =>
{
for (int I = 0; I <= pCurrInd - 1; I++) {
bool IsOK1 = false, IsOK2 = false, IsOK3 = false, IsOK4 = false;
bool IsOK5 = false, IsOK6 = false, IsOK7 = false; //回転1から7
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
char CurrVal = pTargetList[pCurrInd][X, Y];
if (pTargetList[I][UB - X, Y] != CurrVal) IsOK1 = true;
if (pTargetList[I][UB - X, UB - Y] != CurrVal) IsOK2 = true;
if (pTargetList[I][X, UB - Y] != CurrVal) IsOK3 = true;
if (pTargetList[I][Y, X] != CurrVal) IsOK4 = true;
if (pTargetList[I][UB - Y, X] != CurrVal) IsOK5 = true;
if (pTargetList[I][UB - Y, UB - X] != CurrVal) IsOK6 = true;
if (pTargetList[I][Y, UB - X] != CurrVal) IsOK7 = true;
}
}
if (IsOK1 == false || IsOK2 == false || IsOK3 == false || IsOK4 == false
|| IsOK5 == false || IsOK6 == false || IsOK7 == false)
return true;
}
return false;
};
for (int I = pTargetList.Count - 1; I >= 0; I--) {
if (IsExist(I)) pTargetList.RemoveAt(I);
}
}
//解を出力
static void PrintAnswer(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
