代码: 全选
def normalize(shape):
min_r = min(r for r, c in shape)
min_c = min(c for r, c in shape)
return tuple(sorted(((r - min_r, c - min_c) for r, c in shape)))
def rotate(shape):
return [(c, -r) for r, c in shape]
def all_orientations(shape):
orientations = set()
current = shape
for _ in range(4):
current = normalize(current)
orientations.add(current)
reflected = normalize([(r, -c) for r, c in current])
orientations.add(reflected)
current = rotate(current)
return [list(orientation) for orientation in orientations]
pieces = {
'F': [(0,1), (1,0), (1,1), (1,2), (2,2)],
'I': [(0,0), (1,0), (2,0), (3,0), (4,0)],
'L': [(0,0), (1,0), (2,0), (3,0), (3,1)],
'N': [(0,1), (1,1), (2,1), (2,0), (3,0)],
'P': [(0,0), (0,1), (1,0), (1,1), (2,0)],
'T': [(0,0), (0,1), (0,2), (1,1), (2,1)],
'U': [(0,0), (0,2), (1,0), (1,1), (1,2)],
'V': [(0,0), (1,0), (2,0), (2,1), (2,2)],
#'W': [(0,0), (1,0), (1,1), (2,1), (2,2)],
'W': [(0,0), (1,0), (1,1), (1,2), (2,2)],
'X': [(0,1), (1,0), (1,1), (1,2), (2,1)],
'Y': [(0,1), (1,1), (2,1), (3,1), (2,0)],
'Z': [(0,0), (0,1), (1,1), (1,2), (2,2)]
}
piece_orientations = {letter: all_orientations(shape) for letter, shape in pieces.items()}
BOARD_ROWS = 6
BOARD_COLS = 10
def print_board(board):
for row in board:
print(''.join(row))
print()
def find_next_empty(board):
for r in range(BOARD_ROWS):
for c in range(BOARD_COLS):
if board[r][c] == '.':
return r, c
return None, None
def can_place(board, shape, top, left):
positions = []
for dr, dc in shape:
r, c = top + dr, left + dc
if r < 0 or r >= BOARD_ROWS or c < 0 or c >= BOARD_COLS:
return None
if board[r][c] != '.':
return None
positions.append((r, c))
return positions
def solve(board, remaining, solutions):
pos = find_next_empty(board)
if pos == (None, None):
solutions.append([row[:] for row in board])
return True
r, c = pos
for letter in list(remaining):
for orientation in piece_orientations[letter]:
for (dr, dc) in orientation:
top = r - dr
left = c - dc
positions = can_place(board, orientation, top, left)
if positions is not None:
for pr, pc in positions:
board[pr][pc] = letter
remaining.remove(letter)
if solve(board, remaining, solutions):
return True
remaining.add(letter)
for pr, pc in positions:
board[pr][pc] = '.'
return False
def main():
board = [['.' for _ in range(BOARD_COLS)] for _ in range(BOARD_ROWS)]
remaining = set(pieces.keys())
solutions = []
if solve(board, remaining, solutions):
print("found")
print_board(solutions[0])
else:
print("not found")
if __name__ == '__main__':
main()