using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
//ピースごとの配置候補
static Dictionary<char, List<bool[,]>> HaitiKouhoListDict =
new Dictionary<char, List<bool[,]>>();
static char[] PieceNameArr = { 'b', 'i', 'l', 'o',
'L', 'N', 'P', 'U',
'V', 'W', 'X', 'Y' };
static int UB_X;
static int UB_Y;
struct JyoutaiDef
{
internal char[,] BanArr;
internal int CurrX;
internal int CurrY;
}
static void Main()
{
char[,] Q1Arr = {{'W','W','Y','Y','Y','Y','L','L','L','L'},
{' ','W','W','U','Y','U','?','?','?','L'},
{' ',' ','W','U','U','U','?','?','?','?'},
{' ',' ',' ','?','?','?','?','?','?','?'},
{' ',' ',' ',' ','?','?','?','?','?','?'},
{' ',' ',' ',' ',' ','?','?','?','?','?'},
{' ',' ',' ',' ',' ',' ','?','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ',' ','?'}};
char[,] Q2Arr = {{'L','L','L','L','P','P','P','N','N','N'},
{' ','?','?','L','P','P','N','N','U','U'},
{' ',' ','?','?','?','?','?','?','?','U'},
{' ',' ',' ','?','?','?','?','?','U','U'},
{' ',' ',' ',' ','?','?','?','?','?','?'},
{' ',' ',' ',' ',' ','?','?','?','?','?'},
{' ',' ',' ',' ',' ',' ','?','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ',' ','?'}};
char[,] Q3Arr = {{'?','?','?','i','i','i','i','N','N','N'},
{' ','?','?','?','?','?','N','N','U','U'},
{' ',' ','?','?','?','?','?','?','?','U'},
{' ',' ',' ','?','?','?','?','?','U','U'},
{' ',' ',' ',' ','?','?','?','?','?','?'},
{' ',' ',' ',' ',' ','?','?','?','?','?'},
{' ',' ',' ',' ',' ',' ','?','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ',' ','?'}};
char[,] Q4Arr = {{'?','?','?','?','P','P','i','l','l','l'},
{' ','?','?','?','P','P','i','?','?','l'},
{' ',' ','?','?','?','P','i','?','?','?'},
{' ',' ',' ','?','?','?','i','?','?','?'},
{' ',' ',' ',' ','?','?','?','?','?','?'},
{' ',' ',' ',' ',' ','?','?','?','?','?'},
{' ',' ',' ',' ',' ',' ','?','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ',' ','?'}};
char[,] Q5Arr = {{'i','i','i','i','P','P','P','N','N','N'},
{' ','?','?','?','P','P','N','N','?','?'},
{' ',' ','?','?','?','?','?','?','?','?'},
{' ',' ',' ','?','?','?','?','?','?','?'},
{' ',' ',' ',' ','?','?','?','?','?','?'},
{' ',' ',' ',' ',' ','?','?','?','?','?'},
{' ',' ',' ',' ',' ',' ','?','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ',' ','?'}};
char[,] Q6Arr = {{'?','?','?','?','?','N','N','N','P','P'},
{' ','?','?','?','N','N','?','P','P','P'},
{' ',' ','?','?','?','?','?','?','?','?'},
{' ',' ',' ','?','?','?','?','?','?','?'},
{' ',' ',' ',' ','?','?','?','?','?','?'},
{' ',' ',' ',' ',' ','?','?','?','?','?'},
{' ',' ',' ',' ',' ',' ','?','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ',' ','?'}};
char[,] Q7Arr = {{'?','?','?','?','?','l','l','V','V','V'},
{' ','?','?','?','?','l','U','U','U','V'},
{' ',' ','?','?','?','l','U','?','U','V'},
{' ',' ',' ','?','?','?','?','?','?','?'},
{' ',' ',' ',' ','?','?','?','?','?','?'},
{' ',' ',' ',' ',' ','?','?','?','?','?'},
{' ',' ',' ',' ',' ',' ','?','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ',' ','?'}};
char[,] Q8Arr = {{'?','?','?','?','?','?','L','l','l','l'},
{' ','?','?','?','?','?','L','?','?','l'},
{' ',' ','?','?','?','?','L','?','?','?'},
{' ',' ',' ','?','?','L','L','?','?','?'},
{' ',' ',' ',' ','?','?','?','?','?','?'},
{' ',' ',' ',' ',' ','?','?','?','?','?'},
{' ',' ',' ',' ',' ',' ','?','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ','?','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ','?','?'},
{' ',' ',' ',' ',' ',' ',' ',' ',' ','?'}};
char[,] WkArr = Q1Arr;
UB_X = WkArr.GetUpperBound(1);
UB_Y = WkArr.GetUpperBound(0);
char[,] QuestionArr = new char[UB_X + 1, UB_Y + 1];
for (int X = 0; X <= UB_X; X++)
for (int Y = 0; Y <= UB_Y; Y++)
QuestionArr[X, Y] = WkArr[Y, X];
foreach (char AnyPiece in PieceNameArr) {
HaitiKouhoListDict[AnyPiece] = DeriveHaitiKouhoList(AnyPiece);
}
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.BanArr = QuestionArr;
WillPush.CurrX = WillPush.CurrY = 0;
stk.Push(WillPush);
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//クリア判定
if (Popped.BanArr.Cast<char>().All(X => X != '?')) {
Console.WriteLine("解を発見");
PrintAnswer(Popped.BanArr);
return;
}
//X座標の繰上げ処理
if (Popped.CurrX > UB_X) {
Popped.CurrX = 0;
Popped.CurrY++;
}
//最終行を超えた場合
if (Popped.CurrY > UB_Y) continue;
//使用済のピース名の配列
char[] UsedPieceArr = Popped.BanArr.Cast<char>().Distinct().ToArray();
foreach (char AnyPiece in PieceNameArr) {
if (Array.IndexOf(UsedPieceArr, AnyPiece) >= 0) continue;
//ピースの配置候補リスト
List<bool[,]> HaitiKouhoList = new List<bool[,]>();
HaitiKouhoList.AddRange(HaitiKouhoListDict[AnyPiece]);
//現在のマス目が空きマスの場合は、マス目を埋める必要あり
if (Popped.BanArr[Popped.CurrX, Popped.CurrY] == '?') {
HaitiKouhoList.RemoveAll(X => X[0, 0] == false);
}
//マス目にピースを埋めれない候補をRemove
HaitiKouhoList.RemoveAll(X =>
CanFillPiece(X, Popped.CurrX, Popped.CurrY, Popped.BanArr) == false);
//ピースを配置する経路のPush処理
foreach (bool[,] AnyPieceMap in HaitiKouhoList) {
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
if (AnyPiece == 'b' || AnyPiece == 'V' ||
AnyPiece == 'o' || AnyPiece == 'W')
WillPush.CurrX = Popped.CurrX;
else WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
for (int X = 0; X <= AnyPieceMap.GetUpperBound(0); X++) {
for (int Y = 0; Y <= AnyPieceMap.GetUpperBound(1); Y++) {
if (AnyPieceMap[X, Y] == false) continue;
WillPush.BanArr[Popped.CurrX + X, Popped.CurrY + Y] = AnyPiece;
}
}
stk.Push(WillPush);
}
}
//現在のマス目が空きマスでない場合は、ピースを配置しない経路のPush
if (Popped.BanArr[Popped.CurrX, Popped.CurrY] != '?') {
WillPush.BanArr = Popped.BanArr;
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
stk.Push(WillPush);
}
}
}
//ピース名を引数として、回転させた配置のListを返す
static List<bool[,]> DeriveHaitiKouhoList(char pPieceName)
{
bool[,] wkArr = null;
//■
//■■
if (pPieceName == 'b') {
wkArr = new bool[2, 2];
wkArr[0, 0] = true; wkArr[1, 0] = false;
wkArr[0, 1] = wkArr[1, 1] = true;
}
//■
//■
//■
//■
if (pPieceName == 'i') {
wkArr = new bool[1, 4];
wkArr[0, 0] = true;
wkArr[0, 1] = true;
wkArr[0, 2] = true;
wkArr[0, 3] = true;
}
//■
//■
//■■
if (pPieceName == 'l') {
wkArr = new bool[2, 3];
wkArr[0, 0] = true; wkArr[1, 0] = false;
wkArr[0, 1] = true; wkArr[1, 1] = false;
wkArr[0, 2] = wkArr[1, 2] = true;
}
//■■
//■■
if (pPieceName == 'o') {
wkArr = new bool[2, 2];
wkArr[0, 0] = wkArr[1, 0] = true;
wkArr[0, 1] = wkArr[1, 1] = true;
}
//■
//■
//■
//■■
if (pPieceName == 'L') {
wkArr = new bool[2, 4];
wkArr[0, 0] = true; wkArr[1, 0] = false;
wkArr[0, 1] = true; wkArr[1, 1] = false;
wkArr[0, 2] = true; wkArr[1, 2] = false;
wkArr[0, 3] = wkArr[1, 3] = true;
}
// ■
//■■
//■
//■
if (pPieceName == 'N') {
wkArr = new bool[2, 4];
wkArr[0, 0] = false; wkArr[1, 0] = true;
wkArr[0, 1] = wkArr[1, 1] = true;
wkArr[0, 2] = true; wkArr[1, 2] = false;
wkArr[0, 3] = true; wkArr[1, 3] = false;
}
// ■
//■■
//■■
if (pPieceName == 'P') {
wkArr = new bool[2, 3];
wkArr[0, 0] = false; wkArr[1, 0] = true;
wkArr[0, 1] = wkArr[1, 1] = true;
wkArr[0, 2] = wkArr[1, 2] = true;
}
//■ ■
//■■■
if (pPieceName == 'U') {
wkArr = new bool[3, 2];
wkArr[0, 0] = true; wkArr[1, 0] = false; wkArr[2, 0] = true;
wkArr[0, 1] = wkArr[1, 1] = wkArr[2, 1] = true;
}
//■
//■
//■■■
if (pPieceName == 'V') {
wkArr = new bool[3, 3];
wkArr[0, 0] = true; wkArr[1, 0] = wkArr[2, 0] = false;
wkArr[0, 1] = true; wkArr[1, 1] = wkArr[2, 1] = false;
wkArr[0, 2] = wkArr[1, 2] = wkArr[2, 2] = true;
}
//■
//■■
// ■■
if (pPieceName == 'W') {
wkArr = new bool[3, 3];
wkArr[0, 0] = true; wkArr[1, 0] = wkArr[2, 0] = false;
wkArr[0, 1] = wkArr[1, 1] = true; wkArr[2, 1] = false;
wkArr[0, 2] = false; wkArr[1, 2] = wkArr[2, 2] = true;
}
// ■
//■■■
// ■
if (pPieceName == 'X') {
wkArr = new bool[3, 3];
wkArr[0, 0] = false; wkArr[1, 0] = true; wkArr[2, 0] = false;
wkArr[0, 1] = wkArr[1, 1] = wkArr[2, 1] = true;
wkArr[0, 2] = false; wkArr[1, 2] = true; wkArr[2, 2] = false;
}
// ■
//■■
// ■
// ■
if (pPieceName == 'Y') {
wkArr = new bool[2, 4];
wkArr[0, 0] = false; wkArr[1, 0] = true;
wkArr[0, 1] = wkArr[1, 1] = true;
wkArr[0, 2] = false; wkArr[1, 2] = true;
wkArr[0, 3] = false; wkArr[1, 3] = true;
}
return DeriveKaitenArrList(wkArr);
}
//配列を引数として、回転させた配列のリストをDistinctして返す
static List<bool[,]> DeriveKaitenArrList(bool[,] pBaseArr)
{
var KaitenArrList = new List<bool[,]>();
//1個目はそのまま
//■
//■■■
//2個目は1個目を時計回りに90度回転
//■■
//■
//■
//3個目は2個目を時計回りに90度回転
//■■■
// ■
//4個目は3個目を時計回りに90度回転
// ■
// ■
//■■
//5個目は1個目とX軸で線対称
//■■■
//■
//6個目は5個目を時計回りに90度回転
//■■
// ■
// ■
//7個目は6個目を時計回りに90度回転
// ■
//■■■
//8個目は7個目を時計回りに90度回転
//■
//■
//■■
int BaseArrUB_X = pBaseArr.GetUpperBound(0);
int BaseArrUB_Y = pBaseArr.GetUpperBound(1);
for (int I = 1; I <= 8; I++) KaitenArrList.Add(null);
for (int P = 0; P <= 6; P += 2) KaitenArrList[P] = new bool[BaseArrUB_X + 1, BaseArrUB_Y + 1];
for (int P = 1; P <= 7; P += 2) KaitenArrList[P] = new bool[BaseArrUB_Y + 1, BaseArrUB_X + 1];
for (int X = 0; X <= BaseArrUB_X; X++) {
for (int Y = 0; Y <= BaseArrUB_Y; Y++) {
bool SetVal = pBaseArr[X, Y];
KaitenArrList[0][X, Y] = SetVal;
KaitenArrList[1][Y, BaseArrUB_X - X] = SetVal;
KaitenArrList[2][BaseArrUB_X - X, BaseArrUB_Y - Y] = SetVal;
KaitenArrList[3][BaseArrUB_Y - Y, X] = SetVal;
KaitenArrList[4][X, BaseArrUB_Y - Y] = SetVal;
KaitenArrList[5][BaseArrUB_Y - Y, BaseArrUB_X - X] = SetVal;
KaitenArrList[6][BaseArrUB_X - X, Y] = SetVal;
KaitenArrList[7][Y, X] = SetVal;
}
}
//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<bool> wkEnum1 = KaitenArrList[I].Cast<bool>();
IEnumerable<bool> wkEnum2 = KaitenArrList[J].Cast<bool>();
if (wkEnum1.SequenceEqual(wkEnum2) == false) continue;
KaitenArrList.RemoveAt(I);
break;
}
}
return KaitenArrList;
}
//マス目にピースを埋めれるか
static bool CanFillPiece(bool[,] pPieceMap, int pTargetX, int pTargetY, char[,] pBanArr)
{
for (int X = 0; X <= pPieceMap.GetUpperBound(0); X++) {
if (pTargetX + X > UB_X) return false;
for (int Y = 0; Y <= pPieceMap.GetUpperBound(1); Y++) {
if (pTargetY + Y > UB_Y) return false;
if (pPieceMap[X, Y] && 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; Y++) {
for (int X = 0; X <= UB_X; X++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
12ピースは下記となります。 各ピースは回転や裏返しても使えます。 トロミノがb テトロミノがilo ペントミノがLNPUVWXY となります。 ■ ■ ■ ■■ ■■ ■ ■ ■■ ■ ■■ ■ ■ ■ ■■ ■ ■ ■ ■ ■■ ■■■ ■ ■■ ■ ■■ ■ ■ ■ ■ ■ ■ ■■ ■■■ ■■ ■■■ ■■ ■ ■ ■ Q1 Q2 Q3 Q4 WWYYYYLLLL LLLLPPPNNN ???iiiiNNN ????PPilll WWUYU???L ??LPPNNUU ?????NNUU ???PPi??l WUUU???? ???????U ???????U ???Pi??? ??????? ?????UU ?????UU ???i??? ?????? ?????? ?????? ?????? ????? ????? ????? ????? ???? ???? ???? ???? ??? ??? ??? ??? ?? ?? ?? ?? ? ? ? ? Q5 Q6 Q7 Q8 iiiiPPPNNN ?????NNNPP ?????llVVV ??????Llll ???PPNN?? ???NN?PPP ????lUUUV ?????L??l ???????? ???????? ???lU?UV ????L??? ??????? ??????? ??????? ??LL??? ?????? ?????? ?????? ?????? ????? ????? ????? ????? ???? ???? ???? ???? ??? ??? ??? ??? ?? ?? ?? ?? ? ? ? ?