色々な立体パズルを解けるソフトksolve+を使う

ksolve+を使う機会があったので、備忘録がてら書いておきます。

ksolve+とはどんなものか

ksolve+は、動きに制限のないシンプルな立体パズルならだいたい解けるプログラムです。

  • 自力で解けないパズルをとりあえず完成させたい時
  • 手順を見つけたい時 (動かす面に制限を加える事も可能)
  • 自分で見つけた手順を短くしたい時
  • God’s Numberを知りたいとき

などに使えます。

1つの立体パズルに特化していない代わりに、そのパズルの状態や回転させた時の動きを自分で定義する必要があります。
また、特化していないので計算時間も長く、複雑なパズルだとあまり実用的ではありません。

ksolve+の動かし方

GitHubから、最新版のコードを落としてきます。
https://github.com/cubing/ksolve
にアクセスし、右下のDownload ZIPをクリック。
ダウンロードしたzipファイルを展開しておきます。
同梱されているreadme.txtを見ればだいたい使い方はわかります。
結構多機能ですが、さわりだけ紹介します。

ブラウザで動かす

展開したディレクトリ以下の、html/simple-async.htmlというファイルを使うとブラウザで動かせます。
なぜかおかしな文字が入っていて、そのままだと動かないので、simple-async.htmlを適当なテキストエディタで開き、2行目の<i/a>を</a>に直します。

2015/04/25追記:
コメントにあるように、TRDくんが修正してくれて、それが反映されたのでこの作業は不要になりました

ブラウザで開くとこんな画面です。
http://www.cubing.net/ksolve.js/ にも同じものがあるので、これを使ってもOKです。
ksolve-ss
左上に、パズルの定義と動きの定義をテキストで書きます。
予め、2×2の定義が入力されています。
右上に、解きたい状態や、短くしたい手順を書きます。
Go!を押せば、左上のパズルの定義と動きの定義を使って、右上の状態やスクランブルに対する解法を下に出力します。

よくあるパズルの定義は、展開したディレクトリ以下のpuzzlesの中に入っているのでこれをコピペすればOKです。そこにない場合は自分で書きます。左上と右上の書き方は、readme.txtに詳しく書いてありますが、予め入力されている2×2の例から類推できると思います。あとの具体例でも少し説明します。

コマンドラインで動かす

コマンドラインでも動かせます。God’s numberを計算する機能など一部の機能はコマンドラインでしか動かせないみたいです。コマンドラインで動かしたほうが速いかどうかは未検証ですが、多分そうなんじゃないでしょうか(?)。
MacやUnix系の場合、wineがインストールされていれば、

./ksolve ./puzzles/2x2x2.def ./puzzles/2x2x2.txt

で動きます。1つ目の引数にパズルと動きの定義ファイル、2つ目の引数にスクランブル状態の定義ファイルを渡します。
Windowsでもコマンドプロンプトで同じような感じでできるんじゃないでしょうか (多分)。

2015/04/25追記:
TRDくんが確認してくれました。
> ksolve.exe puzzles\2x2x2.def puzzles\2x2x2.txt
で動くそうです。

wineを入れるのは、MacでHomebrewを使っていれば、

brew install wine

で入ると思います。

使えそうなシーンと具体例

事例1. 自分で見つけた手順を短くする (ピラミンクスを例に)

そもそも、ksolve+を知ったのは、記事「ピラミンクスのコツと1-flipメソッドのさわり」を書くにあたって、説明に都合のいい事例を強引に作りたかったときです。
Twitterで「ピラミンクスのスクランブルをoptimalに変換するプログラムってある? 説明用のスクランブルを手で作ったんだけど長い。」とつぶやいたら、うえしゅうくん(@uesyuu)が教えてくれました。

ピラミンクスのコツと1-flipメソッドのさわり」のスクランブル1

U L' U B' L R B L

私がこの事例を作った時、はじめは普通にキーホールメソッドで解いた場合

U R' R' U' R U L' B U' B' U

の逆として

U' B U B' L U' R' U R U'

と作りました。
これでは、長い上にスクランブル自体がこれから説明することのネタバレになっているので好ましくありません。
ので、ksolve+で短くします。

