Sinds 2012 heb ik regelmatig Raspberry Pi’s (B en B+) in m’n handen. Het grootste gedeelte wordt direct in een bruikbare omgeving ingezet voor o.a. monitoring.
Recentelijk ook maar eens een Rpi 2 aangeschaft. En omdat het er wel fancy uit ziet, ook maar meteen een Sense Hat. Vol met handige sensoren en een 8×8 LED matrix. De voor geïnstalleerde voorbeelden bij de Sense Hat leverde niet veel spectaculairs op, anders dan even te zien en te ervaren wat de sensoren in hun mars hadden en hoe de Sense Hat bibliotheek gebruikt kon worden.
Op zoek naar een andere toepassing liep ik tegen een oude bekende aan: pentomino’s. Tijdens de studie in een functionele programmeertaal al een algoritme moeten schrijven om zo snel en efficiënt mogelijk alle oplossingen te vinden voor een bepaald bord. Een mooie uitleg over pentomino’s vind je hier (in het engels). In principe voldoet elk bord dat een matrix biedt van 60 cellen een goede start voor het oplossing van het pentomino probleem. Echter, de Sense Hat heeft een matrix van 8×8, waardoor dit het enige bord is dat visueel opgelost kan worden. Er moeten dan wel 4 ‘gaten’ gemaakt worden in het bord om aan de benodigde 60 cellen te komen.
Een algoritme was zo gevonden. Met een reeks kleine aanpassingen was het ook mogelijk om dit te visualiseren op de Sense Hat, resulterend in onderstaande code.
Als de Sense Hat software correct is geïnstalleerd, zal deze code ‘out-of-the-box’ werken. Aan de commandline kunnen nog een 3-tal parameters meegegeven worden:
- -a: animatie van het zoekalgoritme
- -h: een selectie van de gaten in het bord. De opties zijn 1, 2, 3 of 4.
- -m: maximum aantal te tonen oplossingen. 0 voor alle oplossingen.
<pre>
#!/usr/bin/python3
# Used part of the code from
# Jean-Claude Rimbault (pynokio.org, 2005)
from sense_hat import SenseHat
from time import sleep
import sys, getopt, signal
sense = SenseHat()
# Only 8x8 boards work for SenseHat
w, h = 8, 8
# All twelve pentominoes
pentominos = [ 'F', 'I', 'L', 'N', 'P', 'S', 'T', 'U', 'V', 'W', 'X', 'Y' ]
# All variants of the twelve pentominoes (mirrored, rotated)
shapes = {
'F': ((0, 1, -9, 2, 12),
(0, 1, 11, 2, -8),
(0, 10, 11, 21, 12),
(0, -10, -9, -19, -8),
(0, 1, 11, 21, 12),
(0, 1, -9, -19, -8),
(0, 1, 11, -9, 12),
(0, 1, 11, -9, -8)),
'I': ((0, 1, 2, 3, 4),
(0, 10, 20, 30, 40)),
'L': ((0, 1, 2, 3, 13),
(0, 1, 2, 3, -7),
(0, 10, 20, 30, 1),
(0, -10, -20, -30, 1),
(0, 1, 11, 21, 31),
(0, 1, -9, -19, -29),
(0, 10, 1, 2, 3),
(0, -10, 1, 2, 3)),
'N': ((0, 1, 11, 12, 13),
(0, 1, -9, -8, -7),
(0, 1, 2, 12, 13),
(0, 1, 2, -8, -7),
(0, 10, 20, 21, 31),
(0, 10, 20, 19, 29),
(0, 10, 11, 21, 31),
(0, 10, 9, 19, 29)),
'P': ((0, 1, 2, 11, 12),
(0, 1, 2, -9, -8),
(0, 1, 2, 10, 11),
(0, 1, 2, -10, -9),
(0, 1, 10, 11, 20),
(0, 1, 10, 11, 21),
(0, 1, -10, -9, -20),
(0, 1, -10, -9, -19)),
'S': ((0, 1, 11, 21, 22),
(0, 1, -9, -19, -18),
(0, 10, 11, 12, 22),
(0, -10, -9, -8, -18)),
'T': ((0, 1, 11, 21, 2),
(0, 1, -9, -19, 2),
(0, 1, 2, -8, 12),
(0, 10, -10, 1, 2)),
'U': ((0, 1, 10, 20, 21),
(0, 1, 11, 20, 21),
(0, -10, -9, -8, 2),
(0, 10, 11, 12, 2)),
'V': ((0, 1, 2, 12, 22),
(0, 1, 2, -8, -18),
(0, 1, 2, 10, 20),
(0, 1, 2, -10, -20)),
'W': ((0, 1, 11, 12, 22),
(0, 1, -9, -8, -18),
(0, 10, 11, 21, 22),
(0, -10, -9, -19, -18)),
'X': ((0, -9, 1, 11, 2),),
'Y': ((0, 1, 2, 3, 12),
(0, 1, 2, 3, -8),
(0, 10, 20, 30, 11),
(0, -10, -20, -30, -9),
(0, 1, 11, 21, -9),
(0, 1, -9, -19, 11),
(0, 11, 1, 2, 3),
(0, -9, 1, 2, 3))
}
colors = {
' ': (0,0,0),
'.': (0,0,0),
'F': (200,200,0),
'I': (0,200,0),
'L': (255,150,150),
'N': (150,255,150),
'P': (0,0,200),
'S': (150,255,255),
'T': (150,150,255),
'U': (0,200,200),
'V': (200,0,200),
'W': (255,150,255),
'X': (200,0,0),
'Y': (255,255,150),
}
board = ['#'] * 115
holes = 1
animate = 0
maxsolutions = 10
foundsolutions = 0
def initboard():
for row in range(w):
for col in range(h):
board[row*10+col+11] = ' '
# Holes in the board (exactly 4 needs to be defined to get solutions)
if holes == 1:
# 1
h1 = 0
h2 = 7
elif holes == 2:
# 2
h1 = 1
h2 = 6
elif holes == 3:
# 3
h1 = 2
h2 = 5
else:
# 4
h1 = 3
h2 = 4
board[h1*10+h1+11] = '.'
board[h1*10+h2+11] = '.'
board[h2*10+h1+11] = '.'
board[h2*10+h2+11] = '.'
def display(realsolution):
for col in range(h):
for row in range(w):
c = colors[board[row*10+col+11]]
sense.set_pixel(row,col,c)
if realsolution == 1:
print(board[row*10+col+11] + " ", end='')
if realsolution == 1:
print()
sleep(0.01)
def resetdisplay():
input("Press Enter clear the Sense Hat leds...")
for col in range(h):
for row in range(w):
sense.set_pixel(row,col,(0,0,0))
def solve():
global foundsolutions
for q in range(len(board)):
if board[q] == ' ':
# Iterate over the pentominoes
for p in pentominos:
# Iterate over the different shapes
for s in shapes[p]:
# Iterate over each rotation/mirrorred version
for c in s:
for d in s:
if board[q+d-c] != ' ':
break
else:
for d in s:
board[q+d-c] = p
i = pentominos.index(p)
pentominos.remove(p)
if not pentominos:
foundsolutions += 1
print("Found a solution " + str(foundsolutions))
display(1)
if (maxsolutions != 0):
if foundsolutions &gt;= maxsolutions:
resetdisplay()
sys.exit(1)
else:
if animate:
display(0)
solve()
pentominos.insert(i, p)
for d in s:
board[q+d-c] = ' '
return
def sigint_handler(signum, frame):
print("Solving puzzle interrupted by user")
resetdisplay()
sys.exit(1)
def main(argv):
global animate, maxsolutions, holes
try:
opts, args = getopt.getopt(argv, "m:h:a")
except getopt.GetoptError:
print("pentominos.py -m &amp;lt;maxsolutions&gt; -h &amp;lt;holes&gt; -a")
print(" -a : animate solution search")
print(" -h holes : may be 1, 2, 3 or 4. Each one takes out 4 cells from the board")
print(" -m maxsolutions: if 0 all solutions are shown. Otherwise it stops at the given maximum")
sys.exit(2)
for opt, arg in opts:
if opt == '-a':
animate = 1
elif opt == '-m':
maxsolutions = int(arg)
elif opt == '-h':
holes = int(arg)
if animate == 1:
print("Running with animation, max solutions is " + str(maxsolutions))
else:
print("Showing only solutions, max solutions is " + str(maxsolutions))
signal.signal(signal.SIGINT, sigint_handler)
if __name__ == "__main__":
main(sys.argv[1:])
initboard()
solve()
resetdisplay()
</pre>
<pre class="wp-block-syntaxhighlighter-code">