JavaScriptを使って2x3のパズルを解く方法

前提・実現したいこと

JavaScriptを使って以下の画像のように0から5までの6つの数が長方形状に並んでいて、中央を含め左側の4つを幹回りに1つ回転させる移動をL、右側の4つを右回りに1つ回転させる移動をRとします。今回の画像の例では初期状態を[2,1,5,0,3,4]のように与えられ、ゴール状態をg = [0,1,2,3,4,5]とし、与えられた状態からゴール状態までの変化させるための辞書式で最も若い最短の動きを文字列として"RRLLRRR..."のように返す関数puzzle(state)を作りたいのですが、どのようにプログラムを組めばいいのかわかりません。

試したこと

幅優先探索を使い与えられた状態からゴール状態まで探索すれば良いことは分かっているのですが、出現したパターンを記憶させる方法やゴール状態からどのようにして文字列を取り出せばよいかなどが分かりません。

補足

画像のパターンの場合は"LR"を返すような関数を考えています。また、ゴール状態は毎回g = [0,1,2,3,4,5]です。

yambejp

2020/11/26 10:13

解く方法がほしいのですか？ゲーム自体が動作すればいいのですか？

mjnvrsty_J

2020/11/26 12:42

解く方法が欲しいです

行動規範の内容に同意します

回答2件

ベストアンサー

なにか効率的な解法がありそうな気もしますが、
この程度のデータ数なら全通りチェックすればよさそうです。
計算上10ループすると元データから変換可能な最終データまで拾え
120通りのデータになります

codepen lr game

投稿2020/11/27 01:11

yambejp

総合スコア116724

babu_babu_baboo

2020/11/27 03:59 編集

'LLLRRR','LLLRR','LLLR','LLRRR','LLRR','LLR','LRRR','LRR','LR',’RRR','RR','R'での結果をさらに繰り返しているうちにできるでしょうね。そのためのコアな部分を書いてみたのですが、利用されるどころか見向きもされませんでした。

mjnvrsty_J

2020/11/27 05:04

お二方ともありがとうございました。先に回答いただいた方も気を害されたようで申し訳ないですが、初めて質問したためこんなにも早く回答が来るとは思っておらず見逃しておりました。コードは見させていただきました。知らなかった内容もいろいろあり大変勉強になりました。本当にありがとうございました。

行動規範の内容に同意します

解法は知りませんが根幹となりませんか？
応用の仕方の例も掲載し、ちょっと手直ししました。

HTML&JS
1<!DOCTYPE html>
2<meta charset="UTF-8">
3<title>A23</title>
4<style>
5td, input[type="button"] {
6  font-size: xx-large;
7  border: 2px gray ridge;
8  border-radius: 40px;
9  padding: 1ex 1em;
10}
11</style>
12
13<body>
14<table id="A">
15  <tr><td><td><td>
16  <tr><td><td><td>
17</table>
18<p>
19  <input type="button" value="L">
20  <input type="button" value="Reset">
21  <input type="button" value="R"><br>
22  <input type="text" size="40" value="" id="S">
23</p>
24
25<script>
26class A23 {
27  constructor (...arg) {
28    this.reset (...arg);
29  }
30
31  R () {
32    let [a,b,c,d,e,f] = this.map;
33    this.map = [a,e,b,d,f,c];
34    this.history += 'R';
35    return this;
36  }
37
38  L () {
39    let [a,b,c,d,e,f] = this.map;
40    this.map = [b,e,c,a,d,f];
41    this.history += 'L';
42    return this;
43  }
44
45  advance (str ='') {
46    [...str].forEach (s=> this[s]());
47    this.history += str;
48    return this;
49  }
50
51  reset (LR = '', map = [0, 1, 2, 3, 4, 5]) {
52    this.map = map;
53    this.history = '';
54    return this.advance (LR);
55  }
56
57  copy () {
58    return new this.constructor ('', this.map);
59  }
60}
61
62//____________________________
63
64function disp () {
65  [...A.querySelectorAll ('td')]
66    .forEach ((e, i)=> e.textContent = a23.map[i]);
67  S.value = a23.history;
68}
69
70function handler ({target: e}) {
71  let { type, value } = e;
72  if ('button' === type)
73    switch (e.value) {
74    case 'L' : a23.L (); break;
75    case 'R' : a23.R (); break;
76    case 'Reset': a23.reset ();
77    }
78    disp ();
79}
80
81const a23 = new A23;
82disp ();
83document.addEventListener ('click', handler, false);
84
85
86</script>