質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
DXライブラリ

DXライブラリとは、DirectXを使ったWindowsソフトの開発に必ず付いて回るDirectXやWindows関連のプログラムを使い易くまとめた形で利用できるようにしたC++言語用のゲームライブラリです。

Q&A

1回答

1695閲覧

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

syujioooooo

総合スコア1

DXライブラリ

DXライブラリとは、DirectXを使ったWindowsソフトの開発に必ず付いて回るDirectXやWindows関連のプログラムを使い易くまとめた形で利用できるようにしたC++言語用のゲームライブラリです。

0グッド

0クリップ

投稿2023/04/16 06:33

編集2023/05/05 19:22

実現したいこと

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

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

前提

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

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

エラーメッセージ

該当のソースコード

#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;
}

cpp
ソースコード

### 試したこと 上のプログラムを作りました。 ### 補足情報(FW/ツールのバージョンなど) ここにより詳細な情報を記載してください。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

otn

2023/04/16 07:00

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

2023/04/16 07:04

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

2023/04/17 00:19 編集

今ある回答を見ると、修正しても解くのに時間がかかりすぎて無反応になるようですが、15 ゲームは動的計画法で解くことができ、それを使えば短時間の解決の連続にすることができるので、無反応は避けられます。 考え方としては、4 × 4 のうち一番上の行をまずそろえて残り 4 × 3 にします。 次に左の列を揃えて 3 × 3 にします。 次に上の行を揃えて 3 × 2 にします。 そして左の列を揃えて 2 × 2 にします。 つまり、盤面の大きさと状態と揃える方向を引数とした関数を作り、それを再帰的に適用します。 一列揃えるには、まず二コマ残して揃え、残りを外で連続させておいて一度に収納します。 そうしないと、最後の一コマを揃えることができません。 画面は後回しにし、まずソルバーを作って文字出力で確認すると手戻りしにくくなります。
guest

回答1

0

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

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

c++

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

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

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

c++

1#include <cstdint> 2#include <unordered_set> 3 4auto hash(const State& state) { 5 std::uint64_t ret = 0; 6 for (int i = 0; i < 16; ++i) 7 ret |= std::uint64_t(state.panel[i]) << (i * 4); 8 return ret; 9} 10 11void solvePuzzle() { 12 State initialState; 13 for (int i = 0; i < 16; i++) { 14 initialState.panel[i] = panel[i]; 15 if (panel[i] == 15) { 16 initialState.spaceIndex = i; 17 } 18 } 19 initialState.cost = calculateCost(initialState); 20 21 std::priority_queue<State> openList; 22 std::unordered_set<std::uint64_t> used; 23 openList.push(initialState); 24 used.insert(hash(initialState)); 25 26 std::vector<int> dx = { -1, 1, 0, 0 }; 27 std::vector<int> dy = { 0, 0, -1, 1 }; 28 29 while (!openList.empty()) { 30 State current = openList.top(); 31 openList.pop(); 32 33 if (current.cost == 0) { 34 for (int move : current.moves) { 35 int x = initialState.spaceIndex % 4; 36 int y = initialState.spaceIndex / 4; 37 int newX = x + dx[move]; 38 int newY = y + dy[move]; 39 change(newX, newY); 40 initialState.spaceIndex = newY * 4 + newX; 41 Sleep(500); // 一つずつ動かすための待機時間 42 } 43 break; 44 } 45 46 for (int move = 0; move < 4; move++) { 47 int x = current.spaceIndex % 4; 48 int y = current.spaceIndex / 4; 49 int newX = x + dx[move]; 50 int newY = y + dy[move]; 51 52 if (newX >= 0 && newX < 4 && newY >= 0 && newY < 4) { 53 State next = current; 54 next.spaceIndex = newY * 4 + newX; 55 next.panel[current.spaceIndex] = next.panel[next.spaceIndex]; 56 next.panel[next.spaceIndex] = 15; 57 next.cost = calculateCost(next); 58 next.moves.push_back(move); 59 auto h = hash(next); 60 if (used.count(h) <= 0) { 61 openList.push(next); 62 used.insert(h); 63 } 64 } 65 } 66 } 67}

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

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

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

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

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

投稿2023/04/16 11:38

編集2023/05/05 10:22
actorbug

総合スコア2212

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問