6個ずつの自然数からなる組がふたつある。 それぞれの組から要素をひとつずつ選んで加えることを考えると、 全部で6×6＝36個の和ができることになる。 この和に、2から37までのすべての数が一度ずつ現れるようにしたい。 どのようにふたつの組を作ればよいであろうか？ すべての答えを求めてほしい。
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
struct JyoutaiDef
{
internal List<int> LeftValList;
internal List<int> RightValList;
internal HashSet<int> SumValSet;
}
static void Main()
{
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
for (int I = 0; I <= 2; I++) {
WillPush.LeftValList = new List<int>() { I };
WillPush.RightValList = new List<int>();
WillPush.SumValSet = new HashSet<int>();
stk.Push(WillPush);
}
int AnswerCnt = 0;
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
int LeftValCnt = Popped.LeftValList.Count;
int RightValCnt = Popped.RightValList.Count;
int LeftValMin = Popped.LeftValList.Min();
int LeftValMax = Popped.LeftValList.Max();
int LeftValSum = Popped.LeftValList.Sum();
int RightValSum = Popped.RightValList.Sum();
if (LeftValCnt == 6 && RightValCnt == 6) {
if (LeftValSum > RightValSum) continue;
Console.WriteLine("解{0,2}を発見", ++AnswerCnt);
PrintAnswer(Popped.LeftValList, Popped.RightValList);
continue;
}
if (LeftValCnt < 6) {
int RestCnt = 6 - LeftValCnt;
for (int I = LeftValMax + 1; I <= 37; I++) {
if (I + RestCnt - 1 > 37) break;
WillPush.LeftValList = new List<int>(Popped.LeftValList) { I };
WillPush.RightValList = Popped.RightValList;
WillPush.SumValSet = Popped.SumValSet;
stk.Push(WillPush);
}
}
else if (RightValCnt < 6) {
Action<int> AddRightVal = pVal =>
{
WillPush.LeftValList = Popped.LeftValList;
WillPush.SumValSet = new HashSet<int>(Popped.SumValSet);
foreach (int AnyInt in Popped.LeftValList) {
int wkSum = AnyInt + pVal;
if (WillPush.SumValSet.Add(wkSum) == false) return;
}
WillPush.RightValList = new List<int>(Popped.RightValList) { pVal };
stk.Push(WillPush);
};
if (RightValCnt == 0) { //この場合は、引き算によって値が確定する
AddRightVal(2 - LeftValMin);
continue;
}
if (RightValCnt == 5) { //この場合は、引き算によって値が確定する
AddRightVal(37 - LeftValMax);
continue;
}
int RightValMax = Popped.RightValList.Max();
int RestCnt = 6 - RightValCnt;
for (int I = RightValMax + 1; I <= 37; I++) {
if (LeftValMax + I + RestCnt - 1 > 37) break;
AddRightVal(I);
}
}
}
}
//解を表示
static void PrintAnswer(List<int> pLeftValList, List<int> pRightValList)
{
var sb = new System.Text.StringBuilder();
sb.Append("LeftVal ");
for (int I = 0; I <= pLeftValList.Count - 1; I++) {
sb.AppendFormat("{0,2}", pLeftValList[I]);
if (I < pLeftValList.Count - 1) sb.Append(',');
}
sb.AppendLine();
sb.Append("RightVal ");
for (int I = 0; I <= pRightValList.Count - 1; I++) {
sb.AppendFormat("{0,2}", pRightValList[I]);
if (I < pRightValList.Count - 1) sb.Append(',');
}
sb.AppendLine();
Console.WriteLine(sb.ToString());
}
}
省略 解 8を発見 LeftVal 1, 4, 7,10,13,16 RightVal 1, 2, 3,19,20,21 解 9を発見 LeftVal 1, 3, 5, 7, 9,11 RightVal 1, 2,13,14,25,26 解10を発見 LeftVal 1, 2, 7, 8,13,14 RightVal 1, 3, 5,19,21,23 解11を発見 LeftVal 1, 2, 5, 6, 9,10 RightVal 1, 3,13,15,25,27 解12を発見 LeftVal 1, 2, 3,10,11,12 RightVal 1, 4, 7,19,22,25 解13を発見 LeftVal 1, 2, 3, 7, 8, 9 RightVal 1, 4,13,16,25,28 解14を発見 LeftVal 1, 2, 3, 4, 5, 6 RightVal 1, 7,13,19,25,31 解15を発見 LeftVal 0, 3, 6, 9,12,15 RightVal 2, 3, 4,20,21,22 解16を発見 LeftVal 0, 2, 4, 6, 8,10 RightVal 2, 3,14,15,26,27 解17を発見 LeftVal 0, 1, 6, 7,12,13 RightVal 2, 4, 6,20,22,24 解18を発見 LeftVal 0, 1, 4, 5, 8, 9 RightVal 2, 4,14,16,26,28 解19を発見 LeftVal 0, 1, 2, 9,10,11 RightVal 2, 5, 8,20,23,26 解20を発見 LeftVal 0, 1, 2, 6, 7, 8 RightVal 2, 5,14,17,26,29 解21を発見 LeftVal 0, 1, 2, 3, 4, 5 RightVal 2, 8,14,20,26,32
0も自然数に含むとして、解を列挙してます。