using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
const int UB = 4;
const bool IsSinbunsuuOnly = true; //真分数のみか？
const bool IsKiyakubunsuuOnly = true; //既約分数のみか？
//25マスの分母の値
static int[,] BunboArr = new int[UB + 1, UB + 1];
//縦方向と横方向と斜め方向の、合計12方向の分母の積
static int[] BunboProdArr = new int[12];
//マス目ごとの分子の候補のDict
static Dictionary<string, List<int>> BunsiKouhoDict = new Dictionary<string, List<int>>();
struct JyoutaiDef
{
internal int CurrX;
internal int CurrY;
internal int[,] BunsiArr;
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
int[,] wkArr = new int[UB + 1, UB + 1] {{14,10,16,10,22},
{64,55,14, 5, 8},
{15, 4,32,88,35},
{44,56,25,12,16},
{ 5,48,22,28,20}};
//X方向とY方向を変換
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
BunboArr[X, Y] = wkArr[Y, X];
}
}
//12方向の分母の積を求める
BunboProdArr = DeriveProdArr(BunboArr);
//マス目ごとの分子の候補を求める
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
DeriveBunsiKouhoEachMasume(X, Y);
}
}
foreach (var AnyKey in BunsiKouhoDict.Keys) {
Console.Write("{0}の分子候補は、{1}通り。", AnyKey, BunsiKouhoDict[AnyKey].Count);
foreach (int AnyInt in BunsiKouhoDict[AnyKey]) {
Console.Write("{0},", AnyInt);
}
Console.WriteLine();
}
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrX = WillPush.CurrY = 0;
foreach (int AnyBunsiKouho in BunsiKouhoDict[GetFormattedXY(0, 0)]) {
WillPush.BunsiArr = new int[UB + 1, UB + 1];
//未決定の分子は全て1にしておく
for (int X = 0; X <= UB; X++) {
for (int Y = 0; Y <= UB; Y++) {
WillPush.BunsiArr[X, Y] = 1;
}
}
WillPush.BunsiArr[0, 0] = AnyBunsiKouho;
stk.Push(WillPush);
}
int AnswerCnt = 0;
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
if (WillPush.CurrX > UB) {
WillPush.CurrX = 0;
WillPush.CurrY++;
}
if (WillPush.CurrY > UB) {
Console.WriteLine("解{0,2}を発見。経過時間={1}", ++AnswerCnt, sw.Elapsed);
PrintAnswer(Popped.BunsiArr);
continue;
}
string XY = GetFormattedXY(WillPush.CurrX, WillPush.CurrY);
foreach (int AnyBunsiKouho in BunsiKouhoDict[XY]) {
WillPush.BunsiArr = (int[,])Popped.BunsiArr.Clone();
WillPush.BunsiArr[WillPush.CurrX, WillPush.CurrY] = AnyBunsiKouho;
if (IsValid(WillPush.CurrX, WillPush.CurrY, WillPush.BunsiArr))
stk.Push(WillPush);
}
}
}
//座標をFormatして返す
static string GetFormattedXY(int pX, int pY)
{
return string.Format("({0},{1})", pX, pY);
}
//12方向の分母か分子の積を求める
static int[] DeriveProdArr(int[,] pTargetArr)
{
int[,] wkP = pTargetArr;
int[] WillReturn = new int[12];
//横方向
WillReturn[0] = wkP[0, 0] * wkP[1, 0] * wkP[2, 0] * wkP[3, 0] * wkP[4, 0];
WillReturn[1] = wkP[0, 1] * wkP[1, 1] * wkP[2, 1] * wkP[3, 1] * wkP[4, 1];
WillReturn[2] = wkP[0, 2] * wkP[1, 2] * wkP[2, 2] * wkP[3, 2] * wkP[4, 2];
WillReturn[3] = wkP[0, 3] * wkP[1, 3] * wkP[2, 3] * wkP[3, 3] * wkP[4, 3];
WillReturn[4] = wkP[0, 4] * wkP[1, 4] * wkP[2, 4] * wkP[3, 4] * wkP[4, 4];
//縦方向
WillReturn[5] = wkP[0, 0] * wkP[0, 1] * wkP[0, 2] * wkP[0, 3] * wkP[0, 4];
WillReturn[6] = wkP[1, 0] * wkP[1, 1] * wkP[1, 2] * wkP[1, 3] * wkP[1, 4];
WillReturn[7] = wkP[2, 0] * wkP[2, 1] * wkP[2, 2] * wkP[2, 3] * wkP[2, 4];
WillReturn[8] = wkP[3, 0] * wkP[3, 1] * wkP[3, 2] * wkP[3, 3] * wkP[3, 4];
WillReturn[9] = wkP[4, 0] * wkP[4, 1] * wkP[4, 2] * wkP[4, 3] * wkP[4, 4];
//斜め方向
WillReturn[10] = wkP[0, 0] * wkP[1, 1] * wkP[2, 2] * wkP[3, 3] * wkP[4, 4];
WillReturn[11] = wkP[0, 4] * wkP[1, 3] * wkP[2, 2] * wkP[3, 1] * wkP[4, 0];
return WillReturn;
}
//マス目ごとの分子の候補を求める
static void DeriveBunsiKouhoEachMasume(int pX, int pY)
{
var BunboProdList = new List<int>();
//横方向
BunboProdList.Add(BunboProdArr[pY]);
//縦方向
BunboProdList.Add(BunboProdArr[5 + pX]);
//斜め方向1
if (pX == pY) BunboProdList.Add(BunboProdArr[10]);
//斜め方向1
if (pX + pY == UB) BunboProdList.Add(BunboProdArr[11]);
string StrKey = GetFormattedXY(pX, pY);
BunsiKouhoDict.Add(StrKey, new List<int>());
for (int I = 1; I < int.MaxValue; I++) {
//条件1
//9の約数(1か3か9)であるか、
//経路の分母の積と互いに素でないこと
bool Jyouken1 = false;
if (9 % I == 0) Jyouken1 = true;
if (BunboProdList.TrueForAll(X => DeriveGCD(I, X) != 1)) Jyouken1 = true;
if (Jyouken1 == false) continue;
//条件2
//経路(2個か3個か4個)の分母の積の最小値で割ったら、9/70400以下であること
if (BunsuuIsGreater(9, 70400, I, BunboProdList.Min())) break;
//条件3
//経路(2個か3個か4個)の分母の積に分子を掛けて、
//既約分数にした時の分母が70400以上であること
if (BunboProdList.Exists(X => IsOSKiyakuBunsuuBunbo(I, X) == false))
continue;
BunsiKouhoDict[StrKey].Add(I);
}
//真分数のみ
if (IsSinbunsuuOnly) {
BunsiKouhoDict[StrKey].RemoveAll(X => X >= BunboArr[pX, pY]);
}
//既約分数のみ
if (IsKiyakubunsuuOnly) {
Predicate<int> IsTagainiso = (p1) =>
{
return DeriveGCD(p1, BunboArr[pX, pY]) == 1;
};
BunsiKouhoDict[StrKey].RemoveAll(X => IsTagainiso(X) == false);
}
}
//既約分数にした時の分母が70400以上か？
static bool IsOSKiyakuBunsuuBunbo(int pBunsi, int pBunbo)
{
int GCD;
while ((GCD = DeriveGCD(pBunsi, pBunbo)) > 1) {
pBunsi /= GCD;
pBunbo /= GCD;
}
return pBunbo >= 70400;
}
//p1 よりも p2が大きかったらTrueを返す
static bool BunsuuIsGreater(int pBunsi1, int pBunbo1, int pBunsi2, int pBunbo2)
{
//通分して比較
return (long)pBunsi1 * pBunbo2 < (long)pBunsi2 * pBunbo1;
}
//p1 と p2が等しかったらTrueを返す
static bool BunsuuIsEqual(int pBunsi1, int pBunbo1, int pBunsi2, int pBunbo2)
{
//通分して比較
return pBunsi1 * pBunbo2 == pBunsi2 * pBunbo1;
}
//ユークリッドの互除法で2数の最大公約数を求める
static int DeriveGCD(int pVal1, int pVal2)
{
int WarareruKazu = Math.Max(pVal1, pVal2);
int WaruKazu = Math.Min(pVal1, pVal2);
while (true) {
int Amari = WarareruKazu % WaruKazu;
if (Amari == 0) return WaruKazu;
WarareruKazu = WaruKazu;
WaruKazu = Amari;
}
}
//現在が有効な状態(解に到達する可能性があるか)をチェック
static bool IsValid(int pX, int pY, int[,] pBunsiArr)
{
int[] BunsiProdArr = DeriveProdArr(pBunsiArr);
//横方向のチェック
if (1 <= pX && pX <= 3) {
if (BunsuuIsGreater(9, 70400, BunsiProdArr[pY], BunboProdArr[pY]))
return false;
if (IsOSKiyakuBunsuuBunbo(BunsiProdArr[pY], BunboProdArr[pY]) == false)
return false;
}
if (pX == UB) {
if (BunsuuIsEqual(9, 70400, BunsiProdArr[pY], BunboProdArr[pY]) == false)
return false;
}
//縦方向のチェック
if (1 <= pY && pY <= 3) {
if (BunsuuIsGreater(9, 70400, BunsiProdArr[5 + pX], BunboProdArr[5 + pX]))
return false;
if (IsOSKiyakuBunsuuBunbo(BunsiProdArr[5 + pX], BunboProdArr[5 + pX]) == false)
return false;
}
if (pY == UB) {
if (BunsuuIsEqual(9, 70400, BunsiProdArr[5 + pX], BunboProdArr[5 + pX]) == false)
return false;
}
//斜め方向のチェック1
if (pX == 1 && pY == 1 || pX == 2 && pY == 2 || pX == 3 && pY == 3) {
if (BunsuuIsGreater(9, 70400, BunsiProdArr[10], BunboProdArr[10]))
return false;
if (IsOSKiyakuBunsuuBunbo(BunsiProdArr[10], BunboProdArr[10]) == false)
return false;
}
if (pX == UB && pY == UB) {
if (BunsuuIsEqual(9, 70400, BunsiProdArr[10], BunboProdArr[10]) == false)
return false;
}
//斜め方向のチェック2
if (pX == 3 && pY == 1 || pX == 2 && pY == 2 || pX == 1 && pY == 3) {
if (BunsuuIsGreater(9, 70400, BunsiProdArr[11], BunboProdArr[11]))
return false;
if (IsOSKiyakuBunsuuBunbo(BunsiProdArr[11], BunboProdArr[11]) == false)
return false;
}
if (pX == 0 && pY == UB) {
if (BunsuuIsEqual(9, 70400, BunsiProdArr[11], BunboProdArr[11]) == false)
return false;
}
return true;
}
//答えを出力
static void PrintAnswer(int[,] pBunsiArr)
{
for (int Y = 0; Y <= UB; Y++) {
var sb1 = new System.Text.StringBuilder();
var sb2 = new System.Text.StringBuilder();
var sb3 = new System.Text.StringBuilder();
for (int X = 0; X <= UB; X++) {
sb1.AppendFormat("{0,3} ", pBunsiArr[X, Y]);
sb2.Append("--- ");
sb3.AppendFormat("{0,3} ", BunboArr[X, Y]);
}
Console.WriteLine(sb1.ToString());
Console.WriteLine(sb2.ToString());
Console.WriteLine(sb3.ToString());
Console.WriteLine();
}
}
}
(0,0)の分子候補は、4通り。1,3,5,9,
(0,1)の分子候補は、13通り。1,3,5,7,9,11,15,21,25,33,45,49,63,
(0,2)の分子候補は、7通り。1,2,4,7,8,11,14,
(0,3)の分子候補は、11通り。1,3,5,7,9,15,21,25,27,35,39,
(0,4)の分子候補は、4通り。1,2,3,4,
(1,0)の分子候補は、4通り。1,3,7,9,
(1,1)の分子候補は、25通り。1,2,3,4,6,7,8,9,12,14,16,18,21,24,26,28,34,36,38,42,46,48,49,52,54,
(1,2)の分子候補は、2通り。1,3,
(1,3)の分子候補は、8通り。1,3,5,9,11,15,33,45,
(1,4)の分子候補は、6通り。1,5,7,11,25,35,
(2,0)の分子候補は、6通り。1,3,5,7,9,15,
(2,1)の分子候補は、5通り。1,3,5,9,11,
(2,2)の分子候補は、8通り。1,3,5,7,9,11,15,21,
(2,3)の分子候補は、16通り。1,2,3,4,6,7,8,9,11,12,14,16,18,21,22,24,
(2,4)の分子候補は、7通り。1,3,5,7,9,15,21,
(3,0)の分子候補は、4通り。1,3,7,9,
(3,1)の分子候補は、4通り。1,2,3,4,
(3,2)の分子候補は、19通り。1,3,5,7,9,15,21,27,39,45,49,51,57,63,65,69,81,85,87,
(3,3)の分子候補は、4通り。1,5,7,11,
(3,4)の分子候補は、7通り。1,3,5,9,11,15,27,
(4,0)の分子候補は、7通り。1,3,5,7,9,15,21,
(4,1)の分子候補は、4通り。1,3,5,7,
(4,2)の分子候補は、16通り。1,2,3,4,6,8,9,11,12,16,18,22,24,26,33,34,
(4,3)の分子候補は、7通り。1,3,5,7,9,11,15,
(4,4)の分子候補は、5通り。1,3,7,9,11,
解 1を発見。経過時間=00:00:12.4014038
9 1 1 7 1
--- --- --- --- ---
14 10 16 10 22
21 4 3 1 1
--- --- --- --- ---
64 55 14 5 8
1 3 7 3 12
--- --- --- --- ---
15 4 32 88 35
1 9 24 1 7
--- --- --- --- ---
44 56 25 12 16
2 7 1 9 3
--- --- --- --- ---
5 48 22 28 20
省略
解64を発見。経過時間=00:05:45.1016620
1 1 3 7 3
--- --- --- --- ---
14 10 16 10 22
7 36 1 1 1
--- --- --- --- ---
64 55 14 5 8
1 3 21 1 12
--- --- --- --- ---
15 4 32 88 35
27 1 8 1 7
--- --- --- --- ---
44 56 25 12 16
2 7 1 27 1
--- --- --- --- ---
5 48 22 28 20