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."
This games takes its origins from Pentominoes coined by Solomon W. Golomb in 1953. Pentominoes are 5-square figures, resulting in 15 different shapes:
These shapes can tile 2D plane in various ways:
Now back to pengiuns!!!
from IPython.display import YouTubeVideo
YouTubeVideo("WKKy7x1gRzc")
Let's try to solve this board game using Python and numpy arrays!
#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
if not PY3:
from __future import print_function, unicode_literals, absolute_imports
import numpy as np
#setup the board
b=np.zeros([5,5])
b
array([[ 0., 0., 0., 0., 0.], [ 0., 0., 0., 0., 0.], [ 0., 0., 0., 0., 0.], [ 0., 0., 0., 0., 0.], [ 0., 0., 0., 0., 0.]])
#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)
[[16 1 0 0 0] [ 0 1 1 1 0]] 5 [[ 0 16 1 0 0] [ 0 1 1 1 0]] 5 [[ 0 0 16 1 0] [ 0 1 1 1 0]] 5 [[ 0 0 0 16 1] [ 0 1 1 1 0]] 5
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)
[[16 1 0 0] [ 0 1 1 0] [ 0 1 0 0]] 5 [[ 0 16 1 0] [ 0 1 1 0] [ 0 1 0 0]] 5 [[ 0 0 16 1] [ 0 1 1 0] [ 0 1 0 0]] 5
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)
[[ 0 16 0 0] [ 0 1 1 0] [ 1 1 0 0]] 5 [[ 0 16 0 0] [ 0 1 1 0] [ 0 1 1 0]] 5 [[ 0 16 0 0] [ 0 1 1 0] [ 0 0 1 1]] 5
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)
[[16 0 0 0] [ 1 1 1 1]] 5 [[ 0 16 0 0] [ 1 1 1 1]] 5 [[ 0 0 16 0] [ 1 1 1 1]] 5 [[ 0 0 0 16] [ 1 1 1 1]] 5
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)
[[ 1 1 16] [ 1 0 0] [ 1 0 0]] 5 [[ 1 1 16] [ 0 1 0] [ 0 1 0]] 5 [[ 1 1 16] [ 0 0 1] [ 0 0 1]] 5
# 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()
[[16 1 0 0] [ 0 1 1 1]] [[ 0 1] [ 0 1] [ 1 1] [16 0]] [[ 0 16] [ 1 1] [ 1 0] [ 1 0]] [[ 1 1 1 0] [ 0 0 1 16]] [[16 1 0] [ 1 1 1]] [[ 0 1] [ 1 1] [16 1]] [[ 1 16] [ 1 1] [ 1 0]] [[ 1 1 1] [ 0 1 16]] [[ 0 16 1] [ 1 1 1]] [[ 1 1] [16 1] [ 0 1]] [[ 1 0] [ 1 16] [ 1 1]] [[ 1 1 1] [ 1 16 0]] [[ 0 0 16 1] [ 1 1 1 0]] [[ 1 0] [16 1] [ 0 1] [ 0 1]] [[ 1 0] [ 1 0] [ 1 16] [ 0 1]] [[ 0 1 1 1] [ 1 16 0 0]] [[16 1 0] [ 0 1 1] [ 0 1 0]] [[ 0 1 0] [ 1 1 1] [16 0 0]] [[ 0 0 16] [ 1 1 1] [ 0 1 0]] [[ 0 1 0] [ 1 1 0] [ 0 1 16]] [[16 1] [ 1 1] [ 1 0]] [[ 1 1 0] [16 1 1]] [[ 1 1 16] [ 0 1 1]] [[ 0 1] [ 1 1] [ 1 16]] [[ 0 16 1] [ 1 1 0] [ 1 0 0]] [[ 1 0 0] [16 1 0] [ 0 1 1]] [[ 1 1 0] [ 0 1 16] [ 0 0 1]] [[ 0 0 1] [ 0 1 1] [ 1 16 0]] [[ 0 16 0] [ 0 1 1] [ 1 1 0]] [[ 0 1 0] [16 1 1] [ 0 0 1]] [[ 1 0 0] [ 1 1 16] [ 0 1 0]] [[ 0 1 1] [ 1 1 0] [ 0 16 0]] [[16 0] [ 1 1] [ 1 1]] [[ 0 1 1] [16 1 1]] [[ 1 1 16] [ 1 1 0]] [[ 1 1] [ 1 1] [ 0 16]] [[16 0 0] [ 1 1 0] [ 0 1 1]] [[ 0 0 1] [ 0 1 1] [16 1 0]] [[ 0 1 16] [ 1 1 0] [ 1 0 0]] [[ 1 1 0] [ 0 1 1] [ 0 0 16]] [[16 0 0 0] [ 1 1 1 1]] [[ 0 1] [ 0 1] [ 0 1] [16 1]] [[ 1 16] [ 1 0] [ 1 0] [ 1 0]] [[ 1 1 1 1] [ 0 0 0 16]] [[ 0 16 0 0] [ 1 1 1 1]] [[ 0 1] [ 0 1] [16 1] [ 0 1]] [[ 1 0] [ 1 16] [ 1 0] [ 1 0]] [[ 1 1 1 1] [ 0 0 16 0]] [[ 0 0 16 0] [ 1 1 1 1]] [[ 0 1] [16 1] [ 0 1] [ 0 1]] [[ 1 0] [ 1 0] [ 1 16] [ 1 0]] [[ 1 1 1 1] [ 0 16 0 0]] [[ 0 0 0 16] [ 1 1 1 1]] [[16 1] [ 0 1] [ 0 1] [ 0 1]] [[ 1 0] [ 1 0] [ 1 0] [ 1 16]] [[ 1 1 1 1] [16 0 0 0]] [[ 1 1 16] [ 1 0 0] [ 1 0 0]] [[16 0 0] [ 1 0 0] [ 1 1 1]] [[ 1 1 1] [ 0 0 1] [ 0 0 16]] [[ 0 0 1] [ 0 0 1] [16 1 1]] [[ 1 1 16] [ 0 1 0] [ 0 1 0]] [[16 0 0] [ 1 1 1] [ 1 0 0]] [[ 0 0 1] [ 1 1 1] [ 0 0 16]] [[ 0 1 0] [ 0 1 0] [16 1 1]] [[ 1 1 16] [ 0 0 1] [ 0 0 1]] [[16 1 1] [ 1 0 0] [ 1 0 0]] [[ 0 0 1] [ 0 0 1] [ 1 1 16]] [[ 1 0 0] [ 1 0 0] [16 1 1]]
# 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
#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
0 0 0 0 0 0 0 1 0 0 0 2 0 0 1 0 0 0 1 1 0 0 1 2 0 0 2 0 0 0 2 1 0 0 2 2 0 0 3 0 0 0 3 1 0 0 3 2 0 1 0 0 0 1 0 1 0 1 0 2 0 1 1 0 0 1 1 1
b
array([[ 0., 1., 1., 0., 0.], [ 0., 16., 1., 1., 0.], [ 0., 0., 0., 0., 0.], [ 0., 0., 0., 0., 0.], [ 0., 0., 0., 0., 0.]])
# list all cells with penguin locations, whether set or not
b[condition]
array([ 16., 0., 0., 0.])
condition
array([[False, False, False, False, False], [False, True, False, False, False], [False, True, True, False, False], [False, False, False, True, False], [False, False, False, False, False]], dtype=bool)
%%time
#main algorithm for backtracking solver
b=np.zeros([5,5])
#paths visited in tree
paths=[{},{},{},{},{}]
solved=False
#sequence of pieces to set
pieces=[p5,p4,p3,p2,p1]
#path depth
pn=0
#sequence of board positions
bhist=[b.copy()]
#set of pieces set on board
phist=[]
#iterate until solved or exhausted all options
while not solved:
p=pieces.pop()
level_set=False
#try all locations, rotations, and piece configurations
for i,j,r,e in product(range(4),range(4),
range(4),
range(len(p))):
if (i,j,r,e) in paths[pn]:
pass #print("skip: ", (pn,i,j,r,e))
else:
if set_piece(b,p[e],loc=(i,j),rot=r,condition=condition):
# if piece is placed on board correcly,
# then record this and move on
paths[pn][i,j,r,e]=True
level_set=True
#print pn,i,j,t,r,e
pn+=1
phist.append(p)
bhist.append(b.copy())
if len(pieces)==0:
print("solved", pn)
solved=True
break
if not level_set:
# if failed to place the piece on board,
# then backtrack one piece back in history
# clean paths visited up to this level
paths[pn:]=[{} for i in range(pn,len(paths))]
pn-=1
#print(pn, "backtrack")#, len(pieces)
if pn<0:
print("something wrong")
break
pieces.append(phist.pop())
pieces.append(p)
b=bhist.pop()
b=bhist[-1].copy()
solved 5 CPU times: user 4.7 s, sys: 15.7 ms, total: 4.71 s Wall time: 4.67 s
# no pieces left
pieces
[]
# paths tried on last leaves of tree
paths
[{(0, 0, 2, 0): True, (0, 1, 1, 0): True, (0, 1, 1, 1): True, (0, 1, 3, 1): True}, {(2, 0, 0, 0): True}, {(0, 2, 2, 0): True, (0, 3, 1, 0): True}, {(3, 2, 0, 2): True}, {(0, 0, 3, 1): True}]
# sequence of setting pieces on the board starting from piece #1 (p1)
for bi in bhist:
print(bi)
print()
[[ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.]] [[ 0. 1. 1. 16. 0.] [ 0. 0. 1. 1. 0.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.]] [[ 0. 1. 1. 16. 0.] [ 0. 0. 1. 1. 0.] [ 0. 16. 0. 0. 0.] [ 0. 1. 1. 0. 0.] [ 1. 1. 0. 0. 0.]] [[ 0. 1. 1. 16. 1.] [ 0. 0. 1. 1. 1.] [ 0. 16. 16. 1. 1.] [ 0. 1. 1. 0. 0.] [ 1. 1. 0. 0. 0.]] [[ 0. 1. 1. 16. 1.] [ 0. 0. 1. 1. 1.] [ 0. 16. 16. 1. 1.] [ 0. 1. 1. 16. 1.] [ 1. 1. 1. 1. 1.]] [[ 1. 1. 1. 16. 1.] [ 1. 16. 1. 1. 1.] [ 1. 16. 16. 1. 1.] [ 1. 1. 1. 16. 1.] [ 1. 1. 1. 1. 1.]]
# 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)
(108, 5, 5) (128, 5, 5) (120, 5, 5) (120, 5, 5) (160, 5, 5)
%%time
# Find all board positions with pieces #1 and #2 on board without conflicts
b12=[]
for b1,b2 in product(pnpl[0],pnpl[1]):
board=b1+b2
if (board[(board==1) | (board==16)].size==10):
b12.append(board)
b12=np.array(b12)
print(b12.shape)
(4400, 5, 5) CPU times: user 177 ms, sys: 3.89 ms, total: 181 ms Wall time: 181 ms
%%time
# Find all board positions with pieces #3, #4 and #5 on board without conflicts
b345=[]
for b3,b4,b5 in product(pnpl[2],pnpl[3],pnpl[4]):
board=b3+b4+b5
if (board[(board==1) | (board==16)].size==15):
b345.append(board)
b345=np.array(b345)
print(b345.shape)
(61056, 5, 5) CPU times: user 24.4 s, sys: 19.4 ms, total: 24.4 s Wall time: 24.4 s
%%time
# Find all board positions with pieces #2, #3, #4 and #5 on board without conflicts
b2345=[]
for bi,bj in product(pnpl[1],b345):
board=bi+bj
if (board[(board==1) | (board==16)].size==20):
b2345.append(board)
b2345=np.array(b2345)
print(b2345.shape)
(48568, 5, 5) CPU times: user 1min 15s, sys: 11.8 ms, total: 1min 15s Wall time: 1min 15s
%%time
# Find all board positions with all pieces on board without conflicts
ball=[]
for bi,bj in product(pnpl[0],b2345):
board=bi+bj
if (board[(board==1) | (board==16)].size==25):
ball.append(board)
ball=np.array(ball)
print(ball.shape)
(296, 5, 5) CPU times: user 50.7 s, sys: 32 ms, total: 50.8 s Wall time: 50.8 s
ball[:,0,0].shape
(296,)
(ball[:,0,0]==16) & (ball[:,1,1]==16)
array([False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, True, True, False, False, False, False, False, False, False, False, True, True, True, True, False, False, False, False, False, False, False, False, False, True, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False], dtype=bool)
#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])
0 0 0 2 0 2 0 0 0 3 1 2 0 4 2 4 1 0 2 1 1 2 0 3 2 0 4 0 2 1 1 0 2 3 3 4 2 4 0 4 3 2 4 1 3 4 2 3 4 0 2 0 4 1 3 2 4 2 4 4 4 4 4 2
#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)<d:
pass
elif abs(a-k)+abs(b-l)<d:
pass
elif abs(i-k)+abs(j-l)<d:
pass
else:
ix1=ball[:,a,b]==16
ix2=ball[:,i,j]==16
ix3=ball[:,k,l]==16
if ball[ix1 & ix2 & ix3].size==25:
print(k,l,a,b,i,j)
0 0 1 3 4 1 0 0 1 4 4 3 0 0 4 1 1 3 0 0 4 3 1 4 0 1 1 4 4 0 0 1 1 4 4 2 0 1 2 4 3 0 0 1 2 4 4 1 0 1 2 4 4 2 0 1 3 0 2 4 0 1 3 0 4 4 0 1 4 0 1 4 0 1 4 1 2 4 0 1 4 2 1 4 0 1 4 2 2 4 0 1 4 4 3 0 0 2 2 0 4 3 0 2 2 4 3 0 0 2 3 0 2 4 0 2 3 0 3 4 0 2 3 0 4 3 0 2 3 4 3 0 0 2 4 3 2 0 0 2 4 3 3 0 0 3 2 0 4 3 0 3 3 1 4 4 0 3 4 3 2 0 0 3 4 4 3 1 0 4 1 0 3 3 0 4 3 0 4 3 0 4 3 3 1 0 0 4 4 3 3 0 1 0 0 4 3 3 1 0 1 4 4 2 1 0 3 3 0 4 1 0 4 2 1 4 1 1 3 4 4 0 1 1 4 0 3 4 1 3 0 0 4 1 1 3 4 1 0 0 1 4 0 0 4 3 1 4 0 1 4 0 1 4 0 1 4 2 1 4 1 0 4 2 1 4 2 0 4 2 1 4 2 0 4 3 1 4 4 0 0 1 1 4 4 2 0 1 1 4 4 2 1 0 1 4 4 2 2 0 1 4 4 3 0 0 1 4 4 3 2 0 2 0 0 2 4 3 2 0 0 3 4 3 2 0 1 4 4 2 2 0 1 4 4 3 2 0 4 2 1 4 2 0 4 3 0 2 2 0 4 3 0 3 2 0 4 3 1 4 2 4 0 1 3 0 2 4 0 1 4 1 2 4 0 1 4 2 2 4 0 2 3 0 2 4 3 0 0 1 2 4 3 0 0 2 2 4 4 1 0 1 2 4 4 2 0 1 3 0 0 1 2 4 3 0 0 1 4 4 3 0 0 2 2 4 3 0 0 2 3 4 3 0 0 2 4 3 3 0 0 4 4 3 3 0 2 4 0 1 3 0 2 4 0 2 3 0 3 4 0 2 3 0 4 3 0 2 3 0 4 3 0 4 3 0 4 4 0 1 3 1 0 3 4 4 3 1 4 4 0 3 3 3 0 4 1 0 3 3 1 0 0 4 3 4 0 2 3 0 3 4 1 1 4 0 3 4 3 0 0 2 3 4 4 0 1 1 4 0 0 1 1 4 4 0 1 1 3 4 4 0 1 4 0 1 4 0 3 4 1 1 4 1 0 0 1 3 4 1 0 1 2 4 4 1 1 3 0 0 4 1 2 4 0 1 4 2 0 1 1 4 4 2 0 1 2 4 4 2 1 0 1 4 4 2 1 4 0 1 4 2 1 4 1 0 4 2 1 4 2 0 4 2 2 0 1 4 4 2 2 4 0 1 4 3 0 0 1 4 4 3 0 2 2 0 4 3 0 2 3 0 4 3 0 3 2 0 4 3 0 4 3 0 4 3 1 4 0 0 4 3 1 4 2 0 4 3 2 0 0 2 4 3 2 0 0 3 4 3 2 0 1 4 4 3 3 0 0 2 4 3 3 0 0 4 4 4 0 1 3 0 4 4 0 3 3 1 4 4 3 0 0 1 4 4 3 1 0 3