-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathpyramid.html
331 lines (283 loc) · 16.5 KB
/
pyramid.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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>fritzm.github.io - Project Genius pyramid puzzle</title>
<meta name="description" content="">
<meta name="author" content="Fritz Mueller">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<!-- Le HTML5 shim, for IE6-8 support of HTML elements -->
<!--[if lt IE 9]>
<script src="https://fritzm.github.io/theme/html5.js"></script>
<![endif]-->
<!-- Le styles -->
<link href="https://fritzm.github.io/theme/bootstrap.min.css" rel="stylesheet">
<link href="https://fritzm.github.io/theme/bootstrap.min.responsive.css" rel="stylesheet">
<link href="https://fritzm.github.io/theme/local.css" rel="stylesheet">
<link href="https://fritzm.github.io/theme/pygments.css" rel="stylesheet">
<!-- Photoswipe -->
<link rel="stylesheet" href="https://fritzm.github.io/theme/photoswipe.css">
<link rel="stylesheet" href="https://fritzm.github.io/theme/default-skin/default-skin.css">
<script src="https://fritzm.github.io/theme/photoswipe.min.js"></script>
<script src="https://fritzm.github.io/theme/photoswipe-ui-default.min.js"></script>
<script src="https://fritzm.github.io/galleries.js"></script>
<script type="text/javascript">
var pswipe = function(gname, index) {
var pswpElement = document.querySelectorAll('.pswp')[0];
var items = galleries[gname];
var options = { index: index };
var gallery = new PhotoSwipe(pswpElement, PhotoSwipeUI_Default, items, options);
gallery.init();
};
</script>
<!-- So Firefox can bookmark->"abo this site" -->
<link href="https://fritzm.github.io/feeds/all.rss.xml" rel="alternate" title="fritzm.github.io" type="application/rss+xml">
</head>
<body>
<div class="navbar">
<div class="navbar-inner">
<div class="container">
<a class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse">
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</a>
<a class="brand" href="https://fritzm.github.io">fritzm.github.io</a>
<div class="nav-collapse">
<ul class="nav">
</ul>
</div>
</div>
</div>
</div>
<div class="container">
<div class="content">
<div class="row">
<div class="span9">
<div class='article'>
<div class="content-title">
<h1>Project Genius pyramid puzzle</h1>
Fri 26 February 2021
by <a class="url fn" href="https://fritzm.github.io/author/fritz-mueller.html">Fritz Mueller</a>
</div>
<div><p><em>[A catch-up article from Christmas, 2020]</em></p>
<p>My family knows I have a fondness for puzzles, so my son will typically gift me a few each year at Christmas.
Among the puzzles received this year was the <a href="https://www.amazon.com/Project-Genius-Teaser-Puzzle-Wooden/dp/B07794JV4F">Project Genius Pyramid</a>:</p>
<p><img src='/images/puzzles/pyramid-together_thumbnail_tall.jpeg' title='Project Genius pyramid puzzle, assembled' onclick='pswipe("puzzles",0);'/>
<img src='/images/puzzles/pyramid-apart_thumbnail_tall.jpeg' title='Project Genius pyramid puzzle, disassembled' onclick='pswipe("puzzles",1);'/></p>
<p>This is pretty entertaining to play with -- since the planes and angles are not orthogonal, the fits of the
pieces are less familiar, and I found it more difficult than usual to use "geometry brain" to think ahead
while exploring solutions.</p>
<p>I have recently been playing around a bit with Knuth's "Dancing Links" algorithm, described in his paper
<a href="https://arxiv.org/pdf/cs/0011047.pdf">here</a>. This is a relatively short paper, and if you are unfamiliar
with it I'll say I feel it is really worth a read! The gist is a relatively straightforward backtracking
algorithm for efficiently finding exact covers of binary matrices, packed with the usual Knuthian tricks and
insights. As many classes of problems lend themselves to expression as an exact cover over a set of
constraints, the algorithm has broad applications including tiling/packing problems (e.g. Pentominoes, Soma),
general n-Queens, Sudoku, logic puzzles, etc. Having coded up an implementation (on Github
<a href="https://github.com/fritzm/dlx">here</a>), it seemed it would be fun to extend it to explore the pyramid puzzle.</p>
<p>As a tiling puzzle, the first thing to understand was the cell geometry of the pieces and the space to be
filled. The base geometry here is an <a href="https://en.wikipedia.org/wiki/Tetrahedral-octahedral_honeycomb">alternated cubic
honeycomb</a>, composed of octahedra and
tetrahedra. The complex in this case is further sliced into layers which bisect each octahedron, resulting in
cells that are tetrahedra and upward- and downward- facing pyramids: </p>
<p><img style="display:block; margin-left:auto; margin-right:auto" src="/images/programming/Alternated_cubic_slab_honeycomb_thumbnail_tall.png" title="Trav-ler 5028 schematic"/></p>
<p>It turns out that the centers of these cells are arranged on a simple rectilinear lattice. The "flavor" (up-pyramid, down-pyramid, tetrahedron) of each cell is simply determined by its position in the lattice; for
a cell at coordinates <span class="math">\(x, y, z\)</span>:</p>
<div class="math">$$
\begin{equation}
\operatorname{\mathit{cell\ flavor}} =
\begin{cases}
\operatorname{\mathit{up-pyramid}} & \text{when}\ (x+z,y+z)\ \text{is}\ (even, even)\\
\operatorname{\mathit{down-pyramid}} & \text{when}\ (x+z,y+z)\ \text{is}\ (odd, odd)\\
\operatorname{\mathit{tetrahedron}} & \text{otherwise}
\end{cases}
\end{equation}
$$</div>
<p>So, a simple three-dimensional array and indexing scheme may be used to represent the puzzle space, so long
as sufficient care is taken with restricting possible piece placements to preserve flavor-invariance.</p>
<p>A further choice of the puzzle makers was to break a symmetry of the puzzle by choosing a layer height such
that the cell-center lattice, while rectilinear, is <em>not</em> cubic (the octahedra in the fundamental complex are
taller than they are wide/deep, and the tetrahedra are similarly stretched.) I am not sure whether this was
done to avoid having the final pyramid look too squat, or if it was done deliberately to reduce the solution
space. In any case, this means that we need only consider "right-side-up" and "upside-down" orientations of
each piece; the potential "sideways" orientations do not fit the puzzle space.</p>
<p>A final consideration for the solver is restriction to essentially unique solutions by elimination of rotations,
refections, and permutation of repeated pieces. This puzzle has some pieces that are chiral without reflected
versions, and no repeated pieces otherwise, so reflected and permuted solutions do not exist. To account for
rotations, I chose to restrict one piece ("E") to a single orientation (the "E" piece can only appear in
solutions in its right-side-up configuration, because if placed upside-down it blocks any other piece form
being able to occupy the apex of the pyramid).</p>
<p>These considerations were pretty straightforward to cast into code for the dancing-links solver; a subsequent
run quickly produced an atlas of <a href="https://fritzm.github.io/pyramid-slns.html"><strong>80 essentially unique solutions</strong></a>. When
physically replicating these with the puzzle, it takes a little practice to get used to moving from the
rectilinear cell-center space in which the solutions are printed to the isomorphic pyramid/tetrahedron space
in which the puzzle physically exists, but this becomes pretty easy once you've played around with it for a
bit.</p>
<p>Of the 80 solutions found by the program, only one seems to be generally known on the web, which is <a href="https://www.youtube.com/watch?v=lufGSoVIkn8">the one
published by the makers of the puzzle.</a> It is solution
30 as found by the program:</p>
<pre style="all:revert; font-family:'Courier New';">
#30:
┌───────────────┬───┐
│ A A A A │ B │
├───────┬───────┤ │ ┌───────┬───┐
│ H H │ E E │ B │ │ I I │ E │
│ ┌───┤ │ │ ├───┐ ├───┤ ┌───┐
│ H │ G │ E E │ B │ │ G │ I │ F │ │ I │
├───┤ ├───────┴───┤ │ ├───┘ │ └───┘
│ C │ G │ J J J │ │ G │ F F │
│ ├───┴───────┐ │ └───┴───────┘
│ C │ D D D │ J │
└───┴───────────┴───┘
</pre>
<p>For puzzle fans who may own this puzzle, here is an additional challenge based on some inspection of the
atlas: some solutions found by the program have a contained sub-puzzle of a smaller pyramid with base 2x3 (in
physical puzzle space, where the larger pyramid is considered to have base 3x3.) Can you find any?</p>
<script type="text/javascript">if (!document.getElementById('mathjaxscript_pelican_#%@#$@#')) {
var align = "center",
indent = "0em",
linebreak = "false";
if (false) {
align = (screen.width < 768) ? "left" : align;
indent = (screen.width < 768) ? "0em" : indent;
linebreak = (screen.width < 768) ? 'true' : linebreak;
}
var mathjaxscript = document.createElement('script');
mathjaxscript.id = 'mathjaxscript_pelican_#%@#$@#';
mathjaxscript.type = 'text/javascript';
mathjaxscript.src = 'https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.3/latest.js?config=TeX-AMS-MML_HTMLorMML';
var configscript = document.createElement('script');
configscript.type = 'text/x-mathjax-config';
configscript[(window.opera ? "innerHTML" : "text")] =
"MathJax.Hub.Config({" +
" config: ['MMLorHTML.js']," +
" TeX: { extensions: ['AMSmath.js','AMSsymbols.js','noErrors.js','noUndefined.js'], equationNumbers: { autoNumber: 'none' } }," +
" jax: ['input/TeX','input/MathML','output/HTML-CSS']," +
" extensions: ['tex2jax.js','mml2jax.js','MathMenu.js','MathZoom.js']," +
" displayAlign: '"+ align +"'," +
" displayIndent: '"+ indent +"'," +
" showMathMenu: true," +
" messageStyle: 'normal'," +
" tex2jax: { " +
" inlineMath: [ ['\\\\(','\\\\)'] ], " +
" displayMath: [ ['$$','$$'] ]," +
" processEscapes: true," +
" preview: 'TeX'," +
" }, " +
" 'HTML-CSS': { " +
" availableFonts: ['STIX', 'TeX']," +
" preferredFont: 'STIX'," +
" styles: { '.MathJax_Display, .MathJax .mo, .MathJax .mi, .MathJax .mn': {color: 'inherit ! important'} }," +
" linebreaks: { automatic: "+ linebreak +", width: '90% container' }," +
" }, " +
"}); " +
"if ('default' !== 'default') {" +
"MathJax.Hub.Register.StartupHook('HTML-CSS Jax Ready',function () {" +
"var VARIANT = MathJax.OutputJax['HTML-CSS'].FONTDATA.VARIANT;" +
"VARIANT['normal'].fonts.unshift('MathJax_default');" +
"VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
"VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
"VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
"});" +
"MathJax.Hub.Register.StartupHook('SVG Jax Ready',function () {" +
"var VARIANT = MathJax.OutputJax.SVG.FONTDATA.VARIANT;" +
"VARIANT['normal'].fonts.unshift('MathJax_default');" +
"VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
"VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
"VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
"});" +
"}";
(document.body || document.getElementsByTagName('head')[0]).appendChild(configscript);
(document.body || document.getElementsByTagName('head')[0]).appendChild(mathjaxscript);
}
</script></div>
<hr>
</div>
</div>
<div class="span3">
<div class="well" style="padding: 8px 0; background-color: #FBFBFB;">
<ul class="nav nav-list">
<li class="nav-header">
Site
</li>
<li><a href="https://fritzm.github.io/archives.html">Archives</a>
<li><a href="https://fritzm.github.io/tags.html">Tags</a>
<li><a href="https://fritzm.github.io/feeds/all.rss.xml" rel="alternate">RSS feed</a></li>
</ul>
</div>
<div class="well" style="padding: 8px 0; background-color: #FBFBFB;">
<ul class="nav nav-list">
<li class="nav-header">
Categories
</li>
<li><a href="https://fritzm.github.io/category/arcade-games.html">Arcade Games</a></li>
<li><a href="https://fritzm.github.io/category/math.html">Math</a></li>
<li><a href="https://fritzm.github.io/category/micros.html">Micros</a></li>
<li><a href="https://fritzm.github.io/category/pdp-11.html">PDP-11</a></li>
<li><a href="https://fritzm.github.io/category/programming.html">Programming</a></li>
<li><a href="https://fritzm.github.io/category/radios.html">Radios</a></li>
</ul>
</div>
<div class="social">
<div class="well" style="padding: 8px 0; background-color: #FBFBFB;">
<ul class="nav nav-list">
<li class="nav-header">
Social
</li>
<li><a href="http://facebook.com/fritzmueller">facebook</a></li>
<li><a href="http://instagram.com/infrafritz">Instagram</a></li>
<li><a href="http://www.linkedin.com/pub/fritz-mueller/a/679/62/">LinkedIn</a></li>
<li><a href="http://jsfiddle.net/user/fritzm/fiddles/">JSFiddle</a></li>
<li><a href="https://github.com/fritzm">GitHub</a></li>
</ul>
</div>
</div>
</div>
</div> </div>
<footer>
<br />
<p><a href="https://fritzm.github.io">fritzm.github.io</a> © Fritz Mueller 2023</p>
</footer>
</div> <!-- /container -->
<!-- Photoswipe -->
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">
<div class="pswp__bg"></div>
<div class="pswp__scroll-wrap">
<div class="pswp__container">
<div class="pswp__item"></div>
<div class="pswp__item"></div>
<div class="pswp__item"></div>
</div>
<div class="pswp__ui pswp__ui--hidden">
<div class="pswp__top-bar">
<div class="pswp__counter"></div>
<button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
<button class="pswp__button pswp__button--share" title="Share"></button>
<button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
<button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
<div class="pswp__preloader">
<div class="pswp__preloader__icn">
<div class="pswp__preloader__cut">
<div class="pswp__preloader__donut"></div>
</div>
</div>
</div>
</div>
<div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
<div class="pswp__share-tooltip"></div>
</div>
<button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
</button>
<button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
</button>
<div class="pswp__caption">
<div class="pswp__caption__center"></div>
</div>
</div>
</div>
</div>
<script src="http://ajax.googleapis.com/ajax/libs/jquery/1.7.1/jquery.min.js"></script>
<script src="https://fritzm.github.io/theme/bootstrap-collapse.js"></script>
</body>
</html>