碁石の白と黒が8個ずつFig.1のように並んでいる。この白と黒をそっくり入れ換えたい。
どの石も線に沿って進まなければならない。さらに・・・
１) 白は右上か右下の方向、黒は左上か左下の方向にしか進めない。つまり前進しかできない
２) どの石も、進行方向のすぐ隣が空所ならそこへ移動できる
３) どの石も進行方向のすぐ隣に違った色の石が1個あってそのまた先が空所のときは、その石を飛び越えて移動できる
以上のルールで完成してほしい。黒白交互に動く必要はない。
Fig.1 碁の並び
解答の例をひとつあげよう。Fig.2のように盤に番号をつける。
11, 7, 9, 8,10,13,11,14, 9, 6,
8, 5, 7,11, 9,10, 8, 2, 1, 6,
3, 5, 7, 4, 9,12,15,17,14,16,
13,15,11, 7, 9,14,11,13,10, 8,
9, 6, 8, 2, 5, 7,11, 9,12,10,
8, 9
52手かかっている。もっと少ない手数でできるのは確かである。
さて、あなたは何手にまで縮めることができるか。
Fig.2 碁の位置番号
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 17;
struct JyoutaiDef
{
internal int Level;
internal char[] GoishiArr; //添え字の0は使用しない
internal List<char[]> GoishiArrLog;
}
static void Main()
{
//ノード間のネットワーク図を作成
DeriveNodeNetWork();
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.Level = 0;
WillPush.GoishiArr = new char[UB + 1];
for (int I = 1; I <= 8; I++) WillPush.GoishiArr[I] = '○';
WillPush.GoishiArr[9] = '空';
for (int I = 10; I <= 17; I++) WillPush.GoishiArr[I] = '●';
WillPush.GoishiArrLog = new List<char[]>() { WillPush.GoishiArr };
stk.Push(WillPush);
int AnswerLevel = int.MaxValue;
var MinTesuuDict = new Dictionary<string, int>();
MinTesuuDict.Add(GetHash(WillPush.GoishiArr), 0);
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//下限値枝切り
if (AnswerLevel <= Popped.Level + CalcNeedMinTesuu(Popped.GoishiArr)) continue;
//クリア判定
if (IsClear(Popped.GoishiArr)) {
Console.WriteLine("手数={0}の解候補を発見", Popped.Level);
for (int I = 0; I <= Popped.GoishiArrLog.Count - 1; I++) {
if (I > 0) Console.WriteLine("{0}手目", I);
PrintBan(Popped.GoishiArrLog[I]);
}
AnswerLevel = Popped.Level;
continue;
}
//碁石の移動処理
int SpaceInd = Array.IndexOf<char>(Popped.GoishiArr, '空');
Action<int, int> PushSyori = (pFrom, pTo) =>
{
WillPush.Level = Popped.Level + 1;
WillPush.GoishiArr = (char[])Popped.GoishiArr.Clone();
WillPush.GoishiArr[pFrom] = Popped.GoishiArr[pTo];
WillPush.GoishiArr[pTo] = Popped.GoishiArr[pFrom];
int MinTesuu;
string Hash = GetHash(WillPush.GoishiArr);
if (MinTesuuDict.TryGetValue(Hash, out MinTesuu)) {
if (MinTesuu <= WillPush.Level)
return;
}
MinTesuuDict[Hash] = WillPush.Level;
WillPush.GoishiArrLog = new List<char[]>(Popped.GoishiArrLog) { WillPush.GoishiArr };
stk.Push(WillPush);
};
//白石が1マス移動
foreach (NodeNetWork1 EachFromTo in NodeNetWork1Arr.Where(X => X.ToPos == SpaceInd)) {
if (Popped.GoishiArr[EachFromTo.FromPos] != '○') continue;
PushSyori(EachFromTo.FromPos, EachFromTo.ToPos);
//初手では、白石が1マス移動とする
if (Popped.Level == 0) break;
}
//初手では、白石が1マス移動とする
if (Popped.Level == 0) continue;
//黒石が1マス移動
foreach (NodeNetWork1 EachFromTo in NodeNetWork1Arr.Where(X => X.FromPos == SpaceInd)) {
if (Popped.GoishiArr[EachFromTo.ToPos] != '●') continue;
PushSyori(EachFromTo.ToPos, EachFromTo.FromPos);
}
//白石が2マス移動
foreach (NodeNetWork2 EachFromTo in NodeNetWork2Arr.Where(X => X.ToPos == SpaceInd)) {
if (Popped.GoishiArr[EachFromTo.FromPos] != '○') continue;
if (Popped.GoishiArr[EachFromTo.JumpPos] != '●') continue;
PushSyori(EachFromTo.FromPos, EachFromTo.ToPos);
}
//黒石が2マス移動
foreach (NodeNetWork2 EachFromTo in NodeNetWork2Arr.Where(X => X.FromPos == SpaceInd)) {
if (Popped.GoishiArr[EachFromTo.ToPos] != '●') continue;
if (Popped.GoishiArr[EachFromTo.JumpPos] != '○') continue;
PushSyori(EachFromTo.ToPos, EachFromTo.FromPos);
}
}
Console.WriteLine("最少手数は{0}手です。", AnswerLevel);
}
//移動のネットワーク図 (飛び越しなし)
struct NodeNetWork1
{
internal int FromPos;
internal int ToPos;
}
static NodeNetWork1[] NodeNetWork1Arr;
//移動のネットワーク図 (飛び越しあり)
struct NodeNetWork2
{
internal int FromPos;
internal int JumpPos;
internal int ToPos;
}
static NodeNetWork2[] NodeNetWork2Arr;
//移動のネットワーク図を作成
static void DeriveNodeNetWork()
{
var NodeNetWork1List = new List<NodeNetWork1>();
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 1, ToPos = 2 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 1, ToPos = 3 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 2, ToPos = 4 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 2, ToPos = 5 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 3, ToPos = 5 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 3, ToPos = 6 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 4, ToPos = 7 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 5, ToPos = 7 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 5, ToPos = 8 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 6, ToPos = 8 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 7, ToPos = 9 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 8, ToPos = 9 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 9, ToPos = 10 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 9, ToPos = 11 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 10, ToPos = 12 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 10, ToPos = 13 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 11, ToPos = 13 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 11, ToPos = 14 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 12, ToPos = 15 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 13, ToPos = 15 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 13, ToPos = 16 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 14, ToPos = 16 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 15, ToPos = 17 });
NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 16, ToPos = 17 });
NodeNetWork1Arr = NodeNetWork1List.ToArray();
var NodeNetWork2List = new List<NodeNetWork2>();
NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 1, JumpPos = 2, ToPos = 4 });
NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 1, JumpPos = 3, ToPos = 6 });
NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 2, JumpPos = 5, ToPos = 8 });
NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 3, JumpPos = 5, ToPos = 7 });
NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 4, JumpPos = 7, ToPos = 9 });
NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 6, JumpPos = 8, ToPos = 9 });
NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 7, JumpPos = 9, ToPos = 11 });
NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 8, JumpPos = 9, ToPos = 10 });
NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 9, JumpPos = 10, ToPos = 12 });
NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 9, JumpPos = 11, ToPos = 14 });
NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 10, JumpPos = 13, ToPos = 16 });
NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 11, JumpPos = 13, ToPos = 15 });
NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 12, JumpPos = 15, ToPos = 17 });
NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 14, JumpPos = 16, ToPos = 17 });
NodeNetWork2Arr = NodeNetWork2List.ToArray();
}
//クリア判定
static bool IsClear(char[] pGoishiArr)
{
for (int I = 1; I <= 8; I++)
if (pGoishiArr[I] != '●') return false;
if (pGoishiArr[9] != '空') return false;
for (int I = 10; I <= 17; I++)
if (pGoishiArr[I] != '○') return false;
return true;
}
//必要な最低手数を求める
static int CalcNeedMinTesuu(char[] pGoishiArr)
{
int MinTesuu = 0;
if (pGoishiArr[1] == '○') MinTesuu += 3;
if (pGoishiArr[2] == '○') MinTesuu += 2;
if (pGoishiArr[3] == '○') MinTesuu += 2;
if (pGoishiArr[4] == '○') MinTesuu += 2;
if (pGoishiArr[5] == '○') MinTesuu += 2;
if (pGoishiArr[6] == '○') MinTesuu += 2;
if (pGoishiArr[7] == '○') MinTesuu++;
if (pGoishiArr[8] == '○') MinTesuu++;
if (pGoishiArr[9] != '空') MinTesuu++;
if (pGoishiArr[10] == '●') MinTesuu++;
if (pGoishiArr[11] == '●') MinTesuu++;
if (pGoishiArr[12] == '●') MinTesuu += 2;
if (pGoishiArr[13] == '●') MinTesuu += 2;
if (pGoishiArr[14] == '●') MinTesuu += 2;
if (pGoishiArr[15] == '●') MinTesuu += 2;
if (pGoishiArr[16] == '●') MinTesuu += 2;
if (pGoishiArr[17] == '●') MinTesuu += 3;
return MinTesuu;
}
//盤面をハッシュ値に変換
static string GetHash(char[] pGoishiArr)
{
var sb = new System.Text.StringBuilder();
Array.ForEach(pGoishiArr, X => sb.Append(X));
return sb.ToString();
}
//盤面を表示
static void PrintBan(char[] pGoishiArr)
{
const string SP = " ";
var sb = new System.Text.StringBuilder();
sb.AppendFormat("{0}{0}{1}{0}{0}{0}{2}", SP, pGoishiArr[4], pGoishiArr[12]);
sb.AppendLine();
sb.AppendFormat("{0}{1}{0}{2}{0}{3}{0}{4}",
SP, pGoishiArr[2], pGoishiArr[7], pGoishiArr[10], pGoishiArr[15]);
sb.AppendLine();
sb.AppendFormat("{1}{0}{2}{0}{3}{0}{4}{0}{5}",
SP, pGoishiArr[1], pGoishiArr[5], pGoishiArr[9], pGoishiArr[13], pGoishiArr[17]);
sb.AppendLine();
sb.AppendFormat("{0}{1}{0}{2}{0}{3}{0}{4}",
SP, pGoishiArr[3], pGoishiArr[8], pGoishiArr[11], pGoishiArr[16]);
sb.AppendLine();
sb.AppendFormat("{0}{0}{1}{0}{0}{0}{2}", SP, pGoishiArr[6], pGoishiArr[14]);
sb.AppendLine();
Console.WriteLine(sb.ToString());
}
}