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; //数値の値
internal PointDef[] KinbouPointArr; //4近傍の座標の配列
}
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();
char[,] wkBanArr = (char[,])mQuestionArr.Clone();
//第2フェーズ 初回の確定探索
SyokaiKakuteiTansaku(wkBanArr);
//第3フェーズ 確定探索
ExecKakuteiTansaku(wkBanArr);
//Console.WriteLine("初回の確定探索後");
//PrintBan(wkBanArr);
//第4フェーズ 確定探索付の深さ優先探索
ExecDFS(wkBanArr);
}
//第1フェーズ 数値情報を作成する
static void CreateNumInfoArr()
{
var NumInfoList = new List<NumInfoDef>();
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
//数値マスでない場合
bool IsNum = false;
if (mQuestionArr[LoopX, LoopY] == '０') IsNum = true;
if (mQuestionArr[LoopX, LoopY] == '１') IsNum = true;
if (mQuestionArr[LoopX, LoopY] == '２') IsNum = true;
if (mQuestionArr[LoopX, LoopY] == '３') IsNum = true;
if (mQuestionArr[LoopX, LoopY] == '４') IsNum = true;
if (IsNum == false) continue;
NumInfoDef WillAdd;
PointDef CurrPoint = new PointDef() { X = LoopX, Y = LoopY };
WillAdd.Point = CurrPoint;
WillAdd.IntNum = mQuestionArr[LoopX, LoopY] - '０';
WillAdd.KinbouPointArr = DeriveKinbouPointArr(CurrPoint);
NumInfoList.Add(WillAdd);
}
}
mNumInfoArr = NumInfoList.ToArray();
}
//4近傍の座標の配列を返す
static PointDef[] DeriveKinbouPointArr(PointDef pCurrPoint)
{
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;
//白マスでなければ対象外
if (mQuestionArr[pX, pY] != '□')
return;
WillReturnList.Add(new PointDef() { X = pX, Y = pY });
};
AddAct(pCurrPoint.X, pCurrPoint.Y - 1);
AddAct(pCurrPoint.X, pCurrPoint.Y + 1);
AddAct(pCurrPoint.X - 1, pCurrPoint.Y);
AddAct(pCurrPoint.X + 1, pCurrPoint.Y);
return WillReturnList.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);
Console.Write("4近傍の座標の配列 ");
foreach (var EachPoint in mNumInfoArr[I].KinbouPointArr) {
Console.Write("({0},{1}),", EachPoint.X, EachPoint.Y);
}
Console.WriteLine();
}
}
//第2フェーズ 初回の確定探索
static void SyokaiKakuteiTansaku(char[,] pBanArr)
{
//確定探索1 数値マスの0と4の分の処理を行う
KakuteiTansaku1(pBanArr);
//確定探索2 数値マスの3の斜めに・を配置
KakuteiTansaku2(pBanArr);
}
//確定探索1 数値マスの0と4の分の処理を行う
static void KakuteiTansaku1(char[,] pBanArr)
{
foreach (var EachNumInfo in mNumInfoArr) {
if (EachNumInfo.IntNum == 0) {
foreach (PointDef EachPoint in EachNumInfo.KinbouPointArr) {
if (pBanArr[EachPoint.X, EachPoint.Y] == '□')
pBanArr[EachPoint.X, EachPoint.Y] = '・';
}
}
if (EachNumInfo.IntNum == 4) {
foreach (PointDef EachPoint in EachNumInfo.KinbouPointArr) {
SetAkari(pBanArr, EachPoint);
}
}
}
mNumInfoArr = Array.FindAll(mNumInfoArr, A => A.IntNum != 0 && A.IntNum != 4);
}
//確定探索2 数値マスの3の斜めに・を配置
static void KakuteiTansaku2(char[,] pBanArr)
{
foreach (var EachNumInfo in mNumInfoArr) {
if (EachNumInfo.IntNum != 3) continue;
Action<int, int> wkAct = (pX, pY) =>
{
if (pX < 0 || UB_X < pX) return;
if (pY < 0 || UB_Y < pY) return;
if (pBanArr[pX, pY] == '□')
pBanArr[pX, pY] = '・';
};
wkAct(EachNumInfo.Point.X - 1, EachNumInfo.Point.Y - 1);
wkAct(EachNumInfo.Point.X - 1, EachNumInfo.Point.Y + 1);
wkAct(EachNumInfo.Point.X + 1, EachNumInfo.Point.Y - 1);
wkAct(EachNumInfo.Point.X + 1, EachNumInfo.Point.Y + 1);
}
}
//第3フェーズ 確定探索を行い有効な盤面かを返す
static bool ExecKakuteiTansaku(char[,] pBanArr)
{
while (true) {
char[,] PrevBanArr = (char[,])pBanArr.Clone();
//確定探索3 数値マスの4近傍に配置できる照明が確定している場合
if (KakuteiTansaku3(pBanArr) == false) return false;
//確定探索4 照らすことの出来るマスが1つしかなかったら照明を配置
if (KakuteiTansaku4(pBanArr) == false) return false;
//確定探索で確定するマスがなくなったらBreak
if (pBanArr.Cast<char>().SequenceEqual(PrevBanArr.Cast<char>())) break;
}
return true;
}
//確定探索3 数値マスの4近傍に配置できる照明が確定している場合
//戻り値として、有効な盤面かを返す
static bool KakuteiTansaku3(char[,] pBanArr)
{
foreach (var EachNumInfo in mNumInfoArr) {
var HaitiKouhoList = new List<PointDef>();
int AkariCnt = 0;
foreach (PointDef EachPoint in EachNumInfo.KinbouPointArr) {
if (pBanArr[EachPoint.X, EachPoint.Y] == '□')
HaitiKouhoList.Add(EachPoint);
if (pBanArr[EachPoint.X, EachPoint.Y] == '★')
AkariCnt++;
}
//★が多すぎる場合はNG
if (EachNumInfo.IntNum < AkariCnt) return false;
//空白が不足する場合はNG
if (EachNumInfo.IntNum > HaitiKouhoList.Count + AkariCnt)
return false;
if (EachNumInfo.IntNum == HaitiKouhoList.Count + AkariCnt) {
HaitiKouhoList.ForEach(A => SetAkari(pBanArr, A));
}
}
return true;
}
//照明を配置する
static void SetAkari(char[,] pBanArr, PointDef pSetPoint)
{
pBanArr[pSetPoint.X, pSetPoint.Y] = '★';
Action<int, int> SetAct = (pHeniX, pHeniY) =>
{
int LoopX = pSetPoint.X, LoopY = pSetPoint.Y;
while (true) {
//次のマスからが対象となる
LoopX += pHeniX; LoopY += pHeniY;
//範囲外の場合
if (LoopX < 0 || UB_X < LoopX) break;
if (LoopY < 0 || UB_Y < LoopY) break;
//壁に到達した場合
if ('０' <= pBanArr[LoopX, LoopY] && pBanArr[LoopX, LoopY] <= '４'
|| pBanArr[LoopX, LoopY] == '■') break;
if (pBanArr[LoopX, LoopY] == '□' || pBanArr[LoopX, LoopY] == '・') {
pBanArr[LoopX, LoopY] = '＊';
}
}
};
SetAct(0, -1);
SetAct(0, 1);
SetAct(-1, 0);
SetAct(1, 0);
}
//確定探索4 照らすことの出来るマスが1つしかなかったら照明を配置
//戻り値として、有効な盤面かを返す
static bool KakuteiTansaku4(char[,] pBanArr)
{
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (pBanArr[LoopX, LoopY] != '□' && pBanArr[LoopX, LoopY] != '・')
continue;
List<PointDef> HaitiKouhoList =
DeriveHaitiKouhoList(pBanArr, new PointDef() { X = LoopX, Y = LoopY });
if (HaitiKouhoList.Count == 0)
return false;
if (HaitiKouhoList.Count == 1) {
SetAkari(pBanArr, HaitiKouhoList[0]);
}
}
}
return true;
}
//□か・のマスの座標を引数として、照らすことのできる座標のListを返す
static List<PointDef> DeriveHaitiKouhoList(char[,] pBanArr, PointDef pTerasuPoint)
{
var WillReturn = new List<PointDef>();
if (pBanArr[pTerasuPoint.X, pTerasuPoint.Y] == '□') {
WillReturn.Add(pTerasuPoint);
}
Action<int, int> AddAct = (pHeniX, pHeniY) =>
{
int LoopX = pTerasuPoint.X, LoopY = pTerasuPoint.Y;
while (true) {
//次のマスからが対象となる
LoopX += pHeniX; LoopY += pHeniY;
//範囲外の場合
if (LoopX < 0 || UB_X < LoopX) break;
if (LoopY < 0 || UB_Y < LoopY) break;
//壁に到達した場合
if ('０' <= pBanArr[LoopX, LoopY] && pBanArr[LoopX, LoopY] <= '４'
|| pBanArr[LoopX, LoopY] == '■') break;
if (pBanArr[LoopX, LoopY] == '□') {
WillReturn.Add(new PointDef() { X = LoopX, Y = LoopY });
}
}
};
AddAct(0, -1);
AddAct(0, 1);
AddAct(-1, 0);
AddAct(1, 0);
return WillReturn;
}
//第4フェーズ
//確定探索付の深さ優先探索
static void ExecDFS(char[,] pBanArr)
{
var Stk = new Stack<char[,]>();
char[,] WillPushBanArr = pBanArr;
Stk.Push(WillPushBanArr);
while (Stk.Count > 0) {
char[,] PoppedBanArr = Stk.Pop();
//クリア判定
if (IsClear(PoppedBanArr)) {
Console.WriteLine("解を発見");
PrintBan(PoppedBanArr);
return;
}
bool WillBreak = false;
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (PoppedBanArr[LoopX, LoopY] != '□' && PoppedBanArr[LoopX, LoopY] != '・')
continue;
PointDef CurrPoint = new PointDef() { X = LoopX, Y = LoopY };
List<PointDef> HaitiKouhoList = DeriveHaitiKouhoList(PoppedBanArr, CurrPoint);
foreach (PointDef EachHaitiKouho in HaitiKouhoList) {
WillPushBanArr = (char[,])PoppedBanArr.Clone();
SetAkari(WillPushBanArr, EachHaitiKouho);
//確定探索を行い、有効な盤面ならPush処理
if (ExecKakuteiTansaku(WillPushBanArr)) {
Stk.Push(WillPushBanArr);
}
}
WillBreak = true;
break;
}
if (WillBreak) break;
}
}
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
//数値マスの4近傍の照明の数のチェック
foreach (var EachNumInfo in mNumInfoArr) {
int AkariCnt = 0;
foreach (PointDef EachPoint in EachNumInfo.KinbouPointArr) {
if (pBanArr[EachPoint.X, EachPoint.Y] == '★')
AkariCnt++;
}
if (EachNumInfo.IntNum != AkariCnt)
return false;
}
//全てのマスが照明で照らされていること
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
if (pBanArr[LoopX, LoopY] == '□' || pBanArr[LoopX, LoopY] == '・')
return false;
}
}
return true;
}
//盤面を出力
static void PrintBan(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
sb.Append(pBanArr[LoopX, LoopY]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
1 盤面のいくつかの白マスに照明を置き（○を書き）ましょう。 2 盤面の数字は、その数字の入っているマスにタテヨコに隣り合う白マスのうち、 照明が入るマスの数を表しています。 3 照明は、そのマスから上下左右に、黒マスか外枠にぶつかるまでの範囲を照らします。 ナナメの位置にあるマスは照らせません。 4 照明どうしが照らし合ってはいけません。 5 どの照明にも照らされない白マスがあってはいけません。