using System;
using System.Collections.Generic;
class Program
{
const int NeedSum = 64 * (64 + 1) / 2 - 2004;
const int UB = 7;
static int[,] mQuestionArr = new int[UB + 1, UB + 1];
//問題を定義
static void QuestionDef()
{
//右向きが1,下向きが2,左向きが3,上向きが4
int Muki = 1;
int CurrX = 0, CurrY = 0;
int CurrNum = 1;
mQuestionArr[0, 0] = CurrNum++;
while (true) {
int HeniX = 0, HeniY = 0;
if (Muki == 1) HeniX = 1;
if (Muki == 2) HeniY = 1;
if (Muki == 3) HeniX = -1;
if (Muki == 4) HeniY = -1;
int NewX = CurrX + HeniX;
int NewY = CurrY + HeniY;
if (NewX < 0 || UB < NewX || NewY < 0 || UB < NewY
|| mQuestionArr[NewX, NewY] > 0) {
if (++Muki == 5) Muki = 1;
continue;
}
mQuestionArr[NewX, NewY] = CurrNum++;
CurrX = NewX;
CurrY = NewY;
if (CurrNum > 64) break;
}
}
static void Main()
{
//問題を定義
QuestionDef();
var AnswerList = new List<JyoutaiDef>();
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
if (X == 0 || X == UB || Y == 0 || Y == UB)
AnswerList.AddRange(ExecUnionFind(X, Y));
}
}
for (int I = 0; I <= AnswerList.Count - 1; I++) {
Console.WriteLine("配置{0}", I + 1);
PrintBan(ExecReduceArr(AnswerList[I].BanArr));
}
}
struct JyoutaiDef
{
internal int[,] BanArr;
internal int SumVal;
}
static HashSet<string> mVisitedSet = new HashSet<string>();
//始点の座標を引数をしてUnionFind
static List<JyoutaiDef> ExecUnionFind(int pStaX, int pStaY)
{
var WillReturn = new List<JyoutaiDef>();
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.BanArr = new int[UB + 1, UB + 1];
WillPush.BanArr[pStaX, pStaY] = mQuestionArr[pStaX, pStaY];
WillPush.SumVal = mQuestionArr[pStaX, pStaY];
Stk.Push(WillPush);
mVisitedSet.Add(GetBanHash(WillPush.BanArr));
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
//クリア判定
if (Popped.SumVal == NeedSum) {
WillReturn.Add(Popped);
continue;
}
var wkUsedFromPos = new HashSet<int>();
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
if (Popped.BanArr[LoopX, LoopY] == 0) continue;
Action<int, int> PushSyori = (pNewX, pNewY) =>
{
if (pNewX < 0 || UB < pNewX) return;
if (pNewY < 0 || UB < pNewY) return;
if (Popped.BanArr[pNewX, pNewY] > 0) return;
WillPush.BanArr = (int[,])Popped.BanArr.Clone();
WillPush.BanArr[pNewX, pNewY] = mQuestionArr[pNewX, pNewY];
WillPush.SumVal = Popped.SumVal + mQuestionArr[pNewX, pNewY];
//再訪不可
if (mVisitedSet.Add(GetBanHash(WillPush.BanArr)) == false)
return;
//枝切り
if (WillPush.SumVal <= NeedSum)
Stk.Push(WillPush);
};
PushSyori(LoopX, LoopY - 1);
PushSyori(LoopX, LoopY + 1);
PushSyori(LoopX - 1, LoopY);
PushSyori(LoopX + 1, LoopY);
wkUsedFromPos.Add(GetPointHash(LoopX, LoopY));
}
}
}
return WillReturn;
}
static int GetPointHash(int pX, int pY)
{
return pX * (UB + 1) + pY;
}
static string GetBanHash(int[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
sb.AppendFormat("{0},", pBanArr[X, Y]);
}
}
return sb.ToString();
}
//最小の2次元配列に縮小する
static int[,] ExecReduceArr(int[,] pBanArr)
{
int[,] WillReturnArr;
int XMin = pBanArr.GetUpperBound(0), YMin = pBanArr.GetUpperBound(1);
int XMax = 0, YMax = 0;
for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
if (pBanArr[X, Y] == 0) continue;
if (XMin > X) XMin = X;
if (YMin > Y) YMin = Y;
if (XMax < X) XMax = X;
if (YMax < Y) YMax = Y;
}
}
WillReturnArr = new int[XMax - XMin + 1, YMax - YMin + 1];
for (int X = 0; X <= WillReturnArr.GetUpperBound(0); X++) {
for (int Y = 0; Y <= WillReturnArr.GetUpperBound(1); Y++) {
WillReturnArr[X, Y] = pBanArr[XMin + X, YMin + Y];
}
}
return WillReturnArr;
}
//盤面を出力
static void PrintBan(int[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
//if (pBanArr[X, Y] == 0) continue;
sb.AppendFormat("{0,2},", pBanArr[X, Y]);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
配置1
1, 2, 3, 4, 5, 6, 7, 8,
0, 0, 0,31, 0, 0, 0, 9,
配置2
1, 2, 3, 4, 5, 6,
28, 0, 0, 0, 0, 0,
27, 0, 0, 0, 0, 0,
配置3
1, 2, 3, 4, 5,
0,29, 0, 0,32,
配置4
1, 2, 3, 4, 5,
0, 0,30,31, 0,
配置5
2, 3, 4, 5, 6, 7, 8,
0, 0, 0,32, 0, 0, 9,
配置6
2, 3, 4, 5,
0,30, 0,32,
配置7
3, 4, 5, 6, 7, 8,
0, 0, 0, 0,34, 9,
配置8
0, 4, 5, 6,
30,31, 0, 0,
配置9
5, 6,
32,33,
配置10
41, 0,
18,17,
配置11
6, 7, 8,
0, 0, 9,
0, 0,10,
0, 0,11,
0, 0,12,
0, 0,13,
配置12
7,
34,
35,
配置13
34, 9,
0,10,
0,11,
0,12,
配置14
33,34, 9,
配置15
37,12,
0,13,
0,14,
