8-3 ぶどうの房パズル初級編

問題

下の図に１〜３までの自然数を１つずつ入れるパズルです。
下の段にある○の中には、すぐ上にある２つの○の中にある数字の差が入ります。
同じ数字は１回しか使えません。

正解例はこうなります


以上をふまえて、下の図での1〜6までの自然数の組み合わせを求めます。

ソース

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

const int husaCnt = 6;

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

bool IsValid(JyoutaiDef pJyoutai);

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 (wkP[3] != 0 && wkP[0] != 0 && wkP[1] != 0) {
        if (wkP[3] != abs(wkP[0] - wkP[1])) return false;
    }
    if (wkP[4] != 0 && wkP[1] != 0 && wkP[2] != 0) {
        if (wkP[4] != abs(wkP[1] - wkP[2])) return false;
    }
    if (wkP[5] != 0 && wkP[3] != 0 && wkP[4] != 0) {
        if (wkP[5] != abs(wkP[3] - wkP[4])) return false;
    }

    return true;
}

実行結果

answer=6,2,5,4,3,1,
answer=6,1,4,5,3,2,
answer=5,6,2,1,4,3,
answer=5,2,6,3,4,1,
answer=4,6,1,2,5,3,
answer=4,1,6,3,5,2,
answer=2,6,5,4,1,3,
answer=1,6,4,5,2,3,

解説

STLのcountアルゴリズムは便利ですね。