Skip to content

Instantly share code, notes, and snippets.

@den-run-ai

den-run-ai/pynguins.ipynb

Last active October 25, 2022 01:17
Show Gist options
  • Save den-run-ai/9a5e1fdeaf611dc60ea8 to your computer and use it in GitHub Desktop.
Save den-run-ai/9a5e1fdeaf611dc60ea8 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
pynguins.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"I would like to highly recommend this Board Game \"Penguins on Ice\" for kids and parents - this was a gift from my aunt: \n",
"\n",
"http://www.toysrus.com/buy/educational/penguins-on-ice-sg155us-44233536"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Quoting the site:\n",
"\"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.\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![Penguins on Ice](http://www.toysrus.com/graphics/product_images/pTRU1-19340859dt.jpg)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This games takes its origins from Pentominoes coined by Solomon W. Golomb in 1953. Pentominoes are 5-square figures, resulting in 15 different shapes:\n",
"\n",
"![All Pentominoes](https://upload.wikimedia.org/wikipedia/commons/thumb/6/69/Pentomino_Naming_Conventions.svg/300px-Pentomino_Naming_Conventions.svg.png)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"These shapes can tile 2D plane in various ways:\n",
" \n",
"![Tiling with Pentominoes](https://upload.wikimedia.org/wikipedia/commons/thumb/0/09/Pentomino_Puzzle_Solutions.svg/400px-Pentomino_Puzzle_Solutions.svg.png)\n",
"\n",
"**Now back to pengiuns!!!**"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from IPython.display import YouTubeVideo"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"\n",
" <iframe\n",
" width=\"400\"\n",
" height=\"300\"\n",
" src=\"https://www.youtube.com/embed/WKKy7x1gRzc\"\n",
" frameborder=\"0\"\n",
" allowfullscreen\n",
" ></iframe>\n",
" "
],
"text/plain": [
"<IPython.lib.display.YouTubeVideo at 0x7f9660135780>"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"YouTubeVideo(\"WKKy7x1gRzc\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's try to solve this board game using Python and numpy arrays!"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"#check python version\n",
"\n",
"import sys\n",
"if sys.version_info < (3,0):\n",
" PY3=False\n",
" if sys.version_info >= (2,7):\n",
" raise Exception('not supported Python runtime {}'.format(sys.version_info))\n",
"else:\n",
" PY3=True"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"if not PY3:\n",
" from __future import print_function, unicode_literals, absolute_imports"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"array([[ 0., 0., 0., 0., 0.],\n",
" [ 0., 0., 0., 0., 0.],\n",
" [ 0., 0., 0., 0., 0.],\n",
" [ 0., 0., 0., 0., 0.],\n",
" [ 0., 0., 0., 0., 0.]])"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"#setup the board\n",
"\n",
"b=np.zeros([5,5])\n",
"b"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[16 1 0 0 0]\n",
" [ 0 1 1 1 0]]\n",
"5\n",
"[[ 0 16 1 0 0]\n",
" [ 0 1 1 1 0]]\n",
"5\n",
"[[ 0 0 16 1 0]\n",
" [ 0 1 1 1 0]]\n",
"5\n",
"[[ 0 0 0 16 1]\n",
" [ 0 1 1 1 0]]\n",
"5\n"
]
}
],
"source": [
"#setup all 5 pieces and possible configurations\n",
"\n",
"## 16 = penguin cell on piece\n",
"## 1 = ice cell on piece\n",
"## 0 = empty\n",
"\n",
"p1=[np.array([[16,1,0,0,0],\n",
" [0,1,1,1,0]]),\n",
" np.array([[0,16,1,0,0],\n",
" [0,1,1,1,0]]),\n",
" np.array([[0,0,16,1,0],\n",
" [0,1,1,1,0]]),\n",
" np.array([[0,0,0,16,1],\n",
" [0,1,1,1,0]])]\n",
"for p in p1:\n",
" print(p)\n",
" print(p[p>0].size)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[16 1 0 0]\n",
" [ 0 1 1 0]\n",
" [ 0 1 0 0]]\n",
"5\n",
"[[ 0 16 1 0]\n",
" [ 0 1 1 0]\n",
" [ 0 1 0 0]]\n",
"5\n",
"[[ 0 0 16 1]\n",
" [ 0 1 1 0]\n",
" [ 0 1 0 0]]\n",
"5\n"
]
}
],
"source": [
"p2=[np.array([[16,1,0,0],\n",
" [0,1,1,0],\n",
" [0,1,0,0]]),\n",
" np.array([[0,16,1,0],\n",
" [0,1,1,0],\n",
" [0,1,0,0]]),\n",
" np.array([[0,0,16,1],\n",
" [0,1,1,0],\n",
" [0,1,0,0]])]\n",
"for p in p2:\n",
" print(p)\n",
" print(p[p>0].size)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[ 0 16 0 0]\n",
" [ 0 1 1 0]\n",
" [ 1 1 0 0]]\n",
"5\n",
"[[ 0 16 0 0]\n",
" [ 0 1 1 0]\n",
" [ 0 1 1 0]]\n",
"5\n",
"[[ 0 16 0 0]\n",
" [ 0 1 1 0]\n",
" [ 0 0 1 1]]\n",
"5\n"
]
}
],
"source": [
"p3=[np.array([[0,16,0,0],\n",
" [0,1,1,0],\n",
" [1,1,0,0]]),\n",
" np.array([[0,16,0,0],\n",
" [0,1,1,0],\n",
" [0,1,1,0]]),\n",
" np.array([[0,16,0,0],\n",
" [0,1,1,0],\n",
" [0,0,1,1]])]\n",
"for p in p3:\n",
" print(p)\n",
" print(p[p>0].size)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[16 0 0 0]\n",
" [ 1 1 1 1]]\n",
"5\n",
"[[ 0 16 0 0]\n",
" [ 1 1 1 1]]\n",
"5\n",
"[[ 0 0 16 0]\n",
" [ 1 1 1 1]]\n",
"5\n",
"[[ 0 0 0 16]\n",
" [ 1 1 1 1]]\n",
"5\n"
]
}
],
"source": [
"p4=[np.array([[16,0,0,0],\n",
" [1,1,1,1]]),\n",
" np.array([[0,16,0,0],\n",
" [1,1,1,1]]),\n",
" np.array([[0,0,16,0],\n",
" [1,1,1,1]]),\n",
" np.array([[0,0,0,16],\n",
" [1,1,1,1]])]\n",
"for p in p4:\n",
" print(p)\n",
" print(p[p>0].size)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[ 1 1 16]\n",
" [ 1 0 0]\n",
" [ 1 0 0]]\n",
"5\n",
"[[ 1 1 16]\n",
" [ 0 1 0]\n",
" [ 0 1 0]]\n",
"5\n",
"[[ 1 1 16]\n",
" [ 0 0 1]\n",
" [ 0 0 1]]\n",
"5\n"
]
}
],
"source": [
"p5=[np.array([[1,1,16],\n",
" [1,0,0],\n",
" [1,0,0]]),\n",
" np.array([[1,1,16],\n",
" [0,1,0],\n",
" [0,1,0]]),\n",
" np.array([[1,1,16],\n",
" [0,0,1],\n",
" [0,0,1]])]\n",
"for p in p5:\n",
" print(p)\n",
" print(p[p>0].size)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[16 1 0 0]\n",
" [ 0 1 1 1]]\n",
"\n",
"[[ 0 1]\n",
" [ 0 1]\n",
" [ 1 1]\n",
" [16 0]]\n",
"\n",
"[[ 0 16]\n",
" [ 1 1]\n",
" [ 1 0]\n",
" [ 1 0]]\n",
"\n",
"[[ 1 1 1 0]\n",
" [ 0 0 1 16]]\n",
"\n",
"[[16 1 0]\n",
" [ 1 1 1]]\n",
"\n",
"[[ 0 1]\n",
" [ 1 1]\n",
" [16 1]]\n",
"\n",
"[[ 1 16]\n",
" [ 1 1]\n",
" [ 1 0]]\n",
"\n",
"[[ 1 1 1]\n",
" [ 0 1 16]]\n",
"\n",
"[[ 0 16 1]\n",
" [ 1 1 1]]\n",
"\n",
"[[ 1 1]\n",
" [16 1]\n",
" [ 0 1]]\n",
"\n",
"[[ 1 0]\n",
" [ 1 16]\n",
" [ 1 1]]\n",
"\n",
"[[ 1 1 1]\n",
" [ 1 16 0]]\n",
"\n",
"[[ 0 0 16 1]\n",
" [ 1 1 1 0]]\n",
"\n",
"[[ 1 0]\n",
" [16 1]\n",
" [ 0 1]\n",
" [ 0 1]]\n",
"\n",
"[[ 1 0]\n",
" [ 1 0]\n",
" [ 1 16]\n",
" [ 0 1]]\n",
"\n",
"[[ 0 1 1 1]\n",
" [ 1 16 0 0]]\n",
"\n",
"[[16 1 0]\n",
" [ 0 1 1]\n",
" [ 0 1 0]]\n",
"\n",
"[[ 0 1 0]\n",
" [ 1 1 1]\n",
" [16 0 0]]\n",
"\n",
"[[ 0 0 16]\n",
" [ 1 1 1]\n",
" [ 0 1 0]]\n",
"\n",
"[[ 0 1 0]\n",
" [ 1 1 0]\n",
" [ 0 1 16]]\n",
"\n",
"[[16 1]\n",
" [ 1 1]\n",
" [ 1 0]]\n",
"\n",
"[[ 1 1 0]\n",
" [16 1 1]]\n",
"\n",
"[[ 1 1 16]\n",
" [ 0 1 1]]\n",
"\n",
"[[ 0 1]\n",
" [ 1 1]\n",
" [ 1 16]]\n",
"\n",
"[[ 0 16 1]\n",
" [ 1 1 0]\n",
" [ 1 0 0]]\n",
"\n",
"[[ 1 0 0]\n",
" [16 1 0]\n",
" [ 0 1 1]]\n",
"\n",
"[[ 1 1 0]\n",
" [ 0 1 16]\n",
" [ 0 0 1]]\n",
"\n",
"[[ 0 0 1]\n",
" [ 0 1 1]\n",
" [ 1 16 0]]\n",
"\n",
"[[ 0 16 0]\n",
" [ 0 1 1]\n",
" [ 1 1 0]]\n",
"\n",
"[[ 0 1 0]\n",
" [16 1 1]\n",
" [ 0 0 1]]\n",
"\n",
"[[ 1 0 0]\n",
" [ 1 1 16]\n",
" [ 0 1 0]]\n",
"\n",
"[[ 0 1 1]\n",
" [ 1 1 0]\n",
" [ 0 16 0]]\n",
"\n",
"[[16 0]\n",
" [ 1 1]\n",
" [ 1 1]]\n",
"\n",
"[[ 0 1 1]\n",
" [16 1 1]]\n",
"\n",
"[[ 1 1 16]\n",
" [ 1 1 0]]\n",
"\n",
"[[ 1 1]\n",
" [ 1 1]\n",
" [ 0 16]]\n",
"\n",
"[[16 0 0]\n",
" [ 1 1 0]\n",
" [ 0 1 1]]\n",
"\n",
"[[ 0 0 1]\n",
" [ 0 1 1]\n",
" [16 1 0]]\n",
"\n",
"[[ 0 1 16]\n",
" [ 1 1 0]\n",
" [ 1 0 0]]\n",
"\n",
"[[ 1 1 0]\n",
" [ 0 1 1]\n",
" [ 0 0 16]]\n",
"\n",
"[[16 0 0 0]\n",
" [ 1 1 1 1]]\n",
"\n",
"[[ 0 1]\n",
" [ 0 1]\n",
" [ 0 1]\n",
" [16 1]]\n",
"\n",
"[[ 1 16]\n",
" [ 1 0]\n",
" [ 1 0]\n",
" [ 1 0]]\n",
"\n",
"[[ 1 1 1 1]\n",
" [ 0 0 0 16]]\n",
"\n",
"[[ 0 16 0 0]\n",
" [ 1 1 1 1]]\n",
"\n",
"[[ 0 1]\n",
" [ 0 1]\n",
" [16 1]\n",
" [ 0 1]]\n",
"\n",
"[[ 1 0]\n",
" [ 1 16]\n",
" [ 1 0]\n",
" [ 1 0]]\n",
"\n",
"[[ 1 1 1 1]\n",
" [ 0 0 16 0]]\n",
"\n",
"[[ 0 0 16 0]\n",
" [ 1 1 1 1]]\n",
"\n",
"[[ 0 1]\n",
" [16 1]\n",
" [ 0 1]\n",
" [ 0 1]]\n",
"\n",
"[[ 1 0]\n",
" [ 1 0]\n",
" [ 1 16]\n",
" [ 1 0]]\n",
"\n",
"[[ 1 1 1 1]\n",
" [ 0 16 0 0]]\n",
"\n",
"[[ 0 0 0 16]\n",
" [ 1 1 1 1]]\n",
"\n",
"[[16 1]\n",
" [ 0 1]\n",
" [ 0 1]\n",
" [ 0 1]]\n",
"\n",
"[[ 1 0]\n",
" [ 1 0]\n",
" [ 1 0]\n",
" [ 1 16]]\n",
"\n",
"[[ 1 1 1 1]\n",
" [16 0 0 0]]\n",
"\n",
"[[ 1 1 16]\n",
" [ 1 0 0]\n",
" [ 1 0 0]]\n",
"\n",
"[[16 0 0]\n",
" [ 1 0 0]\n",
" [ 1 1 1]]\n",
"\n",
"[[ 1 1 1]\n",
" [ 0 0 1]\n",
" [ 0 0 16]]\n",
"\n",
"[[ 0 0 1]\n",
" [ 0 0 1]\n",
" [16 1 1]]\n",
"\n",
"[[ 1 1 16]\n",
" [ 0 1 0]\n",
" [ 0 1 0]]\n",
"\n",
"[[16 0 0]\n",
" [ 1 1 1]\n",
" [ 1 0 0]]\n",
"\n",
"[[ 0 0 1]\n",
" [ 1 1 1]\n",
" [ 0 0 16]]\n",
"\n",
"[[ 0 1 0]\n",
" [ 0 1 0]\n",
" [16 1 1]]\n",
"\n",
"[[ 1 1 16]\n",
" [ 0 0 1]\n",
" [ 0 0 1]]\n",
"\n",
"[[16 1 1]\n",
" [ 1 0 0]\n",
" [ 1 0 0]]\n",
"\n",
"[[ 0 0 1]\n",
" [ 0 0 1]\n",
" [ 1 1 16]]\n",
"\n",
"[[ 1 0 0]\n",
" [ 1 0 0]\n",
" [16 1 1]]\n",
"\n"
]
}
],
"source": [
"# for all pieces look at all possible rotations!\n",
"\n",
"for p in [p1,p2,p3,p4,p5]:\n",
" for piece in p:\n",
" for rot in range(4):\n",
" piece=piece[~np.all(piece == 0, axis=1)]\n",
" piece=piece.T[~np.all(piece == 0, axis=0)].T\n",
" piece=np.rot90(piece,rot)\n",
" print(piece)\n",
" print()"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"# set piece on the board based on location, rotation, and condition\n",
"\n",
"def set_piece(board,piece,loc=(0,0),rot=0,condition=None):\n",
" \n",
" #cleanup horizontal and vertical lines with all zeros\n",
" piece=piece[~np.all(piece == 0, axis=1)]\n",
" piece=piece.T[~np.all(piece == 0, axis=0)].T\n",
" \n",
" # piece can be rotated in 4 positions\n",
" piece=np.rot90(piece,rot)\n",
" a,b=piece.shape\n",
" if ((a+loc[0]<=board.shape[0]) #piece within board bounds\n",
" and\n",
" (b+loc[1]<=board.shape[1])):\n",
" board[loc[0]:a+loc[0],loc[1]:b+loc[1]]+=piece #set piece\n",
" if ((board[board==2].size>0) # overlap type #1\n",
" or\n",
" (board[board==17].size>0) # overlap type #2\n",
" or\n",
" (board[board==32].size>0) # overlap type #3\n",
" or\n",
" ((not condition is None) and \n",
" (board[(board==1) & condition].size>0))): # game positions\n",
" board[loc[0]:a+loc[0],loc[1]:b+loc[1]]-=piece #rollback if bad\n",
" return False \n",
" else: \n",
" return True\n",
" else:\n",
" return False"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 0 0 0\n",
"0 0 0 1\n",
"0 0 0 2\n",
"0 0 1 0\n",
"0 0 1 1\n",
"0 0 1 2\n",
"0 0 2 0\n",
"0 0 2 1\n",
"0 0 2 2\n",
"0 0 3 0\n",
"0 0 3 1\n",
"0 0 3 2\n",
"0 1 0 0\n",
"0 1 0 1\n",
"0 1 0 2\n",
"0 1 1 0\n",
"0 1 1 1\n"
]
}
],
"source": [
"#set empty board and empty condition\n",
"b=np.zeros([5,5])\n",
"condition=np.zeros([5, 5], dtype=bool)\n",
"\n",
"#problem #28\n",
"#condition[1,0]=True\n",
"#condition[2,0]=True\n",
"#condition[2,2]=True\n",
"#condition[0,3]=True\n",
"#condition[2,3]=True\n",
"\n",
"#problem #30\n",
"#condition[2,0]=True\n",
"#condition[1,2]=True\n",
"#condition[3,2]=True\n",
"#condition[0,4]=True\n",
"#condition[4,4]=True\n",
"\n",
"#problem #44\n",
"#condition[1,0]=True\n",
"#condition[1,2]=True\n",
"#condition[3,2]=True\n",
"#condition[2,4]=True\n",
"#condition[3,4]=True\n",
"\n",
"#problem #58\n",
"condition[1,1]=True\n",
"condition[2,1]=True\n",
"condition[2,2]=True\n",
"condition[3,3]=True\n",
"\n",
"#problem #59\n",
"# condition[1,0]=True\n",
"# condition[2,0]=True\n",
"# condition[0,3]=True\n",
"# condition[1,3]=True\n",
"\n",
"#basic testing, set second piece on board based on condition\n",
"from itertools import product\n",
"for i,j,r,e in product(range(4),range(4),range(4),range(len(p2))):\n",
" print(i,j,r,e)\n",
" if set_piece(b,p2[e],loc=(i,j),rot=r,condition=condition):\n",
" #print i,j,t,r,e\n",
" break"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"array([[ 0., 1., 1., 0., 0.],\n",
" [ 0., 16., 1., 1., 0.],\n",
" [ 0., 0., 0., 0., 0.],\n",
" [ 0., 0., 0., 0., 0.],\n",
" [ 0., 0., 0., 0., 0.]])"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"b"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"array([ 16., 0., 0., 0.])"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# list all cells with penguin locations, whether set or not\n",
"b[condition]"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"array([[False, False, False, False, False],\n",
" [False, True, False, False, False],\n",
" [False, True, True, False, False],\n",
" [False, False, False, True, False],\n",
" [False, False, False, False, False]], dtype=bool)"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"condition"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false,
"scrolled": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"solved 5\n",
"CPU times: user 4.7 s, sys: 15.7 ms, total: 4.71 s\n",
"Wall time: 4.67 s\n"
]
}
],
"source": [
"%%time\n",
"\n",
"#main algorithm for backtracking solver\n",
"\n",
"b=np.zeros([5,5])\n",
"\n",
"#paths visited in tree\n",
"paths=[{},{},{},{},{}]\n",
"solved=False\n",
"\n",
"#sequence of pieces to set\n",
"pieces=[p5,p4,p3,p2,p1]\n",
"\n",
"#path depth\n",
"pn=0\n",
"\n",
"#sequence of board positions\n",
"bhist=[b.copy()]\n",
"\n",
"#set of pieces set on board\n",
"phist=[]\n",
"\n",
"\n",
"#iterate until solved or exhausted all options\n",
"while 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()"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[]"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# no pieces left\n",
"pieces"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[{(0, 0, 2, 0): True,\n",
" (0, 1, 1, 0): True,\n",
" (0, 1, 1, 1): True,\n",
" (0, 1, 3, 1): True},\n",
" {(2, 0, 0, 0): True},\n",
" {(0, 2, 2, 0): True, (0, 3, 1, 0): True},\n",
" {(3, 2, 0, 2): True},\n",
" {(0, 0, 3, 1): True}]"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# paths tried on last leaves of tree\n",
"\n",
"paths"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[ 0. 0. 0. 0. 0.]\n",
" [ 0. 0. 0. 0. 0.]\n",
" [ 0. 0. 0. 0. 0.]\n",
" [ 0. 0. 0. 0. 0.]\n",
" [ 0. 0. 0. 0. 0.]]\n",
"\n",
"[[ 0. 1. 1. 16. 0.]\n",
" [ 0. 0. 1. 1. 0.]\n",
" [ 0. 0. 0. 0. 0.]\n",
" [ 0. 0. 0. 0. 0.]\n",
" [ 0. 0. 0. 0. 0.]]\n",
"\n",
"[[ 0. 1. 1. 16. 0.]\n",
" [ 0. 0. 1. 1. 0.]\n",
" [ 0. 16. 0. 0. 0.]\n",
" [ 0. 1. 1. 0. 0.]\n",
" [ 1. 1. 0. 0. 0.]]\n",
"\n",
"[[ 0. 1. 1. 16. 1.]\n",
" [ 0. 0. 1. 1. 1.]\n",
" [ 0. 16. 16. 1. 1.]\n",
" [ 0. 1. 1. 0. 0.]\n",
" [ 1. 1. 0. 0. 0.]]\n",
"\n",
"[[ 0. 1. 1. 16. 1.]\n",
" [ 0. 0. 1. 1. 1.]\n",
" [ 0. 16. 16. 1. 1.]\n",
" [ 0. 1. 1. 16. 1.]\n",
" [ 1. 1. 1. 1. 1.]]\n",
"\n",
"[[ 1. 1. 1. 16. 1.]\n",
" [ 1. 16. 1. 1. 1.]\n",
" [ 1. 16. 16. 1. 1.]\n",
" [ 1. 1. 1. 16. 1.]\n",
" [ 1. 1. 1. 1. 1.]]\n",
"\n"
]
}
],
"source": [
"# sequence of setting pieces on the board starting from piece #1 (p1)\n",
"\n",
"for bi in bhist:\n",
" print(bi)\n",
" print()"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(108, 5, 5)\n",
"(128, 5, 5)\n",
"(120, 5, 5)\n",
"(120, 5, 5)\n",
"(160, 5, 5)\n"
]
}
],
"source": [
"# Setup all possible numpy arrays with board positions with only one piece on board\n",
"\n",
"b=np.zeros([5,5])\n",
"pnpl=[]\n",
"for pi,p in enumerate([p5,p4,p3,p2,p1]):\n",
" plist=[]\n",
" for i,j,r,e in product(range(4),range(4),\n",
" range(4),\n",
" range(len(p))):\n",
" b0=b.copy()\n",
" if set_piece(b0,p[e],loc=(i,j),rot=r):\n",
" plist.append(b0)\n",
" pnpl.append(np.array(plist))\n",
" print(pnpl[-1].shape)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(4400, 5, 5)\n",
"CPU times: user 177 ms, sys: 3.89 ms, total: 181 ms\n",
"Wall time: 181 ms\n"
]
}
],
"source": [
"%%time\n",
"# Find all board positions with pieces #1 and #2 on board without conflicts\n",
"b12=[]\n",
"for 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)\n",
"b12=np.array(b12)\n",
"print(b12.shape)"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"collapsed": false,
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(61056, 5, 5)\n",
"CPU times: user 24.4 s, sys: 19.4 ms, total: 24.4 s\n",
"Wall time: 24.4 s\n"
]
}
],
"source": [
"%%time\n",
"# Find all board positions with pieces #3, #4 and #5 on board without conflicts\n",
"b345=[]\n",
"for 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)\n",
"b345=np.array(b345)\n",
"print(b345.shape)"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(48568, 5, 5)\n",
"CPU times: user 1min 15s, sys: 11.8 ms, total: 1min 15s\n",
"Wall time: 1min 15s\n"
]
}
],
"source": [
"%%time\n",
"# Find all board positions with pieces #2, #3, #4 and #5 on board without conflicts\n",
"b2345=[]\n",
"for bi,bj in product(pnpl[1],b345):\n",
" board=bi+bj\n",
" if (board[(board==1) | (board==16)].size==20):\n",
" b2345.append(board)\n",
"b2345=np.array(b2345)\n",
"print(b2345.shape)"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(296, 5, 5)\n",
"CPU times: user 50.7 s, sys: 32 ms, total: 50.8 s\n",
"Wall time: 50.8 s\n"
]
}
],
"source": [
"%%time\n",
"# Find all board positions with all pieces on board without conflicts\n",
"ball=[]\n",
"for bi,bj in product(pnpl[0],b2345):\n",
" board=bi+bj\n",
" if (board[(board==1) | (board==16)].size==25):\n",
" ball.append(board)\n",
"ball=np.array(ball)\n",
"print(ball.shape)"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"(296,)"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ball[:,0,0].shape"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"array([False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, True, True, False,\n",
" False, False, False, False, False, False, False, True, True,\n",
" True, True, False, False, False, False, False, False, False,\n",
" False, False, True, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False, False,\n",
" False, False, False, False, False, False, False, False], dtype=bool)"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(ball[:,0,0]==16) & (ball[:,1,1]==16)"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 0 0 2\n",
"0 2 0 0\n",
"0 3 1 2\n",
"0 4 2 4\n",
"1 0 2 1\n",
"1 2 0 3\n",
"2 0 4 0\n",
"2 1 1 0\n",
"2 3 3 4\n",
"2 4 0 4\n",
"3 2 4 1\n",
"3 4 2 3\n",
"4 0 2 0\n",
"4 1 3 2\n",
"4 2 4 4\n",
"4 4 4 2\n"
]
}
],
"source": [
"#find all unique board positions, contrained by 2 pieces only!\n",
"\n",
"for a,b in product(range(5),range(5)):\n",
" for i,j in product(range(5),range(5)):\n",
" if abs(a-i)+abs(b-j)<2:\n",
" pass\n",
" else:\n",
" ix1=ball[:,a,b]==16\n",
" ix2=ball[:,i,j]==16\n",
" if ball[ix1 & ix2].size==25:\n",
" print(a,b,i,j)\n",
" #print(ball[ix1 & ix2])"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0 0 1 3 4 1\n",
"0 0 1 4 4 3\n",
"0 0 4 1 1 3\n",
"0 0 4 3 1 4\n",
"0 1 1 4 4 0\n",
"0 1 1 4 4 2\n",
"0 1 2 4 3 0\n",
"0 1 2 4 4 1\n",
"0 1 2 4 4 2\n",
"0 1 3 0 2 4\n",
"0 1 3 0 4 4\n",
"0 1 4 0 1 4\n",
"0 1 4 1 2 4\n",
"0 1 4 2 1 4\n",
"0 1 4 2 2 4\n",
"0 1 4 4 3 0\n",
"0 2 2 0 4 3\n",
"0 2 2 4 3 0\n",
"0 2 3 0 2 4\n",
"0 2 3 0 3 4\n",
"0 2 3 0 4 3\n",
"0 2 3 4 3 0\n",
"0 2 4 3 2 0\n",
"0 2 4 3 3 0\n",
"0 3 2 0 4 3\n",
"0 3 3 1 4 4\n",
"0 3 4 3 2 0\n",
"0 3 4 4 3 1\n",
"0 4 1 0 3 3\n",
"0 4 3 0 4 3\n",
"0 4 3 3 1 0\n",
"0 4 4 3 3 0\n",
"1 0 0 4 3 3\n",
"1 0 1 4 4 2\n",
"1 0 3 3 0 4\n",
"1 0 4 2 1 4\n",
"1 1 3 4 4 0\n",
"1 1 4 0 3 4\n",
"1 3 0 0 4 1\n",
"1 3 4 1 0 0\n",
"1 4 0 0 4 3\n",
"1 4 0 1 4 0\n",
"1 4 0 1 4 2\n",
"1 4 1 0 4 2\n",
"1 4 2 0 4 2\n",
"1 4 2 0 4 3\n",
"1 4 4 0 0 1\n",
"1 4 4 2 0 1\n",
"1 4 4 2 1 0\n",
"1 4 4 2 2 0\n",
"1 4 4 3 0 0\n",
"1 4 4 3 2 0\n",
"2 0 0 2 4 3\n",
"2 0 0 3 4 3\n",
"2 0 1 4 4 2\n",
"2 0 1 4 4 3\n",
"2 0 4 2 1 4\n",
"2 0 4 3 0 2\n",
"2 0 4 3 0 3\n",
"2 0 4 3 1 4\n",
"2 4 0 1 3 0\n",
"2 4 0 1 4 1\n",
"2 4 0 1 4 2\n",
"2 4 0 2 3 0\n",
"2 4 3 0 0 1\n",
"2 4 3 0 0 2\n",
"2 4 4 1 0 1\n",
"2 4 4 2 0 1\n",
"3 0 0 1 2 4\n",
"3 0 0 1 4 4\n",
"3 0 0 2 2 4\n",
"3 0 0 2 3 4\n",
"3 0 0 2 4 3\n",
"3 0 0 4 4 3\n",
"3 0 2 4 0 1\n",
"3 0 2 4 0 2\n",
"3 0 3 4 0 2\n",
"3 0 4 3 0 2\n",
"3 0 4 3 0 4\n",
"3 0 4 4 0 1\n",
"3 1 0 3 4 4\n",
"3 1 4 4 0 3\n",
"3 3 0 4 1 0\n",
"3 3 1 0 0 4\n",
"3 4 0 2 3 0\n",
"3 4 1 1 4 0\n",
"3 4 3 0 0 2\n",
"3 4 4 0 1 1\n",
"4 0 0 1 1 4\n",
"4 0 1 1 3 4\n",
"4 0 1 4 0 1\n",
"4 0 3 4 1 1\n",
"4 1 0 0 1 3\n",
"4 1 0 1 2 4\n",
"4 1 1 3 0 0\n",
"4 1 2 4 0 1\n",
"4 2 0 1 1 4\n",
"4 2 0 1 2 4\n",
"4 2 1 0 1 4\n",
"4 2 1 4 0 1\n",
"4 2 1 4 1 0\n",
"4 2 1 4 2 0\n",
"4 2 2 0 1 4\n",
"4 2 2 4 0 1\n",
"4 3 0 0 1 4\n",
"4 3 0 2 2 0\n",
"4 3 0 2 3 0\n",
"4 3 0 3 2 0\n",
"4 3 0 4 3 0\n",
"4 3 1 4 0 0\n",
"4 3 1 4 2 0\n",
"4 3 2 0 0 2\n",
"4 3 2 0 0 3\n",
"4 3 2 0 1 4\n",
"4 3 3 0 0 2\n",
"4 3 3 0 0 4\n",
"4 4 0 1 3 0\n",
"4 4 0 3 3 1\n",
"4 4 3 0 0 1\n",
"4 4 3 1 0 3\n"
]
}
],
"source": [
"#find all unique board positions, contrained by 3 pieces only!\n",
"\n",
"d=4\n",
"for k,l in product(range(5),range(5)):\n",
" for a,b in product(range(5),range(5)):\n",
" for i,j in product(range(5),range(5)):\n",
" if abs(a-i)+abs(b-j)<d:\n",
" pass\n",
" elif abs(a-k)+abs(b-l)<d:\n",
" pass\n",
" elif abs(i-k)+abs(j-l)<d:\n",
" pass\n",
" else:\n",
" ix1=ball[:,a,b]==16\n",
" ix2=ball[:,i,j]==16\n",
" ix3=ball[:,k,l]==16\n",
" if ball[ix1 & ix2 & ix3].size==25:\n",
" print(k,l,a,b,i,j)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.4.3"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment