using System;
using System.Collections.Generic;
class Program
{
//長方形ごとの配置候補
static Dictionary<char, List<LenInfoDef>> HaitiKouhoListDict =
new Dictionary<char, List<LenInfoDef>>();
static char[] mRectNameArr = { 'A', 'B', 'C', 'D', 'E',
'F', 'G', 'H', 'I', 'J',
'K', 'L', 'M', 'N', 'O'};
static int UB;
static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
static void Main()
{
foreach (char EachRectName in mRectNameArr) {
HaitiKouhoListDict[EachRectName] = DeriveHaitiKouhoList(EachRectName);
}
//長方形の面積合計を求める
int MensekiSum = 0;
foreach (char EachRectName in mRectNameArr) {
LenInfoDef wkLenInfo = DeriveRectLenInfo(EachRectName);
MensekiSum += wkLenInfo.HabaX * wkLenInfo.HabaY;
}
Console.WriteLine("長方形の面積合計={0}", MensekiSum);
int SquareIppen = DeriveHeihouKon(MensekiSum);
UB = SquareIppen - 1;
Console.WriteLine("正方形の一辺={0}", SquareIppen);
//深さ優先探索を行う
ExecDFS();
}
//長方形名を引数として、回転させた長方形のListを返す
static List<LenInfoDef> DeriveHaitiKouhoList(char pRectName)
{
var WillReturn = new List<LenInfoDef>();
LenInfoDef wkLenInfo = DeriveRectLenInfo(pRectName);
Action<int, int> wkAct = (pHabaX, pHabaY) =>
{
LenInfoDef WillAdd;
WillAdd.HabaX = pHabaX;
WillAdd.HabaY = pHabaY;
WillReturn.Add(WillAdd);
};
wkAct(wkLenInfo.HabaX, wkLenInfo.HabaY);
wkAct(wkLenInfo.HabaY, wkLenInfo.HabaX);
return WillReturn;
}
struct LenInfoDef
{
internal int HabaX;
internal int HabaY;
}
static LenInfoDef DeriveRectLenInfo(char pRectName)
{
if (pRectName == 'A') return new LenInfoDef() { HabaX = 13, HabaY = 60 };
if (pRectName == 'B') return new LenInfoDef() { HabaX = 15, HabaY = 37 };
if (pRectName == 'C') return new LenInfoDef() { HabaX = 16, HabaY = 41 };
if (pRectName == 'D') return new LenInfoDef() { HabaX = 17, HabaY = 51 };
if (pRectName == 'E') return new LenInfoDef() { HabaX = 18, HabaY = 48 };
if (pRectName == 'F') return new LenInfoDef() { HabaX = 19, HabaY = 56 };
if (pRectName == 'G') return new LenInfoDef() { HabaX = 20, HabaY = 44 };
if (pRectName == 'H') return new LenInfoDef() { HabaX = 21, HabaY = 29 };
if (pRectName == 'I') return new LenInfoDef() { HabaX = 23, HabaY = 32 };
if (pRectName == 'J') return new LenInfoDef() { HabaX = 24, HabaY = 31 };
if (pRectName == 'K') return new LenInfoDef() { HabaX = 25, HabaY = 27 };
if (pRectName == 'L') return new LenInfoDef() { HabaX = 26, HabaY = 61 };
if (pRectName == 'M') return new LenInfoDef() { HabaX = 28, HabaY = 40 };
if (pRectName == 'N') return new LenInfoDef() { HabaX = 30, HabaY = 43 };
return new LenInfoDef() { HabaX = 42, HabaY = 47 };
}
//平方根を求める
static int DeriveHeihouKon(int pVal)
{
for (int I = 0; I * I <= pVal; I++) {
if (I * I == pVal) return I;
}
return -1;
}
struct VectorInfoDef
{
internal char RectName;
internal int FromX;
internal int FromY;
internal int ToX;
internal int ToY;
}
struct JyoutaiDef
{
internal int CurrX;
internal int CurrY;
internal List<VectorInfoDef> VectorInfoList;
}
//深さ優先探索を行う
static void ExecDFS()
{
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrX = WillPush.CurrY = 0;
WillPush.VectorInfoList = new List<VectorInfoDef>();
Stk.Push(WillPush);
var AnswerKouhoArrList = new List<char[,]>();
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
//クリア判定
if (Popped.VectorInfoList.Count == 15) {
AnswerKouhoArrList.Add(DeriveBanArr(Popped.VectorInfoList));
Console.WriteLine("解候補{0}を発見。経過時間={1}",
AnswerKouhoArrList.Count, sw.Elapsed);
continue;
}
//長方形を配置する座標を求める
DeriveSetRectPos(Popped.VectorInfoList, ref Popped.CurrX, ref Popped.CurrY);
foreach (char EachRectName in mRectNameArr) {
if (Popped.VectorInfoList.Exists(A => A.RectName == EachRectName))
continue;
//長方形の配置候補リスト
List<LenInfoDef> HaitiKouhoList = new List<LenInfoDef>();
HaitiKouhoList.AddRange(HaitiKouhoListDict[EachRectName]);
//長方形を配置する経路のPush処理
foreach (LenInfoDef EachHaitiKouho in HaitiKouhoList) {
VectorInfoDef wkVectorInfo;
wkVectorInfo.RectName = EachRectName;
wkVectorInfo.FromX = Popped.CurrX;
wkVectorInfo.FromY = Popped.CurrY;
wkVectorInfo.ToX = Popped.CurrX + EachHaitiKouho.HabaX - 1;
wkVectorInfo.ToY = Popped.CurrY + EachHaitiKouho.HabaY - 1;
if (UB < wkVectorInfo.ToX) continue;
if (UB < wkVectorInfo.ToY) continue;
if (IsNaisetuRect(wkVectorInfo, Popped.VectorInfoList))
continue;
WillPush.CurrX = wkVectorInfo.ToX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.VectorInfoList = new List<VectorInfoDef>(Popped.VectorInfoList);
WillPush.VectorInfoList.Add(wkVectorInfo);
if (WillEdakiri(WillPush.VectorInfoList) == false)
Stk.Push(WillPush);
}
}
}
RemoveKaitenKai(AnswerKouhoArrList);
for (int I = 0; I <= AnswerKouhoArrList.Count - 1; I++) {
Console.WriteLine("解{0}", I + 1);
PrintAnswer(AnswerKouhoArrList[I]);
}
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
//長方形を配置する座標を求める
static void DeriveSetRectPos(List<VectorInfoDef> pVectorInfoList,
ref int pSetPosFromX, ref int pSetPosFromY)
{
int PosX = pSetPosFromX;
int PosY = pSetPosFromY;
while (true) {
if (UB < PosX) {
PosX = 0;
PosY++;
}
//座標が、既存の長方形の中にあるかを判定
int wkInd =
pVectorInfoList.FindIndex(A => A.FromX <= PosX && PosX <= A.ToX
&& A.FromY <= PosY && PosY <= A.ToY);
if (wkInd == -1) {
pSetPosFromX = PosX;
pSetPosFromY = PosY;
return;
}
PosX = pVectorInfoList[wkInd].ToX + 1;
}
}
//長方形が、既存の長方形の中にあるかを判定
static bool IsNaisetuRect(VectorInfoDef pRect, List<VectorInfoDef> pVectorInfoList)
{
return pVectorInfoList.Exists(A => pRect.FromX <= A.ToX && A.FromX <= pRect.ToX
&& pRect.FromY <= A.ToY && A.FromY <= pRect.ToY);
}
//枝切り
static bool WillEdakiri(List<VectorInfoDef> pVectorInfoList)
{
if (pVectorInfoList.Exists(A => A.RectName == 'N' && A.FromX == 0 && A.FromY == 0))
return true;
if (pVectorInfoList.Exists(A => A.RectName == 'O' && A.FromX == 0 && A.FromY == 0))
return true;
int wkInd1 = pVectorInfoList.FindIndex(A => A.FromX == 0 && A.FromY == 0);
int wkInd2 = pVectorInfoList.FindIndex(A => A.ToX == UB && A.FromY == 0);
int wkInd3 = pVectorInfoList.FindIndex(A => A.FromX == 0 && A.ToY == UB);
//左右対称解の除外で、左上の長方形 < 右上の長方形
if (wkInd1 >= 0 && wkInd2 >= 0) {
if (pVectorInfoList[wkInd1].RectName > pVectorInfoList[wkInd2].RectName)
return true;
}
//回転解の除外で、右上の長方形 < 左下の長方形
if (wkInd2 >= 0 && wkInd3 >= 0) {
if (pVectorInfoList[wkInd2].RectName > pVectorInfoList[wkInd3].RectName)
return true;
}
//最小の長方形でも、UB超えするなら枝切り
if (pVectorInfoList.Exists(A => A.ToX != UB && A.ToX + (13 - 1) > UB))
return true;
if (pVectorInfoList.Exists(A => A.ToY != UB && A.ToY + (13 - 1) > UB))
return true;
return false;
}
//長方形を配置した2次元配列を返す
static char[,] DeriveBanArr(List<VectorInfoDef> pVectorInfoList)
{
char[,] WillReturn = new char[UB + 1, UB + 1];
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
WillReturn[X, Y] = ' ';
}
}
foreach (VectorInfoDef EachVectorInfo in pVectorInfoList) {
for (int X = EachVectorInfo.FromX; X <= EachVectorInfo.ToX; X++) {
for (int Y = EachVectorInfo.FromY; Y <= EachVectorInfo.ToY; Y++) {
WillReturn[X, Y] = EachVectorInfo.RectName;
}
}
}
return WillReturn;
}
//回転した解を除外
static void RemoveKaitenKai(List<char[,]> pAnswerKouhoArrList)
{
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 = pAnswerKouhoArrList[pCurrInd][X, Y];
if (pAnswerKouhoArrList[I][UB - X, Y] != CurrVal) IsOK1 = true;
if (pAnswerKouhoArrList[I][UB - X, UB - Y] != CurrVal) IsOK2 = true;
if (pAnswerKouhoArrList[I][X, UB - Y] != CurrVal) IsOK3 = true;
if (pAnswerKouhoArrList[I][Y, X] != CurrVal) IsOK4 = true;
if (pAnswerKouhoArrList[I][UB - Y, X] != CurrVal) IsOK5 = true;
if (pAnswerKouhoArrList[I][UB - Y, UB - X] != CurrVal) IsOK6 = true;
if (pAnswerKouhoArrList[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 = pAnswerKouhoArrList.Count - 1; I >= 0; I--) {
if (IsExist(I)) pAnswerKouhoArrList.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());
}
}