ピラミンクスの定義ファイルは予め入っています。
展開したディレクトリ以下の、puzzles/Pyraminx.defがそれです。この中身を左上にコピペします。
下に同じものを載せておきます (クリックで展開します)。

Name Pyraminx

# def-file by Kåre Krig

# Put puzzle flat on a table, with one side facing you.
# Possible turns would then be U,L,R,B

# The pyramid shaped tops are not considered by the program.
# But should not pose a problem to anyone.

# Centers (inner three colored pieces)
# 1 U
# 2 L
# 3 R
# 4 B

# Centers orientation
# 0 solved
# 1 twisted one step clockwise
# 2 twisted one step counter clockwise

# Edges (two colored pieces)
# UL = the slot/piece touching both the U and L centers.
# 1 UL
# 2 UR
# 3 UB
# 4 LR
# 5 RB
# 6 LB

# Edges orientation
# 0 correct, 1 wrong
# Pieces 1,2,3 in the upper layer are correct if they would
# be correct after a single U-move.
# Pieces 1,2,3 in the lower layer are correct if they would be
# correct after being moved to the top layer with a clockwise
# twist.
# Pieces 4,5,6 in the lower layer are correct it the bottom
# color is the right one.
# Pieces 4,5,6 in the upper layer are correct if they would be
# correct after being moved to the bottom layer with a counter
# clockwise turn.

Set EDGES 6 2
Set CENTERS 4 3

Solved
EDGES
1 2 3 4 5 6
CENTERS
1 2 3 4
End

Move U
EDGES
2 3 1 4 5 6
CENTERS
1 2 3 4
1 0 0 0
End

Move R
EDGES
1 4 3 5 2 6
0 1 0 0 1 0
CENTERS
1 2 3 4
0 0 1 0
End

Move L
EDGES
6 2 3 1 5 4
1 0 0 1 0 0
CENTERS
1 2 3 4
0 1 0 0
End

Move B
EDGES
1 2 5 4 6 3
0 0 1 0 0 1
CENTERS
1 2 3 4
0 0 0 1
End

右上には

ScrambleAlg
U R' R' U' R U L' B U' B' U
End

と書きます。こんな感じ。
ksolve-pyr1
「Go!」を押すと計算が始まり、すぐに下のテキストボックスに

U L' U B' L R B L

が表示されます。

事例2. ある状態を解く手順を見つける (ギアキューブ トランスフォームを例に)

3D ギアキューブ トランスフォームというパズルがあります。海外ではGear Shiftと呼ばれています。

3D ギアキューブ トランスフォーム ブラック
タカラトミーアーツ (2011-11-12)
売り上げランキング: 73,438

このパズルを買ったとします。
頑張ってここまで↓
geartrans
解けたけど、ここからから先がどうしてもわからない。
こういう時、ksolve+で手順を探せます。
私の知る限り、ギアキューブトランスフォームの定義ファイルは世の中に存在しないので、まず、自分で定義ファイルを書きます。
こんな感じに書いてみました (クリックで展開します)。

Name Gear Shift

# def-file by Kentaro Nishi
# BIGCORNERS: UBR UFL DFR DBL
# SMALLCORNERS: UBL UFR DFL DBR
# Move "U" indicates pull U-face and turn small corners in U-face clockwise 72 degrees.
# Move "A" indicates turn all small corners clockwise 72 degrees.

Set BIGCORNERS 4 8
Set SMALLCORNERS 4 5

Solved
BIGCORNERS
1 2 3 4
0 0 0 0
SMALLCORNERS
1 2 3 4
0 0 0 0
End

Move U
BIGCORNERS
1 2 3 4
1 1 0 0
SMALLCORNERS
1 2 3 4
1 1 0 0
End

Move D
BIGCORNERS
1 2 3 4
0 0 1 1
SMALLCORNERS
1 2 3 4
0 0 1 1
End

Move F
BIGCORNERS
1 2 3 4
0 1 1 0
SMALLCORNERS
1 2 3 4
0 1 1 0
End

Move B
BIGCORNERS
1 2 3 4
1 0 0 1
SMALLCORNERS
1 2 3 4
1 0 0 1
End

Move R
BIGCORNERS
1 2 3 4
1 0 1 0
SMALLCORNERS
1 2 3 4
0 1 0 1
End

Move L
BIGCORNERS
1 2 3 4
0 1 0 1
SMALLCORNERS
1 2 3 4
1 0 1 0
End

Move A
BIGCORNERS
1 2 3 4
1 1 1 1
SMALLCORNERS
1 2 3 4
1 1 1 1
End

Uは、パズルをU方向に引っ張って広げ、小さいコーナーを75度(1歯分)回すことを表します。F, B, R, Lも同様です。
これに加えて、パズルを広げずに小さいコーナーを1歯分時計回りに回す動きをAとして定義しました。
ギアキューブトランスフォームには、パーツの位置合わせは存在しませんが、ksolve+の仕様上1行目に位置の動きを書き、2行目に向きの動きを書くことになっているので、全ての箇所に 1 2 3 4と書いています。
細かい書き方はzipに同梱されているreadme.txtに英語ですが書いてあります。
4×4のセンターのように、入れ替えてもよいパーツがあるときは、Solvedの定義で重複した数字を書けます。

このように適切に定義ファイルを書けば、未知のパズルも解くことができます。
これを左上に入力し、右上には状態を書きます。

先ほどの写真の例は、UFLの小さいコーナーが反時計回りに72度(1歯分)回っているので、

Scramble 1-corner
BIGCORNERS
1 2 3 4
0 0 0 0
SMALLCORNERS
1 2 3 4
0 1 0 0
End

のように書きます。
どの数字がどのパーツに該当するかはパズルの定義ファイルに合わせます。
上記の定義ファイルでは、冒頭に書いたとおり、

# BIGCORNERS: UBR UFL DFR DBL
# SMALLCORNERS: UBL UFR DFL DBR

の順で定義してあるのでこのようになるわけです。

これを右上に書いて、「Go」を押すと、解が見つかります。

R8' F8' D8

これは、右上に入力した状態を”作る”手順なので、これを逆転させて

D8' F8 R8

で解けることがわかりました。
大きいコーナーの歯数は8なので、大きな歯を1周させることをD面(時計回り)、F面(反時計回り)、R面(反時計回り)にやればコーナーを1歯分ねじれるということです。

ちなみに、triboxストア

の説明 (赤く囲った部分) にもあるように、タカラトミーの3Dギアキューブトランスフォームには、私が監修した攻略ガイドが同梱されています。
結講面白いのでぜひ買ってくださいね (売れた個数に応じて私が儲かるわけではないが)。

事例3. God’s Numberを調べる (ピラミンクスを例に)

この機能はコマンドラインで動かす時しか使えないみたいです。
2つ目の引数に、”!”とかくと、God’s Numberが計算されます。

./ksolve ./puzzles/Pyraminx.def !

とすると、

(前略)
Moves Positions
0 1
1 8
2 48
3 288
4 1728
5 9896
6 51808
7 220111
8 480467
9 166276
10 2457
11 32
Total positions: 933120
(後略)

と表示され、ピラミンクスのGod’s numberが11手であることが計算できます。

先ほどのギアキューブトランスフォームの定義でやってみたら

0 1
1 273
2 22002
3 463060
4 794664
Total positions: 1280000

となった。8^4×5^4 = 2,560,000 positionsにならないのはなんでだっけ……(?)

おわりに

ksolve+の使い方のさわりを具体例とともに紹介しました。
ピラミンクスや2×2の手順発掘や事例1のような例題作成に一番使えそうですね。
計算時間から言って複雑なパズルには使えないので、事例2のように解けないパズルを解くというのは実際上は考えにくいかもしれません。。

You may also like...

4 Responses

  1. TRD より:

    寺田です。問題は修正版をGitHubでプルリクしてマージされましたのでユーザ側で修正する必要が無くなりました。本文に追記をお願い致します。

    Windowsでコナンどラインで動かす場合、こちらもすでにバイナリが生成されていますので、
    > ksolve.exe puzzles\2x2x2.def puzzles\2x2x2.txt
    で実行可能なことを確認しました。

コメントを残す

メールアドレスが公開されることはありません。