using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 8 - 1;
struct PointDef
{
internal int X;
internal int Y;
}
struct JyoutaiDef
{
internal char[,] BanArr;
internal int CurrX;
internal int CurrY;
internal int KnightCnt;
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.BanArr = new char[UB + 1, UB + 1];
for (int LoopX = 0; LoopX <= UB; LoopX++) {
for (int LoopY = 0; LoopY <= UB; LoopY++) {
WillPush.BanArr[LoopX, LoopY] = '0';
}
}
WillPush.CurrX = WillPush.CurrY = 0;
WillPush.KnightCnt = 0;
stk.Push(WillPush);
int MinKnightCnt = int.MaxValue;
var AnswerBanArrList = new List<char[,]>();
var VisitedSet = new HashSet<ulong>();
VisitedSet.Add(BanToULong(WillPush.BanArr));
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//下限値枝切り
if (MinKnightCnt < Popped.KnightCnt)
continue;
//クリア判定
//8*8=64であり、ナイト1つにつき9マスをカバーできる。
//9*7=63 < 64 で
//9*8=72 > 64 なので、ナイトは最低8個必要
if (Popped.KnightCnt >= 8) {
if (Popped.BanArr.Cast<char>().All(X => X != '0')) {
if (MinKnightCnt > Popped.KnightCnt) {
MinKnightCnt = Popped.KnightCnt;
Console.WriteLine("ナイトの数={0}の解候補を発見",
MinKnightCnt);
AnswerBanArrList.Clear();
}
AnswerBanArrList.Add(Popped.BanArr);
continue;
}
}
//X座標の繰上げ処理
if (Popped.CurrX > UB) {
Popped.CurrX = 0;
Popped.CurrY++;
//1行目のナイトの数で左右対称解を除外
if (Popped.CurrY == 1) {
int LeftCnt = 0, RigthCnt = 0;
for (int LoopX = 0; LoopX <= 3; LoopX++)
if (Popped.BanArr[LoopX, 0] == 'N') LeftCnt++;
for (int LoopX = 4; LoopX <= UB; LoopX++)
if (Popped.BanArr[LoopX, 0] == 'N') RigthCnt++;
if (LeftCnt > RigthCnt) continue;
}
}
//最終行を超えた場合
if (Popped.CurrY > UB) continue;
//ナイトの効きマスの場合
char CurrMasu = Popped.BanArr[Popped.CurrX, Popped.CurrY];
if (CurrMasu != '0') {
WillPush.BanArr = Popped.BanArr;
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.KnightCnt = Popped.KnightCnt;
stk.Push(WillPush);
continue;
}
//5通りの配置候補がある
List<PointDef> KikiMasuList =
DeriveKikiMasuList(Popped.CurrX, Popped.CurrY);
//探索ノードの重複をRemove
KikiMasuList.RemoveAll(A => A.X < Popped.CurrX && A.Y < Popped.CurrY);
//'0'なカレントマスにナイトを配置する経路
KikiMasuList.Add(new PointDef() { X = Popped.CurrX, Y = Popped.CurrY });
foreach (PointDef EachKouho in KikiMasuList) {
//別のナイトの効きマスなら配置不可
if (DeriveKikiMasuList(EachKouho.X, EachKouho.Y).Exists(
A => Popped.BanArr[A.X, A.Y] == 'N')) {
continue;
}
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
WillPush.BanArr[EachKouho.X, EachKouho.Y] = 'N';
ExecIncrement(WillPush.BanArr, EachKouho.X, EachKouho.Y);
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.KnightCnt = Popped.KnightCnt + 1;
//訪問済ノードなら枝切り
if (VisitedSet.Add(BanToULong(WillPush.BanArr)) == false)
continue;
stk.Push(WillPush);
}
}
RemoveKaitenKai(AnswerBanArrList);
for (int I = 0; I <= AnswerBanArrList.Count - 1; I++) {
Console.WriteLine("解{0}", I + 1);
PrintAnswer(AnswerBanArrList[I]);
}
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
//座標を引数として、ナイトの効きマスのListを返す
static List<PointDef> DeriveKikiMasuList(int pCurrX, int pCurrY)
{
var WillReturn = new List<PointDef>();
Action<int, int> AddAct = (pX, pY) =>
{
if (pX < 0 || UB < pX) return;
if (pY < 0 || UB < pY) return;
WillReturn.Add(new PointDef() { X = pX, Y = pY });
};
AddAct(pCurrX - 2, pCurrY - 1);
AddAct(pCurrX - 2, pCurrY + 1);
AddAct(pCurrX + 2, pCurrY - 1);
AddAct(pCurrX + 2, pCurrY + 1);
AddAct(pCurrX - 1, pCurrY - 2);
AddAct(pCurrX - 1, pCurrY + 2);
AddAct(pCurrX + 1, pCurrY - 2);
AddAct(pCurrX + 1, pCurrY + 2);
return WillReturn;
}
//ナイトの効きマスの数値をインクリメント
static void ExecIncrement(char[,] pBanArr, int pCurrX, int pCurrY)
{
List<PointDef> KikiMasuList = DeriveKikiMasuList(pCurrX, pCurrY);
KikiMasuList.ForEach(A => pBanArr[A.X, A.Y]++);
}
//盤面を符号なしLong型で表現
static ulong BanToULong(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
char CurrChar = pBanArr[X, Y];
sb.Append(CurrChar == 'N' ? '1' : '0');
}
}
return Convert.ToUInt64(sb.ToString(), 2);
}
//回転した解を除外
static void RemoveKaitenKai(List<char[,]> pAnswerBanArrList)
{
Predicate<int> IsExist = (pCurrInd) =>
{
for (int I = 0; I <= pCurrInd - 1; I++) {
bool IsOK1 = false, IsOK2 = false, IsOK3 = false, IsOK4 = false;
bool IsOK5 = false, IsOK6 = false, IsOK7 = false; //回転1から7
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
char CurrVal = pAnswerBanArrList[pCurrInd][X, Y];
if (pAnswerBanArrList[I][UB - X, Y] != CurrVal) IsOK1 = true;
if (pAnswerBanArrList[I][UB - X, UB - Y] != CurrVal) IsOK2 = true;
if (pAnswerBanArrList[I][X, UB - Y] != CurrVal) IsOK3 = true;
if (pAnswerBanArrList[I][Y, X] != CurrVal) IsOK4 = true;
if (pAnswerBanArrList[I][UB - Y, X] != CurrVal) IsOK5 = true;
if (pAnswerBanArrList[I][UB - Y, UB - X] != CurrVal) IsOK6 = true;
if (pAnswerBanArrList[I][Y, UB - X] != CurrVal) IsOK7 = true;
}
}
if (IsOK1 == false || IsOK2 == false || IsOK3 == false || IsOK4 == false
|| IsOK5 == false || IsOK6 == false || IsOK7 == false)
return true;
}
return false;
};
for (int I = pAnswerBanArrList.Count - 1; I >= 0; I--) {
if (IsExist(I)) pAnswerBanArrList.RemoveAt(I);
}
}
//解を出力
static void PrintAnswer(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());
}
}