#!/usr/bin/env python # coding: utf-8 # I would like to highly recommend this Board Game "Penguins on Ice" for kids and parents - this was a gift from my aunt: # # http://www.toysrus.com/buy/educational/penguins-on-ice-sg155us-44233536 # Quoting the site: # "From SmartGames, the worldwide leader in single player puzzle games, comes Penguins on Ice. Penguins on Ice is an award-winning, completely unique game based on ancient Greek Pentomino...featuring puzzle pieces that shift in order to fit into place! Arrange the sliding ice blocks so that they all fit on the game board while making sure that the five penguins are in the right spots as shown in the included challenge booklet. With simple challenges for beginners to complex puzzles that will test experienced players, Penguins on Ice is a fun way to develop logical thinking skills and spatial reasoning abilities." # ![Penguins on Ice](http://www.toysrus.com/graphics/product_images/pTRU1-19340859dt.jpg) # This games takes its origins from Pentominoes coined by Solomon W. Golomb in 1953. Pentominoes are 5-square figures, resulting in 15 different shapes: # # ![All Pentominoes](https://upload.wikimedia.org/wikipedia/commons/thumb/6/69/Pentomino_Naming_Conventions.svg/300px-Pentomino_Naming_Conventions.svg.png) # These shapes can tile 2D plane in various ways: # # ![Tiling with Pentominoes](https://upload.wikimedia.org/wikipedia/commons/thumb/0/09/Pentomino_Puzzle_Solutions.svg/400px-Pentomino_Puzzle_Solutions.svg.png) # # **Now back to pengiuns!!!** # In[1]: from IPython.display import YouTubeVideo # In[2]: YouTubeVideo("WKKy7x1gRzc") # Let's try to solve this board game using Python and numpy arrays! # In[3]: #check python version import sys if sys.version_info < (3,0): PY3=False if sys.version_info >= (2,7): raise Exception('not supported Python runtime {}'.format(sys.version_info)) else: PY3=True # In[4]: if not PY3: from __future import print_function, unicode_literals, absolute_imports # In[5]: import numpy as np # In[6]: #setup the board b=np.zeros([5,5]) b # In[7]: #setup all 5 pieces and possible configurations ## 16 = penguin cell on piece ## 1 = ice cell on piece ## 0 = empty p1=[np.array([[16,1,0,0,0], [0,1,1,1,0]]), np.array([[0,16,1,0,0], [0,1,1,1,0]]), np.array([[0,0,16,1,0], [0,1,1,1,0]]), np.array([[0,0,0,16,1], [0,1,1,1,0]])] for p in p1: print(p) print(p[p>0].size) # In[8]: p2=[np.array([[16,1,0,0], [0,1,1,0], [0,1,0,0]]), np.array([[0,16,1,0], [0,1,1,0], [0,1,0,0]]), np.array([[0,0,16,1], [0,1,1,0], [0,1,0,0]])] for p in p2: print(p) print(p[p>0].size) # In[9]: p3=[np.array([[0,16,0,0], [0,1,1,0], [1,1,0,0]]), np.array([[0,16,0,0], [0,1,1,0], [0,1,1,0]]), np.array([[0,16,0,0], [0,1,1,0], [0,0,1,1]])] for p in p3: print(p) print(p[p>0].size) # In[10]: p4=[np.array([[16,0,0,0], [1,1,1,1]]), np.array([[0,16,0,0], [1,1,1,1]]), np.array([[0,0,16,0], [1,1,1,1]]), np.array([[0,0,0,16], [1,1,1,1]])] for p in p4: print(p) print(p[p>0].size) # In[11]: p5=[np.array([[1,1,16], [1,0,0], [1,0,0]]), np.array([[1,1,16], [0,1,0], [0,1,0]]), np.array([[1,1,16], [0,0,1], [0,0,1]])] for p in p5: print(p) print(p[p>0].size) # In[12]: # for all pieces look at all possible rotations! for p in [p1,p2,p3,p4,p5]: for piece in p: for rot in range(4): piece=piece[~np.all(piece == 0, axis=1)] piece=piece.T[~np.all(piece == 0, axis=0)].T piece=np.rot90(piece,rot) print(piece) print() # In[13]: # set piece on the board based on location, rotation, and condition def set_piece(board,piece,loc=(0,0),rot=0,condition=None): #cleanup horizontal and vertical lines with all zeros piece=piece[~np.all(piece == 0, axis=1)] piece=piece.T[~np.all(piece == 0, axis=0)].T # piece can be rotated in 4 positions piece=np.rot90(piece,rot) a,b=piece.shape if ((a+loc[0]<=board.shape[0]) #piece within board bounds and (b+loc[1]<=board.shape[1])): board[loc[0]:a+loc[0],loc[1]:b+loc[1]]+=piece #set piece if ((board[board==2].size>0) # overlap type #1 or (board[board==17].size>0) # overlap type #2 or (board[board==32].size>0) # overlap type #3 or ((not condition is None) and (board[(board==1) & condition].size>0))): # game positions board[loc[0]:a+loc[0],loc[1]:b+loc[1]]-=piece #rollback if bad return False else: return True else: return False # In[14]: #set empty board and empty condition b=np.zeros([5,5]) condition=np.zeros([5, 5], dtype=bool) #problem #28 #condition[1,0]=True #condition[2,0]=True #condition[2,2]=True #condition[0,3]=True #condition[2,3]=True #problem #30 #condition[2,0]=True #condition[1,2]=True #condition[3,2]=True #condition[0,4]=True #condition[4,4]=True #problem #44 #condition[1,0]=True #condition[1,2]=True #condition[3,2]=True #condition[2,4]=True #condition[3,4]=True #problem #58 condition[1,1]=True condition[2,1]=True condition[2,2]=True condition[3,3]=True #problem #59 # condition[1,0]=True # condition[2,0]=True # condition[0,3]=True # condition[1,3]=True #basic testing, set second piece on board based on condition from itertools import product for i,j,r,e in product(range(4),range(4),range(4),range(len(p2))): print(i,j,r,e) if set_piece(b,p2[e],loc=(i,j),rot=r,condition=condition): #print i,j,t,r,e break # In[15]: b # In[16]: # list all cells with penguin locations, whether set or not b[condition] # In[17]: condition # In[18]: get_ipython().run_cell_magic('time', '', '\n#main algorithm for backtracking solver\n\nb=np.zeros([5,5])\n\n#paths visited in tree\npaths=[{},{},{},{},{}]\nsolved=False\n\n#sequence of pieces to set\npieces=[p5,p4,p3,p2,p1]\n\n#path depth\npn=0\n\n#sequence of board positions\nbhist=[b.copy()]\n\n#set of pieces set on board\nphist=[]\n\n\n#iterate until solved or exhausted all options\nwhile not solved:\n p=pieces.pop()\n level_set=False\n \n #try all locations, rotations, and piece configurations\n for i,j,r,e in product(range(4),range(4),\n range(4),\n range(len(p))):\n if (i,j,r,e) in paths[pn]:\n pass #print("skip: ", (pn,i,j,r,e))\n else:\n if set_piece(b,p[e],loc=(i,j),rot=r,condition=condition):\n # if piece is placed on board correcly,\n # then record this and move on\n paths[pn][i,j,r,e]=True\n level_set=True\n #print pn,i,j,t,r,e\n pn+=1\n phist.append(p)\n bhist.append(b.copy())\n if len(pieces)==0:\n print("solved", pn)\n solved=True\n break\n if not level_set:\n # if failed to place the piece on board,\n # then backtrack one piece back in history\n # clean paths visited up to this level\n paths[pn:]=[{} for i in range(pn,len(paths))]\n pn-=1\n #print(pn, "backtrack")#, len(pieces)\n if pn<0:\n print("something wrong")\n break\n pieces.append(phist.pop())\n pieces.append(p) \n b=bhist.pop()\n b=bhist[-1].copy()\n') # In[19]: # no pieces left pieces # In[20]: # paths tried on last leaves of tree paths # In[21]: # sequence of setting pieces on the board starting from piece #1 (p1) for bi in bhist: print(bi) print() # In[22]: # Setup all possible numpy arrays with board positions with only one piece on board b=np.zeros([5,5]) pnpl=[] for pi,p in enumerate([p5,p4,p3,p2,p1]): plist=[] for i,j,r,e in product(range(4),range(4), range(4), range(len(p))): b0=b.copy() if set_piece(b0,p[e],loc=(i,j),rot=r): plist.append(b0) pnpl.append(np.array(plist)) print(pnpl[-1].shape) # In[24]: get_ipython().run_cell_magic('time', '', '# Find all board positions with pieces #1 and #2 on board without conflicts\nb12=[]\nfor b1,b2 in product(pnpl[0],pnpl[1]):\n board=b1+b2\n if (board[(board==1) | (board==16)].size==10):\n b12.append(board)\nb12=np.array(b12)\nprint(b12.shape)\n') # In[25]: get_ipython().run_cell_magic('time', '', '# Find all board positions with pieces #3, #4 and #5 on board without conflicts\nb345=[]\nfor b3,b4,b5 in product(pnpl[2],pnpl[3],pnpl[4]):\n board=b3+b4+b5\n if (board[(board==1) | (board==16)].size==15):\n b345.append(board)\nb345=np.array(b345)\nprint(b345.shape)\n') # In[26]: get_ipython().run_cell_magic('time', '', '# Find all board positions with pieces #2, #3, #4 and #5 on board without conflicts\nb2345=[]\nfor bi,bj in product(pnpl[1],b345):\n board=bi+bj\n if (board[(board==1) | (board==16)].size==20):\n b2345.append(board)\nb2345=np.array(b2345)\nprint(b2345.shape)\n') # In[27]: get_ipython().run_cell_magic('time', '', '# Find all board positions with all pieces on board without conflicts\nball=[]\nfor bi,bj in product(pnpl[0],b2345):\n board=bi+bj\n if (board[(board==1) | (board==16)].size==25):\n ball.append(board)\nball=np.array(ball)\nprint(ball.shape)\n') # In[28]: ball[:,0,0].shape # In[29]: (ball[:,0,0]==16) & (ball[:,1,1]==16) # In[44]: #find all unique board positions, contrained by 2 pieces only! for a,b in product(range(5),range(5)): for i,j in product(range(5),range(5)): if abs(a-i)+abs(b-j)<2: pass else: ix1=ball[:,a,b]==16 ix2=ball[:,i,j]==16 if ball[ix1 & ix2].size==25: print(a,b,i,j) #print(ball[ix1 & ix2]) # In[46]: #find all unique board positions, contrained by 3 pieces only! d=4 for k,l in product(range(5),range(5)): for a,b in product(range(5),range(5)): for i,j in product(range(5),range(5)): if abs(a-i)+abs(b-j)