15パズルの最短手数の最大値ってどうなっているんだろう？とふと疑問に思い調べてみると、「任意の可能な配置へ80手以内で変形でき、80手が必要な配置は確認されている」（Wikipediaより）とのこと。
15パズルは空白を利用して15個のピースを移動させて順番に並べるパズルですが、空白部分を16番ピースをみなすと16個のピースを全部で並び方は16!（1×2×…×16）とおりあることになります。ただしパズルとして成立するのはその半分だけです。なので考えられるピースの配置は 16! / 2 とおりです。これは10^13よりも大きな数で全列挙することはできません。
そこで今回は妥協して3×3の8パズルを考えます。これだと 9! / 2 = 181440とおりなので全探索することができます。
Contents
幅優先探索で最短手数の最大値を調べる
幅優先探索をして考えることにします。まず3×3の盤面を二次元配列として考えるのは面倒なので、3行を1つの文字列にまとめてしまうことにします。ピースの番号をそのまま文字にして空白部分を’*’とすると、整列された状態は”12345678*”と表すことができます。
まず空白の上下左右を調べて移動可能であれば移動後の文字列を取得するメソッドを定義します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Program { static List<string> GetSwapStrings(string s, int n) { List<string> rets = new List<string>(); int idx = s.IndexOf('*'); // 空白部分は二次元配列なら何行目の何列目になるか？ int r = idx / n; int c = idx % n; int[] dx = [1, -1, 0, 0]; // 右,左,下,上 int[] dy = [0, 0, 1, -1]; for (int i = 0; i < 4; i++) { int nr = r + dy[i]; int nc = c + dx[i]; if (nr < 0 || nr >= n || nc < 0 || nc >= n) // となりにピースが存在しない continue; int n_idx = nr * n + nc; // となりにピースが存在する場合は入れ替えたときの文字列を取得する char[] t = s.ToArray(); t[idx] = t[n_idx]; t[n_idx] = '*'; rets.Add(new string(t)); } return rets; } } |
幅優先探索で移動できる場合を全部取得します。内部で辞書をふたつ使っていますが、結果を取得するためにこれらをタプルで返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Program { // start: 初期状態, n: 1辺の長さ static (Dictionary<string, int>, Dictionary<string, string>) Bfs(string start, int n) { // 一度探索した場所は探索しない。Valueはその局面にたどり着くまでの手数 Dictionary<string, int> dic = new Dictionary<string, int>(); // その局面の前の局面も保存しておく。いまは使わないがあとで使うのでここで定義しておく。 Dictionary<string, string> from = new Dictionary<string, string>(); Queue<string> q = new Queue<string>(); dic.Add(start, 0); from.Add(start, ""); q.Enqueue(start); while (q.Count > 0) { string s = q.Dequeue(); int d = dic[s]; var swaps = GetSwapStrings(s, n); foreach (string swap in swaps) { if (!dic.ContainsKey(swap)) { q.Enqueue(swap); dic.Add(swap, d + 1); from.Add(swap, s); } } } return (dic, from); } } |
定義したメソッドで最短手数が最長になるものを探します。すると31手になるものが2つあることがわかります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Program { static void Main() { int N = 3; string start = "12345678*"; (Dictionary<string, int>, Dictionary<string, string>) ret = Bfs(start, N); Console.WriteLine($"全部で{ret.Item1.Count}とおり"); var pairs = ret.Item1.ToArray(); int max = pairs.Max(_ => _.Value); pairs = pairs.Where(_ => _.Value == max).ToArray(); Console.WriteLine($"最短手数の最大値は{max}で{pairs.Length}とおり"); Console.WriteLine(); void ShowCells(string s) { for (int i = 0; i < 3; i++) Console.WriteLine(s.Substring(i * 3, 3)); Console.WriteLine(); } foreach (var pair in pairs) ShowCells(pair.Key); } } |
手順を取得する
ついでに手順も取得できるようにします。幅優先探索の処理でfromに格納した情報からひとつ前の状態をしることができるので、逆順にたどって具体的な最短手順を表示させることができるようにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Program { static List<string> GetHistory(Dictionary<string, string> from) { List<string> rets = new List<string>(); rets.Add("12345678*"); string s = from["12345678*"]; while (s != "") { rets.Add(s); s = from[s]; } rets.Reverse(); // 逆順なので前から順番に表示させたいなら順序を反転させる return rets; } } |
最短手順が最長になるものが取得されたらこれを幅優先探索することで整列された状態に戻すための手順を取得し、これを0手目から31手目まで表示させます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
class Program { static void Main() { int N = 3; string start = "12345678*"; (Dictionary<string, int>, Dictionary<string, string>) ret = Bfs(start, N); Console.WriteLine($"全部で{ret.Item1.Count}とおり"); var pairs = ret.Item1.ToArray(); int max = pairs.Max(_ => _.Value); pairs = pairs.Where(_ => _.Value == max).ToArray(); Console.WriteLine($"最短手数の最大値は{max}で{pairs.Length}とおり"); Console.WriteLine(); void ShowCells(string s) { for (int i = 0; i < 3; i++) Console.WriteLine(s.Substring(i * 3, 3)); Console.WriteLine(); } foreach (var pair in pairs) ShowCells(pair.Key); foreach (var pair in pairs) { (Dictionary<string, int>, Dictionary<string, string>) ret2 = Bfs(pair.Key, N); List<string> history = GetHistory(ret2.Item2); int cnt = 0; foreach (string s in history) { Console.WriteLine($"{cnt}手目"); ShowCells(s); cnt++; } } } } |
