15パズルを自動で解いてくれる仕組みを作りたい。

Question

実現したいこと

ボタンを右クリックでパズルが自動で組んでくれるようなものを作る
プログラムを書いてエラーもないのですがうまく動いてくれません。
原因がわかる方いましたら教えていただきたいです。

• ▲▲機能を動作するようにする

前提

ここに質問の内容を詳しく書いてください。
（例）
ｃｐｐで上のようなシステムを作っています
エラーはないのですがうまくパズルしてくれません。

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

#include "DxLib.h"
#include <windows.h>
#include <direct.h>
#include <shlwapi.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <functional>
#include <thread>

// グローバル変数
int pics[16];
int pic_all;
int panel[16];
enum Status { TITLE, MAIN, CLEAR };
Status status = TITLE;

struct State {
int panel[16];
int spaceIndex;
int cost;
std::vector<int> moves;

State() : panel{ 0 }, spaceIndex(0), cost(0), moves() {}

};
void solvePuzzle();

void asyncSolvePuzzle() {
std::thread solver(solvePuzzle);
solver.detach();
}
bool operator<(const State& a, const State& b) {
return a.cost > b.cost;
}

// マンハッタン距離を計算する
int manhattanDistance(int index, int value) {
int x1 = index % 4;
int y1 = index / 4;
int x2 = value % 4;
int y2 = value / 4;
return abs(x1 - x2) + abs(y1 - y2);
}

// 現在の状態のコストを計算する
int calculateCost(const State& state) {
int cost = 0;
for (int i = 0; i < 16; i++) {
if (state.panel[i] != 15) {
cost += manhattanDistance(i, state.panel[i]);
}
}
return cost;
}

// 選択したパネルと空白を入れ替える
void change(int x, int y) {
int p1 = y * 4 + x;
int p2 = -1;
if (x > 0 && panel[p1 - 1] == 15) p2 = p1 - 1;
if (x < 3 && panel[p1 + 1] == 15) p2 = p1 + 1;
if (y > 0 && panel[p1 - 4] == 15) p2 = p1 - 4;
if (y < 3 && panel[p1 + 4] == 15) p2 = p1 + 4;
if (p2 != -1) {
panel[p2] = panel[p1];
panel[p1] = 15;
}
}

// 自動でパズルを解く
void solvePuzzle() {
State initialState;
for (int i = 0; i < 16; i++) {
initialState.panel[i] = panel[i];
if (panel[i] == 15) {
initialState.spaceIndex = i;
}
}
initialState.cost = calculateCost(initialState);

std::priority_queue<State> openList;
openList.push(initialState);

std::vector<int> dx = { -1, 1, 0, 0 };
std::vector<int> dy = { 0, 0, -1, 1 };

while (!openList.empty()) {
    State current = openList.top();
    openList.pop();

    if (current.cost == 0) {
        for (int move : current.moves) {
            int x = current.spaceIndex % 4;
            int y = current.spaceIndex / 4;
            int newX = x + dx[move];
            int newY = y + dy[move];
            change(newX, newY);
            current.spaceIndex = newY * 4 + newX;
            Sleep(500); // 一つずつ動かすための待機時間
        }
        break;
    }

    for (int move = 0; move < 4; move++) {
        int x = current.spaceIndex % 4;
        int y = current.spaceIndex / 4;
        int newX = x + dx[move];
        int newY = y + dy[move];

        if (newX >= 0 && newX < 4 && newY >= 0 && newY < 4) {
            State next = current;
            next.spaceIndex = newY * 4 + newX;
            next.panel[current.spaceIndex] = next.panel[next.spaceIndex];
            next.panel[next.spaceIndex] = 15;
            next.cost = calculateCost(next);
            next.moves.push_back(move);
            openList.push(next);
        }
    }
}

}

// タイトル画面
void gameTitle() {
if (GetMouseInput() & MOUSE_INPUT_LEFT) {
// 初期パネルのシャッフル
for (int i = 0; i < 16; i++) panel[i] = i;
for (int i = 0; i < 1000; i++) {
change(GetRand(3), GetRand(3));
}
status = MAIN;
}
DrawGraph(0, 0, pic_all, FALSE);
DrawString(102, 142, "CLICK TO START", GetColor(255, 0, 0));
}

// メイン画面
void gameMain() {

int mouseInput = GetMouseInput();
if (mouseInput & MOUSE_INPUT_LEFT) {
    int x, y;
    GetMousePoint(&x, &y);
    change(x / 80, y / 80);
    // パネルが全部揃ったか判定
    bool clear = true;
    for (int i = 0; i < 16; i++) {
        if (panel[i] != i) clear = false;
    }
    if (clear) status = CLEAR;
}
else if (mouseInput & MOUSE_INPUT_RIGHT) {
    static bool solving = false;
    if (!solving) {
        solving = true;
        asyncSolvePuzzle();
        solving = false;
    }
}

// パネルの描画
for (int i = 0; i < 16; i++) {
    if (panel[i] < 15) {
        DrawGraph((i % 4) * 80, (i / 4) * 80, pics[panel[i]], FALSE);
    }
}

}

// 終了画面
void gameClear() {
DrawGraph(0, 0, pic_all, FALSE);
DrawString(115, 142, "GAME CLEAR!", GetColor(255, 0, 0));
}

