トップページに戻る
次のC#のサンプルへ
前のC#のサンプルへ
24-25 ナンバーリンク
問題
ニコリのナンバーリンクを解きます。
例題と答え
1 白マスに線を引いて、同じ数字どうしをつなげましょう。
2 線は、マスの中央を通るようにタテヨコに引きます。
線を交差させたり、枝分かれさせたりしてはいけません。
3 数字の入っているマスを通過するように線を引いてはいけません。
4 １マスに２本以上の線を引いてはいけません。
ソース(作成中その1)
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int mQuestionNo = 2;
static char[,] mQuestionArr; //問題の初期盤面
static int UB;
//問題を定義
static void QuestionDef()
{
string[] wkStrArr = null;
if (mQuestionNo == 1) {
wkStrArr = new string[] {"１２□□５□",
"□□□□４□",
"□３□□□□",
"□□□２□□",
"□１４□□５",
"□□□□□３"};
}
if (mQuestionNo == 2) {
wkStrArr = new string[] {"５□４□□□□□□５",
"１□□□□□□□□□",
"□□□□□□１□□□",
"□□□□□□□□□□",
"□□□□□□□□□□",
"□□□□□□□□２□",
"□□□３□□□□□□",
"□□□□□□□２□□",
"□□□□□□□４３□",
"□□□□□□□□□□"};
}
if (mQuestionNo == 3) {
wkStrArr = new string[] {"□□１６□□４□□□",
"□□□□７□□□□□",
"□□□□□□□５□□",
"□□□□２□□□□□",
"□□□□３□４□□□",
"□□□□□□□□□６",
"□□□□□□□□□□",
"□□□□□□□□□□",
"□７５□□□□１２□",
"□□□□３□□□□□"};
}
UB = wkStrArr.GetUpperBound(0);
mQuestionArr = new char[UB + 1, UB + 1];
for (int Y = 0; Y <= UB; Y++)
for (int X = 0; X <= UB; X++)
mQuestionArr[Y, X] = wkStrArr[X][Y];
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
//問題を定義
QuestionDef();
//リンクの開始座標と終了座標を取得
DeriveLinkInfoArr();
var PrevBanArrList = new List<char[,]>() { mQuestionArr };
foreach (LinkInfoDef EachLinkInfo in mLinkInfoArr) {
var CurrBanArrList = new List<char[,]>();
PrevBanArrList.ForEach(X => CurrBanArrList.AddRange(ExecDFS(X, EachLinkInfo)));
PrevBanArrList = CurrBanArrList;
Console.WriteLine("{0}のリンクは{1}通り", EachLinkInfo.ID, CurrBanArrList.Count);
CurrBanArrList.ForEach(A => PrintBan(A));
}
for (int I = 0; I <= PrevBanArrList.Count - 1; I++) {
Console.WriteLine("解{0}", I + 1);
PrintBan(PrevBanArrList[I]);
}
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
struct JyoutaiDefDFS
{
internal int CurrX;
internal int CurrY;
internal char[,] BanArr;
}
//深さ優先探索でリンクを作成
static List<char[,]> ExecDFS(char[,] pBanArr, LinkInfoDef pLinkInfo)
{
var WillReturn = new List<char[,]>();
var Stk = new Stack<JyoutaiDefDFS>();
JyoutaiDefDFS WillPush;
WillPush.CurrX = pLinkInfo.StaX;
WillPush.CurrY = pLinkInfo.StaY;
WillPush.BanArr = pBanArr;
Stk.Push(WillPush);
int PopCnt = 0;
while (Stk.Count > 0) {
JyoutaiDefDFS Popped = Stk.Pop();
if (++PopCnt % 10000 == 0) {
Console.WriteLine("{0}回目のPop", PopCnt);
PrintBan(Popped.BanArr);
}
//クリア判定(終点の4近傍にいたら探索終了)
bool IsOK = false;
if (Popped.CurrX == pLinkInfo.EndX && Popped.CurrY == pLinkInfo.EndY - 1) IsOK = true;
if (Popped.CurrX == pLinkInfo.EndX && Popped.CurrY == pLinkInfo.EndY + 1) IsOK = true;
if (Popped.CurrX == pLinkInfo.EndX - 1 && Popped.CurrY == pLinkInfo.EndY) IsOK = true;
if (Popped.CurrX == pLinkInfo.EndX + 1 && Popped.CurrY == pLinkInfo.EndY) IsOK = true;
if (IsOK) {
WillReturn.Add(Popped.BanArr);
continue;
}
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB < pNewX) return;
if (pNewY < 0 || UB < pNewY) return;
if (Popped.BanArr[pNewX, pNewY] != '□') return;
//ゴールでも直近でもないマスと隣接していたら枝切り
PointDef PrevPos = new PointDef() { X = Popped.CurrX, Y = Popped.CurrY };
PointDef CurrPos = new PointDef() { X = pNewX, Y = pNewY };
PointDef GoalPos = new PointDef() { X = pLinkInfo.EndX, Y = pLinkInfo.EndY };
List<char> wk4KinbouList = Derive4KinbouList(Popped.BanArr, PrevPos, CurrPos, GoalPos);
if (wk4KinbouList.Contains(pLinkInfo.ID)) return;
WillPush.CurrX = pNewX;
WillPush.CurrY = pNewY;
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
WillPush.BanArr[pNewX, pNewY] = pLinkInfo.ID;
//リンクが凹の形なら枝切り
if (HasHekomiLink(WillPush.BanArr)) return;
//UnionFindで枝切り判定
if (WillEdakiriUnionFind(WillPush.BanArr, pLinkInfo.ID)) return;
//空白の島に同じ数字が2箇所隣接しているかを判定
if (IsValidShima(WillPush.BanArr, pLinkInfo.ID) == false) return;
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 WillReturn;
}
struct PointDef
{
internal int X;
internal int Y;
}
//4近傍の値のList(直近とゴールは除外)を返す
static List<char> Derive4KinbouList(char[,] pBanArr,
PointDef pPrevPoint, PointDef pCurrPoint, PointDef pGoalPoint)
{
var WillReturn = new List<char>();
int CurrX = pCurrPoint.X;
int CurrY = pCurrPoint.Y;
Action<int, int> wkAct = (pTargetX, pTargetY) =>
{
if (pTargetX < 0 || UB < pTargetX) return;
if (pTargetY < 0 || UB < pTargetY) return;
if (pTargetX == pPrevPoint.X && pTargetY == pPrevPoint.Y)
return;
if (pTargetX == pGoalPoint.X && pTargetY == pGoalPoint.Y)
return;
WillReturn.Add(pBanArr[pTargetX, pTargetY]);
};
wkAct(CurrX, CurrY - 1);
wkAct(CurrX, CurrY + 1);
wkAct(CurrX - 1, CurrY);
wkAct(CurrX + 1, CurrY);
return WillReturn;
}
//UnionFindで枝切り判定
static bool WillEdakiriUnionFind(char[,] pBanArr, char pID)
{
foreach (LinkInfoDef EachLinkInfo in mLinkInfoArr) {
if (pID.CompareTo(EachLinkInfo.ID) >= 0) continue;
if (ExecUnionFind(pBanArr, EachLinkInfo) == false)
return true;
}
return false;
}
struct JyoutaiDefUnionFind
{
internal int CurrX;
internal int CurrY;
}
//UnionFindでリンクを作成可能かを返す
static bool ExecUnionFind(char[,] pBanArr, LinkInfoDef pLinkInfo)
{
var Stk = new Stack<JyoutaiDefUnionFind>();
JyoutaiDefUnionFind WillPush;
WillPush.CurrX = pLinkInfo.StaX;
WillPush.CurrY = pLinkInfo.StaY;
Stk.Push(WillPush);
var VisitedSet = new HashSet<int>();
VisitedSet.Add(PointToInt(WillPush.CurrX, WillPush.CurrY));
while (Stk.Count > 0) {
JyoutaiDefUnionFind Popped = Stk.Pop();
//クリア判定(終点の4近傍にいたら探索終了)
bool IsOK = false;
if (Popped.CurrX == pLinkInfo.EndX && Popped.CurrY == pLinkInfo.EndY - 1) IsOK = true;
if (Popped.CurrX == pLinkInfo.EndX && Popped.CurrY == pLinkInfo.EndY + 1) IsOK = true;
if (Popped.CurrX == pLinkInfo.EndX - 1 && Popped.CurrY == pLinkInfo.EndY) IsOK = true;
if (Popped.CurrX == pLinkInfo.EndX + 1 && Popped.CurrY == pLinkInfo.EndY) IsOK = true;
if (IsOK) return true;
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB < pNewX) return;
if (pNewY < 0 || UB < pNewY) return;
if (pBanArr[pNewX, pNewY] != '□') return;
//再訪防止
if (VisitedSet.Add(PointToInt(pNewX, 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 false;
}
//空白の島に同じ数字が2箇所隣接しているかを判定
static bool IsValidShima(char[,] pBanArr, char pID)
{
//チェック済の島のSet
var CheckedPosSet = new HashSet<int>();
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
if (pBanArr[X, Y] != '□') continue;
if (CheckedPosSet.Add(PointToInt(X, Y))) {
if (IsValidShimaHelper(pBanArr, CheckedPosSet, X, Y, pID) == false) {
return false;
}
}
}
}
return true;
}
//空白の島に同じ数字に2箇所隣接しているかを判定
static bool IsValidShimaHelper(char[,] pBanArr, HashSet<int> pCheckedPosSet,
int pStaX, int pStaY, char pID)
{
var Stk = new Stack<JyoutaiDefUnionFind>();
JyoutaiDefUnionFind WillPush;
WillPush.CurrX = pStaX;
WillPush.CurrY = pStaY;
Stk.Push(WillPush);
var RinsetuNumList = new List<char>();
var VisitedSet = new HashSet<int>();
VisitedSet.Add(PointToInt(pStaX, pStaY));
while (Stk.Count > 0) {
JyoutaiDefUnionFind Popped = Stk.Pop();
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB < pNewX) return;
if (pNewY < 0 || UB < pNewY) return;
//再訪防止
if (VisitedSet.Add(PointToInt(pNewX, pNewY))) {
if (pBanArr[pNewX, pNewY] != '□') {
RinsetuNumList.Add(pBanArr[pNewX, pNewY]);
return;
}
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);
}
//2つだけ隣接した数字がなかったらNG
if (RinsetuNumList.GroupBy(A => A).Any(A => A.Count() == 2 && A.Key >= pID) == false) {
return false;
}
pCheckedPosSet.UnionWith(VisitedSet);
return true;
}
//リンクが凹の形なら枝切り
static bool HasHekomiLink(char[,] pBanArr)
{
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
if (pBanArr[X, Y] != '□') continue;
var NumList = new List<char>();
Action<int, int> wkAct = (pTargetX, pTargetY) =>
{
if (pTargetX < 0 || UB < pTargetX) return;
if (pTargetY < 0 || UB < pTargetY) return;
if (pBanArr[pTargetX, pTargetY] == '□') return;
NumList.Add(pBanArr[pTargetX, pTargetY]);
};
wkAct(X, Y - 1);
wkAct(X, Y+ 1);
wkAct(X- 1, Y);
wkAct(X+ 1, Y);
if (NumList.GroupBy(A => A).Any(A => A.Count() >= 3))
return true;
}
}
return false;
}
struct LinkInfoDef
{
internal char ID;
internal int StaX;
internal int StaY;
internal int EndX;
internal int EndY;
}
static LinkInfoDef[] mLinkInfoArr;
//リンクの開始座標と終了座標を取得
static void DeriveLinkInfoArr()
{
var LinkInfoList = new List<LinkInfoDef>();
char[] IDArr = mQuestionArr.Cast<char>().Where(A => A != '□').Distinct().ToArray();
Array.Sort(IDArr);
LinkInfoDef WillAdd;
foreach (char EachID in IDArr) {
WillAdd.ID = EachID;
WillAdd.StaX = WillAdd.StaY = -1;
WillAdd.EndX = WillAdd.EndY = -1;
int HitCnt = 0;
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if (mQuestionArr[X, Y] != EachID) continue;
HitCnt++;
if (HitCnt == 1) {
WillAdd.StaX = X; WillAdd.StaY = Y;
}
if (HitCnt == 2) {
WillAdd.EndX = X; WillAdd.EndY = Y;
LinkInfoList.Add(WillAdd);
}
}
}
}
mLinkInfoArr = LinkInfoList.ToArray();
}
//X座標とY座標のペアをInt型に変換
static int PointToInt(int pX, int pY)
{
return pX * (UB + 1) + pY;
}
//盤面を出力
static void PrintBan(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
ソース(作成中その2)
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int mQuestionNo = 5;
static char[,] mQuestionArr; //問題の初期盤面
static int UB;
//問題を定義
static void QuestionDef()
{
string[] wkStrArr = null;
if (mQuestionNo == 1) {
wkStrArr = new string[] {"１２□□５□",
"□□□□４□",
"□３□□□□",
"□□□２□□",
"□１４□□５",
"□□□□□３"};
}
if (mQuestionNo == 2) {
wkStrArr = new string[] {"５□４□□□□□□５",
"１□□□□□□□□□",
"□□□□□□１□□□",
"□□□□□□□□□□",
"□□□□□□□□□□",
"□□□□□□□□２□",
"□□□３□□□□□□",
"□□□□□□□２□□",
"□□□□□□□４３□",
"□□□□□□□□□□"};
}
if (mQuestionNo == 3) {
wkStrArr = new string[] {"□□１６□□４□□□",
"□□□□７□□□□□",
"□□□□□□□５□□",
"□□□□２□□□□□",
"□□□□３□４□□□",
"□□□□□□□□□６",
"□□□□□□□□□□",
"□□□□□□□□□□",
"□７５□□□□１２□",
"□□□□３□□□□□"};
}
if (mQuestionNo == 4) {
wkStrArr = new string[] {"□□□□□□□□□□",
"□４□□□□□□□□",
"□６７□□□３２□□",
"８□□□□□□□□□",
"□□３□□１□□□□",
"□□４□□□２□□□",
"□□５□□□□１□□",
"□□□□□□□□□６",
"□□□□□□□□□５",
"□□□８□□□□□７"};
}
if (mQuestionNo == 5) {
wkStrArr = new string[] {"□□□□□□□□□□□□□□□",
"□□□□□□□□□□□□□□□",
"□□□１２□□□８７６５□□□",
"□□□４３□□□□□□６□□□",
"□□□□□□□□□□□５□□□",
"□□□□□□□□□□□４□□□",
"□□２Ｃ□□□□９□□□□□□",
"□□Ｄ□□□□□□□□□３□□",
"□□□□□□Ｆ□□□□ＦＥ□□",
"□□□１□□□□□□□□□□□",
"□□□Ａ□□□□□□□□□□□",
"□□□Ｂ□□□□□□９８□□□",
"□□□ＣＤＥＢ□□□Ａ７□□□",
"□□□□□□□□□□□□□□□",
"□□□□□□□□□□□□□□□"};
}
UB = wkStrArr.GetUpperBound(0);
mQuestionArr = new char[UB + 1, UB + 1];
for (int Y = 0; Y <= UB; Y++)
for (int X = 0; X <= UB; X++)
mQuestionArr[Y, X] = wkStrArr[X][Y];
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
//問題を定義
QuestionDef();
//リンクの開始座標と終了座標を取得
DeriveLinkInfoArr();
//深さ優先探索でリンクを作成
ExecDFS();
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
struct PointDef
{
internal int X;
internal int Y;
}
struct JyoutaiDefDFS
{
internal char[,] BanArr;
internal int Level;
internal Dictionary<char, string> LinkInfoDict;
internal HashSet<char> IsGoalSet;
}
//深さ優先探索でリンクを作成
static void ExecDFS()
{
var Stk = new Stack<JyoutaiDefDFS>();
JyoutaiDefDFS WillPush;
WillPush.BanArr = mQuestionArr;
WillPush.Level = 0;
WillPush.LinkInfoDict = new Dictionary<char, string>();
foreach (LinkInfoDef EachLinkInfo in mLinkInfoArr) {
string PosStr = string.Format("{0},{1}", EachLinkInfo.StaX, EachLinkInfo.StaY);
WillPush.LinkInfoDict[EachLinkInfo.ID] = PosStr;
}
WillPush.IsGoalSet = new HashSet<char>();
Stk.Push(WillPush);
int PopCnt = 0;
while (Stk.Count > 0) {
JyoutaiDefDFS Popped = Stk.Pop();
PopCnt++;
if (PopCnt % 10000 == 0) {
Console.WriteLine("Pop回数={0}", PopCnt);
PrintBan(Popped.BanArr);
}
//クリア判定
if (Popped.IsGoalSet.Count == mLinkInfoArr.Length) {
Console.WriteLine("解を発見");
PrintBan(Popped.BanArr);
break;
}
//リンクを伸ばす文字を決める
char CurrID = '\0';
int I = Popped.Level % mLinkInfoArr.Length;
while (true) {
if (I > mLinkInfoArr.GetUpperBound(0))
I = 0;
CurrID = mLinkInfoArr[I].ID;
if (Popped.IsGoalSet.Contains(CurrID) == false)
break;
I++;
}
string[] SplitStr = Popped.LinkInfoDict[CurrID].Split(',');
int CurrX = int.Parse(SplitStr[0]);
int CurrY = int.Parse(SplitStr[1]);
int EndX = -1, EndY = -1;
foreach (LinkInfoDef EachLinkInfo in mLinkInfoArr) {
if (EachLinkInfo.ID == CurrID) {
EndX = EachLinkInfo.EndX;
EndY = EachLinkInfo.EndY;
break;
}
}
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB < pNewX) return;
if (pNewY < 0 || UB < pNewY) return;
if (Popped.BanArr[pNewX, pNewY] != '□') return;
//ゴールでも直近でもないマスと隣接していたら枝切り
PointDef PrevPos = new PointDef() { X = CurrX, Y = CurrY };
PointDef CurrPos = new PointDef() { X = pNewX, Y = pNewY };
PointDef GoalPos = new PointDef() { X = EndX, Y = EndY };
List<char> wk4KinbouList = Derive4KinbouList(Popped.BanArr, PrevPos, CurrPos, GoalPos);
if (wk4KinbouList.Contains(CurrID)) return;
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
WillPush.BanArr[pNewX, pNewY] = CurrID;
//リンクが凹の形なら枝切り
if (HasHekomiLink(WillPush.BanArr)) return;
//UnionFindで枝切り判定
if (WillEdakiriUnionFind(WillPush.BanArr, CurrID, pNewX, pNewY)) return;
WillPush.Level = Popped.Level + 1;
WillPush.LinkInfoDict = new Dictionary<char, string>(Popped.LinkInfoDict);
WillPush.LinkInfoDict[CurrID] = string.Format("{0},{1}", pNewX, pNewY);
//クリア判定(終点の4近傍にいたら探索終了)
bool IsOK = false;
if (pNewX == EndX && pNewY == EndY - 1) IsOK = true;
if (pNewX == EndX && pNewY == EndY + 1) IsOK = true;
if (pNewX == EndX - 1 && pNewY == EndY) IsOK = true;
if (pNewX == EndX + 1 && pNewY == EndY) IsOK = true;
if (IsOK) {
WillPush.IsGoalSet = new HashSet<char>(Popped.IsGoalSet);
WillPush.IsGoalSet.Add(CurrID);
}
else WillPush.IsGoalSet = Popped.IsGoalSet;
Stk.Push(WillPush);
};
PushSyori(CurrX, CurrY - 1);
PushSyori(CurrX, CurrY + 1);
PushSyori(CurrX - 1, CurrY);
PushSyori(CurrX + 1, CurrY);
}
}
//UnionFindで枝切り判定
static bool WillEdakiriUnionFind(char[,] pBanArr, char pID, int pCurrX, int pCurrY)
{
foreach (LinkInfoDef EachLinkInfo in mLinkInfoArr) {
if (EachLinkInfo.ID != pID) continue;
if (ExecUnionFind(pBanArr, EachLinkInfo, pCurrX, pCurrY) == false)
return true;
}
return false;
}
struct JyoutaiDefUnionFind
{
internal int CurrX;
internal int CurrY;
}
//UnionFindでリンクを作成可能かを返す
static bool ExecUnionFind(char[,] pBanArr, LinkInfoDef pLinkInfo, int pCurrX, int pCurrY)
{
var Stk = new Stack<JyoutaiDefUnionFind>();
JyoutaiDefUnionFind WillPush;
WillPush.CurrX = pCurrX;
WillPush.CurrY = pCurrY;
Stk.Push(WillPush);
var VisitedSet = new HashSet<int>();
VisitedSet.Add(PointToInt(WillPush.CurrX, WillPush.CurrY));
while (Stk.Count > 0) {
JyoutaiDefUnionFind Popped = Stk.Pop();
//クリア判定(終点の4近傍にいたら探索終了)
bool IsOK = false;
if (Popped.CurrX == pLinkInfo.EndX && Popped.CurrY == pLinkInfo.EndY - 1) IsOK = true;
if (Popped.CurrX == pLinkInfo.EndX && Popped.CurrY == pLinkInfo.EndY + 1) IsOK = true;
if (Popped.CurrX == pLinkInfo.EndX - 1 && Popped.CurrY == pLinkInfo.EndY) IsOK = true;
if (Popped.CurrX == pLinkInfo.EndX + 1 && Popped.CurrY == pLinkInfo.EndY) IsOK = true;
if (IsOK) return true;
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB < pNewX) return;
if (pNewY < 0 || UB < pNewY) return;
if (pBanArr[pNewX, pNewY] != '□') return;
//再訪防止
if (VisitedSet.Add(PointToInt(pNewX, 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);
}
//Console.WriteLine("{0}へのリンクを貼れませんでした", pLinkInfo.ID);
//Console.WriteLine("pCurrX={0},pCurrY={1}", pCurrX, pCurrY);
//PrintBan(pBanArr);
return false;
}
//リンクが凹の形なら枝切り
static bool HasHekomiLink(char[,] pBanArr)
{
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
if (pBanArr[X, Y] != '□') continue;
var NumList = new List<char>();
Action<int, int> wkAct = (pTargetX, pTargetY) =>
{
if (pTargetX < 0 || UB < pTargetX) return;
if (pTargetY < 0 || UB < pTargetY) return;
if (pBanArr[pTargetX, pTargetY] == '□') return;
NumList.Add(pBanArr[pTargetX, pTargetY]);
};
wkAct(X, Y - 1);
wkAct(X, Y + 1);
wkAct(X - 1, Y);
wkAct(X + 1, Y);
if (NumList.GroupBy(A => A).Any(A => A.Count() >= 3))
return true;
}
}
return false;
}
//4近傍の値のList(直近とゴールは除外)を返す
static List<char> Derive4KinbouList(char[,] pBanArr,
PointDef pPrevPoint, PointDef pCurrPoint, PointDef pGoalPoint)
{
var WillReturn = new List<char>();
int CurrX = pCurrPoint.X;
int CurrY = pCurrPoint.Y;
Action<int, int> wkAct = (pTargetX, pTargetY) =>
{
if (pTargetX < 0 || UB < pTargetX) return;
if (pTargetY < 0 || UB < pTargetY) return;
if (pTargetX == pPrevPoint.X && pTargetY == pPrevPoint.Y)
return;
if (pTargetX == pGoalPoint.X && pTargetY == pGoalPoint.Y)
return;
WillReturn.Add(pBanArr[pTargetX, pTargetY]);
};
wkAct(CurrX, CurrY - 1);
wkAct(CurrX, CurrY + 1);
wkAct(CurrX - 1, CurrY);
wkAct(CurrX + 1, CurrY);
return WillReturn;
}
struct LinkInfoDef
{
internal char ID;
internal int StaX;
internal int StaY;
internal int EndX;
internal int EndY;
}
static LinkInfoDef[] mLinkInfoArr;
//リンクの開始座標と終了座標を取得
static void DeriveLinkInfoArr()
{
var LinkInfoList = new List<LinkInfoDef>();
char[] IDArr = mQuestionArr.Cast<char>().Where(A => A != '□').Distinct().ToArray();
Array.Sort(IDArr);
LinkInfoDef WillAdd;
foreach (char EachID in IDArr) {
WillAdd.ID = EachID;
WillAdd.StaX = WillAdd.StaY = -1;
WillAdd.EndX = WillAdd.EndY = -1;
int HitCnt = 0;
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
if (mQuestionArr[X, Y] != EachID) continue;
HitCnt++;
if (HitCnt == 1) {
WillAdd.StaX = X; WillAdd.StaY = Y;
}
if (HitCnt == 2) {
WillAdd.EndX = X; WillAdd.EndY = Y;
LinkInfoList.Add(WillAdd);
}
}
}
}
mLinkInfoArr = LinkInfoList.ToArray();
}
//X座標とY座標のペアをInt型に変換
static int PointToInt(int pX, int pY)
{
return pX * (UB + 1) + pY;
}
//盤面を出力
static void PrintBan(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB; Y++) {
for (int X = 0; X <= UB; X++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
実行結果
解説