Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@chuntaweb(chuntaweb)

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

Posted at

もくじ

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

はじめに

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)

最後に

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

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

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?