using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
//ピースごとの配置候補
static Dictionary<char, List<int[,]>> HaitiKouhoListDict =
new Dictionary<char, List<int[,]>>();
static char[] PieceNameArr = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
const int UB_X = 3;
const int UB_Y = 2;
struct JyoutaiDef
{
internal int CurrX;
internal int CurrY;
internal int[,] BanArr;
internal List<int[,]> BanArrLog;
internal string[,] PieceArr; //設置したアボロ
}
//各面の状態を表す変数
//状態1 状態2 状態3 状態4 状態9
//* *** *** * ***
//** ** ** ** ***
//*** * * *** ***
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
foreach (char AnyPiece in PieceNameArr) {
HaitiKouhoListDict[AnyPiece] = DeriveHaitiKouhoList(AnyPiece);
}
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrX = WillPush.CurrY = 0;
WillPush.BanArr = new int[UB_X + 1, UB_Y + 1];
WillPush.BanArrLog = new List<int[,]>();
WillPush.PieceArr = new string[UB_X + 1, UB_Y + 1];
for (int X = 0; X <= UB_X; X++)
for (int Y = 0; Y <= UB_Y; Y++)
WillPush.PieceArr[X, Y] = "";
stk.Push(WillPush);
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//クリア判定
if (Popped.BanArr.Cast<int>().All(X => X == 9)) {
Console.WriteLine("解を発見。経過時間={0}", sw.Elapsed);
PrintAnswer(Popped.PieceArr);
Console.WriteLine("アボロの敷き詰めログ");
Popped.BanArrLog.ForEach(A => PrintBan(A));
return;
}
//X座標の繰上げ処理
if (Popped.CurrX > UB_X) {
Popped.CurrX = 0;
Popped.CurrY++;
}
//最終行を超えた場合
if (Popped.CurrY > UB_Y) continue;
//使用済のピース名のSet
var UsedPieceSet = new HashSet<char>();
for (int X = 0; X <= Popped.PieceArr.GetUpperBound(0); X++)
for (int Y = 0; Y <= Popped.PieceArr.GetUpperBound(1); Y++)
UsedPieceSet.UnionWith(Popped.PieceArr[X, Y]);
foreach (char AnyPiece in PieceNameArr) {
if (UsedPieceSet.Contains(AnyPiece)) continue;
//ピースの配置候補リスト
List<int[,]> HaitiKouhoList = new List<int[,]>();
HaitiKouhoList.AddRange(HaitiKouhoListDict[AnyPiece]);
//現在のマス目が埋まってない場合は、マス目を埋める必要あり
if (Popped.BanArr[Popped.CurrX, Popped.CurrY] != 9) {
HaitiKouhoList.RemoveAll(X => X[0, 0] == 0);
}
//UB超えをRemove
HaitiKouhoList.RemoveAll(A => Popped.CurrX + A.GetUpperBound(0) > UB_X);
HaitiKouhoList.RemoveAll(A => Popped.CurrY + A.GetUpperBound(1) > UB_Y);
//ピースを配置する経路のPush処理
foreach (int[,] AnyPieceMap in HaitiKouhoList) {
WillPush.BanArr = (int[,])Popped.BanArr.Clone();
WillPush.PieceArr = (string[,])Popped.PieceArr.Clone();
bool CanFill = true;
//マス目にピースを埋める処理
for (int X = 0; X <= AnyPieceMap.GetUpperBound(0); X++) {
for (int Y = 0; Y <= AnyPieceMap.GetUpperBound(1); Y++) {
if (AnyPieceMap[X, Y] == 0) continue;
CanFill = (ExecFillPiece(Popped.CurrX + X, Popped.CurrY + Y,
AnyPieceMap[X, Y], WillPush.BanArr));
if (CanFill == false) break;
WillPush.PieceArr[Popped.CurrX + X, Popped.CurrY + Y] += AnyPiece;
}
if (CanFill == false) break;
}
if (CanFill) {
WillPush.CurrX = Popped.CurrX;
WillPush.CurrY = Popped.CurrY;
WillPush.BanArrLog = new List<int[,]>();
Popped.BanArrLog.ForEach(A => WillPush.BanArrLog.Add((int[,])A.Clone()));
WillPush.BanArrLog.Add(WillPush.BanArr);
stk.Push(WillPush);
}
}
}
//現在のマス目が埋まっている場合は、ピースを配置しない経路のPush
if (Popped.BanArr[Popped.CurrX, Popped.CurrY] == 9) {
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.BanArr = Popped.BanArr;
WillPush.BanArrLog = Popped.BanArrLog;
WillPush.PieceArr = Popped.PieceArr;
stk.Push(WillPush);
}
}
}
//マス目にピースを埋める、埋めれたかをBool型で返す
static bool ExecFillPiece(int pCurrX, int pCurrY, int pAddKind, int[,] pBanArr)
{
bool WillReturn = false;
int CurrKind = pBanArr[pCurrX, pCurrY];
if (pAddKind == 1) WillReturn = (CurrKind == 0 || CurrKind == 3);
if (pAddKind == 2) WillReturn = (CurrKind == 0 || CurrKind == 4);
if (pAddKind == 3) WillReturn = (CurrKind == 0 || CurrKind == 1);
if (pAddKind == 4) WillReturn = (CurrKind == 0 || CurrKind == 2);
if (pAddKind == 9) WillReturn = (CurrKind == 0);
if (WillReturn == false) return false;
if (pAddKind == 1) pBanArr[pCurrX, pCurrY] = (CurrKind == 0 ? 1 : 9);
if (pAddKind == 2) pBanArr[pCurrX, pCurrY] = (CurrKind == 0 ? 2 : 9);
if (pAddKind == 3) pBanArr[pCurrX, pCurrY] = (CurrKind == 0 ? 3 : 9);
if (pAddKind == 4) pBanArr[pCurrX, pCurrY] = (CurrKind == 0 ? 4 : 9);
if (pAddKind == 9) pBanArr[pCurrX, pCurrY] = 9;
return true;
}
//ピース名を引数として、回転させた配置のListを返す
static List<int[,]> DeriveHaitiKouhoList(char pPieceName)
{
int[,] wkArr = null;
//41
if (pPieceName == 'A') {
wkArr = new int[2, 1];
wkArr[0, 0] = 4; wkArr[1, 0] = 1;
}
//1
//3
if (pPieceName == 'B') {
wkArr = new int[1, 2];
wkArr[0, 0] = 1;
wkArr[0, 1] = 3;
}
//9
if (pPieceName == 'C') {
wkArr = new int[1, 1];
wkArr[0, 0] = 9;
}
//1
//9
if (pPieceName == 'D') {
wkArr = new int[1, 2];
wkArr[0, 0] = 1;
wkArr[0, 1] = 9;
}
//4
//32
if (pPieceName == 'E') {
wkArr = new int[2, 2];
wkArr[0, 0] = 4; wkArr[1, 0] = 0;
wkArr[0, 1] = 3; wkArr[1, 1] = 2;
}
//1
//91
if (pPieceName == 'F') {
wkArr = new int[2, 2];
wkArr[0, 0] = 1; wkArr[1, 0] = 0;
wkArr[0, 1] = 9; wkArr[1, 1] = 1;
}
//11
//32
if (pPieceName == 'G') {
wkArr = new int[2, 2];
wkArr[0, 0] = 1; wkArr[1, 0] = 1;
wkArr[0, 1] = 3; wkArr[1, 1] = 2;
}
//1
//31
// 3
if (pPieceName == 'H') {
wkArr = new int[2, 3];
wkArr[0, 0] = 1; wkArr[1, 0] = 0;
wkArr[0, 1] = 3; wkArr[1, 1] = 1;
wkArr[0, 2] = 0; wkArr[1, 2] = 3;
}
return DeriveKaitenArrList(wkArr);
}
//配列を引数として、回転させた配列のリストをDistinctして返す
static List<int[,]> DeriveKaitenArrList(int[,] pBaseArr)
{
var KaitenArrList = new List<int[,]>();
int[,] wkArr;
//1 そのまま
wkArr = pBaseArr; KaitenArrList.Add((int[,])wkArr.Clone());
//2 右に90度回転
wkArr = Kaiten90do(wkArr); KaitenArrList.Add((int[,])wkArr.Clone());
//3 右に180度回転
wkArr = Kaiten90do(wkArr); KaitenArrList.Add((int[,])wkArr.Clone());
//4 右に270度回転
wkArr = Kaiten90do(wkArr); KaitenArrList.Add((int[,])wkArr.Clone());
//5 左右反転
wkArr = SayuuHanten(wkArr); KaitenArrList.Add((int[,])wkArr.Clone());
//6 右に90度回転
wkArr = Kaiten90do(wkArr); KaitenArrList.Add((int[,])wkArr.Clone());
//7 右に180度回転
wkArr = Kaiten90do(wkArr); KaitenArrList.Add((int[,])wkArr.Clone());
//8 右に270度回転
wkArr = Kaiten90do(wkArr); KaitenArrList.Add((int[,])wkArr.Clone());
//Distinctする
for (int I = KaitenArrList.Count - 1; 0 <= I; I--) {
for (int J = 0; J <= I - 1; J++) {
if (KaitenArrList[I].GetUpperBound(0) !=
KaitenArrList[J].GetUpperBound(0)) continue;
if (KaitenArrList[I].GetUpperBound(1) !=
KaitenArrList[J].GetUpperBound(1)) continue;
IEnumerable<int> wkEnum1 = KaitenArrList[I].Cast<int>();
IEnumerable<int> wkEnum2 = KaitenArrList[J].Cast<int>();
if (wkEnum1.SequenceEqual(wkEnum2) == false) continue;
KaitenArrList.RemoveAt(I);
break;
}
}
return KaitenArrList;
}
//右に90度回転させた盤面を返す
static int[,] Kaiten90do(int[,] pBanArr)
{
int[,] WillReturn = new int[pBanArr.GetUpperBound(1) + 1,
pBanArr.GetUpperBound(0) + 1];
for (int X = 0; X <= WillReturn.GetUpperBound(0); X++) {
for (int Y = 0; Y <= WillReturn.GetUpperBound(1); Y++) {
int wkVal = pBanArr[Y, WillReturn.GetUpperBound(0) - X];
//各面の三角形も90度回転させる
switch (wkVal) {
case 1: wkVal = 2; break;
case 2: wkVal = 3; break;
case 3: wkVal = 4; break;
case 4: wkVal = 1; break;
}
WillReturn[X, Y] = wkVal;
}
}
return WillReturn;
}
//左右反転させた盤面を返す
static int[,] SayuuHanten(int[,] pBanArr)
{
int[,] WillReturn = new int[pBanArr.GetUpperBound(0) + 1,
pBanArr.GetUpperBound(1) + 1];
for (int X = 0; X <= WillReturn.GetUpperBound(0); X++) {
for (int Y = 0; Y <= WillReturn.GetUpperBound(1); Y++) {
int wkVal = pBanArr[WillReturn.GetUpperBound(0) - X, Y];
//各面の三角形も左右反転させる
switch (wkVal) {
case 1: wkVal = 4; break;
case 2: wkVal = 3; break;
case 3: wkVal = 2; break;
case 4: wkVal = 1; break;
}
WillReturn[X, Y] = wkVal;
}
}
return WillReturn;
}
//盤面を出力
static void PrintBan(int[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
if (pBanArr[X, Y] == 0) sb.Append('*');
else sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
//解を出力
static void PrintAnswer(string[,] pPieceArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= pPieceArr.GetUpperBound(1); Y++) {
for (int X = 0; X <= pPieceArr.GetUpperBound(0); X++) {
sb.Append(pPieceArr[X, Y].PadRight(2) + ',');
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
問 全ピースで下図をつくる(ユニーク解)。
