using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 3 - 1;
//候補な数値の最大値
//1に隣接したマスは最大でも13である
//13に隣接したマスは最大でも24である
//24に隣接したマスは最大でも34である
//34に隣接したマスは最大でも43である
const int KouhoMax = 43;
struct JyoutaiDef
{
internal int CurrX;
internal int CurrY;
internal int[,] BanArr;
internal HashSet<int> DiffSet;
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrX = WillPush.CurrY = 0;
WillPush.BanArr = new int[UB + 1, UB + 1];
WillPush.DiffSet = new HashSet<int>();
Stk.Push(WillPush);
var AnswerSet = new HashSet<string>();
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
//X座標の繰上げ処理
if (Popped.CurrX > UB) {
Popped.CurrX = 0;
Popped.CurrY++;
}
//最終行を超えた場合
if (Popped.CurrY > UB) {
var wkHashSet = DeriveHashSet(Popped.BanArr);
if (AnswerSet.Overlaps(wkHashSet)) {
continue;
}
AnswerSet.Add(wkHashSet.First());
if (AnswerSet.Count % 20000 == 0) {
Console.WriteLine("解{0}を発見。経過時間={1}",
AnswerSet.Count, sw.Elapsed);
}
continue;
}
int[] UsedNumArr = Popped.BanArr.Cast<int>().Where(X => X > 0).ToArray();
for (int I = 1; I <= KouhoMax; I++) {
//使用済数値は不可
if (UsedNumArr.Contains(I)) continue;
//回転解の除外で、
//1は、左上、中央上、中央の3箇所のみ配置可とする
if (I == 1) {
bool IsOK = false;
if (Popped.CurrX == 0 && Popped.CurrY == 0) IsOK = true;
if (Popped.CurrX == 1 && Popped.CurrY == 0) IsOK = true;
if (Popped.CurrX == 1 && Popped.CurrY == 1) IsOK = true;
if (IsOK == false) continue;
}
//1は、中央までに配置する
if (Popped.CurrX == 1 && Popped.CurrY == 1
&& UsedNumArr.Contains(1) == false && I != 1) {
continue;
}
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.BanArr = (int[,])Popped.BanArr.Clone();
WillPush.BanArr[Popped.CurrX, Popped.CurrY] = I;
WillPush.DiffSet = new HashSet<int>(Popped.DiffSet);
if (AddDiff(Popped.CurrX, Popped.CurrY,
WillPush.BanArr, WillPush.DiffSet) == false) continue;
if (WillEdakiri(Popped.CurrX, Popped.CurrY, WillPush.BanArr))
continue;
Stk.Push(WillPush);
}
}
Console.WriteLine("解は{0}通り。経過時間={1}", AnswerSet.Count, sw.Elapsed);
}
//階差を追加し、有効な状態かを返す
//階差は1から12の必要があり、差は12通りしかない
static bool AddDiff(int pCurrX, int pCurrY, int[,] pBanArr, HashSet<int> pDiffSet)
{
Func<int, int, int> DeriveDiffFunc = (pBaseX, pBaseY) =>
Math.Abs(pBanArr[pCurrX, pCurrY] - pBanArr[pBaseX, pBaseY]);
if (pCurrX == 1 && pCurrY == 0) {
if (pDiffSet.Add(DeriveDiffFunc(0, 0)) == false)
return false;
}
if (pCurrX == 2 && pCurrY == 0) {
if (pDiffSet.Add(DeriveDiffFunc(1, 0)) == false)
return false;
}
if (pCurrX == 0 && pCurrY == 1) {
if (pDiffSet.Add(DeriveDiffFunc(0, 0)) == false)
return false;
}
if (pCurrX == 1 && pCurrY == 1) {
if (pDiffSet.Add(DeriveDiffFunc(1, 0)) == false)
return false;
if (pDiffSet.Add(DeriveDiffFunc(0, 1)) == false)
return false;
}
if (pCurrX == 2 && pCurrY == 1) {
if (pDiffSet.Add(DeriveDiffFunc(2, 0)) == false)
return false;
if (pDiffSet.Add(DeriveDiffFunc(1, 1)) == false)
return false;
}
if (pCurrX == 0 && pCurrY == 2) {
if (pDiffSet.Add(DeriveDiffFunc(0, 1)) == false)
return false;
}
if (pCurrX == 1 && pCurrY == 2) {
if (pDiffSet.Add(DeriveDiffFunc(1, 1)) == false)
return false;
if (pDiffSet.Add(DeriveDiffFunc(0, 2)) == false)
return false;
}
if (pCurrX == 2 && pCurrY == 2) {
if (pDiffSet.Add(DeriveDiffFunc(2, 1)) == false)
return false;
if (pDiffSet.Add(DeriveDiffFunc(1, 2)) == false)
return false;
}
if (pDiffSet.Any(X => X < 1 || 12 < X)) return false;
return true;
}
//枝切りするかを判定
static bool WillEdakiri(int pCurrX, int pCurrY, int[,] pBanArr)
{
//左上が1の場合
if (pBanArr[0, 0] == 1 && pCurrX == 0 && pCurrY == 1)
if (pBanArr[1, 0] > pBanArr[0, 1]) return true;
//左上が1でない場合
if (pBanArr[0, 0] != 1 && pCurrX == 2 && pCurrY == 0)
if (pBanArr[0, 0] > pBanArr[2, 0]) return true;
//中央が1の場合で
//A B
// 1
//C
//A<B かつ A<C の場合は、B<Cとする
if (pBanArr[1, 1] == 1 && pCurrX == 0 && pCurrY == 2) {
if (pBanArr[2, 0] > pBanArr[0, 2])
return true;
}
return false;
}
//回転も含めたハッシュ値のSetを返す
static HashSet<string> DeriveHashSet(int[,] pBanArr)
{
var sbArr = new System.Text.StringBuilder[8];
for (int I = 0; I <= sbArr.GetUpperBound(0); I++) {
sbArr[I] = new System.Text.StringBuilder();
}
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
sbArr[0].AppendFormat("{0},", pBanArr[X, Y]);
sbArr[1].AppendFormat("{0},", pBanArr[UB - X, Y]);
sbArr[2].AppendFormat("{0},", pBanArr[UB - X, UB - Y]);
sbArr[3].AppendFormat("{0},", pBanArr[X, UB - Y]);
sbArr[4].AppendFormat("{0},", pBanArr[Y, X]);
sbArr[5].AppendFormat("{0},", pBanArr[UB - Y, X]);
sbArr[6].AppendFormat("{0},", pBanArr[UB - Y, UB - X]);
sbArr[7].AppendFormat("{0},", pBanArr[Y, UB - X]);
}
}
var WillReturn = new HashSet<string>();
for (int I = 0; I <= sbArr.GetUpperBound(0); I++) {
WillReturn.Add(sbArr[I].ToString());
}
return WillReturn;
}
}