スライドパズルが解けるかの判定
スライドパズルの状態は置換群として表現できるため、置換群の性質を利用して判定することが出来る。
非ITエンジニアの友人がAIエージェントを利用して作成したスライドパズルが、最初ただ単にシャッフルした配列から初期配置を生成する仕組みになっていた。これを見たとき、解けないケースが発生することに気づいたので、これを書いた。
判定アルゴリズム
次のようなアルゴリズムで判定できる。
- 空白のタイルが左下にあるn x nのスライドパズルの初期状態について、上の行から順に、左から右に向かって番号を付け、線形配列に変換する。つまり、空白をOとして、{1, 2, …, n^2-1, O}のように変換する。
- 変換された線形配列において、Oを無視して、転倒数を数える。
- グリッドにおける空白タイルの下から数えた行番号をrを求める。
- nが奇数の場合：転倒数が偶数であれば解ける。
- nが偶数の場合：rと転倒数の合計が奇数であれば解ける。
スライドパズルの状態は置換群として表現できるため、置換群の性質を利用して解けるかどうか判定することが出来る。 nが偶数の場合は、垂直方向の操作が奇数回の隣接互換に対応するため、置換のパリティを反転させることに注意。
問1
完全にランズムにシャッフルした配列からスライドパズルを生成した場合、どの程度の確率で解けなくなるか？
解答
nが奇数の場合、転倒数の偶奇性のみが可解性を決定するため、50%の確率で解けなくなる。 nが偶数の場合も、転倒数の偶奇性と空白タイルの偶奇性の組み合わせが可解性を決定するため、50%の確率で解けなくなる。問2
次のスライドパズルは解けるか？
1
2
3
4
5
6
8
7
O
解答
nが奇数で転倒数が(8, 7)の1個（奇数）であるため解けない。問3
次のスライドパズルは解けるか？
8
1
2
O
4
3
7
6
5
解答
nが奇数で転倒数が(8,1), (8,2), (8,4), (8,3), (8,7), (8,6), (8,5), (4,3), (7,6), (7,5), (6,5) の計 11 個（奇数）であるため解けない。問4
次のスライドパズルは解けるか？
1
2
3
4
5
6
7
8
9
10
11
12
13
15
14
O
解答
nが偶数で、転倒数が(15, 14) の 1 個（奇数）であり、空白タイルの位置が下から1行目、合計が2（偶数）であるため解けない。問5
次のスライドパズルは解けるか？
3
2
1
4
9
6
5
7
8
O
11
10
15
14
13
12
解答
nが偶数で、転倒数が14個（偶数）であり、空白タイルの位置が下から2行目、合計が16（偶数）であるため解けない。 転倒数は、次のようにマージソートなどを利用するとO(n log n)で計算できる。 function countInversionsMergeSort(arr) {
let count = 0;
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let merged = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
merged.push(left[i]);
i++;
} else {
merged.push(right[j]);
j++;
count += left.length - i;
}
}
return merged.concat(left.slice(i)).concat(right.slice(j));
}
mergeSort(arr);
return count;
}