-
Notifications
You must be signed in to change notification settings - Fork 26
/
blockparty.html
104 lines (87 loc) · 3.05 KB
/
blockparty.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
<!DOCTYPE html>
<html>
<head>
<title>Puzzle: Block Party</title>
<link rel="stylesheet" type="text/css" href="style.css">
<style>
table {
margin-left: 3em;
}
td {
text-align: center;
padding: 0 .6em;
}
.times {
font-size: 85%;
padding: 0 .1em;
line-height: 0;
vertical-align: baseline;
position: relative;
top: -.1em;
}
</style>
<body>
<p class="subtle"><a href="/">« Boston Python puzzles</a></p>
<h1>Block Party</h1>
<p>Another little known use of Python programming is solving real-world block
puzzles.</p>
<p>Take for example the notoriously difficult
<a href="http://www.pavelspuzzles.com/2010/08/the_calibron_12block_puzzle.html">12-Block Calibron puzzle</a>.
It was invented by the son of Thomas Edison. Or at least, he got the credit for
it. (Like father, like son.)</p>
<p>It seems simple: you've got 12 rectangular tiles with these dimensions: </p>
<table>
<tr>
<td>32<span class="times">×</span>11</td>
<td>32<span class="times">×</span>10</td>
<td>28<span class="times">×</span>14</td>
<td>28<span class="times">×</span>7</td>
<td>28<span class="times">×</span>6</td>
<td>21<span class="times">×</span>18</td>
</tr>
<tr>
<td>21<span class="times">×</span>18</td>
<td>21<span class="times">×</span>14</td>
<td>21<span class="times">×</span>14</td>
<td>17<span class="times">×</span>14</td>
<td>14<span class="times">×</span>4</td>
<td>10<span class="times">×</span>7</td>
</tr>
</table>
<p>or, as a Python-ready list:</p>
<pre>
tiles = [
(32, 11),
(32, 10),
(28, 14),
(28, 7),
(28, 6),
(21, 18),
(21, 18),
(21, 14),
(21, 14),
(17, 14),
(14, 4),
(10, 7),
]
</pre>
<p>(Yes, there are duplicates in the list, you have pairs of blocks of the same
size.) All you have to do (ha!) is arrange them so they form a single rectangle
with no gaps.</p>
<p>The problem is that the search space is very big. So this cries out for a
computational approach.</p>
<p>1. What is the total surface area of the final solution?</p>
<p>2. OK that was easy. But how about the height and width of all possible (or
let's call them, potential) rectangle solutions? Write a program that generates
that list.</p>
<p>3. Finally, the really hard part. Write a program that searches for a
solution to the 12-Block Calibron puzzle. (Apparently there is only one.)</p>
<p>4. Bonus: How unique is the 12-Block Calibron within puzzle space? What
makes an n-block Calibron a good puzzle, that has one and only one solution?
Write a program that generates n-block Calibron puzzles.</p>
<h2>Solutions</h2>
<ul>
<li>Ned Batchelder's solution is <a href="https://github.com/BostonPython/puzzles/blob/gh-pages/solutions/nedbat/calibron.py">calibron.py</a></li>
<li>Andrew Ross's solution is <a href="https://github.com/BostonPython/puzzles/blob/gh-pages/solutions/asross/calibron.py">calibron.py</a></li>
</ul>
<p>If you have a solution you'd like to share see the <a href="solutions.html">Solutions page</a> for instructions.</p>