# based god Donald Knuth
# http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz
# sám bych to asi nevymyslel
class Cell:
def __init__(self,left=None,right=None,up=None,down=None,col=None):
self.left=left
self.right=right
self.up=up
self.down=down
self.col=col
class Column(Cell):
def __init__(self,name,*args,**kwargs):
super().__init__(*args,**kwargs)
super().__init__(*args,up=self,down=self,**kwargs)
self.name=name
self.size=0
def cover(self):
self.right.left=self.left
self.left.right=self.right
r=self.down
while r is not self:
c=r.right
while c is not r:
c.down.up=c.up
c.up.down=c.down
c.col.size-=1
c=c.right
r=r.down
def uncover(self):
r=self.up
c=r.left
c.col.size+=1
c.down.up=c
c.up.down=c
c=c.left
r=r.up
self.right.left=self
self.left.right=self
class Header:
def __init__(self,left=None,right=None):
class Header(Column):
def __init__(self):
super().__init__("head")
self.left=self
self.right=self
self._res=[]
def search(self,k=0):
if self.right is self:
self.print()
return True
if len(self._res)<=k:
self._res.append(None)
col=self.chooseCol()
col.cover()
row=col.down
while row is not col:
row=row.down
self._res[k]=row
c=row.right
while c is not row:
c.col.cover()
self.search(k+1)
c=row.left
c.col.uncover()
@@ -51,40 +51,24 @@ def listRotations(obj):
return res
def listShifts(board,obj):
return [
(dz,dy,dx)
for dz in range(board.shape[0]-obj.shape[0]+1)
for dy in range(board.shape[1]-obj.shape[1]+1)
for dx in range(board.shape[2]-obj.shape[2]+1)
]
def fits(board,piece,shift):
(dz,dy,dx)=shift
res=[]
for (z,plane) in enumerate(piece):
for (y,row) in enumerate(plane):
for (x,item) in enumerate(row):
if item==0: continue
coords=(z+dz,y+dy,x+dx)
if board[coords]: return False
res.append(coords)
if __name__=="__main__":
board=np.zeros((1,2,3))
boat=np.array([[[0,1,0],[1,1,1]]])
es=np.array([[[1,1,0],[0,1,1]]])
el=np.array([[[1,1,1],[1,0,0]]])
pieces={"boat":boat}
for (name,piece) in pieces.items():
for p in listRotations(piece):
for shift in listShifts(board,p):
fit=fits(board,p,shift)
if fit is not False:
print(fit)
EMPTY="."
FULL="O"
import numpy as np
class Piece:
def __init__(self,variants):
self.variants=variants
from pieces import listRotations,listShifts,fits
from dlx import Header,Column,Cell
pieceSet=dict()
pieceSet["sq"]=Piece([
# OO
((0,0),(0,1),(1,0),(1,1))
])
board=np.zeros((1,4,3))
sz=np.array([[[1,1,0],[0,1,1]]])
pieceSet["long"]=Piece([
# OOOO
((0,0),(0,1),(0,2),(0,3)),
((0,0),(1,0),(2,0),(3,0))
pieceSet["boat"]=Piece([
# OOO
# .O.
((0,0),(0,1),(0,2),(1,1)),
((0,0),(1,0),(2,0),(1,1)),
((0,0),(1,-1),(1,0),(1,1)),
((0,0),(1,-1),(1,0),(2,0))
(nz,ny,nx)=board.shape
pieces=[("el1",el),("el2",el),("sz",sz)]
header=[name for (name,p) in pieces]+\
[(z,y,x) for z in range(nz) for y in range(ny) for x in range(nx) if not board[z][y][x]]
index={label:i for (i,label) in enumerate(header)}
pieceSet["sz"]=Piece([
# .OO
# OO.
((0,0),(0,1),(1,-1),(1,0)),
((0,0),(1,0),(1,1),(2,1)),
((0,0),(0,1),(1,1),(1,2)),
((0,0),(1,0),(1,-1),(2,-1))
matrix=[]
pieceSet["el"]=Piece([
# O..
((0,0),(1,0),(0,1),(0,2)),
((0,0),(1,0),(2,0),(2,1)),
((0,0),(1,-2),(1,-1),(1,0)),
((0,0),(0,1),(1,1),(2,1)),
# ..O
((0,0),(0,1),(0,2),(1,2)),
((0,0),(0,1),(1,0),(2,0)),
((0,0),(1,0),(1,1),(1,2)),
((0,0),(1,0),(2,0),(2,-1))
WIDTH=8
HEIGHT=5
board=[[EMPTY]*WIDTH for r in range(HEIGHT)]
for (name,piece) in pieces:
row=[0]*len(header)
row[index[name]]=1
for coords in fit: row[index[coords]]=1
matrix.append(row)
def fill(board,pieces):
point=firstEmpty(board)
if not point: return True
for (i,(k,p)) in enumerate(pieces):
if k==0: continue
for v in p.variants:
if place(board,point,v):
pieces[i][0]-=1
partialRes=fill(board,pieces)
if partialRes:
res.append(((point,v), partialRes))
remove(board,point,v)
pieces[i][0]+=1
# print(header)
# for row in matrix: print(row)
def firstEmpty(board):
for (r,row) in enumerate(board):
for (c,cell) in enumerate(row):
if cell==EMPTY:
return (r,c)
return None
columns=[]
head=Header()
for label in header:
c=Column(label)
head.left.right=c
c.left=head.left
head.left=c
c.right=head
columns.append(c)
def place(board,point,piece):
(r,c)=point
if not all(0<=r+ri<HEIGHT and 0<=c+ci<WIDTH and board[r+ri][c+ci]==EMPTY for (ri,ci) in piece):
return False
for (ri,ci) in piece:
board[r+ri][c+ci]=FULL
def remove(board,point,piece):
board[r+ri][c+ci]=EMPTY
for row in matrix:
cells=[]
for (item,col) in zip(row,columns):
if item!=1: continue
c=Cell(up=col.up,down=col,col=col)
col.up.down=c
col.up=c
cells.append(c)
c.right=cells[0]
c.left=cells[0].left
c.left.right=c
c.right.left=c
def visualise(board,tree,letter="A"):
if tree is True:
for row in board:
print("".join(row))
print()
return
for (((r,c),piece),rest) in tree:
board[r+ri][c+ci]=letter
visualise(board,rest,chr(ord(letter)+1))
res=fill(board,[[k,pieceSet[x]] for (k,x) in [(2,"sq"),(2,"el"),(2,"boat"),(2,"long"),(2,"sz")]])
if res:
visualise(board,res)
else:
print(res)
head.search()
Status change: