8-4 ぶどうの房パズル上級編

問題

下の図での1〜15までの自然数の組み合わせを求めます。

ソース

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

const int husaCnt = 15;

struct JyoutaiDef
{
    int Level;
    int intArr[husaCnt];
};

bool IsValid(JyoutaiDef pJyoutai);
bool IsValidSub(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 <= husaCnt; I++) {
        WillPush.intArr[0] = I;
        stk.push(WillPush);
    }

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

        if (Popped.Level == husaCnt) {
            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=%s\n", WillOut);
            continue;
        }

        WillPush.Level = Popped.Level + 1;

        for (int I = 1; I <= husaCnt; I++) {
            if (std::count(Popped.intArr,Popped.intArr+husaCnt,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)
{
    int* wkP = pJyoutai.intArr;

    if (IsValidSub(wkP[5], wkP[0], wkP[1]) == false) return false;
    if (IsValidSub(wkP[6], wkP[1], wkP[2]) == false) return false;
    if (IsValidSub(wkP[7], wkP[2], wkP[3]) == false) return false;
    if (IsValidSub(wkP[8], wkP[3], wkP[4]) == false) return false;
    if (IsValidSub(wkP[9], wkP[5], wkP[6]) == false) return false;
    if (IsValidSub(wkP[10], wkP[6], wkP[7]) == false) return false;
    if (IsValidSub(wkP[11], wkP[7], wkP[8]) == false) return false;
    if (IsValidSub(wkP[12], wkP[9], wkP[10]) == false) return false;
    if (IsValidSub(wkP[13], wkP[10], wkP[11]) == false) return false;
    if (IsValidSub(wkP[14], wkP[12], wkP[13]) == false) return false;
    return true;
}

bool IsValidSub(int P1, int P2, int P3)
{
    if (P1 != 0 && P2 != 0 && P3 != 0) {
        if (P1 != abs(P2 - P3)) return false;
    }
    return true;
}

実行結果

answer=13,3,15,14,6,10,12,1,8,2,11,7,9,4,5,
answer=6,14,15,3,13,8,1,12,10,7,11,2,4,9,5,

解説

差のチェック用のヘルパメソッドを作ってます。