using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB_X = 4;
const int UB_Y = 3;
struct PointDef
{
internal int X;
internal int Y;
}
static char[,] mQuestionArr = new char[UB_X + 1, UB_Y + 1]; //問題の初期盤面
//交換パターン
struct ChangePatternDef
{
internal int[] ChangeArr; //交換後の位置番号[交換前の位置番号]な配列
internal int Cost;
}
static ChangePatternDef[] mChangePatternArr;
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
//移動パターンの配列を作成
Console.WriteLine("移動パターンの配列を作成します");
CreateMovePatternArr();
//解となる移動パターンの組み合わせをDFSで求める
//Console.WriteLine("解となる移動パターンの組み合わせをDFSで求めます");
//DeriveAnswerPattern();
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
struct JyoutaiDefBFS
{
internal char[,] BanArr;
internal int Level;
}
//移動パターンの配列を作成
static void CreateMovePatternArr()
{
var ChangePatternList = new List<ChangePatternDef>();
var Que = new Queue<JyoutaiDefBFS>();
JyoutaiDefBFS WillEnqueue;
WillEnqueue.BanArr = new char[UB_X + 1, UB_Y + 1];
string[] wkArr ={"０１２３４",
"ＸＸ□■Ｙ",
"Ｘ■□ＹＹ",
"５６７８９"};
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
WillEnqueue.BanArr[X, Y] = wkArr[Y][X];
}
}
WillEnqueue.Level = 0;
Que.Enqueue(WillEnqueue);
var VisitedSet = new HashSet<long>();
VisitedSet.Add(GetHash(WillEnqueue.BanArr));
while (Que.Count > 0) {
JyoutaiDefBFS Popped = Que.Dequeue();
//移動パターンの終了判定
if (Popped.Level >= 1 && IsEndMovePattern(Popped.BanArr)) {
ChangePatternList.Add(DeriveMovePattern(Popped));
Console.WriteLine("入替パターン{0}。({1}手)", ChangePatternList.Count, Popped.Level);
PrintBan(Popped.BanArr);
continue;
}
foreach (char EachPiece in "ＸＹ０１２３４５６７８９") {
//盤面とピースを引数として、1手後の盤面のListを返す
List<char[,]> MovedArrList = DeriveMovedArrList(Popped.BanArr, EachPiece);
foreach (char[,] EachMovedArr in MovedArrList) {
WillEnqueue.BanArr = EachMovedArr;
WillEnqueue.Level = Popped.Level + 1;
//再訪防止
long CurrHash = GetHash(WillEnqueue.BanArr);
if (VisitedSet.Add(CurrHash) == false)
continue;
Que.Enqueue(WillEnqueue);
}
}
}
//コストの昇順でソートしておく
mChangePatternArr = ChangePatternList.OrderBy(A => A.Cost).ToArray();
}
//移動情報を作成して返す
static ChangePatternDef DeriveMovePattern(JyoutaiDefBFS pJyoutai)
{
ChangePatternDef WillReturn;
WillReturn.ChangeArr = new int[10];
for (int I = 0; I <= 4; I++)
WillReturn.ChangeArr[I] = pJyoutai.BanArr[I, 0] - '０';
for (int I = 5; I <= 9; I++)
WillReturn.ChangeArr[I] = pJyoutai.BanArr[I - 5, 3] - '０';
WillReturn.Cost = pJyoutai.Level;
return WillReturn;
}
//移動パターンの終了判定
static bool IsEndMovePattern(char[,] pBanArr)
{
Predicate<char> IsNumPred = (pChar) =>
'０' <= pChar && pChar <= '９';
if (IsNumPred(pBanArr[0, 0]) == false) return false;
if (IsNumPred(pBanArr[1, 0]) == false) return false;
if (IsNumPred(pBanArr[2, 0]) == false) return false;
if (IsNumPred(pBanArr[3, 0]) == false) return false;
if (IsNumPred(pBanArr[4, 0]) == false) return false;
if (IsNumPred(pBanArr[0, 3]) == false) return false;
if (IsNumPred(pBanArr[1, 3]) == false) return false;
if (IsNumPred(pBanArr[2, 3]) == false) return false;
if (IsNumPred(pBanArr[3, 3]) == false) return false;
if (IsNumPred(pBanArr[4, 3]) == false) return false;
if (pBanArr[2, 1] != '□') return false;
if (pBanArr[2, 2] != '□') return false;
return true;
}
struct MoveInfoDef
{
internal char[,] BanArr;
internal PointDef FromPos;
}
//盤面とピースを引数として、1手後の盤面のListを返す
static List<char[,]> DeriveMovedArrList(char[,] pBanArr, char pPiece)
{
var WillReturn = new List<char[,]>();
PointDef PiecePoint = DerivePiecePoint(pBanArr, pPiece);
var Stk = new Stack<MoveInfoDef>();
MoveInfoDef WillPush;
WillPush.BanArr = pBanArr;
WillPush.FromPos = PiecePoint;
Stk.Push(WillPush);
var VisitedSet = new HashSet<long>();
while (Stk.Count > 0) {
MoveInfoDef Popped = Stk.Pop();
MoveInfoDef[] MovedInfoArr =
DeriveMovedInfoArr(Popped.BanArr, pPiece, Popped.FromPos);
foreach (MoveInfoDef EachJyoutai in MovedInfoArr) {
long CurrHash = GetHash(EachJyoutai.BanArr);
if (CurrHash == GetHash(pBanArr)) continue;
if (VisitedSet.Add(CurrHash) == false) continue;
WillReturn.Add(EachJyoutai.BanArr);
//1手で複数マス動けるピースの場合
if (pPiece != 'Ｘ' && pPiece != 'Ｙ') {
Stk.Push(EachJyoutai);
}
}
}
return WillReturn;
}
//盤面とピースを引数として、移動情報の配列を返す
static MoveInfoDef[] DeriveMovedInfoArr(char[,] pBanArr, char pPiece, PointDef pFromPos)
{
var WillReturn = new List<MoveInfoDef>();
int FromX = pFromPos.X, FromY = pFromPos.Y;
Action<char[,], int, int> AddAct1 = (pArr, pToX, pToY) =>
{
MoveInfoDef WillAdd;
WillAdd.BanArr = pArr;
WillAdd.FromPos = new PointDef() { X = pToX, Y = pToY };
WillReturn.Add(WillAdd);
};
if (pPiece == 'Ｘ') {
//上に移動
if (IsSpace(pBanArr, FromX, FromY - 1)
&& IsSpace(pBanArr, FromX + 1, FromY - 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX, FromY - 1] = wkArr[FromX + 1, FromY - 1] = 'Ｘ';
wkArr[FromX + 1, FromY] = '□';
wkArr[FromX, FromY + 1] = '□';
AddAct1(wkArr, FromX, FromY - 1);
}
//下に移動
if (IsSpace(pBanArr, FromX, FromY + 2)
&& IsSpace(pBanArr, FromX + 1, FromY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX, FromY] = wkArr[FromX + 1, FromY] = '□';
wkArr[FromX + 1, FromY + 1] = 'Ｘ';
wkArr[FromX, FromY + 2] = 'Ｘ';
AddAct1(wkArr, FromX, FromY + 1);
}
//左に移動
if (IsSpace(pBanArr, FromX - 1, FromY)
&& IsSpace(pBanArr, FromX - 1, FromY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX - 1, FromY] = wkArr[FromX - 1, FromY + 1] = 'Ｘ';
wkArr[FromX, FromY + 1] = '□';
wkArr[FromX + 1, FromY] = '□';
AddAct1(wkArr, FromX - 1, FromY);
}
//右に移動
if (IsSpace(pBanArr, FromX + 2, FromY)
&& IsSpace(pBanArr, FromX + 1, FromY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX + 2, FromY] = 'Ｘ';
wkArr[FromX + 1, FromY + 1] = 'Ｘ';
wkArr[FromX, FromY] = wkArr[FromX, FromY + 1] = '□';
AddAct1(wkArr, FromX + 1, FromY);
}
}
if (pPiece == 'Ｙ') {
//上に移動
if (IsSpace(pBanArr, FromX - 1, FromY)
&& IsSpace(pBanArr, FromX, FromY - 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX - 1, FromY] = 'Ｙ';
wkArr[FromX, FromY - 1] = 'Ｙ';
wkArr[FromX - 1, FromY + 1] = wkArr[FromX, FromY + 1] = '□';
AddAct1(wkArr, FromX, FromY - 1);
}
//下に移動
if (IsSpace(pBanArr, FromX - 1, FromY + 2)
&& IsSpace(pBanArr, FromX, FromY + 2)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX, FromY] = '□';
wkArr[FromX - 1, FromY + 1] = '□';
wkArr[FromX - 1, FromY + 2] = wkArr[FromX, FromY + 2] = 'Ｙ';
AddAct1(wkArr, FromX, FromY + 1);
}
//左に移動
if (IsSpace(pBanArr, FromX - 2, FromY + 1)
&& IsSpace(pBanArr, FromX - 1, FromY)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX - 2, FromY + 1] = 'Ｙ';
wkArr[FromX - 1, FromY] = 'Ｙ';
wkArr[FromX, FromY] = wkArr[FromX, FromY + 1] = '□';
AddAct1(wkArr, FromX - 1, FromY);
}
//右に移動
if (IsSpace(pBanArr, FromX + 1, FromY)
&& IsSpace(pBanArr, FromX + 1, FromY + 1)) {
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[FromX + 1, FromY] = 'Ｙ';
wkArr[FromX + 1, FromY + 1] = 'Ｙ';
wkArr[FromX - 1, FromY + 1] = wkArr[FromX, FromY] = '□';
AddAct1(wkArr, FromX + 1, FromY);
}
}
if ("０１２３４５６７８９".Contains(pPiece)) {
Action<int, int> AddAct2 = (pToX, pToY) =>
{
if (IsSpace(pBanArr, pToX, pToY) == false) return;
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[pToX, pToY] = pPiece; wkArr[FromX, FromY] = '□';
MoveInfoDef WillAdd;
WillAdd.BanArr = wkArr;
WillAdd.FromPos = new PointDef() { X = pToX, Y = pToY };
WillReturn.Add(WillAdd);
};
//上に移動
AddAct2(FromX, FromY - 1);
//下に移動
AddAct2(FromX, FromY + 1);
//左に移動
AddAct2(FromX - 1, FromY);
//右に移動
AddAct2(FromX + 1, FromY);
}
return WillReturn.ToArray();
}
//座標が空白かを判定
static bool IsSpace(char[,] pBanArr, int pX, int pY)
{
if (pX < 0 || UB_X < pX) return false;
if (pY < 0 || UB_Y < pY) return false;
return pBanArr[pX, pY] == '□';
}
//盤面とピースを引数として、ピースの左上の座標を返す
static PointDef DerivePiecePoint(char[,] pBanArr, char pPiece)
{
for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
if (pBanArr[LoopX, LoopY] == pPiece) {
return new PointDef() { X = LoopX, Y = LoopY };
}
}
}
return new PointDef() { X = -1, Y = -1 };
}
//ハッシュ値を求める
static long GetHash(char[,] pBanArr)
{
long WillReturn = 0;
var AppearedSet = new HashSet<char>();
char[] wkArr = "□ＸＹ０１２３４５６７８９".ToArray();
long Omomi = 1;
for (int X = 0; X <= UB_X; X++) {
for (int Y = 0; Y <= UB_Y; Y++) {
char CurrChar = pBanArr[X, Y];
if (CurrChar == '■') continue;
if (CurrChar == 'Ｘ' || CurrChar == 'Ｙ')
if (AppearedSet.Add(CurrChar) == false)
continue;
int CurrNum = Array.IndexOf(wkArr, CurrChar);
WillReturn += CurrNum * Omomi;
Omomi *= 13;
}
}
//13の15乗=51185893014090757なのでLong型ならオーバーフローしない
return WillReturn;
}
struct JyoutaiDefDFS
{
internal char[] TopBottomArr;
internal int Level;
internal List<int> ChangePatternIDList;
}
static void DeriveAnswerPattern()
{
var Stk = new Stack<JyoutaiDefDFS>();
JyoutaiDefDFS WillPush;
WillPush.TopBottomArr = "ＢＬＡＣＫＷＨＩＴＥ".ToCharArray();
WillPush.Level = 0;
WillPush.ChangePatternIDList = new List<int>();
Stk.Push(WillPush);
var MinTesuuDict = new Dictionary<string, int>();
MinTesuuDict.Add(GetHash2(WillPush.TopBottomArr), 0);
int LeafCnt = 0;
while (Stk.Count > 0) {
JyoutaiDefDFS Popped = Stk.Pop();
LeafCnt++;
if (IsClear(Popped.TopBottomArr)) {
Console.WriteLine("{0}手の解を発見", Popped.Level);
continue;
}
foreach (ChangePatternDef EachChangePattern in mChangePatternArr) {
WillPush.TopBottomArr = Popped.TopBottomArr;
WillPush.Level = Popped.Level + EachChangePattern.Cost;
if (WillPush.Level > 190)
break;
Stk.Push(WillPush);
}
}
Console.WriteLine("葉ノード数={0}", LeafCnt);
}
//クリア判定
static bool IsClear(char[] pTopBottomArr)
{
return pTopBottomArr.SequenceEqual("ＷＨＩＴＥＢＬＡＣＫ");
}
static string GetHash2(char[] pTopBottomArr)
{
return "";
}
//盤面を出力
static void PrintBan(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
sb.Append(pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
黒(BLACK)と白(WHITE)を入れ換えるスライドパズル。 中央の2つの赤いピースは、盤に固定されてます。 最少手数は190手。