もくじ
- はじめに
- ソーマキューブとは
- 過去の話
- 工夫した点 処理速度向上のために
- 苦労した点 成功しているか判定するために
- アルゴリズムとソースコードについて
- 最後に
はじめに
pythonでソーマキューブを解いてみました。
結果、480通りの立方体の作成パターンを解くことができました。
たかがパズルされどパズル、実装する段階でいろいろな事を学ぶことができました。
その時のノウハウを記事に残しておきます。
この記事が誰かのお役に立てば幸いです。
ソーマキューブとは
ソーマキューブとは7つの立体パズルを組み合わせて立方体を作る立体パズル。
詳細は下記を参照してください。
立方体以外にも様々な立体図形を作成することができますが、今回は3×3の立方体を完成形としました。
当たり前ですが、立方体は回転させても見た目は変わりません。
6方向分回転させることができるので、この6パターンは1パターンとしてカウントします。
過去の話
実はプログラムでソーマキューブを解くのは今回が初めてではありません。
1回目はプログラミングの「いろは」もわかっていない学生の時で、今から約13年前。
その時は先生にプログラミングのやり方を教えてもらいつつ、解説もアリで
数か月かけて実施した記憶があります。最終的には解くことができましたが、処理時間が2時間ぐらい
かかったかと思います。
正直しっかりと理解していたか疑問です。
2回目は1年前ぐらい。これは途中で飽きてやめちゃいました。
工夫した点 処理速度向上のために
前述した通り、過去に処理時間について悩まされた記憶があったため、今回は処理速度について
いつも以上に気にしました。
listでなくsetを利用
pythonにもjavaのようなsetがあります。
listと比較するとかなり早いです。(その分、順序の保証はありません)
今回はピースのオブジェクトを途中までlistで扱い、途中からはsetで扱いました。
# ==================================================
# CUBE
# ==================================================
class Cube:
def __init__(self, label, pList):
# label
self.label = label
# pieseList
self.pList = pList
# ==================================================
# COORDINATE
# ==================================================
class XYZ:
def __init__(self, x, y, z):
# x
self.x = x
# y
self.y = y
# z
self.z = z
# ==================================================
# Cube for calc
# ==================================================
class Cube4Calc:
def __init__(self, label, pList):
# label
self.label = label
# piese list sets
self.pList = set(pList)
# ==================================================
# convertToCalcCube
# ==================================================
def convToCalcCube(cube):
calcCube = cc.Cube4Calc(cube.label, [])
for p in cube.pList:
calcCube.pList.add(convPToPIdx(p))
return calcCube
# ==================================================
# convertPieseToPieseIndex
# ==================================================
def convPToPIdx(p):
return p.x + (p.z * 3) + (p.y * 9)
for文の途中で枝切り
7つ全てのピースの全ての組み合わせを試すと、途方もない量の処理が必要です。
1つめから順番に組み合わせを試し、NGであれば以降の処理を行わないように記述しました。
※再帰処理で記述するのが綺麗ですが、分かりやすさのために不細工なfor文になっています。
# ==================================================
# getResolveCubeList
# ==================================================
def getResolveCubeList(cube4CalcLList, cube4CalcZList, cube4CalcTList, cube4CalcAList, cube4CalcBList, cube4CalcPList, cube4CalcVList):
resolveCubeList = []
for cube4CalcL in cube4CalcLList:
for cube4CalcZ in cube4CalcZList:
sumCube4Calc_LZ = createSumCube4Calc(cube4CalcL, cube4CalcZ, 8)
if not sumCube4Calc_LZ is None:
for cube4CalcT in cube4CalcTList:
sumCube4Calc_LZT = createSumCube4Calc(sumCube4Calc_LZ, cube4CalcT, 12)
if not sumCube4Calc_LZT is None:
for cube4CalcA in cube4CalcAList:
sumCube4Calc_LZTA = createSumCube4Calc(sumCube4Calc_LZT, cube4CalcA, 16)
if not sumCube4Calc_LZTA is None:
for cube4CalcB in cube4CalcBList:
sumCube4Calc_LZTAB = createSumCube4Calc(sumCube4Calc_LZTA, cube4CalcB, 20)
if not sumCube4Calc_LZTAB is None:
for cube4CalcP in cube4CalcPList:
sumCube4Calc_LZTABP = createSumCube4Calc(sumCube4Calc_LZTAB, cube4CalcP, 24)
if not sumCube4Calc_LZTABP is None:
for cube4CalcV in cube4CalcVList:
sumCube4Calc_LZTABPV = createSumCube4Calc(sumCube4Calc_LZTABP, cube4CalcV, 27)
if not sumCube4Calc_LZTABPV is None:
resolveCubeList.append(sumCube4Calc_LZTABPV)
return resolveCubeList
# ==================================================
# createSumCube4Calc
# ==================================================
def createSumCube4Calc(cube4Calc_1, cube4Calc_2, length):
sumPList = cube4Calc_1.pList | cube4Calc_2.pList
if len(sumPList) == length:
# print(">>> END createSumCube4Calc")
return cc.Cube4Calc(cube4Calc_1.label + cube4Calc_2.label, sumPList)
return None
苦労した点 成功しているか判定するために
例えばパズルを回転させたとき、自分の想定した通りに回転しているかはxyz座標の表示だけでは分かりにくいです。
アスキーアート風にピースを画像表示するメソッドを用意し、メソッド単位の試験を行う際にこれを利用しました。
※メソッド単位でそのメソッドがうまく動いているか試験を行い、その積み重ねでプログラム全体が完成します。
こんな基本的なことを軽視してしまい、無駄に時間を浪費してしまいました。
遠回りに思えても、上記のプロセスは省略できないことを身をもって実感しました。
# ==================================================
# printGraphicCube
# ==================================================
def printGraphicCube(cube):
# create 2*2 list
graphic = [[0] * 23 for i in range(27)]
for idxZ in range(0, 3)[::-1]:
for p in cube.pList:
if p.z == idxZ:
printGraphicPiese(p.x, p.y, p.z, graphic)
for y in range(23)[::-1]:
rowStr = ""
for x in range(27):
rowStr = rowStr + str(graphic[x][y])
print(rowStr)
# ==================================================
# printGraphicPiese
# ==================================================
def printGraphicPiese(x, y, z, graphic):
baseX = x * 5 + z * 2
baseY = y * 3 + z * 2
printRow(graphic, baseX, baseY + 5, 2, "+----+")
printRow(graphic, baseX, baseY + 4, 1, "/ /|")
printRow(graphic, baseX, baseY + 3, 0, "+----+ |")
printRow(graphic, baseX, baseY + 2, 0, "| | /")
printRow(graphic, baseX, baseY + 1, 0, "| |/")
printRow(graphic, baseX, baseY + 0, 0, "+----+")
# ==================================================
# printRow
# ==================================================
def printRow(graphic, x, y, shiftX, graphicStr):
startX = x + shiftX
graphicStrList = list(graphicStr)
cntStr = 0
for posX in range(startX, startX + len(graphicStr)):
graphic[posX][y] = graphicStrList[cntStr]
cntStr = cntStr + 1
アルゴリズムとソースコードについて
メイン処理のポイントを簡単に解説させてください。
# ==================================================
# resolve
# ==================================================
def resolve():
calc4CubeListList = []
for idxC in range(7):
cube = cubeCreater.createBasicCube(idxC)
calc4CubeList = []
# lotationLength = vectol * latation = 6 * 4 = 24
lengthL = 24
# fix pattern first cube (1)
if idxC == 0:
lengthL = 1
for idxL in range(lengthL):
cloneC = copy.deepcopy(cube)
cubeRotationer.lotation(cloneC, idxL)
notOverCubeList = cubeSetter.createNotOverCubeList(cloneC) (2)
for notOverCube in notOverCubeList:
calc4Cube = cubeExchanger.convToCalcCube(notOverCube) (3)
calc4CubeList.append(calc4Cube)
pNum = 4
# only cubeV's pieseNum is 3
if idxC == 6:
pNum = 3
calc4CubeList = cubeExchanger.removeDupCubes(calc4CubeList, pNum) (4)
calc4CubeListList.append(calc4CubeList)
resolveCubeList = cubeResolver.getResolveCubeList(calc4CubeListList[0], calc4CubeListList[1], calc4CubeListList[2], calc4CubeListList[3], calc4CubeListList[4], calc4CubeListList[5], calc4CubeListList[6])
print("finish. ptn = " + str(len(resolveCubeList)))
(1) 6方向分を1パターンとしてカウントするため"L型"キューブの回転を1パターンに固定
if idxC == 0:
lengthL = 1
(2) 回転させたキューブをx,y,z座標について0～3で平行移動させはみ出していないものを取得
notOverCubeList = cubeSetter.createNotOverCubeList(cloneC)
(3) 処理速度向上のために計算用キューブに変換
calc4Cube = cubeExchanger.convToCalcCube(notOverCube)
(4) 重複しているキューブを取り除く
calc4CubeList = cubeExchanger.removeDupCubes(calc4CubeList, pNum)
最後に
今回はソーマキューブを解いてみました。
実装する段階でいろいろな事を学ぶことができ、勉強になりました。
一番の収穫はやっぱりすごく楽しかったことですね。
この記事が誰かのお役に立てば幸いです。