#!/usr/bin/env python3 #-*- coding: utf-8 -*- from operator import add import itertools, my_utils import SAT_lib import pprint """ 3 modes any poly can be reused, but not all must be used. IOW, each poly is used any number of times. mode="x" each poly used exactly once. IOW, each poly is used only 1 times. mode="1" each poly can be used only once, but not all must be used. IOW, each poly is used 0 or 1 times. mode="01" """ domino=[ ["*", "*"]] # https://en.wikipedia.org/wiki/Tromino triominos=[ ["***"], ["* ", "**"]] pentominos=[ [" **", # F "** ", " * "], ["***", # P "** "], ["*****"], # I ["** ", # N " ***"], ["****", # L " *"], ["***", # T " * ", " * "], ["* *", # U "***"], ["* ", # V "* ", "***"], ["* ", # W "** ", " **"], [" * ", # X "***", " * "], [" * ", # Y "****"], ["** ", # Z " * ", " **"]] """ # must be 520 solutions # https://garethrees.org/2015/11/09/exact-cover/ board=[ "********", "********", "********", "*** ***", "*** ***", "********", "********", "********"] tiles=pentominos mode="1" """ # https://en.wikipedia.org/wiki/Mutilated_chessboard_problem mutilated_chess_board=[ " *******", "********", "********", "********", "********", "********", "********", "******* "] #board=mutilated_chess_board #tiles=domino #mode="x" def gen_board(rows, cols): rt=[] for r in range(rows): rt.append ("*"*cols) return rt # must be 36 # https://en.wikipedia.org/wiki/Domino_tiling #board=gen_board(4, 4) #tiles=domino #mode="x" # must be 6728 # https://en.wikipedia.org/wiki/Domino_tiling #board=gen_board(6, 6) #tiles=domino #mode="x" # https://projecteuler.net/problem=161 # must be 41 #board=gen_board(2, 9) #tiles=triominos #mode="x" # https://oeis.org/A215826 # must be 3127 #board=gen_board(3, 9) #tiles=triominos #mode="x" # must be 27950 # https://oeis.org/A174249 board=gen_board(3, 5) tiles=pentominos mode="01" board_height=len(board) board_width=len(board[0]) TILES_TOTAL=len(tiles) def get_board_squares_total(): rt=0 for row in board: for col in row: if col=='*': rt=rt+1 return rt board_number_of_each_coord={} def board_gen_number_for_all_coords(): n=0 for row_i, row in enumerate(board): for col_i, col in enumerate(row): if col=='*': board_number_of_each_coord[(row_i,col_i)]=n n=n+1 def board_coord_to_square_number(coord): if len(board_number_of_each_coord)==0: board_gen_number_for_all_coords() return board_number_of_each_coord[coord] def lists_has_adjacent_cells(l1, l2): # enumerate all possible combinations of items from two lists: return any([my_utils.adjacent_coords(q[0][0], q[0][1], q[1][0], q[1][1]) for q in itertools.product(l1, l2)]) def can_be_placed(into, irow, icol, tile): rt=[] tile_height=len(tile) tile_width=len(tile[0]) for prow in range(tile_height): for pcol in range(tile_width): if tile[prow][pcol]=='*': # tile cannot be placed if there is a hole on board: if into[irow+prow][icol+pcol]==' ': return None if into[irow+prow][icol+pcol]=='*': rt.append((irow+prow, icol+pcol)) return rt # enumerate all positions on board and try to put tile there: def find_all_placements(_type, tile): tile_height=len(tile) tile_width=len(tile[0]) rt=[] for row in range(board_height-tile_height+1): for col in range(board_width-tile_width+1): tmp=can_be_placed(board, row, col, tile) if tmp!=None: rt.append((_type, tmp)) # rt is a list of tuples, each has tile type and list of coordinates, like: #(0, [(0, 1), (1, 1), (1, 2), (2, 1)]), #(0, [(0, 2), (1, 2), (1, 3), (2, 2)]), #... #(1, [(0, 1), (0, 2), (1, 1), (1, 2), (2, 1)]), #(1, [(0, 2), (0, 3), (1, 2), (1, 3), (2, 2)]) return rt def str_to_list_of_chars(lst): return [l for l in lst] def find_all_placements_with_rotations(poly_type, tile): # we operate here with tiles encoded as list of lists of chars tile=[str_to_list_of_chars(tmp) for tmp in tile] # rotate tile in 4 ways. # also, mirror it horizontally # that gives us 8 versions of each tile # remove duplicates duplicates=[] rt=[] for a in range(4): t1=my_utils.rotate_rect_array(tile, a) if t1 not in duplicates: duplicates.append(t1) rt=rt+find_all_placements(poly_type, t1) t2=my_utils.reflect_horizontally(my_utils.rotate_rect_array(tile, a)) if t2 not in duplicates: duplicates.append(t2) rt=rt+find_all_placements(poly_type, t2) return rt # input: list of tiles, like: # [(0, [(2, 1), (3, 0), (3, 1), (3, 2)]), # (1, [(0, 1), (0, 2), (0, 3), (1, 1), (1, 2)]), # (2, [(1, 3), (2, 2), (2, 3)]), # (3, [(1, 0), (2, 0)])] # each tuple has tile type + list of coordinates on board # output: color for each tile, like: [2, 0, 1, 3] def color_tiles(solution): # make a graph G=[] # enumerate all possible pair of tiles: for pair_l in range(len(solution)): for pair_r in range(len(solution)): if pair_l==pair_r: continue if lists_has_adjacent_cells(solution[pair_l][1], solution[pair_r][1]): # add constraint, if tiles adjacent to each other. # it's not a problem to add the same constraint multiple times. G.append((pair_l, pair_r)) #print (G) # this is planar graph anyway, 4 colors enough: return SAT_lib.find_2_coloring_of_graph (G, total=len(solution)) _09=list(map(chr, range(ord('0'), ord('9')+1))) _az=list(map(chr, range(ord('a'), ord('z')+1))) _09_az=_09+_az def print_solution(solution): board2=[["." for col in range(board_width)] for row in range(board_height)] for sol_row_i, sol_row in enumerate(solution): tile_type=sol_row[0] coords=sol_row[1] for coord in coords: row, col=coord board2[row][col]=_09_az[sol_row_i] for row in board2: print ("".join(row)) coloring=color_tiles(solution) for row in range(board_height): s="" for col in range(board_width): if board[row][col]=='*': tmp=False for a in range(len(solution)): if (row, col) in solution[a][1]: s=s+my_utils.ANSI_set_normal_color(coloring[a])+"██" tmp=True break if tmp==False: s=s+my_utils.ANSI_reset()+".." else: # skip holes in board: s=s+" " print (s) print (my_utils.ANSI_reset()) init_rows=[] for i in range(TILES_TOTAL): init_rows=init_rows+find_all_placements_with_rotations(i,tiles[i]) print ("len(init_rows)=", len(init_rows)) # init_rows is a list of tuples # each tuple has tile type (num) + list of coordinates on board which it can cover # like: #(2, [(1, 1), (2, 1), (2, 2)]) #(2, [(2, 1), (3, 1), (3, 2)]) #(3, [(0, 1), (1, 1)]) #(3, [(0, 3), (1, 3)]) matrix_tiles=[] # idx=row in matrix; val=tile type matrix_coords=[] # idx=col in matrix; val=coord matrix=[] for t in init_rows: #print (t) tile_type=t[0] list_of_coords=t[1] #print (tile_type, list_of_coords) x=[0 for i in range(get_board_squares_total())] if mode=="1": y=[0 for i in range(TILES_TOTAL)] for coord in list_of_coords: #print (coord) x[board_coord_to_square_number(coord)]=1 if mode=="1": y[t[0]]=1 if mode=="1": matrix.append(y+x) else: matrix.append(x) matrix_tiles.append(t) solution_n=1 #for solution in SAT_lib.solve_exact_cover(matrix, "kissat", True, 1): # for mutilated chess problem #for solution in SAT_lib.solve_exact_cover(matrix, "gimsatul", False, 3): for solution in SAT_lib.solve_exact_cover(matrix, "libcadical", False, 1): # better for enumeration #print (solution) tmp=[] tiles_used=set() for x in solution: #print (matrix_tiles[x]) tiles_used.add(matrix_tiles[x][0]) #for z in tiles_used: # print (z) #print (tiles_used) tmp.append(matrix_tiles[x]) #print ("tiles_used", tiles_used) if mode=="01": if len(tiles_used)==len(solution): # if no tile was reused, print solution print ("solution number", solution_n) print_solution(tmp) solution_n=solution_n+1 if mode=="x" or mode=="1": print ("solution number", solution_n) print_solution(tmp) solution_n=solution_n+1