J'ai essayé de résoudre Soma Cube avec python

Mokuji

1.Tout d'abord 2. Qu'est-ce que Soma Cube? 3. Histoire passée 4. Ingéniosité pour améliorer la vitesse de traitement 5. Difficultés à déterminer le succès 6. À propos de l'algorithme et du code source 7. Enfin

introduction

J'ai essayé de résoudre le Soma Cube avec python. En conséquence, nous avons pu résoudre 480 modèles de création de cubes différents. Même s'il s'agissait d'un puzzle, j'ai pu apprendre diverses choses au stade de la mise en œuvre du puzzle. Je laisserai le savoir-faire à ce moment-là dans l'article. J'espère que cet article aide quelqu'un.

Cliquez ici pour le code source

Qu'est-ce que Soma Cube?

Soma Cube est un puzzle en trois dimensions qui combine sept puzzles en trois dimensions pour créer un cube. Voir ci-dessous pour plus de détails.

[Soma Cube](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)

Vous pouvez créer différentes figures 3D autres que le cube, mais cette fois nous avons fait du cube 3x3 le formulaire complété. De toute évidence, l'apparence du cube ne change pas même s'il est tourné. Puisqu'il peut être tourné dans 6 directions, ces 6 motifs sont comptés comme 1 motif.

Histoire passée

En fait, ce n'est pas la première fois que vous résolvez le Soma Cube par programmation. La première fois, c'était quand j'étais un étudiant qui ne connaissait même pas «l'Iroha» de la programmation, il y a environ 13 ans. À ce moment-là, tout en demandant au professeur de m'apprendre à programmer, l'explication est aussi Je me souviens de l'avoir fait pendant plusieurs mois. J'ai pu le résoudre à la fin, mais le temps de traitement était d'environ 2 heures Je pense que ça a pris. Je me demande si je l'ai vraiment compris. La deuxième fois, c'était il y a environ un an. J'en ai eu assez de ça en chemin et j'ai arrêté.

Ingéniosité pour améliorer la vitesse de traitement

Comme mentionné ci-dessus, je me souviens avoir eu des problèmes avec le temps de traitement dans le passé, donc cette fois à propos de la vitesse de traitement J'étais plus inquiète que d'habitude.

Utiliser ensemble au lieu de liste

python a également un ensemble de type java. C'est beaucoup plus rapide que la liste. (Il n'y a aucune garantie de la commande) Cette fois, l'objet pièce a été traité comme une liste à mi-chemin et comme un ensemble à partir du milieu.

# ==================================================
# 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)

Taille au milieu de la déclaration for

Essayer toutes les combinaisons des sept pièces nécessite une quantité considérable de traitement. J'ai essayé les combinaisons dans l'ordre de la première, et si c'était NG, j'ai écrit que le traitement ultérieur ne serait pas effectué.

• C'est beau à décrire par un traitement récursif, mais c'est une déclaration maladroite par souci de clarté.

# ==================================================
# 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

Difficultés à déterminer le succès

Par exemple, lorsque vous faites pivoter un puzzle, il est difficile de savoir s'il tourne comme prévu en affichant simplement les coordonnées xyz. Nous avons préparé une méthode pour afficher des pièces sous forme d'image dans un style artistique ASCII et l'avons utilisée lors de la réalisation de tests basés sur des méthodes.

• Testez si la méthode fonctionne bien pour chaque méthode, et tout le programme est complété en les accumulant. J'ai négligé une chose aussi fondamentale et j'ai perdu mon temps. Même si cela semble être un détour, j'ai réalisé que le processus ci-dessus ne peut être omis.

# ==================================================
# 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

À propos de l'algorithme et du code source

Permettez-moi d'expliquer brièvement les points du traitement principal.

# ==================================================
# 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) La rotation du cube "en forme de L" est fixée à un motif car six directions sont comptées comme un motif.

if idxC == 0:
	lengthL = 1

(2) Déplacez le cube pivoté en parallèle de 0 à 3 par rapport aux coordonnées x, y, z pour obtenir celle qui ne dépasse pas.

notOverCubeList = cubeSetter.createNotOverCubeList(cloneC)

(3) Conversion en cube de calcul pour améliorer la vitesse de traitement

calc4Cube = cubeExchanger.convToCalcCube(notOverCube)

(4) Retirez les cubes qui se chevauchent

calc4CubeList = cubeExchanger.removeDupCubes(calc4CubeList, pNum)

finalement

Cette fois, j'ai essayé de résoudre le Soma Cube. J'ai pu apprendre diverses choses au stade de la mise en œuvre, ce qui a été une expérience d'apprentissage. Après tout, la meilleure récolte a été très amusante.

J'espère que cet article aide quelqu'un.