トップページに戻る
次のC#のサンプルへ
前のC#のサンプルへ
Cマガ電脳クラブ(第115回) ラドクリフの六角陣
問題
Fig.1の19個の正六角形の中に、1から19までの19個の数すべてをダブりなく入れる。
このとき、左斜め・右斜め・横のいずれの方向も、和が38になるようにしたい。
何通りの配置が考えられるだろうか。
全体を回転した解や、裏返した解は別の解とはしない。
Fig.1 ラドクリフの六角陣
ソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
struct JyoutaiDef
{
internal int CurrX;
internal int CurrY;
internal int[][] BanArr;
internal HashSet<int> UsedNumSet;
}
static void Main()
{
var sw = System.Diagnostics.Stopwatch.StartNew();
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrX = 0;
WillPush.CurrY = 0;
//ジャグ配列で下記のデータ構造とする
// □□□
// □□□□
//□□□□□
// □□□□
// □□□
WillPush.BanArr = new int[5][];
WillPush.BanArr[0] = new int[3];
WillPush.BanArr[1] = new int[4];
WillPush.BanArr[2] = new int[5];
WillPush.BanArr[3] = new int[4];
WillPush.BanArr[4] = new int[3];
WillPush.UsedNumSet = new HashSet<int>();
stk.Push(WillPush);
int AnswerCnt = 0;
int PopCnt = 0;
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
if (++PopCnt % 1000000 == 1) {
Console.WriteLine("{0}回目のPopを行いました。経過時間={1}", PopCnt, sw.Elapsed);
}
int UB_X = Popped.BanArr[Popped.CurrY].GetUpperBound(0);
//X座標の繰上げ処理
if (Popped.CurrX > UB_X) {
Popped.CurrX = 0;
Popped.CurrY++;
}
//最終行を超えた場合
if (Popped.CurrY > Popped.BanArr.GetUpperBound(0)) {
Console.WriteLine("解{0}を発見。経過時間={1}", ++AnswerCnt, sw.Elapsed);
PrintBan(Popped.BanArr);
continue;
}
for (int I = 1; I <= 19; I++) {
if (Popped.UsedNumSet.Contains(I)) continue;
//対称解の除外で、正6角形の左上の頂点を最小とする
if (Popped.CurrX == 2 && Popped.CurrY == 0)
if (Popped.BanArr[0][0] > I) continue;
if (Popped.CurrX == 0 && Popped.CurrY == 2)
if (Popped.BanArr[0][0] > I) continue;
if (Popped.CurrX == 4 && Popped.CurrY == 2)
if (Popped.BanArr[0][0] > I) continue;
if (Popped.CurrX == 0 && Popped.CurrY == 4)
if (Popped.BanArr[0][0] > I) continue;
if (Popped.CurrX == 2 && Popped.CurrY == 4)
if (Popped.BanArr[0][0] > I) continue;
if (Popped.CurrX == 2 && Popped.CurrY == 4)
if (Popped.BanArr[0][0] > I) continue;
//対称解の除外で、
//左上の頂点から見た右の頂点 < 左上の頂点から見た左下の頂点とする
if (Popped.CurrX == 0 && Popped.CurrY == 2)
if (Popped.BanArr[0][2] > I) continue;
WillPush.CurrX = Popped.CurrX + 1;
WillPush.CurrY = Popped.CurrY;
WillPush.BanArr = ExecArrDeepCopy(Popped.BanArr, WillPush.CurrY);
WillPush.BanArr[Popped.CurrY][Popped.CurrX] = I;
WillPush.UsedNumSet = new HashSet<int>(Popped.UsedNumSet);
WillPush.UsedNumSet.Add(I);
//枝切り判定
if (WillEdakiri(WillPush.BanArr, Popped.CurrX, Popped.CurrY) == false)
stk.Push(WillPush);
}
}
Console.WriteLine("解は{0}通り。経過時間={1}", AnswerCnt, sw.Elapsed);
}
//ジャグ配列のディープコピーを返す
static int[][] ExecArrDeepCopy(int[][] pArr, int pCurrY)
{
int[][] WillReturn = new int[pArr.GetUpperBound(0) + 1][];
for (int I = 0; I <= pArr.GetUpperBound(0); I++) {
if (I == pCurrY)
WillReturn[I] = (int[])pArr[I].Clone();
else
WillReturn[I] = pArr[I];
}
return WillReturn;
}
//枝切り判定
static bool WillEdakiri(int[][] pBanArr, int pCurrX, int pCurrY)
{
//横方向の範囲チェック
if (pCurrX == 2 && pCurrY == 1 && pBanArr[1].Sum() + 1 > 38) return true;
if (pCurrX == 2 && pCurrY == 1 && pBanArr[1].Sum() + 19 < 38) return true;
if (pCurrX == 2 && pCurrY == 2 && pBanArr[2].Sum() + 1 + 2 > 38) return true;
if (pCurrX == 3 && pCurrY == 2 && pBanArr[2].Sum() + 1 > 38) return true;
if (pCurrX == 3 && pCurrY == 2 && pBanArr[2].Sum() + 19 < 38) return true;
if (pCurrX == 2 && pCurrY == 3 && pBanArr[3].Sum() + 1 > 38) return true;
if (pCurrX == 2 && pCurrY == 3 && pBanArr[3].Sum() + 19 < 38) return true;
//左下方向の範囲チェック
if (pCurrX == 1 && pCurrY == 2) {
int wkSum = pBanArr[0][1] + pBanArr[1][1] + pBanArr[2][1];
if (wkSum + 1 > 38 || wkSum + 19 < 38)
return true;
}
if (pCurrX == 2 && pCurrY == 2) {
int wkSum = pBanArr[0][2] + pBanArr[1][2] + pBanArr[2][2];
if (wkSum + 1 + 2 > 38)
return true;
}
//右下方向の範囲チェック
if (pCurrX == 2 && pCurrY == 2) {
int wkSum = pBanArr[0][0] + pBanArr[1][1] + pBanArr[2][2];
if (wkSum + 1 + 2 > 38)
return true;
}
//横方向の合計チェック1
if (pCurrX == 2 && pCurrY == 0 && pBanArr[0].Sum() != 38) return true;
//横方向の合計チェック2
if (pCurrX == 3 && pCurrY == 1 && pBanArr[1].Sum() != 38) return true;
//横方向の合計チェック3
if (pCurrX == 4 && pCurrY == 2 && pBanArr[2].Sum() != 38) return true;
//横方向の合計チェック4
if (pCurrX == 3 && pCurrY == 3 && pBanArr[3].Sum() != 38) return true;
//横方向の合計チェック5
if (pCurrX == 2 && pCurrY == 4 && pBanArr[4].Sum() != 38) return true;
//左下方向の合計チェック1
if (pCurrX == 0 && pCurrY == 2) {
if (pBanArr[0][0] + pBanArr[1][0] + pBanArr[2][0] != 38)
return true;
}
//左下方向の合計チェック2
if (pCurrX == 0 && pCurrY == 3) {
if (pBanArr[0][1] + pBanArr[1][1] + pBanArr[2][1] + pBanArr[3][0] != 38)
return true;
}
//左下方向の合計チェック3
if (pCurrX == 0 && pCurrY == 4) {
if (pBanArr[0][2] + pBanArr[1][2] + pBanArr[2][2] + pBanArr[3][1] + pBanArr[4][0] != 38)
return true;
}
//左下方向の合計チェック4
if (pCurrX == 1 && pCurrY == 4) {
if (pBanArr[1][3] + pBanArr[2][3] + pBanArr[3][2] + pBanArr[4][1] != 38)
return true;
}
//左下方向の合計チェック5
if (pCurrX == 2 && pCurrY == 4) {
if (pBanArr[2][4] + pBanArr[3][3] + pBanArr[4][2] != 38)
return true;
}
//右下方向の合計チェック1
if (pCurrX == 4 && pCurrY == 2) {
if (pBanArr[0][2] + pBanArr[1][3] + pBanArr[2][4] != 38)
return true;
}
//右下方向の合計チェック2
if (pCurrX == 3 && pCurrY == 3) {
if (pBanArr[0][1] + pBanArr[1][2] + pBanArr[2][3] + pBanArr[3][3] != 38)
return true;
}
//右下方向の合計チェック3
if (pCurrX == 2 && pCurrY == 4) {
if (pBanArr[0][0] + pBanArr[1][1] + pBanArr[2][2] + pBanArr[3][2] + pBanArr[4][2] != 38)
return true;
}
//右下方向の合計チェック4
if (pCurrX == 1 && pCurrY == 4) {
if (pBanArr[1][0] + pBanArr[2][1] + pBanArr[3][1] + pBanArr[4][1] != 38)
return true;
}
//右下方向の合計チェック5
if (pCurrX == 0 && pCurrY == 4) {
if (pBanArr[2][0] + pBanArr[3][0] + pBanArr[4][0] != 38)
return true;
}
return false;
}
//盤面を出力
static void PrintBan(int[][] pBanArr)
{
var sb = new System.Text.StringBuilder();
for (int I = 0; I <= pBanArr.GetUpperBound(0); I++) {
if (pBanArr[I].Length == 3) sb.Append(new string(' ', 3));
if (pBanArr[I].Length == 4) sb.Append(new string(' ', 1));
foreach (int EachInt in pBanArr[I]) {
sb.AppendFormat("{0,2},", EachInt);
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
実行結果
1回目のPopを行いました。経過時間=00:00:00.0030811
1000001回目のPopを行いました。経過時間=00:00:28.2666336
2000001回目のPopを行いました。経過時間=00:00:59.5157744
3000001回目のPopを行いました。経過時間=00:01:31.9194168
4000001回目のPopを行いました。経過時間=00:02:08.3223105
解1を発見。経過時間=00:02:20.2983652
3,19,16,
17, 7, 2,12,
18, 1, 5, 4,10,
11, 6, 8,13,
9,14,15,
解は1通り。経過時間=00:02:23.4684776
解説