using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 8 - 1;
static char[] PieceNameArr = { 'i', 'F', 'I', 'L', 'N', 'P',
'T', 'U', 'V', 'W', 'Y', 'Z'};
//iテトロミノの配置候補
static List<char[,]> HaitiKouhoListB2W2;
//ピースごとの配置候補(黒2白3)
static Dictionary<char, List<char[,]>> HaitiKouhoListDictB2W3 =
new Dictionary<char, List<char[,]>>();
//ピースごとの配置候補(黒3白2)
static Dictionary<char, List<char[,]>> HaitiKouhoListDictB3W2 =
new Dictionary<char, List<char[,]>>();
static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
static void Main()
{
foreach (char EachPiece in PieceNameArr) {
DeriveHaitiKouhoList(EachPiece);
}
//各ペントミノの塗り分けの組み合わせ候補を列挙
List<Dictionary<char, bool>> IsB2W3DictList = DeriveIsB2W3DictList();
for (int I = 0; I <= IsB2W3DictList.Count - 1; I++) {
var sb = new System.Text.StringBuilder();
sb.AppendFormat("{0}個中の{1}個目の候補、", IsB2W3DictList.Count, I + 1);
foreach (var EachPair in IsB2W3DictList[I]) {
if (EachPair.Value == false) continue;
sb.Append(EachPair.Key);
}
sb.AppendFormat("が黒2白3を検証中。経過時間={0}", sw.Elapsed);
Console.WriteLine(sb.ToString());
HasUniqKai(IsB2W3DictList[I]);
}
}
//各ペントミノの塗り分けの組み合わせ候補を列挙
static List<Dictionary<char, bool>> DeriveIsB2W3DictList()
{
var WillReturn = new List<Dictionary<char, bool>>();
char[] KouhoArr = Array.FindAll(PieceNameArr, X => X != 'i');
int KouhoArrUB = KouhoArr.GetUpperBound(0);
Action<int, int, int, int> wkAct = (p1, p2, p3, p4) =>
{
var IsB2W3Dict = new Dictionary<char, bool>();
for (int I = 0; I <= KouhoArrUB; I++) {
if (I == p1 || I == p2 || I == p3 || I == p4) {
IsB2W3Dict.Add(KouhoArr[I], true);
}
else IsB2W3Dict.Add(KouhoArr[I], false);
}
WillReturn.Add(IsB2W3Dict);
};
//B2W3のピースの数をXとすると、黒は32マスなので
//2X+3(11-X)+2+1=32 を解いて X=4
for (int I = 0; I <= KouhoArrUB; I++) {
for (int J = I + 1; J <= KouhoArrUB; J++) {
for (int K = J + 1; K <= KouhoArrUB; K++) {
for (int L = K + 1; L <= KouhoArrUB; L++) {
wkAct(I, J, K, L);
}
}
}
}
return WillReturn;
}
struct JyoutaiDef
{
internal int PieceCnt;
internal int CurrX;
internal int CurrY;
internal char[,] BanArr;
}
//深さ優先探索で敷き詰めが1通りかを判定
static void HasUniqKai(Dictionary<char, bool> pIsB2W3Dict)
{
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.PieceCnt = 1;
WillPush.CurrX = WillPush.CurrY = 0;
foreach (char[,] EachXPentominoHaitiArr in DeriveXPentominoHaitiArrList()) {
WillPush.BanArr = EachXPentominoHaitiArr;
stk.Push(WillPush);
}
var AnswerBanArrList = new List<char[,]>();
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//クリア判定
if (Popped.PieceCnt == 13) {
AnswerBanArrList.Add(Popped.BanArr);
RemoveKaiten(AnswerBanArrList);
if (AnswerBanArrList.Count == 2) {
return;
}
continue;
}
//X座標の繰上げ処理
if (Popped.CurrX > UB) {
Popped.CurrX = 0;
Popped.CurrY++;
}
//最終行を超えた場合
if (Popped.CurrY > UB) continue;
//使用済のピース名の配列
var UsedPieceArr = Popped.BanArr.Cast<char>().Distinct().ToArray();
foreach (char EachPiece in PieceNameArr) {
if (Array.IndexOf(UsedPieceArr, EachPiece) >= 0) continue;
//ピースの配置候補リスト
List<char[,]> HaitiKouhoList = new List<char[,]>();
if (EachPiece == 'i')
HaitiKouhoList.AddRange(HaitiKouhoListB2W2);
else if (pIsB2W3Dict[EachPiece])
HaitiKouhoList.AddRange(HaitiKouhoListDictB2W3[EachPiece]);
else HaitiKouhoList.AddRange(HaitiKouhoListDictB3W2[EachPiece]);
//現在のマス目が空白の場合は、マス目を埋める必要あり
if (Popped.BanArr[Popped.CurrX, Popped.CurrY] == ' ') {
HaitiKouhoList.RemoveAll(X => X[0, 0] == ' ');
}
//マス目にピースを埋めれない候補をRemove
HaitiKouhoList.RemoveAll(X =>
CanFillPiece(X, Popped.CurrX, Popped.CurrY, Popped.BanArr) == false);
//ピースを配置する経路のPush処理
foreach (char[,] EachPieceMap in HaitiKouhoList) {
WillPush.PieceCnt = Popped.PieceCnt + 1;
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
for (int X = 0; X <= EachPieceMap.GetUpperBound(0); X++) {
for (int Y = 0; Y <= EachPieceMap.GetUpperBound(1); Y++) {
if (EachPieceMap[X, Y] == ' ') continue;
WillPush.BanArr[Popped.CurrX + X, Popped.CurrY + Y] = EachPiece;
}
}
stk.Push(WillPush);
}
}
//現在のマス目が空白でない場合は、ピースを配置しない経路のPush
if (Popped.BanArr[Popped.CurrX, Popped.CurrY] != ' ') {
WillPush.PieceCnt = Popped.PieceCnt;
WillPush.BanArr = Popped.BanArr;
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
stk.Push(WillPush);
}
}
if (AnswerBanArrList.Count == 1) {
Console.WriteLine("ユニーク解で、配置は");
PrintBan(AnswerBanArrList[0]);
}
}
//Xペントミノの配置場所を固定して、盤面のListを返す
static List<char[,]> DeriveXPentominoHaitiArrList()
{
var WillReturn = new List<char[,]>();
char[,] wkArr = null;
Action<int, int> SetAct = (pCenterX, pCenterY) =>
{
wkArr = new char[UB + 1, UB + 1];
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
wkArr[X, Y] = ' ';
}
}
wkArr[pCenterX, pCenterY] = 'X';
wkArr[pCenterX, pCenterY - 1] = 'X';
wkArr[pCenterX, pCenterY + 1] = 'X';
wkArr[pCenterX - 1, pCenterY] = 'X';
wkArr[pCenterX + 1, pCenterY] = 'X';
WillReturn.Add(wkArr);
};
SetAct(2, 1); //配置1
SetAct(4, 1); //配置2
SetAct(3, 2); //配置3
SetAct(5, 2); //配置4
SetAct(4, 3); //配置5
return WillReturn;
}
//マス目にピースを埋めれるか
static bool CanFillPiece(char[,] pPieceArr, int pTargetX, int pTargetY, char[,] pBanArr)
{
int pPieceArrUB_X = pPieceArr.GetUpperBound(0);
int pPieceArrUB_Y = pPieceArr.GetUpperBound(1);
if (pTargetX + pPieceArrUB_X > UB) return false;
if (pTargetY + pPieceArrUB_Y > UB) return false;
for (int X = 0; X <= pPieceArrUB_X; X++) {
for (int Y = 0; Y <= pPieceArrUB_Y; Y++) {
if (pPieceArr[X, Y] != ' ' && pBanArr[pTargetX + X, pTargetY + Y] != ' ')
return false;
int wkSum = pTargetX + X + pTargetY + Y;
if (wkSum % 2 == 0) { //和が偶数で黒マスならNG
if (pPieceArr[X, Y] == 'B') return false;
}
else { //和が奇数で白マスならNG
if (pPieceArr[X, Y] == 'W') return false;
}
}
}
return true;
}
//ピース名を引数として、白と黒を決めて、回転させた配置のListを作成
static void DeriveHaitiKouhoList(char pPieceName)
{
bool[,] wkArr = null;
//■■■■
if (pPieceName == 'i') {
wkArr = new bool[4, 1];
wkArr[0, 0] = wkArr[1, 0] = wkArr[2, 0] = wkArr[3, 0] = true;
}
// ■■
//■■
// ■
if (pPieceName == 'F') {
wkArr = new bool[3, 3];
wkArr[0, 0] = false; wkArr[1, 0] = wkArr[2, 0] = true;
wkArr[0, 1] = wkArr[1, 1] = true; wkArr[2, 1] = false;
wkArr[0, 2] = false; wkArr[1, 2] = true; wkArr[2, 2] = false;
}
//■
//■
//■
//■
//■
if (pPieceName == 'I') {
wkArr = new bool[1, 5];
wkArr[0, 0] = true;
wkArr[0, 1] = true;
wkArr[0, 2] = true;
wkArr[0, 3] = true;
wkArr[0, 4] = 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 == 'T') {
wkArr = new bool[3, 3];
wkArr[0, 0] = wkArr[1, 0] = wkArr[2, 0] = true;
wkArr[0, 1] = false; wkArr[1, 1] = true; wkArr[2, 1] = false;
wkArr[0, 2] = false; wkArr[1, 2] = true; wkArr[2, 2] = false;
}
//■ ■
//■■■
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 == '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;
}
//■■
// ■
// ■■
if (pPieceName == 'Z') {
wkArr = new bool[3, 3];
wkArr[0, 0] = wkArr[1, 0] = true; wkArr[2, 0] = false;
wkArr[0, 1] = false; wkArr[1, 1] = true; wkArr[2, 1] = false;
wkArr[0, 2] = false; wkArr[1, 2] = wkArr[2, 2] = true;
}
DeriveKaitenArrList(pPieceName, false, wkArr);
DeriveKaitenArrList(pPieceName, true, wkArr);
}
//回転させた配列のリストをDistinctして作成
static void DeriveKaitenArrList(char pPieceName, bool pIsHidariUeBlack, bool[,] pBaseArr)
{
//iテトロミノの場合は、初期状態の左上が白のみ、候補を作成
if (pPieceName == 'i' && pIsHidariUeBlack)
return;
int wkUB_X = pBaseArr.GetUpperBound(0);
int wkUB_Y = pBaseArr.GetUpperBound(1);
char[,] wkArr = new char[wkUB_X + 1, wkUB_Y + 1];
for (int LoopX = 0; LoopX <= wkUB_X; LoopX++) {
for (int LoopY = 0; LoopY <= wkUB_Y; LoopY++) {
if (pBaseArr[LoopX, LoopY] == false) {
wkArr[LoopX, LoopY] = ' ';
continue;
}
int wkSum = LoopX + LoopY;
if (pIsHidariUeBlack)
wkArr[LoopX, LoopY] = (wkSum % 2 == 0) ? 'B' : 'W';
else
wkArr[LoopX, LoopY] = (wkSum % 2 == 1) ? 'B' : 'W';
}
}
var KaitenArrList = new List<char[,]>();
for (int I = 1; I <= 8; I++) KaitenArrList.Add(null);
for (int P = 0; P <= 6; P += 2) KaitenArrList[P] = new char[wkUB_X + 1, wkUB_Y + 1];
for (int P = 1; P <= 7; P += 2) KaitenArrList[P] = new char[wkUB_Y + 1, wkUB_X + 1];
for (int X = 0; X <= wkUB_X; X++) {
for (int Y = 0; Y <= wkUB_Y; Y++) {
char SetVal = wkArr[X, Y];
KaitenArrList[0][X, Y] = SetVal;
KaitenArrList[1][Y, wkUB_X - X] = SetVal;
KaitenArrList[2][wkUB_X - X, wkUB_Y - Y] = SetVal;
KaitenArrList[3][wkUB_Y - Y, X] = SetVal;
KaitenArrList[4][X, wkUB_Y - Y] = SetVal;
KaitenArrList[5][wkUB_Y - Y, wkUB_X - X] = SetVal;
KaitenArrList[6][wkUB_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<char> wkEnum1 = KaitenArrList[I].Cast<char>();
IEnumerable<char> wkEnum2 = KaitenArrList[J].Cast<char>();
if (wkEnum1.SequenceEqual(wkEnum2) == false) continue;
KaitenArrList.RemoveAt(I);
break;
}
}
int BlackCnt = wkArr.Cast<char>().Count(X => X == 'B');
int WhiteCnt = wkArr.Cast<char>().Count(X => X == 'W');
if (BlackCnt == 2 && WhiteCnt == 2)
HaitiKouhoListB2W2 = KaitenArrList;
if (BlackCnt == 2 && WhiteCnt == 3)
HaitiKouhoListDictB2W3[pPieceName] = KaitenArrList;
if (BlackCnt == 3 && WhiteCnt == 2)
HaitiKouhoListDictB3W2[pPieceName] = KaitenArrList;
}
//回転を除外
static void RemoveKaiten(List<char[,]> pTargetList)
{
const int UB = 8 - 1;
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 = pTargetList[pCurrInd][X, Y];
if (pTargetList[I][UB - X, Y] != CurrVal) IsOK1 = true;
if (pTargetList[I][UB - X, UB - Y] != CurrVal) IsOK2 = true;
if (pTargetList[I][X, UB - Y] != CurrVal) IsOK3 = true;
if (pTargetList[I][Y, X] != CurrVal) IsOK4 = true;
if (pTargetList[I][UB - Y, X] != CurrVal) IsOK5 = true;
if (pTargetList[I][UB - Y, UB - X] != CurrVal) IsOK6 = true;
if (pTargetList[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 = pTargetList.Count - 1; I >= 0; I--) {
if (IsExist(I)) pTargetList.RemoveAt(I);
}
}
//盤面を出力
static void PrintBan(char[,] 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++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
この12種類のペントミノ全てと、 Fig.Aのようなテトロミノ(4個の正方形でできており、Iの形状をしているもの)1個を隙間なく並べ、 8×8の正方形を作ろうと思う。 しかしこのままだと非常に多くの解があるので、各ピースを構成している 正方形を白か黒に塗り分けて、8×8のチェッカーボードを作ることにする。 例として、Fig.Bに完成したチェッカーボードを示す。 実は、この場合、各ピースの白黒の塗り分け方がうまくて、この1通りの解しかない (もちろん全体の回転。裏返し解は除く)。 では、8×8のチェッカーボードが1通りしか作れない、 前記13ピースの白黒の塗り分け方を、Fig.B以外にも見つけてほしい。 なお、各ピースは裏返して使うことができ、色は両面で同じになっている。 また、全体で白と黒を入れ替えた解を防ぐために、 Xペントミノ(十字の形状をしたもの)の真ん中の正方形は黒であるとする。 Fig.A Iテトロミノ
Fig.B 完成したチェッカーボード
