Exit Full View

Wooden Block Solver.txt

import copy

class Container :

	def __init__( self, width, height, length ) :
		self.width = width
		self.height = height
		self.length = length

		self.voxels = []
		for x in range( 0, width ) :
			flat = []
			for y in range( 0, height ) :
				row = []
				for z in range( 0, length ) :
					row.append( 0 )
				flat.append( row )
			self.voxels.append( flat )
		

	def __str__( self ) :
		result = "";
		for z in range( 0, self.length ) :
			for x in range( 0, self.width ) :
				for y in range( 0, self.height ) :
					result += str(self.voxels[x][y][z])
					result += " "
				result += "\n"
			result += "\n"
		return result

	def is_empty( self, x, y, z ) :
		if not self.is_inside( x, y, z ) :
			return False
		return self.voxels[x][y][z] == 0

	def is_inside( self, x, y, z ) :
		if x < 0 or y < 0 or z < 0 :
			return False

		if x >= self.width or y >= self.height or z >= self.length :
			return False

		return True

	def add_piece( self, geometry, dx, dy, dz, value ) :

		if self.fits( geometry, dx, dy, dz ) :
			for (x,y,z) in geometry :
				self.set( x + dx, y + dy, z + dz, value )

	def fits( self, geometry, dx, dy, dz ) :
		for (x,y,z) in geometry :
			if not self.is_empty( x + dx, y + dy, z + dz ) :
				return False
		return True

	def remove_piece( self, geometry, dx, dy, dz ) :

		for (x,y,z) in geometry :
			self.set( x + dx, y + dy, z + dz, 0 )

	def set( self, x, y, z, value ) :
		self.voxels[x][y][z] = value

class Piece :

	def __init__( self, value, geometry ) :
		self.value = value
		self.geometry = geometry
		self.normalise( geometry )
		self.calc_rotations()

	def add_voxel( self, x, y, z ) :
		self.geometry.append( (x, y, z ) )
		return self
	
	def calc_rotations( self ) :
		self.rotations = []

		rot = self.geometry

		self.add_rotation( rot )

		for x in range( 1, 3 ) :
			rot = self.transform( rot, rotateA )
			self.add_rotation( rot )

		for rot in self.rotations :
			for x in range( 1, 3 ) :
				rot = self.transform( rot, rotateB )
				self.add_rotation( rot )

		for rot in self.rotations :
			for x in range( 1, 3 ) :
				rot = self.transform( rot, rotateC )
				self.add_rotation( rot )

	def add_rotation( self, geometry ) :

		if not self.contains( geometry ) :
			self.rotations.append( geometry )

	def contains( self, geometry ) :
		for geo in self.rotations :

			if geo == geometry :
				return True
		return False

	def normalise( self, geometry ) :
		min_x = min_y = min_z = 1000000

		for (x, y, z) in geometry :
			if ( x < min_x ) : min_x = x
			if ( y < min_y ) : min_y = y
			if ( z < min_z ) : min_z = z

		for a in range( 0, len( geometry ) ) :
			geometry[ a ] = ( geometry[a][0]- min_x, geometry[a][1]- min_y, geometry[a][2]- min_z )

		sorted( geometry, key=lambda xyz: xyz[0] + xyz[1] * 100 + xyz[2] * 10000 )

	def transform( self, geometry, matrix ) :
	
		result = []

		for (x,y,z) in geometry :
			nx = matrix[0][0] * x + matrix[1][0] * y + matrix[2][0] * z
			ny = matrix[0][1] * x + matrix[1][1] * y + matrix[2][1] * z
			nz = matrix[0][2] * x + matrix[1][2] * y + matrix[2][2] * z
			result.append( (nx, ny, nz) )

		self.normalise( result )	
		return result


rotateA = [[1,0,0],[0,0,-1],[0,1,0]]
rotateB = [[0,0,1],[0,1,0],[-1,0,0]]
rotateC = [[0,-1,0],[1,0,0],[0,0,1]]

class Solver :

	def __init__( self, container, pieces ) :
		self.container = container
		self.pieces = pieces

	def solve( self ) :
		self.solutions = []
		self.solve_it( self.pieces, False )

	def solve_it( self, pieces, rotate ) :

		if len( pieces ) == 0 :
			for solution in self.solutions :
				if solution == self.container.voxels :
					return
			print "Solution\n\n"
			print self.container
			self.solutions.append( copy.deepcopy( self.container.voxels ) )
			return

		piece = pieces[0]

		if rotate :
			rotations = piece.rotations
		else :
			rotations = [piece.rotations[0]]

		for geometry in rotations :
			for dx in range( 0, self.container.width ) :
				for dy in range( 0, self.container.height ) :
					for dz in range( 0, self.container.length ) :
					
						if self.container.fits( geometry, dx, dy, dz ) :
							self.container.add_piece( geometry, dx, dy, dz, piece.value )
							self.solve_it( pieces[1:], True )
							self.container.remove_piece( geometry, dx, dy, dz )


container = Container( 3,3,3 )

piece1 = Piece( 1, [ ( 0,0,0 ),( 1,0,0 ),( 2,0,0 ),( 0,1,0 ) ] )
piece2 = Piece( 2, [ ( 0,0,0 ),( 1,0,0 ),( 1,0,1 ),( 0,1,0 ) ] )
piece3 = Piece( 2, [ ( 0,0,0 ),( 1,0,0 ),( 1,0,1 ),( 0,1,0 ) ] ) # Same as 2
piece4 = Piece( 4, [ ( 0,0,0 ),( 1,0,0 ),( 0,1,0 ),( 1,1,0 ),( 0,0,1 ) ] )
piece5 = Piece( 5, [ ( 0,0,0 ),( 1,0,0 ),( 1,0,1 ),( 1,0,2 ),( 0,1,0 ) ] )
piece5m= Piece( 5, [ ( 0,0,0 ),( 0,0,1 ),( 0,0,2 ),( 1,0,0 ),( 1,1,0 ) ] )
piece6 = Piece( 6, [ ( 1,0,0 ),( 2,0,0 ),( 1,1,0 ),( 1,1,1 ),( 0,1,1 ) ] )

solver = Solver( container, [ piece5m, piece6, piece4, piece3, piece2, piece1 ] )
result = solver.solve()