using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main()
{
//場合の数[Str型な盤面]なDP表
var PrevDP = new Dictionary<string, int>();
PrevDP["123456789"] = 1;
int AnswerCnt = 0;
for (int I = 1; I <= 9; I++) {
var CurrDP = new Dictionary<string, int>();
foreach (var EachPair in PrevDP) {
string[] NextBanArr = DeriveNextBanArr(EachPair.Key);
foreach (string EachBan in NextBanArr) {
if (CurrDP.ContainsKey(EachBan))
CurrDP[EachBan] += EachPair.Value;
else CurrDP[EachBan] = EachPair.Value;
}
}
Console.WriteLine("{0}回目のDPの結果", I);
PrintDP(CurrDP);
string AllZero = new string('0', 9);
if (CurrDP.ContainsKey(AllZero)) {
AnswerCnt += CurrDP[AllZero];
}
PrevDP = CurrDP;
}
Console.WriteLine("解={0}", AnswerCnt);
}
//Str型な盤面を引数として、次の盤面候補を配列で返す
static string[] DeriveNextBanArr(string pCurrBan)
{
var WillReturn = new List<string>();
//1枚抜きを列挙
for (int I = 0; I <= pCurrBan.Length - 1; I++) {
if (pCurrBan[I] != '0') {
string wkStr = pCurrBan;
wkStr = wkStr.Remove(I, 1);
wkStr = wkStr.Insert(I, "0");
WillReturn.Add(wkStr);
}
}
//2枚抜きを列挙
Action<char, char> wkAct = (p1, p2) =>
{
if (pCurrBan.Contains(p1) == false) return;
if (pCurrBan.Contains(p2) == false) return;
string wkStr = pCurrBan;
wkStr = wkStr.Replace(p1, '0');
wkStr = wkStr.Replace(p2, '0');
WillReturn.Add(wkStr);
};
wkAct('1', '2'); wkAct('1', '4');
wkAct('2', '3'); wkAct('3', '6');
wkAct('4', '7'); wkAct('6', '9');
wkAct('7', '8'); wkAct('8', '9');
return WillReturn.ToArray();
}
static void PrintDP(Dictionary<string, int> pDP)
{
foreach (var EachPair in pDP.OrderBy(X => X.Key)) {
Console.WriteLine("盤面{0}の場合の数={1}",
EachPair.Key, EachPair.Value);
}
}
}