using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
struct PointDef
{
internal int X;
internal int Y;
}
//数値情報の構造体
struct NumInfoDef
{
internal PointDef Point; //数値の座標
internal int IntNum; //数値の値
}
static NumInfoDef[] mNumInfoArr; //数値情報の配列
static char[,] mQuestionArr;
static int UB_X;
static int UB_Y;
//問題を定義
static void QuestionDef()
{
string[] Q01Arr ={"□３□□□１□",
"□□□□□□□",
"２□□１□□□",
"□□□□□□□",
"□１□□２□□",
"□□２□□□□",
"１□□□１□６"};
string[] wkArr = Q01Arr;
UB_X = wkArr[0].Length - 1;
UB_Y = wkArr.GetUpperBound(0);
mQuestionArr = new char[UB_X + 1, UB_Y + 1];
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
mQuestionArr[X, Y] = wkArr[Y][X];
}
}
}
static void Main()
{
//問題を定義
QuestionDef();
//第1フェーズ 数値情報を作成する
CreateNumInfoArr();
//デバッグ用の数値情報を出力
//DebugPrintNumInfo();
//黒マスがB、白マスがW、未確定が半角SPとなる2次元配列
char[,] BlackWhiteArr = new char[UB_X + 1, UB_Y + 1];
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
BlackWhiteArr[X, Y] = ' ';
}
}
//第2フェーズ 初回の確定探索
SyokaiKakuteiTansaku(BlackWhiteArr);
//第3フェーズ 確定探索
ExecKakuteiTansaku(BlackWhiteArr);
//第4フェーズ 確定探索付の深さ優先探索
ExecDFS(BlackWhiteArr);
}
//第1フェーズ 数値情報を作成する
static void CreateNumInfoArr()
{
var NumInfoList = new List<NumInfoDef>();
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
//数値マスでない場合
char CurrVal = mQuestionArr[LoopX, LoopY];
if (CurrVal == '□') continue;
NumInfoDef WillAdd;
PointDef CurrPoint = new PointDef() { X = LoopX, Y = LoopY };
WillAdd.Point = CurrPoint;
if ('１' <= CurrVal && CurrVal <= '９')
WillAdd.IntNum = CurrVal - '０';
else WillAdd.IntNum = CurrVal - 'Ａ' + 10;
NumInfoList.Add(WillAdd);
}
}
mNumInfoArr = NumInfoList.ToArray();
}
//デバッグ用の数値情報を出力
static void DebugPrintNumInfo()
{
for (int I = 0; I <= mNumInfoArr.GetUpperBound(0); I++) {
Console.WriteLine("■■■■■■■■■■■■■");
Console.WriteLine("{0}個目の数値情報", I + 1);
Console.WriteLine("Point=({0},{1})", mNumInfoArr[I].Point.X, mNumInfoArr[I].Point.Y);
Console.WriteLine("数値の値={0}", mNumInfoArr[I].IntNum);
}
}
//第2フェーズ 初回の確定探索
static void SyokaiKakuteiTansaku(char[,] pBlackWhiteArr)
{
//確定探索1 数字のマスは白マスで確定
KakuteiTansaku01(pBlackWhiteArr);
}
//確定探索1 数字のマスは白マスで確定
static void KakuteiTansaku01(char[,] pBlackWhiteArr)
{
foreach (var NumInfoDef in mNumInfoArr) {
PointDef CurrPoint = NumInfoDef.Point;
SetWhite(pBlackWhiteArr, CurrPoint.X, CurrPoint.Y);
}
}
//第3フェーズ 確定探索
static void ExecKakuteiTansaku(char[,] pBlackWhiteArr)
{
while (true) {
char[,] PrevArr = (char[,])pBlackWhiteArr.Clone();
//確定探索2
//白マスと仮定すると、数字が複数存在する島ができる場合、そのマスは黒マス
KakuteiTansaku2(pBlackWhiteArr);
//確定探索3
//どの数字マスからも幅優先探索で到達不能な空白は、黒マスで確定
KakuteiTansaku3(pBlackWhiteArr);
//確定探索4
//黒マスと仮定して、無効な盤面になるなら、そのマスは白マス
KakuteiTansaku4(pBlackWhiteArr);
//確定探索5
//白マスと仮定して、無効な盤面になるなら、そのマスは黒マス
KakuteiTansaku5(pBlackWhiteArr);
//確定探索で確定するマスがなくなったらBreak
if (pBlackWhiteArr.Cast<char>().SequenceEqual(PrevArr.Cast<char>())) {
break;
}
}
}
//確定探索2
//白マスと仮定すると、数字が複数存在する島ができる場合、そのマスは黒マス
static void KakuteiTansaku2(char[,] pBlackWhiteArr)
{
PointDef[] SpaceArr = DeriveColorArr(pBlackWhiteArr, ' ');
foreach (PointDef EachSpace in SpaceArr) {
char[,] CopiedArr = (char[,])pBlackWhiteArr.Clone();
CopiedArr[EachSpace.X, EachSpace.Y] = 'W';
PointDef[] WhiteShimaArr =
ExecUnionFind(CopiedArr, EachSpace.X, EachSpace.Y, 'W', false);
int NumCnt = 0;
foreach (PointDef EachWhite in WhiteShimaArr) {
if (Array.Exists(mNumInfoArr, A => A.Point.X == EachWhite.X
&& A.Point.Y == EachWhite.Y)) {
NumCnt++;
}
}
if (NumCnt >= 2) SetBlack(pBlackWhiteArr, EachSpace.X, EachSpace.Y);
}
}
struct JyoutaiDefBFS
{
internal int CurrX;
internal int CurrY;
internal int Level;
}
//確定探索3
//どの数字マスからも幅優先探索で到達不能な空白は、黒マスで確定
static void KakuteiTansaku3(char[,] pBlackWhiteArr)
{
var VisitedList = new List<PointDef>();
foreach (NumInfoDef EachNumInfo in mNumInfoArr) {
//数字の1なら対象外
if (EachNumInfo.IntNum == 1) continue;
var Queue = new Queue<JyoutaiDefBFS>();
var CurrVisitedList = new List<PointDef>();
JyoutaiDefBFS WillEnqueue;
WillEnqueue.CurrX = EachNumInfo.Point.X;
WillEnqueue.CurrY = EachNumInfo.Point.Y;
WillEnqueue.Level = 1;
Queue.Enqueue(WillEnqueue);
CurrVisitedList.Add(
new PointDef() { X = EachNumInfo.Point.X, Y = EachNumInfo.Point.Y });
while (Queue.Count > 0) {
JyoutaiDefBFS Dequeued = Queue.Dequeue();
//レベル制限
if (Dequeued.Level == EachNumInfo.IntNum) continue;
Action<int, int> EnqueueSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB_X < pNewX) return;
if (pNewY < 0 || UB_Y < pNewY) return;
if (pBlackWhiteArr[pNewX, pNewY] == 'B') return;
//再訪不可
if (CurrVisitedList.Exists(A => A.X == pNewX && A.Y == pNewY))
return;
CurrVisitedList.Add(new PointDef() { X = pNewX, Y = pNewY });
WillEnqueue.CurrX = pNewX;
WillEnqueue.CurrY = pNewY;
WillEnqueue.Level = Dequeued.Level + 1;
Queue.Enqueue(WillEnqueue);
};
EnqueueSyori(Dequeued.CurrX, Dequeued.CurrY - 1);
EnqueueSyori(Dequeued.CurrX, Dequeued.CurrY + 1);
EnqueueSyori(Dequeued.CurrX - 1, Dequeued.CurrY);
EnqueueSyori(Dequeued.CurrX + 1, Dequeued.CurrY);
}
foreach (PointDef EachPoint in CurrVisitedList) {
if (VisitedList.Exists(A => A.X == EachPoint.X && A.Y == EachPoint.Y)) {
continue;
}
VisitedList.Add(EachPoint);
}
}
PointDef[] SpaceArr = DeriveColorArr(pBlackWhiteArr, ' ');
foreach (PointDef EachSpace in SpaceArr) {
if (VisitedList.Exists(A => A.X == EachSpace.X && A.Y == EachSpace.Y))
continue;
SetBlack(pBlackWhiteArr, EachSpace.X, EachSpace.Y);
}
}
//確定探索4
//黒マスと仮定して、無効な盤面になるなら、そのマスは白マス
static void KakuteiTansaku4(char[,] pBlackWhiteArr)
{
PointDef[] SpaceArr = DeriveColorArr(pBlackWhiteArr, ' ');
foreach (PointDef EachSpace in SpaceArr) {
char[,] CopiedArr = (char[,])pBlackWhiteArr.Clone();
SetBlack(CopiedArr, EachSpace.X, EachSpace.Y);
bool WillSetWhite = false;
//白マスが不足する島の有無を返す
if (ExistsHusokuWhiteShima(CopiedArr)) WillSetWhite = true;
//数字のない白マスの島の有無を返す
if (ExistsNonNumShima(CopiedArr)) WillSetWhite = true;
//黒マスの島の分断有無を返す
if (IsBundanBlack(CopiedArr)) WillSetWhite = true;
if (WillSetWhite) SetWhite(pBlackWhiteArr, EachSpace.X, EachSpace.Y);
}
}
//確定探索5
//白マスと仮定して、無効な盤面になるなら、そのマスは黒マス
static void KakuteiTansaku5(char[,] pBlackWhiteArr)
{
PointDef[] SpaceArr = DeriveColorArr(pBlackWhiteArr, ' ');
foreach (PointDef EachSpace in SpaceArr) {
char[,] CopiedArr = (char[,])pBlackWhiteArr.Clone();
SetWhite(CopiedArr, EachSpace.X, EachSpace.Y);
bool WillSetBlack = false;
//黒マスの島の分断有無を返す
if (IsBundanBlack(CopiedArr)) WillSetBlack = true;
//白マスが数字より多い島の有無を返す
if (ExistsTyoukaWhiteShima(CopiedArr)) WillSetBlack = true;
if (WillSetBlack) SetBlack(pBlackWhiteArr, EachSpace.X, EachSpace.Y);
}
}
struct JyoutaiDefDFS
{
internal char[,] BanArr;
internal int CurrInd;
}
//第4フェーズ 確定探索付の深さ優先探索
static void ExecDFS(char[,] pBlackWhiteArr)
{
var Stk = new Stack<JyoutaiDefDFS>();
JyoutaiDefDFS WillPush;
WillPush.BanArr = pBlackWhiteArr;
WillPush.CurrInd = 0;
Stk.Push(WillPush);
while (Stk.Count > 0) {
JyoutaiDefDFS Popped = Stk.Pop();
//クリア判定
bool IsValid;
if (IsClear(Popped.BanArr, out IsValid)) {
Console.WriteLine("解を発見");
PrintBan(Popped.BanArr);
return;
}
if (IsValid == false) continue;
for (int I = Popped.CurrInd; I <= mNumInfoArr.GetUpperBound(0); I++) {
//数字の1なら対象外
if (mNumInfoArr[I].IntNum == 1) continue;
PointDef NumPoint = mNumInfoArr[I].Point;
PointDef[] WhiteShimaArr =
ExecUnionFind(Popped.BanArr, NumPoint.X, NumPoint.Y, 'W', false);
if (WhiteShimaArr.Length == mNumInfoArr[I].IntNum) continue;
PointDef[] KinbouSpaceArr = DeriveKinbouSpaceArr(Popped.BanArr, WhiteShimaArr);
char[,] CopiedArr = (char[,])Popped.BanArr.Clone();
foreach (PointDef EachSpace in KinbouSpaceArr) {
WillPush.BanArr = (char[,])CopiedArr.Clone();
WillPush.CurrInd = I;
SetWhite(WillPush.BanArr, EachSpace.X, EachSpace.Y);
ExecKakuteiTansaku(WillPush.BanArr);
Stk.Push(WillPush);
//白マスにしないマスは、黒マスとなる
SetBlack(CopiedArr, EachSpace.X, EachSpace.Y);
}
break;
}
}
}
//クリア判定
static bool IsClear(char[,] pBlackWhiteArr, out bool pIsValid)
{
pIsValid = true;
//条件1 黒マスの島が1つしかないこと
if (IsBundanBlack(pBlackWhiteArr)) {
pIsValid = false;
return false;
}
//条件2 2*2の黒マスが存在しないこと
for (int LoopX = 0; LoopX <= UB_X - 1; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y - 1; LoopY++) {
if (pBlackWhiteArr[LoopX, LoopY] == 'B'
&& pBlackWhiteArr[LoopX, LoopY + 1] == 'B'
&& pBlackWhiteArr[LoopX + 1, LoopY] == 'B'
&& pBlackWhiteArr[LoopX + 1, LoopY + 1] == 'B') {
pIsValid = false;
return false;
}
}
}
//条件3 全ての数字マスの島の数が正しいこと
foreach (NumInfoDef EachNumInfo in mNumInfoArr) {
//数字の1なら対象外
if (EachNumInfo.IntNum == 1) continue;
PointDef NumPoint = EachNumInfo.Point;
PointDef[] WhiteShimaArr =
ExecUnionFind(pBlackWhiteArr, NumPoint.X, NumPoint.Y, 'W', false);
if (WhiteShimaArr.Length > EachNumInfo.IntNum) {
pIsValid = false;
return false;
}
//複数の数字を含まないこと
int NumCnt = 0;
foreach (PointDef EachWhite in WhiteShimaArr) {
if (Array.Exists(mNumInfoArr, A => A.Point.X == EachWhite.X
&& A.Point.Y == EachWhite.Y)) {
NumCnt++;
}
}
if (NumCnt >= 2) {
pIsValid = false;
return false;
}
if (WhiteShimaArr.Length != EachNumInfo.IntNum) {
return false;
}
}
//条件4 数字のない白マスの島が存在しないこと
if (ExistsNonNumShima(pBlackWhiteArr))
return false;
return true;
}
//白マスが数字より多い島の有無を返す
static bool ExistsTyoukaWhiteShima(char[,] pBlackWhiteArr)
{
foreach (NumInfoDef EachNumInfo in mNumInfoArr) {
//数字の1なら対象外
if (EachNumInfo.IntNum == 1) continue;
PointDef NumPoint = EachNumInfo.Point;
PointDef[] WhiteShimaArr =
ExecUnionFind(pBlackWhiteArr, NumPoint.X, NumPoint.Y, 'W', false);
if (WhiteShimaArr.Length > EachNumInfo.IntNum)
return true;
}
return false;
}
//白マスが不足する島の有無を返す
static bool ExistsHusokuWhiteShima(char[,] pBlackWhiteArr)
{
foreach (NumInfoDef EachNumInfo in mNumInfoArr) {
//数字の1なら対象外
if (EachNumInfo.IntNum == 1) continue;
PointDef NumPoint = EachNumInfo.Point;
PointDef[] WhiteShimaArr =
ExecUnionFind(pBlackWhiteArr, NumPoint.X, NumPoint.Y, 'W', true);
if (WhiteShimaArr.Length < EachNumInfo.IntNum)
return true;
}
return false;
}
//数字のない白マスの島の有無を返す
static bool ExistsNonNumShima(char[,] pBlackWhiteArr)
{
//白マスの島のList
var WhiteShimaArrList = new List<PointDef[]>();
PointDef[] WhiteArr = DeriveColorArr(pBlackWhiteArr, 'W');
foreach (PointDef EachWhite in WhiteArr) {
//チェック済の白マスならContinue
bool WillContinue = false;
foreach (PointDef[] EachWhiteArr in WhiteShimaArrList) {
if (Array.Exists(EachWhiteArr, A => A.X == EachWhite.X
&& A.Y == EachWhite.Y)) {
WillContinue = true;
}
if (WillContinue) break;
}
if (WillContinue) continue;
PointDef[] WhiteShimaArr =
ExecUnionFind(pBlackWhiteArr, EachWhite.X, EachWhite.Y, 'W', true);
WhiteShimaArrList.Add(WhiteShimaArr);
}
foreach (PointDef[] EachWhiteShimaArr in WhiteShimaArrList) {
//数字マスが島に存在するかを判定
bool HasNum = false;
foreach (PointDef EachWhitePoint in EachWhiteShimaArr) {
if (Array.Exists(mNumInfoArr, A => A.Point.X == EachWhitePoint.X
&& A.Point.Y == EachWhitePoint.Y)) {
HasNum = true;
break;
}
}
if (HasNum == false) return true;
}
return false;
}
//黒マスの島の分断有無を返す
static bool IsBundanBlack(char[,] pBlackWhiteArr)
{
PointDef[] BlackArr = DeriveColorArr(pBlackWhiteArr, 'B');
//黒マスがない場合
if (BlackArr.Length == 0) return false;
PointDef[] BlackShimaArr =
ExecUnionFind(pBlackWhiteArr, BlackArr[0].X, BlackArr[0].Y, 'B', true);
int BlackShimaCnt = BlackShimaArr.Count(A => pBlackWhiteArr[A.X, A.Y] == 'B');
return BlackShimaCnt < BlackArr.Length;
}
//マスの色を指定して、座標の配列を返す
static PointDef[] DeriveColorArr(char[,] pBlackWhiteArr, char pColor)
{
var WillReturn = new List<PointDef>();
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (pBlackWhiteArr[LoopX, LoopY] != pColor)
continue;
WillReturn.Add(new PointDef() { X = LoopX, Y = LoopY });
}
}
return WillReturn.ToArray();
}
//島の座標に隣接した、空白座標の配列を返す
static PointDef[] DeriveKinbouSpaceArr(char[,] pBlackWhiteArr, PointDef[] pShimaArr)
{
var KinbouSpaceList = new List<PointDef>();
foreach (PointDef EachPoint in pShimaArr) {
PointDef[] KinbouArr = DeriveKinbouArr(EachPoint.X, EachPoint.Y);
PointDef[] SpaceArr =
Array.FindAll(KinbouArr, A => pBlackWhiteArr[A.X, A.Y] == ' ');
foreach (PointDef EachSpace in SpaceArr) {
if (KinbouSpaceList.Exists(
A => A.X == EachSpace.X && A.Y == EachSpace.Y)) {
continue;
}
KinbouSpaceList.Add(EachSpace);
}
}
return KinbouSpaceList.ToArray();
}
struct JyoutaiDefUnionFind
{
internal int CurrX;
internal int CurrY;
}
//開始座標とマスの色を指定して連結した座標の配列を返す
static PointDef[] ExecUnionFind(char[,] pBlackWhiteArr, int pStaX, int pStaY,
char pColor, bool pAllowSpace)
{
var VisitedList = new List<PointDef>();
var Stk = new Stack<JyoutaiDefUnionFind>();
JyoutaiDefUnionFind WillPush;
WillPush.CurrX = pStaX;
WillPush.CurrY = pStaY;
Stk.Push(WillPush);
VisitedList.Add(new PointDef() { X = pStaX, Y = pStaY });
while (Stk.Count > 0) {
JyoutaiDefUnionFind Popped = Stk.Pop();
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB_X < pNewX) return;
if (pNewY < 0 || UB_Y < pNewY) return;
bool IsOK = false;
if (pBlackWhiteArr[pNewX, pNewY] == pColor) IsOK = true;
if (pAllowSpace && pBlackWhiteArr[pNewX, pNewY] == ' ') IsOK = true;
if (IsOK == false) return;
//再訪不可
if (VisitedList.Exists(A => A.X == pNewX && A.Y == pNewY))
return;
VisitedList.Add(new PointDef() { X = pNewX, Y = pNewY });
WillPush.CurrX = pNewX;
WillPush.CurrY = pNewY;
Stk.Push(WillPush);
};
PushSyori(Popped.CurrX, Popped.CurrY - 1);
PushSyori(Popped.CurrX, Popped.CurrY + 1);
PushSyori(Popped.CurrX - 1, Popped.CurrY);
PushSyori(Popped.CurrX + 1, Popped.CurrY);
}
return VisitedList.ToArray();
}
//4近傍の座標の配列を返す
static PointDef[] DeriveKinbouArr(int pBaseX, int pBaseY)
{
var WillReturnList = new List<PointDef>();
Action<int, int> AddAct = (pX, pY) =>
{
if (pX < 0 || UB_X < pX) return;
if (pY < 0 || UB_Y < pY) return;
WillReturnList.Add(new PointDef() { X = pX, Y = pY });
};
AddAct(pBaseX, pBaseY - 1);
AddAct(pBaseX, pBaseY + 1);
AddAct(pBaseX - 1, pBaseY);
AddAct(pBaseX + 1, pBaseY);
return WillReturnList.ToArray();
}
static void SetBlack(char[,] pBlackWhiteArr, int pX, int pY)
{
if (pBlackWhiteArr[pX, pY] != ' ') return;
pBlackWhiteArr[pX, pY] = 'B';
//2*2の黒マスができるマスは白マスで確定
SetBlackHelper(pBlackWhiteArr, pX, pY);
PointDef[] KinbouArr = DeriveKinbouArr(pX, pY);
Array.ForEach(KinbouArr, A => SetBlackHelper(pBlackWhiteArr, A.X, A.Y));
}
static void SetBlackHelper(char[,] pBlackWhiteArr, int pBaseX, int pBaseY)
{
if (pBlackWhiteArr[pBaseX, pBaseY] != 'B') return;
Action<int, int> SetAct = (pHeni_X, pHeni_Y) =>
{
int TargetX = pBaseX + pHeni_X;
int TargetY = pBaseY + pHeni_Y;
if (TargetX < 0 || UB_X < TargetX) return;
if (TargetY < 0 || UB_Y < TargetY) return;
if (pBlackWhiteArr[TargetX, TargetY] == 'W') return;
if (pBlackWhiteArr[TargetX, pBaseY] != 'B') return;
if (pBlackWhiteArr[pBaseX, TargetY] != 'B') return;
SetWhite(pBlackWhiteArr, TargetX, TargetY);
};
SetAct(-1, -1);
SetAct(-1, 1);
SetAct(1, -1);
SetAct(1, 1);
}
static void SetWhite(char[,] pBlackWhiteArr, int pX, int pY)
{
if (pBlackWhiteArr[pX, pY] != ' ') return;
pBlackWhiteArr[pX, pY] = 'W';
//島ができたときの周囲の黒マスを設定
PointDef[] WhiteShimaArr = ExecUnionFind(pBlackWhiteArr, pX, pY, 'W', false);
int wkInd = -1;
foreach (PointDef EachShima in WhiteShimaArr) {
wkInd = Array.FindIndex(mNumInfoArr,
A => A.Point.X == EachShima.X && A.Point.Y == EachShima.Y);
if (wkInd >= 0) break;
}
if (wkInd == -1) return;
if (mNumInfoArr[wkInd].IntNum != WhiteShimaArr.Length) return;
PointDef[] KinbouSpaceArr = DeriveKinbouSpaceArr(pBlackWhiteArr, WhiteShimaArr);
foreach (PointDef EachSpace in KinbouSpaceArr) {
SetBlack(pBlackWhiteArr, EachSpace.X, EachSpace.Y);
}
}
//盤面を出力
static void PrintBan(char[,] pBlackWhiteArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
char CurrChar = pBlackWhiteArr[X, Y];
if (CurrChar == 'B') sb.Append('■');
else if (CurrChar == 'W' && mQuestionArr[X, Y] == '□')
sb.Append('・');
else sb.Append(mQuestionArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
1 盤面のいくつかのマスを黒くぬりましょう。 2 盤面の数字は、その数字が含まれる、黒マスによって分断されたところ（シマと呼びます）のマスの数を表します。 3 すべてのシマに数字が１つずつ入るようにします。また、数字が入っているマスを黒くぬってはいけません。 4 すべての黒マスはタテヨコにひとつながりになっていなければなりません。 5 黒マスを２×２以上のカタマリにしてはいけません。