using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
//ピースごとの配置候補
static Dictionary<char, List<char[,]>> HaitiKouhoListDict =
new Dictionary<char, List<char[,]>>();
static char[] PieceNameArr = { 'A', 'B', 'C', 'D',
'E', 'F', 'G', 'H' };
const int UB = 4 - 1;
struct JyoutaiDef
{
internal char[,] YajirusiArr;
internal char[,] PieceNameArr;
internal int CurrX;
internal int CurrY;
}
static void Main()
{
foreach (char EachPiece in PieceNameArr) {
HaitiKouhoListDict[EachPiece] = DeriveHaitiKouhoList(EachPiece);
}
//回転解を除外(ピースAは回転させない)
HaitiKouhoListDict['A'].RemoveRange(1, HaitiKouhoListDict['A'].Count - 1);
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.YajirusiArr = new char[UB + 1, UB + 1];
WillPush.PieceNameArr = new char[UB + 1, UB + 1];
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
WillPush.YajirusiArr[X, Y] = ' ';
WillPush.PieceNameArr[X, Y] = ' ';
}
}
WillPush.CurrX = WillPush.CurrY = 0;
stk.Push(WillPush);
int AnwserCnt = 0;
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//クリア判定
if (Popped.YajirusiArr.Cast<char>().All(X => X != ' ')) {
Console.WriteLine("解{0}を発見", ++AnwserCnt);
PrintAnswer(Popped.PieceNameArr);
PrintAnswer(Popped.YajirusiArr);
continue;
}
//X座標の繰上げ処理
if (Popped.CurrX > UB) {
Popped.CurrX = 0;
Popped.CurrY++;
}
//最終行を超えた場合
if (Popped.CurrY > UB) continue;
//使用済のピース名の配列
char[] UsedPieceArr = Popped.PieceNameArr.Cast<char>().Distinct().ToArray();
foreach (char EachPiece in PieceNameArr) {
if (Array.IndexOf(UsedPieceArr, EachPiece) >= 0) continue;
//対称解の除外で、Aは左半分にのみ配置可
if (EachPiece == 'A' && Popped.CurrX >= 2) continue;
//ピースの配置候補リスト
List<char[,]> HaitiKouhoList = new List<char[,]>();
HaitiKouhoList.AddRange(HaitiKouhoListDict[EachPiece]);
//マス目にピースを埋めれない候補をRemove
HaitiKouhoList.RemoveAll(X =>
CanFillPiece(X, Popped.CurrX, Popped.CurrY, Popped.YajirusiArr) == false);
//ピースを配置する経路のPush処理
foreach (char[,] EachYajirusiArr in HaitiKouhoList) {
WillPush.YajirusiArr = (char[,])Popped.YajirusiArr.Clone();
WillPush.PieceNameArr = (char[,])Popped.PieceNameArr.Clone();
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
for (int X = 0; X <= EachYajirusiArr.GetUpperBound(0); X++) {
for (int Y = 0; Y <= EachYajirusiArr.GetUpperBound(1); Y++) {
WillPush.YajirusiArr[Popped.CurrX + X, Popped.CurrY + Y] =
EachYajirusiArr[X, Y];
WillPush.PieceNameArr[Popped.CurrX + X, Popped.CurrY + Y] =
EachPiece;
}
}
if (IsValid(WillPush.YajirusiArr))
stk.Push(WillPush);
}
}
//現在のマス目が空白でない場合は、ピースを配置しない経路のPush
if (Popped.YajirusiArr[Popped.CurrX, Popped.CurrY] != ' ') {
WillPush.YajirusiArr = Popped.YajirusiArr;
WillPush.PieceNameArr = Popped.PieceNameArr;
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
stk.Push(WillPush);
}
}
}
//ピース名を引数として、回転させた配置のListを返す
static List<char[,]> DeriveHaitiKouhoList(char pPieceName)
{
char[,] wkArr = new char[1, 2];
if (pPieceName == 'A') {
wkArr[0, 0] = '→';
wkArr[0, 1] = '↓';
}
if (pPieceName == 'B') {
wkArr[0, 0] = '→';
wkArr[0, 1] = '←';
}
if (pPieceName == 'C') {
wkArr[0, 0] = '→';
wkArr[0, 1] = '↑';
}
if (pPieceName == 'D') {
wkArr[0, 0] = '↓';
wkArr[0, 1] = '↑';
}
if (pPieceName == 'E') {
wkArr[0, 0] = '↓';
wkArr[0, 1] = '→';
}
if (pPieceName == 'F') {
wkArr[0, 0] = '←';
wkArr[0, 1] = '→';
}
if (pPieceName == 'G') {
wkArr[0, 0] = '↑';
wkArr[0, 1] = '→';
}
if (pPieceName == 'H') {
wkArr[0, 0] = '↑';
wkArr[0, 1] = '↓';
}
return DeriveKaitenArrList(wkArr);
}
//配列を引数として、回転させた配列のリストをDistinctして返す
static List<char[,]> DeriveKaitenArrList(char[,] pBaseArr)
{
var KaitenArrList = new List<char[,]>();
KaitenArrList.Add(pBaseArr);
char[,] wkArr2 = new char[2, 1];
wkArr2[0, 0] = DeriveKaitenYajirusi(pBaseArr[0, 1], 1);
wkArr2[1, 0] = DeriveKaitenYajirusi(pBaseArr[0, 0], 1);
KaitenArrList.Add(wkArr2);
char[,] wkArr3 = new char[1, 2];
wkArr3[0, 0] = DeriveKaitenYajirusi(pBaseArr[0, 1], 2);
wkArr3[0, 1] = DeriveKaitenYajirusi(pBaseArr[0, 0], 2);
KaitenArrList.Add(wkArr3);
char[,] wkArr4 = new char[2, 1];
wkArr4[0, 0] = DeriveKaitenYajirusi(pBaseArr[0, 0], 3);
wkArr4[1, 0] = DeriveKaitenYajirusi(pBaseArr[0, 1], 3);
KaitenArrList.Add(wkArr4);
//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<char> wkEnum1 = KaitenArrList[I].Cast<char>();
IEnumerable<char> wkEnum2 = KaitenArrList[J].Cast<char>();
if (wkEnum1.SequenceEqual(wkEnum2) == false) continue;
KaitenArrList.RemoveAt(I);
break;
}
}
return KaitenArrList;
}
//矢印と90度の回転回数を引数として、回転後の矢印を返す
static char DeriveKaitenYajirusi(char pBaseYajirusi, int pKaitenCnt)
{
Func<char, char> KaitenFunc = pChar =>
{
if (pChar == '↑') return '→';
if (pChar == '→') return '↓';
if (pChar == '↓') return '←';
return '↑';
};
char WillReturn = pBaseYajirusi;
for (int I = 1; I <= pKaitenCnt; I++) {
WillReturn = KaitenFunc(WillReturn);
}
return WillReturn;
}
//有効な盤面かを判定
static bool IsValid(char[,] pYajirusiArr)
{
//横チェック
for (int Y = 0; Y <= UB; Y++)
if (IsValidHelper(pYajirusiArr, 0, Y, 1, Y, 2, Y, 3, Y) == false) return false;
//縦チェック
for (int X = 0; X <= UB; X++)
if (IsValidHelper(pYajirusiArr, X, 0, X, 1, X, 2, X, 3) == false) return false;
//斜めチェック
if (IsValidHelper(pYajirusiArr, 0, 0, 1, 1, 2, 2, 3, 3) == false) return false;
if (IsValidHelper(pYajirusiArr, 0, 3, 1, 2, 2, 1, 3, 0) == false) return false;
return true;
}
//有効な盤面かを判定
static bool IsValidHelper(char[,] pYajirusiArr,
int pX1, int pY1, int pX2, int pY2,
int pX3, int pY3, int pX4, int pY4)
{
var YajirusiList = new List<char>();
YajirusiList.Add(pYajirusiArr[pX1, pY1]);
YajirusiList.Add(pYajirusiArr[pX2, pY2]);
YajirusiList.Add(pYajirusiArr[pX3, pY3]);
YajirusiList.Add(pYajirusiArr[pX4, pY4]);
YajirusiList.RemoveAll(X => X == ' ');
//重複した矢印がないこと
return YajirusiList.Count == YajirusiList.Distinct().Count();
}
//マス目にピースを埋めれるか
static bool CanFillPiece(char[,] pPieceMap, int pTargetX, int pTargetY, char[,] pBanArr)
{
for (int X = 0; X <= pPieceMap.GetUpperBound(0); X++) {
if (pTargetX + X > UB) return false;
for (int Y = 0; Y <= pPieceMap.GetUpperBound(1); Y++) {
if (pTargetY + Y > UB) return false;
if (pBanArr[pTargetX + X, pTargetY + Y] != ' ')
return false;
}
}
return true;
}
//解を出力
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++) {
char CurrChar = pBanArr[X, Y];
if ('A' <= CurrChar && CurrChar <= 'H')
CurrChar = (char)('Ａ' + CurrChar - 'A');
sb.Append(CurrChar);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}