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()