8-6 連環の数 上級編

問題

連なった円の中に1から始まる、連続した自然数を入れていきます。
ただし、円の重なった部分には、その左右に入っている数の和を入れてください

円が8個の場合、1から15までの数を入れてみてください。

ソース

#include <stdio.h>
#include <Windows.h>
#include <stack>
#include <algorithm>

const int CircleCnt = 8;
const int MaxVal = CircleCnt * 2 - 1;

struct JyoutaiDef
{
    int Level;
    int IntArr[MaxVal];
};

bool IsValid(JyoutaiDef pJyoutai);
bool IsValidHelper(int pArr[],int P1, int P2, int P3);

void main()
{
    std::stack<JyoutaiDef> stk;
    JyoutaiDef WillPush;
    ZeroMemory(WillPush.IntArr,sizeof(WillPush.IntArr));
    WillPush.Level = 1;

    for (int I = 1; I <= MaxVal; I++) {
        WillPush.IntArr[0] = I;
        stk.push(WillPush);
    }

    int AnswerCnt = 0;
    while (stk.empty() == false) {
        JyoutaiDef Popped = stk.top(); stk.pop();

        if (Popped.Level == MaxVal) {
            char WillOut[256] = {'\0'};
            for(int I=0;I<= sizeof(Popped.IntArr)/sizeof(int)-1;I++){
                char wk[99];wsprintf(wk,"%d,",Popped.IntArr[I]);
                strcat_s(WillOut,wk);
            }
            printf("answer%d = %s\n", ++AnswerCnt,WillOut);
            continue;
        }

        WillPush.Level = Popped.Level + 1;

        for (int I = 1; I <= MaxVal; I++) {
            if (std::count(Popped.IntArr,Popped.IntArr+sizeof(Popped.IntArr)/sizeof(int),I)>0)
                continue;

            memcpy(WillPush.IntArr,Popped.IntArr,sizeof(Popped.IntArr));
            WillPush.IntArr[WillPush.Level - 1] = I;

            if (IsValid(WillPush)) stk.push(WillPush);
        }
    }
}

bool IsValid(JyoutaiDef pJyoutai)
{
    if (IsValidHelper(pJyoutai.IntArr, 0, 1, 2) == false) return false;
    if (IsValidHelper(pJyoutai.IntArr, 2, 3, 4) == false) return false;
    if (IsValidHelper(pJyoutai.IntArr, 4, 5, 6) == false) return false;
    if (IsValidHelper(pJyoutai.IntArr, 6, 7, 8) == false) return false;
    if (IsValidHelper(pJyoutai.IntArr, 8, 9, 10) == false) return false;
    if (IsValidHelper(pJyoutai.IntArr, 10, 11, 12) == false) return false;
    if (IsValidHelper(pJyoutai.IntArr, 12, 13, 14) == false) return false;
    return true;
}

bool IsValidHelper(int pArr[],int P1, int P2, int P3)
{
    if (pArr[P1] != 0 && pArr[P2] != 0 && pArr[P3] != 0) {
        if (pArr[P2] != pArr[P1] + pArr[P3]) return false;
    }
    return true;
}

実行結果

answer1 = 14,15,1,12,11,13,2,7,5,8,3,9,6,10,4,
answer2 = 14,15,1,12,11,13,2,6,4,9,5,8,3,10,7,
answer3 = 14,15,1,11,10,13,3,8,5,12,7,9,2,6,4,
省略
answer394 = 1,3,2,10,8,12,4,11,7,13,6,15,9,14,5,
answer395 = 1,3,2,9,7,13,6,11,5,15,10,14,4,12,8,
answer396 = 1,3,2,9,7,12,5,13,8,14,6,10,4,15,11,

解説

ヘルパメソッドが活躍してますね。