int WINAPI WinMain(HINSTANCE, HINSTANCE, LPSTR, int) {
SetGraphMode(320, 320, 32);
ChangeWindowMode(TRUE);
DxLib_Init();
SetDrawScreen(DX_SCREEN_BACK);
LoadDivGraph(".\pic.png", 16, 4, 4, 80, 80, pics);
pic_all = LoadGraph(".\pic.png");

while (!ProcessMessage()) {
    ClearDrawScreen();
    switch (status)
        {

case TITLE: gameTitle(); break;
case MAIN: gameMain(); break;
case CLEAR: gameClear(); break;
}
ScreenFlip();
}
DxLib_End();
return 0;
}

ｃｐｐ
ソースコード

### 試したこと

上のプログラムを作りました。

### 補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[otn]

「パズル」というだけではプログラムの内容を何も説明していないので、意味不明のプログラムを誰も読む気にならないかと想います。
> // 選択したパネルと空白を入れ替える
という記述と、15や16という数が散見されることから、「15パズル」のことですかね？タイトルから書き直した方が良いと思います。

あと、
> パズルが自動で組んでくれる
もし15パズルであれば組むのは簡単なので、「パズルを自動で解いてくれる」の間違いでは？？？

[syujioooooo]

ありがとうございます。１５パズルのプログラムです。
タイトルと諸々説明を変更させていただきました

[Zuishin]

今ある回答を見ると、修正しても解くのに時間がかかりすぎて無反応になるようですが、15 ゲームは動的計画法で解くことができ、それを使えば短時間の解決の連続にすることができるので、無反応は避けられます。

考え方としては、4 × 4 のうち一番上の行をまずそろえて残り 4 × 3 にします。
次に左の列を揃えて 3 × 3 にします。
次に上の行を揃えて 3 × 2 にします。
そして左の列を揃えて 2 × 2 にします。
つまり、盤面の大きさと状態と揃える方向を引数とした関数を作り、それを再帰的に適用します。

一列揃えるには、まず二コマ残して揃え、残りを外で連続させておいて一度に収納します。
そうしないと、最後の一コマを揃えることができません。

画面は後回しにし、まずソルバーを作って文字出力で確認すると手戻りしにくくなります。

Answer 1

※DXライブラリ使用ソースをビルドできる環境が手元にないので、以下の回答ではソルバー部分しかチェックしていません。

問題は以下のソースにあります。

    if (current.cost == 0) {
        for (int move : current.moves) {
            int x = current.spaceIndex % 4;
            int y = current.spaceIndex / 4;
            int newX = x + dx[move];
            int newY = y + dy[move];
            change(newX, newY);
            current.spaceIndex = newY * 4 + newX;
            Sleep(500); // 一つずつ動かすための待機時間
        }
        break;
    }

current.movesは、初期状態の空白の位置から、目的の状態にするための移動経路になります。
つまり、current.spaceIndexではなく、initialState.spaceIndexから開始しないといけません。

あと、現在のコードだと、すでに処理済みのパターンが何度も処理されるので非効率です。
unordered_setで処理済みのものを覚えておいて、再度出現したら飛ばすようにしましょう。

#include <cstdint>
#include <unordered_set>

auto hash(const State& state) {
    std::uint64_t ret = 0;
    for (int i = 0; i < 16; ++i)
        ret |= std::uint64_t(state.panel[i]) << (i * 4);
    return ret;
}

void solvePuzzle() {
    State initialState;
    for (int i = 0; i < 16; i++) {
        initialState.panel[i] = panel[i];
        if (panel[i] == 15) {
            initialState.spaceIndex = i;
        }
    }
    initialState.cost = calculateCost(initialState);

    std::priority_queue<State> openList;
    std::unordered_set<std::uint64_t> used;
    openList.push(initialState);
    used.insert(hash(initialState));

    std::vector<int> dx = { -1, 1, 0, 0 };
    std::vector<int> dy = { 0, 0, -1, 1 };

    while (!openList.empty()) {
        State current = openList.top();
        openList.pop();

        if (current.cost == 0) {
            for (int move : current.moves) {
                int x = initialState.spaceIndex % 4;
                int y = initialState.spaceIndex / 4;
                int newX = x + dx[move];
                int newY = y + dy[move];
                change(newX, newY);
                initialState.spaceIndex = newY * 4 + newX;
                Sleep(500); // 一つずつ動かすための待機時間
            }
            break;
        }

        for (int move = 0; move < 4; move++) {
            int x = current.spaceIndex % 4;
            int y = current.spaceIndex / 4;
            int newX = x + dx[move];
            int newY = y + dy[move];

            if (newX >= 0 && newX < 4 && newY >= 0 && newY < 4) {
                State next = current;
                next.spaceIndex = newY * 4 + newX;
                next.panel[current.spaceIndex] = next.panel[next.spaceIndex];
                next.panel[next.spaceIndex] = 15;
                next.cost = calculateCost(next);
                next.moves.push_back(move);
                auto h = hash(next);
                if (used.count(h) <= 0) {
                    openList.push(next);
                    used.insert(h);
                }
            }
        }
    }
}

一応、これらの修正で動作はするようになりますが、最短手より大幅に手数が増えてしまいます。
こちらで紹介されている28手の問題を試してみましたが、このコードだと138手となり、5倍近くの手数が必要となりました。

15パズルをA*アルゴリズムで解きたいが、あるケースで無応答になる

それが嫌なら、ネットで別の方法を探してください。

一例として、英語版Wikipediaの「A* search algorithm」内にある「Weighted A*」を紹介しておきます。
A*アルゴリズムを実装したうえで、ヒューリスティック関数の返す値を2～3倍にするだけです。
3倍で試したところ、上記問題も38手まで縮めることができました。

※最初の回答では、修正しても時間がかかりすぎると説明したが、実際には処理済みをスキップすることで動作したため、回答を大幅に修正した。