using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
struct JyoutaiDef
{
internal int CurrX;
internal int CurrY;
internal Char[,] BanArr;
internal List<int> UsedKouhoNumList;
}
const int UB_X = 6 - 1;
const int UB_Y = 6 - 1;
static int[] AllKouhoNumArr;
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
//埋める候補の数値の配列を作成
AllKouhoNumArr = DeriveAllKouhoNumArr();
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrX = WillPush.CurrY = 0;
WillPush.BanArr = new char[UB_X + 1, UB_Y + 1];
for (int X = 0; X <= UB_X; X++)
for (int Y = 0; Y <= UB_Y; Y++)
WillPush.BanArr[X, Y] = ' ';
WillPush.BanArr[4, 0] = '■';
WillPush.BanArr[2, 1] = '■';
WillPush.BanArr[5, 2] = '■';
WillPush.BanArr[0, 3] = '■';
WillPush.BanArr[3, 4] = '■';
WillPush.BanArr[1, 5] = '■';
WillPush.UsedKouhoNumList = new List<int>();
stk.Push(WillPush);
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
//X座標の繰上げ処理
if (Popped.CurrX > UB_X) {
Popped.CurrX = 0;
Popped.CurrY++;
}
//最終行を超えた場合
if (Popped.CurrY > UB_Y) {
Console.WriteLine("解を発見");
PrintBan(Popped.BanArr);
continue;
}
if (Popped.BanArr[Popped.CurrX, Popped.CurrY] == '■') {
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.BanArr = Popped.BanArr;
WillPush.UsedKouhoNumList = Popped.UsedKouhoNumList;
stk.Push(WillPush);
continue;
}
//横に埋める数値の桁数を求める
int FillNumKetasuu = DeriveFillNumKetasuu(
Popped.BanArr, Popped.CurrX, Popped.CurrY);
//桁数を引数として平方数を抽出
int[] KouhoNumArr = DeriveKouhoNumArr(FillNumKetasuu);
foreach (int EachKouho in KouhoNumArr) {
//2桁以上で使用済の数値ならNG
if (EachKouho >= 10 && Popped.UsedKouhoNumList.Contains(EachKouho))
continue;
WillPush.CurrX = Popped.CurrX + FillNumKetasuu;
WillPush.CurrY = Popped.CurrY;
WillPush.BanArr = (char[,])Popped.BanArr.Clone();
string FillStr = EachKouho.ToString();
for (int I = 0; I <= FillStr.Length - 1; I++) {
WillPush.BanArr[Popped.CurrX + I, Popped.CurrY] = FillStr[I];
}
WillPush.UsedKouhoNumList = new List<int>(Popped.UsedKouhoNumList);
WillPush.UsedKouhoNumList.Add(EachKouho);
bool WillEdakiri;
TateCheck(out WillEdakiri, WillPush);
if (WillEdakiri == false)
stk.Push(WillPush);
}
}
Console.WriteLine("経過時間={0}", sw.Elapsed);
}
//埋める候補の数値の配列を作成
static int[] DeriveAllKouhoNumArr()
{
var HeihouSuuSet = new HashSet<int>();
for (int I = 0; I * I <= 99999; I++) {
HeihouSuuSet.Add(I * I);//平方数
}
for (int I = 0; I <= 9; I++)
HeihouSuuSet.Add(I); //1桁の数値
return HeihouSuuSet.OrderBy(X => X).ToArray();
}
//横に埋める数値の桁数を求める
static int DeriveFillNumKetasuu(char[,] pBanArr, int pCurrX, int pCurrY)
{
int WillReturn = 0;
for (int LoopX = pCurrX; LoopX <= UB_X; LoopX++) {
if (pBanArr[LoopX, pCurrY] == '■')
break;
WillReturn++;
}
return WillReturn;
}
//桁数を引数として埋める数値の候補を抽出
static int[] DeriveKouhoNumArr(int pKetasuu)
{
Predicate<int> IsOK = pInt =>
{
if (pKetasuu == 1)
return 0 <= pInt && pInt <= 9;
if (pKetasuu == 2)
return 10 <= pInt && pInt <= 99;
if (pKetasuu == 3)
return 100 <= pInt && pInt <= 999;
if (pKetasuu == 4)
return 1000 <= pInt && pInt <= 9999;
if (pKetasuu == 5)
return 10000 <= pInt && pInt <= 99999;
return 100000 <= pInt && pInt <= 999999;
};
return Array.FindAll(AllKouhoNumArr, X => IsOK(X));
}
//縦のラインでのチェックと枝切り
static void TateCheck(out bool pWillEdakiri, JyoutaiDef pWillPush)
{
var TateLineStrList = new List<string>();
if (pWillPush.CurrX == 6 && pWillPush.CurrY == 1) {
TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 5, 0, 1));
}
if (pWillPush.CurrX == 5 && pWillPush.CurrY == 2) {
TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 0, 0, 2));
}
if (pWillPush.CurrX == 6 && pWillPush.CurrY == 3) {
TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 3, 0, 3));
}
if (pWillPush.CurrX == 3 && pWillPush.CurrY == 4) {
TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 1, 0, 4));
}
if (pWillPush.CurrX == 1 && pWillPush.CurrY == 5) {
TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 0, 4, 5));
}
if (pWillPush.CurrX == 6 && pWillPush.CurrY == 5) {
TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 2, 2, 5));
}
if (pWillPush.CurrX == 6 && pWillPush.CurrY == 5) {
TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 4, 1, 5));
}
if (pWillPush.CurrX == 6 && pWillPush.CurrY == 5) {
TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 5, 3, 5));
}
pWillEdakiri = false;
foreach (string EachTateLineStr in TateLineStrList) {
//前ゼロはNG
if (EachTateLineStr != "0" && EachTateLineStr.StartsWith("0")) {
pWillEdakiri = true; return;
}
int TateLineNum = int.Parse(EachTateLineStr);
//使用可な数値でなければNG
if (Array.BinarySearch(AllKouhoNumArr, TateLineNum) < 0) {
pWillEdakiri = true; return;
}
//2桁以上で使用済の数値ならNG
if (TateLineNum >= 10 && pWillPush.UsedKouhoNumList.Contains(TateLineNum)) {
pWillEdakiri = true; return;
}
pWillPush.UsedKouhoNumList.Add(TateLineNum);
}
}
//開始座標から終点座標までを縦に走査し、数値を抽出する
static string DeriveTateLineStrNum(char[,] pBanArr,
int pCurrX, int pStaY, int pEndY)
{
var sb = new System.Text.StringBuilder();
for (int LoopY = pStaY; LoopY <= pEndY; LoopY++) {
sb.Append(pBanArr[pCurrX, LoopY]);
}
return sb.ToString();
}
//盤面を出力
static void PrintBan(char[,] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int Y = 0; Y <= UB_Y; Y++) {
for (int X = 0; X <= UB_X; X++) {
char wkChar = pBanArr[X, Y];
if (wkChar == '■') sb.Append('■');
else sb.Append((char)('０' + wkChar - '0'));
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
