using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
struct PointDef
{
internal int X;
internal int Y;
}
static char[,] mQuestionArr;
static int UB_X;
static int UB_Y;
static char[] mNumArr;
//問題を定義
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];
}
}
mNumArr = mQuestionArr.Cast<char>().Distinct().ToArray();
}
static void Main()
{
//問題を定義
QuestionDef();
//黒マスが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] = ' ';
}
}
//第1フェーズ 初回の確定探索
SyokaiKakuteiTansaku(BlackWhiteArr);
//第2フェーズ 確定探索
ExecKakuteiTansaku(BlackWhiteArr);
//第3フェーズ 確定探索付の深さ優先探索
ExecDFS(BlackWhiteArr);
}
//第1フェーズ 初回の確定探索
static void SyokaiKakuteiTansaku(char[,] pBlackWhiteArr)
{
//確定探索1 同じ数字に1マスだけ挟まれたマスは、白マスで確定
KakuteiTansaku1(pBlackWhiteArr);
//確定探索2 4隅とその周囲が同じ数字なら、4隅は黒マスで確定
KakuteiTansaku2(pBlackWhiteArr);
//確定探索3 □２２□□２の場合は、右端の２が黒マスで確定
KakuteiTansaku3(pBlackWhiteArr);
}
//確定探索1 同じ数字に1マスだけ挟まれたマスは、白マスで確定
static void KakuteiTansaku1(char[,] pBlackWhiteArr)
{
//右方向のチェック
for (int X = 0; X <= UB_X - 2; X++)
for (int Y = 0; Y <= UB_Y; Y++)
if (mQuestionArr[X, Y] == mQuestionArr[X + 2, Y])
SetWhite(pBlackWhiteArr, X + 1, Y);
//下方向のチェック
for (int X = 0; X <= UB_X; X++)
for (int Y = 0; Y <= UB_Y - 2; Y++)
if (mQuestionArr[X, Y] == mQuestionArr[X, Y + 2])
SetWhite(pBlackWhiteArr, X, Y + 1);
}
//確定探索2 4隅とその周囲が同じ数字なら、4隅は黒マスで確定
static void KakuteiTansaku2(char[,] pBlackWhiteArr)
{
Action<int, int> SetAct = (pX, pY) =>
{
PointDef[] KinbouPointArr = DeriveKinbouPointArr(pX, pY);
if (Array.TrueForAll(KinbouPointArr,
A => mQuestionArr[A.X, A.Y] == mQuestionArr[pX, pY])) {
SetBlack(pBlackWhiteArr, pX, pY);
}
};
SetAct(0, 0);
SetAct(0, UB_Y);
SetAct(UB_X, 0);
SetAct(UB_Y, UB_Y);
}
//確定探索3 □２２□□２の場合は、右端の２が黒マスで確定
static void KakuteiTansaku3(char[,] pBlackWhiteArr)
{
foreach (char EachNum in mNumArr) {
//右方向のチェック
for (int Y = 0; Y <= UB_Y; Y++) {
var SeqPosSet = new HashSet<int>();
for (int X = 0; X <= UB_X - 1; X++) {
if (mQuestionArr[X, Y] != EachNum) continue;
if (mQuestionArr[X, Y] == mQuestionArr[X + 1, Y]) {
SeqPosSet.Add(X);
SeqPosSet.Add(X + 1);
break;
}
}
if (SeqPosSet.Count == 0) continue;
for (int X = 0; X <= UB_X; X++) {
if (mQuestionArr[X, Y] != EachNum) continue;
if (SeqPosSet.Contains(X)) continue;
SetBlack(pBlackWhiteArr, X, Y);
}
}
//下方向のチェック
for (int X = 0; X <= UB_X; X++) {
var SeqPosSet = new HashSet<int>();
for (int Y = 0; Y <= UB_Y - 1; Y++) {
if (mQuestionArr[X, Y] != EachNum) continue;
if (mQuestionArr[X, Y] == mQuestionArr[X, Y + 1]) {
SeqPosSet.Add(Y);
SeqPosSet.Add(Y + 1);
break;
}
}
if (SeqPosSet.Count == 0) continue;
for (int Y = 0; Y <= UB_Y; Y++) {
if (mQuestionArr[X, Y] != EachNum) continue;
if (SeqPosSet.Contains(Y)) continue;
SetBlack(pBlackWhiteArr, X, Y);
}
}
}
}
//第2フェーズ 確定探索
static void ExecKakuteiTansaku(char[,] pBlackWhiteArr)
{
while (true) {
char[,] PrevArr = (char[,])pBlackWhiteArr.Clone();
//確定探索4 黒マスだと閉路ができるマスは、白マスで確定
KakuteiTansaku4(pBlackWhiteArr);
//確定探索5 白マスだと、上下左右に発生する黒マスで閉路ができる場合、黒マスで確定
KakuteiTansaku5(pBlackWhiteArr);
//確定探索で確定するマスがなくなったらBreak
if (pBlackWhiteArr.Cast<char>().SequenceEqual(PrevArr.Cast<char>())) break;
}
}
//確定探索4 黒マスだと閉路ができるマスは、白マスで確定
static void KakuteiTansaku4(char[,] pBlackWhiteArr)
{
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
if (pBlackWhiteArr[X, Y] != ' ') continue;
char[,] CopiedArr = (char[,])pBlackWhiteArr.Clone();
CopiedArr[X, Y] = 'B';
if (HasBundan(CopiedArr)) {
SetWhite(pBlackWhiteArr, X, Y);
}
}
}
}
//確定探索5 白マスだと、上下左右に発生する黒マスで閉路ができる場合、黒マスで確定
static void KakuteiTansaku5(char[,] pBlackWhiteArr)
{
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
if (pBlackWhiteArr[X, Y] != ' ') continue;
//座標を引数として、上下左右で同じ数字の座標の配列を返す
PointDef[] SameNumPointArr = DeriveSameNumPointArr(pBlackWhiteArr, X, Y);
if (SameNumPointArr.Length == 0) continue;
char[,] CopiedArr = (char[,])pBlackWhiteArr.Clone();
SetWhite(CopiedArr, X, Y);
if (HasBundan(CopiedArr)) {
SetBlack(pBlackWhiteArr, X, Y);
}
}
}
}
//第3フェーズ 確定探索付の深さ優先探索
static void ExecDFS(char[,] pBlackWhiteArr)
{
var Stk = new Stack<char[,]>();
char[,] WillPushBanArr = pBlackWhiteArr;
Stk.Push(WillPushBanArr);
while (Stk.Count > 0) {
char[,] PoppedBanArr = Stk.Pop();
//クリア判定
bool IsValid;
if (IsClear(PoppedBanArr, out IsValid)) {
Console.WriteLine("解を発見");
PrintBan(PoppedBanArr, true);
return;
}
if (IsValid == false) continue;
bool WillBreak = false;
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
if (PoppedBanArr[X, Y] != ' ') continue;
Action<int, int> PushSyori = (pWhiteX, pWhiteY) =>
{
WillPushBanArr = (char[,])PoppedBanArr.Clone();
SetWhite(WillPushBanArr, pWhiteX, pWhiteY);
ExecKakuteiTansaku(WillPushBanArr);
Stk.Push(WillPushBanArr);
};
//座標を引数として、上下左右で同じ数字の座標の配列を返す
PointDef[] SameNumPointArr = DeriveSameNumPointArr(pBlackWhiteArr, X, Y);
SameNumPointArr =
Array.FindAll(SameNumPointArr, A => PoppedBanArr[A.X, A.Y] == ' ');
if (SameNumPointArr.Length == 0) continue;
PushSyori(X, Y);
//横方向で同じ数字の座標
PointDef[] YokoPointArr = Array.FindAll(SameNumPointArr, A => A.Y == Y);
if (YokoPointArr.Length > 0) {
Array.ForEach(YokoPointArr, A => PushSyori(A.X, A.Y));
}
else {
//縦方向で同じ数字の座標
Array.ForEach(SameNumPointArr, A => PushSyori(A.X, A.Y));
}
WillBreak = true;
break;
}
if (WillBreak) break;
}
}
}
//クリア判定
static bool IsClear(char[,] pBlackWhiteArr, out bool pIsValid)
{
pIsValid = true;
//条件1 上下左右に重複した数字がないこと
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
if (pBlackWhiteArr[X, Y] == 'B') continue;
//座標を引数として、上下左右で同じ数字の座標の配列を返す
PointDef[] SameNumPointArr = DeriveSameNumPointArr(pBlackWhiteArr, X, Y);
if (SameNumPointArr.Length > 0) return false;
}
}
//条件2 黒マスが連結していないこと
//横の連結のチェック
for (int X = 0; X <= UB_X - 1; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
if (pBlackWhiteArr[X, Y] == 'B' && pBlackWhiteArr[X + 1, Y] == 'B') {
pIsValid = false;
return false;
}
}
}
//縦の連結のチェック
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y - 1; Y++) {
if (pBlackWhiteArr[X, Y] == 'B' && pBlackWhiteArr[X, Y + 1] == 'B') {
pIsValid = false;
return false;
}
}
}
//条件3 黒マスで分断されてないこと
if (HasBundan(pBlackWhiteArr)) {
pIsValid = false;
return false;
}
return true;
}
struct JyoutaiDefUnionFind
{
internal int CurrX;
internal int CurrY;
}
//黒マスで盤面が分断されてないかを判定
static bool HasBundan(char[,] pBlackWhiteArr)
{
int StaX = -1, StaY = -1;
bool WillBreak = false;
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
if (pBlackWhiteArr[X, Y] != 'B') {
StaX = X;
StaY = Y;
WillBreak = true;
break;
}
}
if (WillBreak) break;
}
var Stk = new Stack<JyoutaiDefUnionFind>();
JyoutaiDefUnionFind WillPush;
WillPush.CurrX = StaX;
WillPush.CurrY = StaY;
Stk.Push(WillPush);
var VisitedSet = new HashSet<int>();
VisitedSet.Add(StaX * (UB_Y + 1) + StaY);
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;
if (pBlackWhiteArr[pNewX, pNewY] == 'B') return;
//再訪不可
if (VisitedSet.Add(pNewX * (UB_Y + 1) + pNewY) == false)
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);
}
int NeedCnt = pBlackWhiteArr.Cast<char>().Count(A => A != 'B');
return VisitedSet.Count < NeedCnt;
}
//黒マスを設置し、4近傍を白マスにする
static void SetBlack(char[,] pBlackWhiteArr, int pX, int pY)
{
if (pBlackWhiteArr[pX, pY] != ' ') return;
pBlackWhiteArr[pX, pY] = 'B';
PointDef[] KinbouPointArr = DeriveKinbouPointArr(pX, pY);
Array.ForEach(KinbouPointArr, A => SetWhite(pBlackWhiteArr, A.X, A.Y));
}
//白マスを設置し、上下左右に同じ数字があったら、黒マスにする
static void SetWhite(char[,] pBlackWhiteArr, int pX, int pY)
{
if (pBlackWhiteArr[pX, pY] != ' ') return;
pBlackWhiteArr[pX, pY] = 'W';
PointDef[] SameNumPointArr = DeriveSameNumPointArr(pBlackWhiteArr, pX, pY);
Array.ForEach(SameNumPointArr, A => SetBlack(pBlackWhiteArr, A.X, A.Y));
}
//4近傍の座標の配列を返す
static PointDef[] DeriveKinbouPointArr(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 PointDef[] DeriveSameNumPointArr(char[,] pBlackWhiteArr, int pBaseX, int pBaseY)
{
var WillReturn = new List<PointDef>();
char CurrNum = mQuestionArr[pBaseX, pBaseY];
Action<int, int> AddAct = (pHeniX, pHeniY) =>
{
int LoopX = pBaseX;
int LoopY = pBaseY;
while (true) {
LoopX += pHeniX;
LoopY += pHeniY;
if (LoopX < 0 || UB_X < LoopX) break;
if (LoopY < 0 || UB_Y < LoopY) break;
if (pBlackWhiteArr[LoopX, LoopY] == 'B') continue;
if (mQuestionArr[LoopX, LoopY] == CurrNum) {
WillReturn.Add(new PointDef() { X = LoopX, Y = LoopY });
}
}
};
AddAct(0, -1);
AddAct(0, 1);
AddAct(-1, 0);
AddAct(1, 0);
return WillReturn.ToArray();
}
//盤面を出力
static void PrintBan(char[,] pBlackWhiteArr, bool pIsAnswer)
{
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' && pIsAnswer == false) sb.Append('○');
else sb.Append(mQuestionArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
1 盤面に並んでいる数字のうちいくつかを黒くぬって、 タテでもヨコでも同じ列に同じ数字が複数個入らないようにしましょう。 2 黒マスをタテヨコに連続させたり、黒マスで盤面を分断したりしてはいけません。