using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int mQuestionNo = 5;
static char[,] mQuestionArr; //問題の初期盤面
static Dictionary<char, int> mUsePieceDict = new Dictionary<char, int>(); //使用するピース
const int UB_X = 6;
const int UB_Y = 2;
//ピースごとの配置候補
static Dictionary<char, List<bool[,]>> HaitiKouhoListDict =
new Dictionary<char, List<bool[,]>>();
static char[] PieceNameArr = { '橙', '黄', '水' };
//問題を定義
static void QuestionDef()
{
string[] wkStrArr = null;
if (mQuestionNo == 1) {
wkStrArr = new string[] {"□□□□□□□",
"□□赤□□□□",
"□□赤□□□□"};
mUsePieceDict.Add('橙', 1);
}
if (mQuestionNo == 2) {
wkStrArr = new string[] {"□□□赤□□□",
"赤□□赤□□□",
"赤□□赤□□□"};
mUsePieceDict.Add('黄', 1);
mUsePieceDict.Add('水', 1);
}
if (mQuestionNo == 3) {
wkStrArr = new string[] {"□赤□□赤□□",
"□赤□□赤□□",
"□□□赤赤□□"};
mUsePieceDict.Add('橙', 2);
mUsePieceDict.Add('水', 1);
}
if (mQuestionNo == 4) {
wkStrArr = new string[] {"□赤□□□□□",
"□赤赤赤□□赤",
"□赤□□□□□"};
mUsePieceDict.Add('黄', 2);
mUsePieceDict.Add('水', 2);
}
if (mQuestionNo == 5) {
wkStrArr = new string[] {"□□赤□□□□",
"□赤赤□□赤赤",
"□□赤□□□□"};
mUsePieceDict.Add('黄', 2);
mUsePieceDict.Add('水', 2);
}
mQuestionArr = new char[UB_X + 1, UB_Y + 1];
for (int Y = 0; Y <= UB_Y; Y++)
for (int X = 0; X <= UB_X; X++)
mQuestionArr[X, Y] = wkStrArr[Y][X];
}
struct JyoutaiDef
{
internal int CurrX;
internal int CurrY;
internal char[,] BanArr;
internal Dictionary<char, int> RestPieceDict;
}
static void Main()
{
foreach (char EachPiece in PieceNameArr) {
HaitiKouhoListDict[EachPiece] = DeriveHaitiKouhoList(EachPiece);
}
//問題を定義
QuestionDef();
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrX = 0;
WillPush.CurrY = 0;
WillPush.BanArr = mQuestionArr;
WillPush.RestPieceDict = mUsePieceDict;
Stk.Push(WillPush);
int AnswerCnt = 0;
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
//クリア判定
if (Popped.RestPieceDict.Count == 0) {
if (IsClear(Popped.BanArr)) {
Console.WriteLine("解{0}を発見", ++AnswerCnt);
PrintAnswer(Popped.BanArr);
}
continue;
}
//X座標の繰上げ処理
if (Popped.CurrX > UB_X) {
Popped.CurrX = 0;
Popped.CurrY++;
}
//最終行を超えた場合
if (Popped.CurrY > UB_Y) continue;
foreach (char EachPiece in Popped.RestPieceDict.Keys) {
//ピースの配置候補リスト
List<bool[,]> HaitiKouhoList = new List<bool[,]>();
HaitiKouhoList.AddRange(HaitiKouhoListDict[EachPiece]);
//マス目にピースを埋めれない候補をRemove
HaitiKouhoList.RemoveAll(X =>
CanFillPiece(X, Popped.CurrX, Popped.CurrY, Popped.BanArr) == false);
//ピースを配置する経路のPush処理
foreach (bool[,] EachPieceMap in HaitiKouhoList) {
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
WillPush.RestPieceDict = new Dictionary<char, int>(Popped.RestPieceDict);
if (WillPush.RestPieceDict[EachPiece] == 1) {
WillPush.RestPieceDict.Remove(EachPiece);
}
else {
WillPush.RestPieceDict[EachPiece]--;
}
for (int X = 0; X <= EachPieceMap.GetUpperBound(0); X++) {
for (int Y = 0; Y <= EachPieceMap.GetUpperBound(1); Y++) {
if (EachPieceMap[X, Y] == false) continue;
WillPush.BanArr[Popped.CurrX + X, Popped.CurrY + Y] = EachPiece;
}
}
Stk.Push(WillPush);
}
}
//ピースを配置しない経路のPush
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.BanArr = Popped.BanArr;
WillPush.RestPieceDict = Popped.RestPieceDict;
Stk.Push(WillPush);
}
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
int WeightSum = 0;
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
if (pBanArr[X, Y] == '□') continue;
if (X == 0) WeightSum += 3;
if (X == 1) WeightSum += 2;
if (X == 2) WeightSum++;
if (X == 4) WeightSum--;
if (X == 5) WeightSum -= 2;
if (X == 6) WeightSum -= 3;
}
}
return WeightSum == 0;
}
//ピース名を引数として、回転させた配置のListを返す
static List<bool[,]> DeriveHaitiKouhoList(char pPieceName)
{
bool[,] wkArr = null;
//■
if (pPieceName == '橙') {
wkArr = new bool[1, 1];
wkArr[0, 0] = true;
}
//■■
if (pPieceName == '黄') {
wkArr = new bool[2, 1];
wkArr[0, 0] = wkArr[1, 0] = true;
}
//■■■
if (pPieceName == '水') {
wkArr = new bool[3, 1];
wkArr[0, 0] = wkArr[1, 0] = wkArr[2, 0] = true;
}
return DeriveKaitenArrList(wkArr);
}
//配列を引数として、回転させた配列のリストをDistinctして返す
static List<bool[,]> DeriveKaitenArrList(bool[,] pBaseArr)
{
var KaitenArrList = new List<bool[,]>();
//1個目はそのまま
//■
//■■■
//2個目は1個目を時計回りに90度回転
//■■
//■
//■
int BaseArrUB_X = pBaseArr.GetUpperBound(0);
int BaseArrUB_Y = pBaseArr.GetUpperBound(1);
for (int I = 1; I <= 2; I++) KaitenArrList.Add(null);
KaitenArrList[0] = new bool[BaseArrUB_X + 1, BaseArrUB_Y + 1];
KaitenArrList[1] = 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;
}
}
//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)
{
if (pTargetX + pPieceMap.GetUpperBound(0) > UB_X) return false;
if (pTargetY + pPieceMap.GetUpperBound(1) > UB_Y) return false;
for (int X = 0; X <= pPieceMap.GetUpperBound(0); X++) {
for (int Y = 0; Y <= pPieceMap.GetUpperBound(1); Y++) {
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());
}
}
初期配置で豆がいくつか配置されてます。 下記のように列ごとに、重さが0から3まであり 長方形の左側の豆がいる座標の重さ合計と 長方形の右側の豆がいる座標の重さ合計が 等しくなる敷き詰めを行えばクリアです。 ３２１０１２３ □□□□□□□ □□□□□□□ □□□□□□□ 赤色は1単位から3単位 橙色は1単位 黄色は2単位 水色は3単位 です。 Q1 (Easyの1) □□□□□□□ □□赤□□□□ □□赤□□□□ 敷き詰めピースは、橙色が1ピース Q2 (Easyの6) □□□赤□□□ 赤□□赤□□□ 赤□□赤□□□ 敷き詰めピースは、黄色が1ピース、水色が1ピース Q3 (Hardの24) □赤□□赤□□ □赤□□赤□□ □□□赤赤□□ 敷き詰めピースは、橙色が2ピース、水色が1ピース Q4 (SuperHardの31) □赤□□□□□ □赤赤赤□□赤 □赤□□□□□ 敷き詰めピースは、黄色が2ピース、水色が2ピース Q5 (SuperHardの40) □□赤□□□□ □赤赤□□赤赤 □□赤□□□□ 敷き詰めピースは、黄色が2ピース、水色が2ピース