8-9 15パズル

問題

15パズルを解きます。

ソース

#include <string>
#include <vector>
#include <valarray>
#include <queue>
#include <iostream>

class JyoutaiDef
{
public:
    int Level;
    std::string MoveLog;
    std::vector<std::valarray<int> > Ban;
    std::string PreMove;

    void Init()
    {
        int wkBan[][4] = {{ 1, 2, 3, 4,},
                          { 0, 5, 6, 7,},
                          { 9,10,11, 8,},
                          {13,14,15,12,}};
        for(int I=0;I<=sizeof(wkBan)/sizeof(wkBan[0])-1;I++){
            std::valarray<int> wkArr(wkBan[I],sizeof(wkBan[I])/sizeof(int));
            Ban.push_back(wkArr);
        }
        PreMove = "";
    }

    bool IsGoal()
    {
        int mustNumber = 0;
        for (int Y = 0; Y <= 3; Y++) {
            for (int X = 0; X <= 3; X++) {
                ++mustNumber;
                if (mustNumber != 16 && Ban.at(Y)[X] != mustNumber) return false;
            }
        }
        return true;
    }
};

void main()
{
    JyoutaiDef Jyoutai;
    Jyoutai.Init();

    std::queue<JyoutaiDef> que;
    que.push(Jyoutai);

    int AnswerLevel = INT_MAX;

    while (que.empty() == false) {
        Jyoutai = que.front(); que.pop();

        if (++Jyoutai.Level > AnswerLevel) continue;

        if (Jyoutai.IsGoal()) {
            std::cout << "Answer" << std::endl;
            std::cout << Jyoutai.MoveLog << std::endl;
            AnswerLevel = Jyoutai.Level;
            continue;
        }

        int X = 0, Y = 0;
        while (Jyoutai.Ban.at(Y)[X] != 0) {
            if (++Y == 4) {
                X++; Y = 0;
            }
        }

        //左の数字を、右に移動
        if (X != 0 && Jyoutai.PreMove!="←"){
            JyoutaiDef Saved = Jyoutai;
            Saved.Ban.at(Y)[X-1] = 0;
            Saved.Ban.at(Y)[X] = Jyoutai.Ban.at(Y)[X-1];
            Saved.MoveLog += "→,";
            Saved.PreMove = "→";
            que.push(Saved);
        }

        //右の数字を、左に移動
        if (X != 3 && Jyoutai.PreMove!="→"){
            JyoutaiDef Saved = Jyoutai;
            Saved.Ban.at(Y)[X+1] = 0;
            Saved.Ban.at(Y)[X] = Jyoutai.Ban.at(Y)[X+1];
            Saved.MoveLog += "←,";
            Saved.PreMove = "←";
            que.push(Saved);
        }

        //上の数字を、下に移動
        if (Y != 0 && Jyoutai.PreMove!="↑"){
            JyoutaiDef Saved = Jyoutai;
            Saved.Ban.at(Y-1)[X] = 0;
            Saved.Ban.at(Y)[X] = Jyoutai.Ban.at(Y-1)[X];
            Saved.MoveLog += "↓,";
            Saved.PreMove = "↓";
            que.push(Saved);
        }

        //下の数字を、上に移動
        if (Y != 3 && Jyoutai.PreMove!="↓"){
            JyoutaiDef Saved = Jyoutai;
            Saved.Ban.at(Y+1)[X] = 0;
            Saved.Ban.at(Y)[X] = Jyoutai.Ban.at(Y+1)[X];
            Saved.MoveLog += "↑,";
            Saved.PreMove = "↑";
            que.push(Saved);
        }
    }
}

実行結果

Answer
←,←,←,↑,↑,

解説

ビルトイン配列の2次元配列を初期化子で初期化してから
For文で、ValArrayのVectorにセットしてます。