pythonでソーマキューブを解いてみた

## もくじ

1. はじめに
2. ソーマキューブとは
3. 過去の話
4. 工夫した点 処理速度向上のために
5. 苦労した点 成功しているか判定するために
6. アルゴリズムとソースコードについて
7. 最後に


## はじめに

pythonでソーマキューブを解いてみました。
結果、480通りの立方体の作成パターンを解くことができました。
たかがパズルされどパズル、実装する段階でいろいろな事を学ぶことができました。
その時のノウハウを記事に残しておきます。
この記事が誰かのお役に立てば幸いです。

[ソースコードはこちら](https://gitlab.com/RyutaKaii/somacube)


## ソーマキューブとは

ソーマキューブとは7つの立体パズルを組み合わせて立方体を作る立体パズル。
詳細は下記を参照してください。

[ソーマキューブ](https://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%9E%E3%82%AD%E3%83%A5%E3%83%BC%E3%83%96)

立方体以外にも様々な立体図形を作成することができますが、今回は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)
```


## 最後に

今回はソーマキューブを解いてみました。
実装する段階でいろいろな事を学ぶことができ、勉強になりました。
一番の収穫はやっぱりすごく楽しかったことですね。

この記事が誰かのお役に立てば幸いです。