using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int mQuestionNo = 1;
static char[,] mQuestionArr; //問題の初期盤面
const int UB = 3;
//問題を定義
static void QuestionDef()
{
string[] wkStrArr = null;
if (mQuestionNo == 1) {
wkStrArr = new string[] {"K***",
"*B**",
"P***",
"****"};
}
if (mQuestionNo == 2) {
wkStrArr = new string[] {"****",
"*B**",
"RP**",
"***N"};
}
if (mQuestionNo == 3) {
wkStrArr = new string[] {"R*B*",
"****",
"*N**",
"**P*"};
}
if (mQuestionNo == 4) {
wkStrArr = new string[] {"*P**",
"****",
"R*Q*",
"*B**"};
}
if (mQuestionNo == 5) {
wkStrArr = new string[] {"***R",
"K*P*",
"****",
"K**P"};
}
if (mQuestionNo == 6) {
wkStrArr = new string[] {"*RQ*",
"***P",
"BN**",
"P***"};
}
if (mQuestionNo == 7) {
wkStrArr = new string[] {"R*N*",
"*B*N",
"P*RB",
"P***"};
}
if (mQuestionNo == 8) {
wkStrArr = new string[] {"P***",
"*NB*",
"*BNP",
"R*R*"};
}
if (mQuestionNo == 9) {
wkStrArr = new string[] {"*RB*",
"*PR*",
"B**N",
"P**N"};
}
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];
}
struct JyoutaiDef
{
internal int Level;
internal char[,] BanArr;
internal List<char[,]> Log;
}
static void Main()
{
//問題を定義
QuestionDef();
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.Level = 0;
WillPush.BanArr = mQuestionArr;
WillPush.Log = new List<char[,]>() { WillPush.BanArr };
Stk.Push(WillPush);
//盤面に対する最少手数のDict
var MinTesuuDict = new Dictionary<long, int>();
MinTesuuDict.Add(GetHash(WillPush.BanArr), 0);
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
//クリア判定
if (IsClear(Popped.BanArr)) {
Console.WriteLine("解を発見");
for (int I = 0; I <= Popped.Log.Count - 1; I++) {
Console.WriteLine("レベル{0}", I);
PrintBan(Popped.Log[I]);
}
break;
}
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
if (Popped.BanArr[LoopX, LoopY] == '*') continue;
List<char[,]> MovedBanArrList =
DeriveMovedBanArrList(Popped.BanArr, LoopX, LoopY);
foreach (char[,] EachBanArr in MovedBanArrList) {
WillPush.Level = Popped.Level + 1;
WillPush.BanArr = EachBanArr;
long CurrHash = GetHash(WillPush.BanArr);
if (MinTesuuDict.ContainsKey(CurrHash)) {
if (MinTesuuDict[CurrHash] <= WillPush.Level)
continue;
}
MinTesuuDict[CurrHash] = WillPush.Level;
WillPush.Log = new List<char[,]>(Popped.Log) { WillPush.BanArr };
Stk.Push(WillPush);
}
}
}
}
}
//クリア判定
static bool IsClear(char[,] pBanArr)
{
int PieceCnt = 0;
for (int Y = 0; Y <= UB; Y++)
for (int X = 0; X <= UB; X++)
if (pBanArr[X, Y] != '*')
PieceCnt++;
return PieceCnt == 1;
}
//移動後の盤情報の配列を返す
static List<char[,]> DeriveMovedBanArrList(char[,] pBanArr, int pFromX, int pFromY)
{
var WillReturn = new List<char[,]>();
Func<int, int, bool> MovePiece = (pToX, pToY) =>
{
if (pToX < 0 || UB < pToX) return false;
if (pToY < 0 || UB < pToY) return false;
if (pBanArr[pToX, pToY] == '*') return false;
char[,] wkArr = (char[,])pBanArr.Clone();
wkArr[pToX, pToY] = pBanArr[pFromX, pFromY];
wkArr[pFromX, pFromY] = '*';
WillReturn.Add(wkArr);
return true;
};
char CurrPiece = pBanArr[pFromX, pFromY];
if (CurrPiece == 'P') {
MovePiece(pFromX - 1, pFromY - 1);
MovePiece(pFromX + 1, pFromY - 1);
}
if (CurrPiece == 'N') {
MovePiece(pFromX - 2, pFromY - 1);
MovePiece(pFromX - 2, pFromY + 1);
MovePiece(pFromX - 1, pFromY - 2);
MovePiece(pFromX - 1, pFromY + 2);
MovePiece(pFromX + 1, pFromY - 2);
MovePiece(pFromX + 1, pFromY + 2);
MovePiece(pFromX + 2, pFromY - 1);
MovePiece(pFromX + 2, pFromY - 1);
}
Action<int, int> HeniLoopAct = (pHeniX, pHeniY) =>
{
int CurrX = pFromX + pHeniX;
int CurrY = pFromY + pHeniY;
while (true) {
if (CurrX < 0 || UB < CurrX) break;
if (CurrY < 0 || UB < CurrY) break;
if (MovePiece(CurrX, CurrY)) break;
CurrX += pHeniX;
CurrY += pHeniY;
}
};
if (CurrPiece == 'B' || CurrPiece == 'Q') {
HeniLoopAct(-1, -1);
HeniLoopAct(-1, 1);
HeniLoopAct(1, -1);
HeniLoopAct(1, 1);
}
if (CurrPiece == 'R' || CurrPiece == 'Q') {
HeniLoopAct(0, -1);
HeniLoopAct(0, 1);
HeniLoopAct(-1, 0);
HeniLoopAct(1, 0);
}
if (CurrPiece == 'K') {
MovePiece(pFromX - 1, pFromY - 1);
MovePiece(pFromX + 0, pFromY - 1);
MovePiece(pFromX - 1, pFromY - 1);
MovePiece(pFromX - 1, pFromY + 0);
MovePiece(pFromX + 1, pFromY + 0);
MovePiece(pFromX - 1, pFromY + 1);
MovePiece(pFromX + 0, pFromY + 1);
MovePiece(pFromX + 1, pFromY + 1);
}
return WillReturn;
}
//盤面をハッシュ値に変換
static long GetHash(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
if (pBanArr[X, Y] == '*') sb.Append(0);
if (pBanArr[X, Y] == 'P') sb.Append(1);
if (pBanArr[X, Y] == 'N') sb.Append(2);
if (pBanArr[X, Y] == 'B') sb.Append(3);
if (pBanArr[X, Y] == 'R') sb.Append(4);
if (pBanArr[X, Y] == 'Q') sb.Append(5);
if (pBanArr[X, Y] == 'K') sb.Append(6);
}
}
//8の16乗=281474976710656なので8進数ならオーバーフローしない
return Convert.ToInt64(sb.ToString(), 8);
}
//盤面を出力
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());
}
}
各ピースは、ピースを取る移動のみ可能です。 ピース数が1になればクリアです。 なお、ポーンはプロモーションできません。 Q1 K*** *B** P*** **** Q2 **** *B** RP** ***N Q3 R*B* **** *N** **P* Q4 *P** **** R*Q* *B** Q5 ***R K*P* **** K**P Q6 *RQ* ***P BN** P*** Q7 R*N* *B*N P*RB P*** Q8 P*** *NB* *BNP R*R* Q9 *RB* *PR* B**N P**N