パズルの説明
今回は「おしどりの遊び」という古典的なパズルを取り上げます。このパズルは囲碁の白石と黒石を交互に並べ、それをペアで動かしながら黒石と白石とに分けるというもので、参考文献 7 によると江戸時代からある遊びだそうです。
石はペアで空いている場所に動かすことができます。このときペアの順番を変えることはできません。たとえば、先頭にある黒白を動かすときに、白黒というように石の順番を逆にすることは許されません。この条件で並べ替えるまでの最短手順を求めてください。
●プログラムの作成
今回は Python3 (ver 3.8.10) でプログラムを作ることにします。最短手順を求めるので「幅優先探索」を使いましょう。幅優先探索でパズルを解く場合、同一局面の探索処理が重要になります。もう何回も説明しているので、耳にタコができているかもしれませんね。まず最初に、石の置き方が何通りあるか数えましょう。
これは空き場所の配置から考えた方が簡単です。2 つの空き場所は離ればなれにならないのですから、7 通りの配置が考えられます。次に、残り 6 ヵ所に 3 個の黒石を置くことを考えます。これは 6 個の中から 3 個を選ぶ組み合わせと考えられるので、組み合わせの公式から (6 * 5 * 4) / (1 * 2 * 3) = 20 通りあります。黒石の置き方が決まれば、白石は残りの 3 ヵ所に置くだけです。したがって、全体では 20 * 7 = 140 通り、局面の総数は少ないので同一局面のチェックは単純な線形探索で十分でしょう。
プログラムは次のようになります。
リスト : オシドリの遊び
# 駒
S = 0
B = 1
W = 2
# 手順の表示
def print_answer(n, buff):
if n > 0:
print_answer(buff[n][1], buff)
print(buff[n][0])
# 幅優先探索
def bfs(start, goal):
queue = [(start, -1, start.index(0))]
check = [start]
rc = 0
while rc < len(queue):
b, _, s = queue[rc]
for i in range(7):
if b[i] == S or b[i + 1] == S: continue
newb = b[:]
newb[s], newb[s + 1] = newb[i], newb[i + 1]
newb[i] = newb[i + 1] = S
if newb not in check:
queue.append((newb, rc, i))
check.append(newb)
if newb == goal:
print_answer(len(queue) - 1, queue)
print(len(queue))
return
rc += 1
def solver():
bfs([B,W,B,W,B,W,S,S], [B,B,B,W,W,W,S,S])
関数 bfs() は幅優先探索で解を求めます。引数 start がスタート、goal がゴールを表します。今回は配列 queue をキューとして使います。キューの要素は、盤面、1 手前の盤面がある queue の添字、空き場所の位置を格納したタプルです。データを追加は append() で行います。データの取り出しは変数 rc をリードカウンタとして使えば簡単です。同一局面のチェックには配列 check を使います。盤面を check に格納することで in, not in 演算子で判定することができます。
あとはキューからデータを取り出して、駒を動かして新しい盤面 newb を生成します。for ループの変数 i と i + 1 が動かす駒の位置です。駒が 2 つあれば、それを空き場所へ動かします。そして、check に newb が無ければ、queue と check に newb を登録します。newb が goal に到達したならば、print_answer() で手順を表示して return で探索を終了します。
●実行結果
それでは実行してみましょう。
>>> solver() [1, 2, 1, 2, 1, 2, 0, 0] [1, 2, 1, 0, 0, 2, 2, 1] [1, 2, 1, 2, 2, 0, 0, 1] [1, 0, 0, 2, 2, 2, 1, 1] [1, 1, 1, 2, 2, 2, 0, 0] 65
4 回で解くことができました。ちなみに、黒と白の分け方を逆にした「白白白黒黒黒空空」も、4 回で解くことができます。ところで、空き場所や石の配置を限定しなければ 3 回で解くことができます。
参考文献 9, 10 は、この条件で解いています。この本によると、黒石と白石を n 個ずつにした場合、最小回数は n 回で解くことができるそうです。
●変形版オシドリの遊び
次はおしどりの遊びの変形版を考えてみましょう。変形版というと、たとえば 3 個 1 組で移動する、などいろいろ考えられますが、今回は石の種類を増やすことにします。
ルールは同じで、石はペアで空いている場所に動かすことができます。このとき、ペアの順番を変えることはできません。石はそれぞれ 2 個ずつとし、石の種類を増やすと移動手順はどうなるか調べてみたいと思います。
●ハッシュ法
幅優先探索でパズルを解く場合、同一局面の探索処理が重要になります。もう何回も説明しているので、耳にタコができているかもしれませんね。今回は Python の辞書 (ディクショナリ) を使うことにします。Python の辞書は「ハッシュ法」というアルゴリズムで実装されています。
ここで簡単にハッシュ法の仕組みを説明しましょう。ハッシュ法は「ハッシュ表」と呼ばれるデータを格納する配列と、データを数値に変換する「ハッシュ関数」を用意します。たとえば、ハッシュ表の大きさを n とすると、ハッシュ関数はデータを 0 から n - 1 までの整数値に変換するように作ります。この値を「ハッシュ値」と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める探索方法がハッシュ法なのです。
ハッシュ法で不特定多数のデータを扱う場合、異なるデータでも同じハッシュ値が生成されることがあります。これを「ハッシュ値の衝突」といいます。つまり、データをハッシュ表に登録しようとしても、すでに先客が居座っているわけです。この場合、2 種類の解決方法があります。
ひとつは空いている場所を探して、そこに入れる方法です。新しい場所を探すといっても、テーブルの先頭から線形探索するのではなく、最初とは違うハッシュ関数を用意して、新しくハッシュ値を計算させて場所を決めます。これを空いている場所が見つかるまで繰り返します。
この方法だと、データの最大数はハッシュ表の大きさに制限されます。また、ハッシュ表の空きが少なくなると、探索効率も極端に低下してしまいます。このため、ハッシュ表の空きが少なくなったら、ハッシュ表のサイズを大きくし、ハッシュ表を作り直す作業を行うのがふつうです。これを「リハッシュ (rehash)」といいます。そのあと探索効率は良くなりますので、リハッシュにかけた時間のもとは十分にとれます。
もうひとつは、ハッシュ表に複数のデータを格納することです。配列にはひとつのデータしか格納できないので、複数個のデータをまとめて格納しておく工夫が必要になります。このときによく利用されるデータ構造が「連結リスト (Linked List)」です。ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されている連結リストの中からデータを探索します。連結リストの代わりに「二分探索木」を使う方法もあります。
この方法では、ハッシュ値の衝突が頻繁に発生すると、データを格納するリストが長くなるため、探索時間が余分にかかってしまいます。効率よく探索を行うためには、ハッシュ表の大きさとハッシュ関数の選択が重要になります。
ハッシュ法のアルゴリズムに興味のある方は拙作のページ Algorithms with Python ハッシュ法 をお読みくださいませ。
●プログラムの作成
プログラムは次のようになります。
リスト : 変形版オシドリの遊び
def print_answer2(b, table):
prev = table[b]
if prev:
print_answer2(prev, table)
print(b)
def bfs2(start, goal):
queue = deque()
queue.append((start, start.index(0)))
check = {}
check[start] = []
while len(queue) > 0:
b, s = queue.popleft()
for i in range(len(start) - 1):
if b[i] == S or b[i + 1] == S: continue
a = list(b)
a[s], a[s + 1] = a[i], a[i + 1]
a[i] = a[i + 1] = S
newb = tuple(a)
if newb not in check:
queue.append((newb, i))
check[newb] = b
if newb == goal:
print_answer2(newb, check)
print(len(check))
return
def solver2():
for i in range(3, 8):
xs = list(range(1, i+1))
start = xs + xs + [0, 0]
goal = []
for j in range(1, i+1):
goal.append(j)
goal.append(j)
goal += [0, 0]
s = time.time()
print(f'----- {i} -----')
bfs2(tuple(start), tuple(goal))
print(time.time() - s)
bfs2() は bfs() と同じく幅優先探索で解を求めます。キューは標準ライブラリ collections の deque を、同一局面のチェックは Python の辞書を使うように変更しています。Python の場合、辞書のキーに配列 (リスト) を使うことができないので、盤面はタプルで表すことにします。deque はデータを取り出すとキュー本体から削除するので、辞書に 1 手前の盤面を記録しておいて、それを使って手順を表示するようにしています。あとは特に難しいところはないと思います。
●実行結果
それでは実行結果を示します。6 種類まで調べると次のようになりました。
>>> solver2() ----- 3 ----- (1, 2, 3, 1, 2, 3, 0, 0) (1, 0, 0, 1, 2, 3, 2, 3) (1, 1, 2, 0, 0, 3, 2, 3) (1, 1, 2, 2, 3, 3, 0, 0) 28 0.0022253990173339844 ----- 4 ----- (1, 2, 3, 4, 1, 2, 3, 4, 0, 0) (1, 0, 0, 4, 1, 2, 3, 4, 2, 3) (1, 4, 1, 0, 0, 2, 3, 4, 2, 3) (0, 0, 1, 1, 4, 2, 3, 4, 2, 3) (1, 1, 0, 0, 4, 2, 3, 4, 2, 3) (1, 1, 2, 3, 4, 0, 0, 4, 2, 3) (1, 1, 2, 0, 0, 3, 4, 4, 2, 3) (1, 1, 2, 2, 3, 3, 4, 4, 0, 0) 12031 0.03376197814941406 ----- 5 ----- (1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 0, 0) (1, 0, 0, 4, 5, 1, 2, 3, 4, 5, 2, 3) (1, 1, 2, 4, 5, 0, 0, 3, 4, 5, 2, 3) (1, 1, 2, 4, 5, 3, 4, 0, 0, 5, 2, 3) (1, 1, 2, 0, 0, 3, 4, 4, 5, 5, 2, 3) (1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 0, 0) 4552 0.011899709701538086 ----- 6 ----- (1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 0, 0) (1, 0, 0, 4, 5, 6, 1, 2, 3, 4, 5, 6, 2, 3) (1, 1, 2, 4, 5, 6, 0, 0, 3, 4, 5, 6, 2, 3) (1, 1, 2, 4, 5, 6, 4, 5, 3, 0, 0, 6, 2, 3) (1, 1, 2, 4, 0, 0, 4, 5, 3, 5, 6, 6, 2, 3) (1, 1, 2, 4, 5, 3, 4, 0, 0, 5, 6, 6, 2, 3) (1, 1, 2, 0, 0, 3, 4, 4, 5, 5, 6, 6, 2, 3) (1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 0, 0) 663167 1.362980842590332 実行環境 : Python3 (ver 3.8.10), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
今回のプログラムは単純な幅優先探索なので、駒の種類を増やすとメモリの使用量が爆発的に増加するため、M.Hiroi の環境ではこのあたりが限界のようです。改訂前のＣ言語で作成したプログラム (oshidori.c) は双方向探索を行っているので、もう少し駒の種類を増やすことができます。興味のある方は プログラムリスト２ をお読みください。
oshidori.c の実行結果を示します。
$ gcc -O2 oshidori.c $ ./a.out ----- 3 種類の探索 ----- 1 2 3 1 2 3 0 0 1 0 0 1 2 3 2 3 1 1 2 0 0 3 2 3 1 1 2 2 3 3 0 0 状態数 15 個 時間 0.000000 ----- 4 種類の探索 ----- 1 2 3 4 1 2 3 4 0 0 1 0 0 4 1 2 3 4 2 3 1 4 1 0 0 2 3 4 2 3 0 0 1 1 4 2 3 4 2 3 1 1 0 0 4 2 3 4 2 3 1 1 2 3 4 0 0 4 2 3 1 1 2 0 0 3 4 4 2 3 1 1 2 2 3 3 4 4 0 0 状態数 467 個 時間 0.000000 ----- 5 種類の探索 ----- 1 2 3 4 5 1 2 3 4 5 0 0 1 0 0 4 5 1 2 3 4 5 2 3 1 1 2 4 5 0 0 3 4 5 2 3 1 1 2 4 5 3 4 0 0 5 2 3 1 1 2 0 0 3 4 4 5 5 2 3 1 1 2 2 3 3 4 4 5 5 0 0 状態数 199 個 時間 0.000000 ----- 6 種類の探索 ----- 1 2 3 4 5 6 1 2 3 4 5 6 0 0 1 0 0 4 5 6 1 2 3 4 5 6 2 3 1 1 2 4 5 6 0 0 3 4 5 6 2 3 1 1 2 4 5 6 4 5 3 0 0 6 2 3 1 1 2 4 0 0 4 5 3 5 6 6 2 3 1 1 2 4 5 3 4 0 0 5 6 6 2 3 1 1 2 0 0 3 4 4 5 5 6 6 2 3 1 1 2 2 3 3 4 4 5 5 6 6 0 0 状態数 2632 個 時間 0.000000 ----- 7 種類の探索 ----- 1 2 3 4 5 6 7 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 0 0 3 4 5 6 7 1 2 1 2 3 0 0 6 7 4 5 3 4 5 6 7 1 2 1 2 3 3 4 6 7 4 5 0 0 5 6 7 1 2 1 2 3 3 4 6 7 4 5 5 6 0 0 7 1 2 1 2 3 3 4 0 0 4 5 5 6 6 7 7 1 2 1 2 3 0 0 3 4 4 5 5 6 6 7 7 1 2 1 0 0 2 3 3 4 4 5 5 6 6 7 7 1 2 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 状態数 16935 個 時間 0.015625 ----- 8 種類の探索 ----- 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 0 0 1 0 0 4 5 6 7 8 1 2 3 4 5 6 7 8 2 3 1 1 2 4 5 6 7 8 0 0 3 4 5 6 7 8 2 3 1 1 2 4 0 0 7 8 5 6 3 4 5 6 7 8 2 3 1 1 2 4 6 3 7 8 5 0 0 4 5 6 7 8 2 3 1 1 2 4 6 3 7 8 5 5 6 4 0 0 7 8 2 3 1 1 2 0 0 3 7 8 5 5 6 4 4 6 7 8 2 3 1 1 2 4 4 3 7 8 5 5 6 0 0 6 7 8 2 3 1 1 2 4 4 3 7 8 5 5 6 6 7 0 0 8 2 3 1 1 2 4 4 3 0 0 5 5 6 6 7 7 8 8 2 3 1 1 2 0 0 3 4 4 5 5 6 6 7 7 8 8 2 3 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 0 0 状態数 977337 個 時間 2.078125 実行環境 : gcc (ver 9.4.0), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
| 種類 | ３ | ４ | ５ | ６ | ７ | ８ |
|---|---|---|---|---|---|---|
| 手数 | ３ | ７ | ５ | ７ | ８ | 11 |
時間の単位は秒です。石の種類が 8 種類になると、スタートとゴールの双方向から探索しても、生成する局面数が約 98 万個と多くなり、実行時間も約 2 秒かかりました。
ところで、石の種類と最短手数の関係ですが、どうもよくわかりません。石の種類をこれ以上増やすとなると、メモリがもっともっと必要になります。石の種類が 6, 7, 8 と増えるにしたがい、生成する局面数も爆発的に増加しているので、幅優先探索だとメモリ不足になるのは避けられません。探索方法を反復深化に切り替えた方がよいと思われます。
石の種類を増やすという単純な変形版なので、もっと簡単に答えが求まると予想していたのですが、見通しが甘かったようです（苦笑）。興味のある方は反復深化にも挑戦してください。
●プログラムリスト１
#
# oshidori.py : オシドリの遊び
#
# Copyright (C) 2022 Makoto Hiroi
#
import time
from collections import deque
# 定数
S = 0
B = 1
W = 2
def print_answer(n, buff):
if n > 0:
print_answer(buff[n][1], buff)
print(buff[n][0])
def bfs(start, goal):
queue = [(start, -1, start.index(0))]
check = [start]
rc = 0
while rc < len(queue):
b, _, s = queue[rc]
for i in range(7):
if b[i] == S or b[i + 1] == S: continue
newb = b[:]
newb[s], newb[s + 1] = newb[i], newb[i + 1]
newb[i] = newb[i + 1] = S
if newb not in check:
queue.append((newb, rc, i))
check.append(newb)
if newb == goal:
print_answer(len(queue) - 1, queue)
print(len(queue))
return
rc += 1
def solver():
bfs([B,W,B,W,B,W,S,S], [B,B,B,W,W,W,S,S])
#
# 変形版オシドリの遊び
#
def print_answer2(b, table):
prev = table[b]
if prev:
print_answer2(prev, table)
print(b)
def bfs2(start, goal):
queue = deque()
queue.append((start, start.index(0)))
check = {}
check[start] = []
while len(queue) > 0:
b, s = queue.popleft()
for i in range(len(start) - 1):
if b[i] == S or b[i + 1] == S: continue
a = list(b)
a[s], a[s + 1] = a[i], a[i + 1]
a[i] = a[i + 1] = S
newb = tuple(a)
if newb not in check:
queue.append((newb, i))
check[newb] = b
if newb == goal:
print_answer2(newb, check)
print(len(check))
return
def solver2():
for i in range(3, 8):
xs = list(range(1, i+1))
start = xs + xs + [0, 0]
goal = []
for j in range(1, i+1):
goal.append(j)
goal.append(j)
goal += [0, 0]
s = time.time()
print(f'----- {i} -----')
bfs2(tuple(start), tuple(goal))
print(time.time() - s)
●プログラムリスト２
/*
* oshidori.c : パズル「おしどり」の解法
*
* Copyright (C) 2000-2022 by Makoto Hiroi
*
*/
/*
黒白黒白黒白空空 -> 黒黒黒白白白空空
動かせる駒はペア単位である
Ｎ種類２個ずつの石で解があるか？
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define NOT_FOUND (-1)
#define MAX_SIZE 20
#define FORWARD 0
#define BACKWARD 1
#define NIL (-1)
/* 適当 */
#define MAX_STATE 0x100000
/* 連結リスト */
typedef struct {
char board[MAX_SIZE];
int next;
} CELL;
/* キュー */
CELL state[MAX_STATE];
char space_postion[MAX_STATE];
int prev_state[MAX_STATE];
char direction[MAX_STATE];
/* ハッシュ表 */
#define HASH_SIZE 19997
int hash_table[HASH_SIZE];
/* ハッシュ関数 */
int hash_value( int n, int size )
{
int i, value = 0;
for( i = 0; i < size; i++ ){
value = value * 10 + state[n].board[i];
}
return value % HASH_SIZE;
}
/* ハッシュ表への登録 */
int insert_hash( int i, int size, int board_size )
{
int h = hash_value( i, size );
int n = hash_table[h];
/* 連結リストの探索 */
while( n != NIL ){
if( memcmp( state[i].board, state[n].board, board_size ) == 0 ){
return n; /* 登録済み */
}
n = state[n].next;
}
/* 先頭に追加 */
state[i].next = hash_table[h];
hash_table[h] = i;
return NOT_FOUND;
}
/* 結果を出力 */
void print_answer_forward( int n, int size )
{
int i;
if( n > 1 ) print_answer_forward( prev_state[n], size );
for( i = 0; i < size; i++ ){
printf("%d ", state[n].board[i] );
}
printf("\n");
}
void print_answer_backward( int n, int size )
{
do {
int i;
n = prev_state[n];
for( i = 0; i < size; i++ ){
printf("%d ", state[n].board[i] );
}
printf("\n");
} while( prev_state[n] != -1 );
}
void print_answer( int i, int j, int size )
{
if( direction[i] == FORWARD ){
print_answer_forward( i, size );
print_answer_backward( j, size );
} else {
print_answer_forward( j, size );
print_answer_backward( i, size );
}
}
/* 初期化 */
void init_data( int size, int board_size )
{
int i, j, k;
/* 初期値 */
for( k = 0, i = 0; i < 2; i++ ){
for( j = 1; j <= size; j++ ){
state[0].board[k++] = j;
}
}
space_postion[0] = k;
state[0].board[k++] = 0;
state[0].board[k] = 0;
prev_state[0] = -1;
direction[0] = FORWARD;
/* ゴール */
for( k = 0, j = 1; j <= size; j++ ){
state[1].board[k++] = j;
state[1].board[k++] = j;
}
space_postion[1] = k;
state[1].board[k++] = 0;
state[1].board[k] = 0;
prev_state[1] = -1;
direction[1] = BACKWARD;
/* ハッシュ表の初期化 */
for( i = 0; i < HASH_SIZE; i++ ){
hash_table[i] = NIL;
}
insert_hash( 0, size, board_size ); /* 登録 */
insert_hash( 1, size, board_size );
}
/* 探索関数 */
void search( int size )
{
int r = 0, w = 2;
int board_size = size * 2 + 2;
/* 初期化 */
init_data( size, board_size );
printf("----- %d 種類の探索 ----- \n", size );
for( ; r < w; r++ ){
int k = space_postion[r];
int i, j;
for( i = 0; i < board_size - 1; i++ ){
if( state[r].board[i] && state[r].board[i + 1] ){
/* 盤面をコピーする */
memcpy( state[w].board, state[r].board, board_size );
state[w].board[k] = state[r].board[i];
state[w].board[k + 1] = state[r].board[i + 1];
state[w].board[i] = 0;
state[w].board[i + 1] = 0;
space_postion[w] = i;
direction[w] = direction[r];
prev_state[w] = r;
/* 検索する */
j = insert_hash( w, size, board_size );
if( j >= 0 ){
if( direction[j] != direction[w] ){
/* 解けた */
print_answer( j, w, board_size );
printf("状態数 %d 個\n", w );
return;
}
} else {
w++; /* 登録 */
if( w >= MAX_STATE ){
fprintf( stderr, "状態数オーバー\n" ); exit( 1 );
}
}
}
}
}
}
int main()
{
int i;
clock_t start, end;
for( i = 3; i <= 8; i++ ){
start = clock();
search( i );
end = clock();
printf("時間 %f\n", (double)(end - start) / CLOCKS_PER_SEC);
}
return 0;
}
改訂 2022 年 10 月 29 日