Public Pastes
Guest

Jonathan

By: a guest on Aug 30th, 2009  |  syntax: Python  |  size: 3.98 KB  |  hits: 14  |  expires: Never
download  |  raw  |  embed  |  report abuse
Copied
  1. import numpy, matplotlib, pylab
  2.  
  3. pieces = [
  4.     numpy.matrix([[1,-1,1,-1],[0,0,0,1]]),
  5.     numpy.matrix([[1,-1,1,-1],[-1,0,0,0]]),
  6.     numpy.matrix([[-1,1,0],[0,-1,0],[0,1,-1]]),
  7.     numpy.matrix([[-1,0],[1,-1],[0,1]]),
  8.     numpy.matrix([[0,-1,1],[0,1,0],[1,-1,0]]),
  9.     numpy.matrix([[-1,1,-1,1],[0,-1,0,0]]),
  10.     numpy.matrix([[1,0,0],[-1,1,-1]]),
  11.     numpy.matrix([[0,-1,0],[-1,1,-1]]),
  12.     numpy.matrix([[1,0,0],[-1,1,0],[0,-1,1]]),
  13.     numpy.matrix([[1,-1,1,0],[0,0,-1,1]]),
  14.     numpy.matrix([[1,-1,1],[-1,0,0]]),
  15.     numpy.matrix([[0,0,1,-1],[-1,1,-1,0]]),
  16.     numpy.matrix([[0,1,0,0],[1,-1,1,-1]])
  17.     ]
  18.  
  19. board = numpy.zeros([8,8], dtype=int)
  20. board[6,6]=1
  21. board[7,6]=1
  22. board[7,7]=1
  23.  
  24. positions = [(0,0) for piece in pieces] # starting positions of pieces
  25. rotations = [0 for piece in pieces] # n of counterclockwise rotations [0..3]
  26. placed = [False for piece in pieces]
  27. curpiece = 0
  28.  
  29. def placePiece(curpiece):
  30.     """Returns true if piece placed correctly, False if not valid position.
  31.    Doesn't check boundaries."""
  32.     # check inouty
  33.     piece = pieces[curpiece]
  34.     position = positions[curpiece]
  35.     for x in range(piece.shape[0]):
  36.         for y in range(piece.shape[1]):
  37.             if (piece[x,y] != 0 and
  38.                 not inouty(position[0]+x, position[1]+y) == piece[x,y]
  39.                 ):                
  40.                 return False
  41.             if piece[x,y] != 0 and board[position[0]+x, position[1]+y] == 1:
  42.                 return False
  43.     return True
  44.  
  45. def incpos(curpiece):
  46.     while True:
  47.         if rotations[curpiece] < 3:
  48.             rotations[curpiece] += 1
  49.             pieces[curpiece] = numpy.rot90(pieces[curpiece])
  50.         elif 8-positions[curpiece][1]-min(pieces[curpiece].shape)>0:
  51.             positions[curpiece] = (positions[curpiece][0], positions[curpiece][1]+1)
  52.             rotations[curpiece] = 0
  53.             pieces[curpiece] = numpy.rot90(pieces[curpiece])
  54.         elif 8-positions[curpiece][0]-min(pieces[curpiece].shape)>0:
  55.             positions[curpiece] = (positions[curpiece][0]+1, 0)
  56.             rotations[curpiece] = 0
  57.             pieces[curpiece] = numpy.rot90(pieces[curpiece])
  58.         else:
  59.             return False
  60.         # break if position valid
  61.         if (8-positions[curpiece][1]-pieces[curpiece].shape[1]>=0 and
  62.             8-positions[curpiece][0]-pieces[curpiece].shape[0]>=0):
  63.             return True
  64.  
  65. def inouty(x,y):
  66.     """+1 if male square, -1 if female square. Anomalous square hard-coded."""
  67.     return ((x+y+1)%2)*2-1
  68.  
  69. def tobin(piece, position):
  70.     n=0L
  71.     for x in range(piece.shape[0]):
  72.         for y in range(piece.shape[1]):
  73.             if piece[x,y] != 0:
  74.                 n = n | (2**((x+position[0])*8+y+position[1]))
  75.     return n
  76.  
  77. def frombin(piece, n):
  78.     mat = numpy.zeros([8,8],int)
  79.     for s in range(8**2):
  80.         if n & 2**s:
  81.             mat[s // 8, s % 8] = piece+1
  82.     return mat
  83.  
  84. allpositions = []
  85. for i in range(len(pieces)):
  86.     if placePiece(i):
  87.         allpositions.append((i, tobin(pieces[i], positions[i])))
  88.     while incpos(i):
  89.         if placePiece(i):
  90.             allpositions.append((i, tobin(pieces[i], positions[i])))
  91.  
  92. fixedpiece = tobin(board, (0,0))
  93.  
  94. def findSolution(boardstate, usedpieces, remainingpieces, uptosquare):
  95.     if len(remainingpieces) == 0:
  96.         return usedpieces
  97.     if boardstate & 2**uptosquare:
  98.         return findSolution(boardstate, usedpieces, remainingpieces, uptosquare + 1)
  99.     else:
  100.         for piece in remainingpieces:
  101.             if (boardstate & piece[1]) == 0 and (piece[1] & 2**uptosquare) != 0:
  102.                 result = findSolution(boardstate | piece[1], usedpieces + [piece],
  103.                                        [p for p in remainingpieces if p[0] != piece[0]], uptosquare+1)
  104.                 if result != None:
  105.                     return result
  106.         return None
  107.    
  108. solution = findSolution(fixedpiece, [], allpositions, 0)
  109. pylab.matshow(sum([frombin(*piecet) for piecet in solution]))
  110. pylab.show()
create a new version of this paste RAW Paste Data