-
Notifications
You must be signed in to change notification settings - Fork 18
/
puzzle.html
562 lines (394 loc) · 40.3 KB
/
puzzle.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
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Depth First and Breadth First Search — US Pycon December 2019 documentation</title>
<link rel="stylesheet" href="_static/css/theme.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<link rel="index" title="Index" href="genindex.html" />
<link rel="search" title="Search" href="search.html" />
<link rel="next" title="SAT Solvers" href="einstein.html" />
<link rel="prev" title="Overview" href="overview.html" />
<script src="_static/js/modernizr.min.js"></script>
</head>
<body class="wy-body-for-nav">
<div class="wy-grid-for-nav">
<nav data-toggle="wy-nav-shift" class="wy-nav-side">
<div class="wy-side-scroll">
<div class="wy-side-nav-search">
<a href="index.html" class="icon icon-home"> US Pycon December 2019
</a>
</div>
<div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
<ul class="current">
<li class="toctree-l1"><a class="reference internal" href="overview.html">Overview</a></li>
<li class="toctree-l1 current"><a class="current reference internal" href="#">Depth First and Breath First Search</a><ul>
<li class="toctree-l2"><a class="reference internal" href="#overview">Overview</a></li>
<li class="toctree-l2"><a class="reference internal" href="#generic-puzzle-solver">Generic Puzzle Solver</a></li>
<li class="toctree-l2"><a class="reference internal" href="#jug-filling-problem">Jug Filling Problem</a></li>
<li class="toctree-l2"><a class="reference internal" href="#sliding-block-puzzle">Sliding Block Puzzle</a></li>
<li class="toctree-l2"><a class="reference internal" href="#core-logic">Core Logic</a></li>
<li class="toctree-l2"><a class="reference internal" href="#full-code-for-the-solver">Full Code for the Solver</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="einstein.html">SAT Solvers</a></li>
<li class="toctree-l1"><a class="reference internal" href="rock_paper.html">Pattern Recognition and Reinforcement Learning</a></li>
<li class="toctree-l1"><a class="reference internal" href="dining.html">SMT and Model Checkers</a></li>
<li class="toctree-l1"><a class="reference internal" href="alpha_zero.html">AlphaZero</a></li>
<li class="toctree-l1"><a class="reference internal" href="philosophy.html">The Future</a></li>
</ul>
</div>
</div>
</nav>
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">
<nav class="wy-nav-top" aria-label="top navigation">
<i data-toggle="wy-nav-top" class="fa fa-bars"></i>
<a href="index.html">US Pycon December 2019</a>
</nav>
<div class="wy-nav-content">
<div class="rst-content">
<div role="navigation" aria-label="breadcrumbs navigation">
<ul class="wy-breadcrumbs">
<li><a href="index.html">Docs</a> »</li>
<li>Depth First and Breath First Search</li>
<li class="wy-breadcrumbs-aside">
</li>
</ul>
<hr/>
</div>
<div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
<div itemprop="articleBody">
<div class="section" id="depth-first-and-breath-first-search">
<h1>Depth First and Breath First Search<a class="headerlink" href="#depth-first-and-breath-first-search" title="Permalink to this headline">¶</a></h1>
<div class="section" id="overview">
<h2>Overview<a class="headerlink" href="#overview" title="Permalink to this headline">¶</a></h2>
<p>A number of puzzles can be solved by either depth first search
or breadth first search.</p>
<p>Both are easy to implement using <code class="docutils literal notranslate"><span class="pre">collections.deque()</span></code>.</p>
<img alt="_images/depth_first_breadth_first.gif" src="_images/depth_first_breadth_first.gif" />
</div>
<div class="section" id="generic-puzzle-solver">
<h2>Generic Puzzle Solver<a class="headerlink" href="#generic-puzzle-solver" title="Permalink to this headline">¶</a></h2>
<p>Here I present a generic puzzle solver that works
on a broad class of puzzles.</p>
<p>The core idea is that we need very few things to describe
the puzzle in a way that a solver can find a solution:</p>
<ol class="arabic simple">
<li>We need an initial position (the unsolved puzzle)</li>
<li>We need a rule (typically an iterator) to generate
all possible moves from a position.</li>
<li>We need to recognize the goal state.</li>
</ol>
<p>Optionally, we can provide some extras:</p>
<ol class="arabic simple" start="4">
<li>A nice <code class="docutils literal notranslate"><span class="pre">__repr__</span></code> method to display the puzzle
position in a way recognizable to us.</li>
<li>A way to recognize that some positions are
considered to be equivalent and don’t need
to be explored twice (i.e. in tic-tac-toe,
all four corner opening moves essentially
describe the same).</li>
</ol>
</div>
<div class="section" id="jug-filling-problem">
<h2>Jug Filling Problem<a class="headerlink" href="#jug-filling-problem" title="Permalink to this headline">¶</a></h2>
<p><strong>Problem statement:</strong>
“Given a two empty jugs with 3 and 5 liter capacities and a full
jug with 8 liters, find a sequence of pours leaving four liters
in the two largest jugs.”</p>
<img alt="_images/jugs-problem.gif" src="_images/jugs-problem.gif" />
<p>How to code it:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">puzzle</span> <span class="k">import</span> <span class="n">Puzzle</span>
<span class="k">class</span> <span class="nc">JugFill</span><span class="p">(</span><span class="n">Puzzle</span><span class="p">):</span>
<span class="sd">'''Given a two empty jugs with 3 and 5 liter capacities and a full</span>
<span class="sd"> jug with 8 liters, find a sequence of pours leaving four liters</span>
<span class="sd"> in the two largest jugs.</span>
<span class="sd"> '''</span>
<span class="c1"># https://dioverdt.files.wordpress.com/2011/01/jugs-problem.gif</span>
<span class="n">pos</span> <span class="o">=</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">8</span><span class="p">)</span>
<span class="n">capacity</span> <span class="o">=</span> <span class="p">(</span><span class="mi">3</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">8</span><span class="p">)</span>
<span class="n">goal</span> <span class="o">=</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">4</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">__iter__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">pos</span><span class="p">)):</span>
<span class="k">for</span> <span class="n">j</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">pos</span><span class="p">)):</span>
<span class="k">if</span> <span class="n">i</span><span class="o">==</span><span class="n">j</span><span class="p">:</span> <span class="k">continue</span>
<span class="n">qty</span> <span class="o">=</span> <span class="nb">min</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">pos</span><span class="p">[</span><span class="n">i</span><span class="p">],</span> <span class="bp">self</span><span class="o">.</span><span class="n">capacity</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">-</span> <span class="bp">self</span><span class="o">.</span><span class="n">pos</span><span class="p">[</span><span class="n">j</span><span class="p">])</span>
<span class="k">if</span> <span class="ow">not</span> <span class="n">qty</span><span class="p">:</span> <span class="k">continue</span>
<span class="n">dup</span> <span class="o">=</span> <span class="nb">list</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">pos</span><span class="p">)</span>
<span class="n">dup</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">-=</span> <span class="n">qty</span>
<span class="n">dup</span><span class="p">[</span><span class="n">j</span><span class="p">]</span> <span class="o">+=</span> <span class="n">qty</span>
<span class="k">yield</span> <span class="n">JugFill</span><span class="p">(</span><span class="nb">tuple</span><span class="p">(</span><span class="n">dup</span><span class="p">))</span>
<span class="k">if</span> <span class="vm">__name__</span> <span class="o">==</span> <span class="s1">'__main__'</span><span class="p">:</span>
<span class="kn">from</span> <span class="nn">pprint</span> <span class="k">import</span> <span class="n">pprint</span>
<span class="n">pprint</span><span class="p">(</span><span class="n">JugFill</span><span class="p">()</span><span class="o">.</span><span class="n">solve</span><span class="p">())</span>
</pre></div>
</div>
<p>How a puzzle instance works:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="gp">>>> </span><span class="kn">from</span> <span class="nn">pprint</span> <span class="k">import</span> <span class="n">pprint</span>
<span class="gp">>>> </span><span class="kn">from</span> <span class="nn">jug_fill</span> <span class="k">import</span> <span class="n">JugFill</span>
<span class="gp">>>> </span><span class="n">p</span> <span class="o">=</span> <span class="n">JugFill</span><span class="p">()</span> <span class="c1"># Make a fresh puzzle</span>
<span class="gp">>>> </span><span class="nb">print</span><span class="p">(</span><span class="n">p</span><span class="p">)</span> <span class="c1"># Display the current position</span>
<span class="go">(0, 0, 8)</span>
<span class="gp">>>> </span><span class="n">p</span><span class="o">.</span><span class="n">isgoal</span><span class="p">()</span> <span class="c1"># Are we at the goal state?</span>
<span class="go">False</span>
<span class="gp">>>> </span><span class="k">for</span> <span class="n">move</span> <span class="ow">in</span> <span class="n">p</span><span class="p">:</span> <span class="c1"># Display possible moves</span>
<span class="gp">... </span> <span class="nb">print</span><span class="p">(</span><span class="n">move</span><span class="p">)</span>
<span class="gp">...</span>
<span class="go">(3, 0, 5)</span>
<span class="go">(0, 5, 3)</span>
</pre></div>
</div>
<p>Running the <em>solve()</em> method immediately generates a solution:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">8</span><span class="p">),</span>
<span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">3</span><span class="p">),</span>
<span class="p">(</span><span class="mi">3</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">),</span>
<span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">6</span><span class="p">),</span>
<span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="mi">6</span><span class="p">),</span>
<span class="p">(</span><span class="mi">2</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">1</span><span class="p">),</span>
<span class="p">(</span><span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">1</span><span class="p">),</span>
<span class="p">(</span><span class="mi">0</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">4</span><span class="p">)]</span>
</pre></div>
</div>
</div>
<div class="section" id="sliding-block-puzzle">
<h2>Sliding Block Puzzle<a class="headerlink" href="#sliding-block-puzzle" title="Permalink to this headline">¶</a></h2>
<p><strong>Problem statement:</strong>
“Slide blocks within a fixed grid so that the largest block
ends-up in the lower left corner.”</p>
<img alt="_images/quzzle.jpg" src="_images/quzzle.jpg" />
<p>How to code it:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">from</span> <span class="nn">puzzle</span> <span class="k">import</span> <span class="n">Puzzle</span>
<span class="kn">import</span> <span class="nn">re</span>
<span class="k">class</span> <span class="nc">PaPuzzle</span><span class="p">(</span><span class="n">Puzzle</span><span class="p">):</span>
<span class="sd">''' PaPuzzle</span>
<span class="sd"> This sliding block puzzle has 9 blocks of varying sizes:</span>
<span class="sd"> one 2x2, four 1x2, two 2x1, and two 1x1. The blocks are</span>
<span class="sd"> on a 5x4 grid with two empty 1x1 spaces. Starting from</span>
<span class="sd"> the position shown, slide the blocks around until the</span>
<span class="sd"> 2x2 is in the lower left:</span>
<span class="sd"> 1122</span>
<span class="sd"> 1133</span>
<span class="sd"> 45</span>
<span class="sd"> 6788</span>
<span class="sd"> 6799</span>
<span class="sd"> '''</span>
<span class="n">pos</span> <span class="o">=</span> <span class="s1">'11221133450067886799'</span>
<span class="n">goal</span> <span class="o">=</span> <span class="n">re</span><span class="o">.</span><span class="n">compile</span><span class="p">(</span> <span class="sa">r</span><span class="s1">'................1...'</span> <span class="p">)</span>
<span class="k">def</span> <span class="nf">isgoal</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">goal</span><span class="o">.</span><span class="n">search</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">pos</span><span class="p">)</span> <span class="o">!=</span> <span class="kc">None</span>
<span class="k">def</span> <span class="nf">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="n">ans</span> <span class="o">=</span> <span class="s1">'</span><span class="se">\n</span><span class="s1">'</span>
<span class="n">pos</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">pos</span><span class="o">.</span><span class="n">replace</span><span class="p">(</span><span class="s1">'0'</span><span class="p">,</span> <span class="s1">'.'</span><span class="p">)</span>
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">8</span><span class="p">,</span> <span class="mi">12</span><span class="p">,</span> <span class="mi">16</span><span class="p">]:</span>
<span class="n">ans</span> <span class="o">=</span> <span class="n">ans</span> <span class="o">+</span> <span class="n">pos</span><span class="p">[</span><span class="n">i</span><span class="p">:</span><span class="n">i</span><span class="o">+</span><span class="mi">4</span><span class="p">]</span> <span class="o">+</span> <span class="s1">'</span><span class="se">\n</span><span class="s1">'</span>
<span class="k">return</span> <span class="n">ans</span>
<span class="n">xlat</span> <span class="o">=</span> <span class="nb">str</span><span class="o">.</span><span class="n">maketrans</span><span class="p">(</span><span class="s1">'38975'</span><span class="p">,</span><span class="s1">'22264'</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">canonical</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">pos</span><span class="o">.</span><span class="n">translate</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">xlat</span><span class="p">)</span>
<span class="n">block</span> <span class="o">=</span> <span class="p">{</span> <span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="o">-</span><span class="mi">4</span><span class="p">),</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="o">-</span><span class="mi">4</span><span class="p">),</span> <span class="p">(</span><span class="mi">2</span><span class="p">,</span><span class="o">-</span><span class="mi">4</span><span class="p">),</span> <span class="p">(</span><span class="mi">3</span><span class="p">,</span><span class="o">-</span><span class="mi">4</span><span class="p">),</span>
<span class="p">(</span><span class="mi">16</span><span class="p">,</span><span class="mi">4</span><span class="p">),</span> <span class="p">(</span><span class="mi">17</span><span class="p">,</span><span class="mi">4</span><span class="p">),</span> <span class="p">(</span><span class="mi">18</span><span class="p">,</span><span class="mi">4</span><span class="p">),</span> <span class="p">(</span><span class="mi">19</span><span class="p">,</span><span class="mi">4</span><span class="p">),</span>
<span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="mi">4</span><span class="p">,</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="mi">8</span><span class="p">,</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="mi">12</span><span class="p">,</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="mi">16</span><span class="p">,</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span>
<span class="p">(</span><span class="mi">3</span><span class="p">,</span><span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="mi">7</span><span class="p">,</span><span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="mi">11</span><span class="p">,</span><span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="mi">15</span><span class="p">,</span><span class="mi">1</span><span class="p">),</span> <span class="p">(</span><span class="mi">19</span><span class="p">,</span><span class="mi">1</span><span class="p">)</span> <span class="p">}</span>
<span class="k">def</span> <span class="nf">__iter__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="n">dsone</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">pos</span><span class="o">.</span><span class="n">find</span><span class="p">(</span><span class="s1">'0'</span><span class="p">)</span>
<span class="n">dstwo</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">pos</span><span class="o">.</span><span class="n">find</span><span class="p">(</span><span class="s1">'0'</span><span class="p">,</span> <span class="n">dsone</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span>
<span class="k">for</span> <span class="n">dest</span> <span class="ow">in</span> <span class="p">[</span><span class="n">dsone</span><span class="p">,</span> <span class="n">dstwo</span><span class="p">]:</span>
<span class="k">for</span> <span class="n">adj</span> <span class="ow">in</span> <span class="p">[</span><span class="o">-</span><span class="mi">4</span><span class="p">,</span> <span class="o">-</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">4</span><span class="p">]:</span>
<span class="k">if</span> <span class="p">(</span><span class="n">dest</span><span class="p">,</span> <span class="n">adj</span><span class="p">)</span> <span class="ow">in</span> <span class="bp">self</span><span class="o">.</span><span class="n">block</span><span class="p">:</span> <span class="k">continue</span>
<span class="n">piece</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">pos</span><span class="p">[</span><span class="n">dest</span><span class="o">+</span><span class="n">adj</span><span class="p">]</span>
<span class="k">if</span> <span class="n">piece</span> <span class="o">==</span> <span class="s1">'0'</span><span class="p">:</span> <span class="k">continue</span>
<span class="n">newmove</span> <span class="o">=</span> <span class="bp">self</span><span class="o">.</span><span class="n">pos</span><span class="o">.</span><span class="n">replace</span><span class="p">(</span><span class="n">piece</span><span class="p">,</span> <span class="s1">'0'</span><span class="p">)</span>
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">20</span><span class="p">):</span>
<span class="k">if</span> <span class="mi">0</span> <span class="o"><=</span> <span class="n">i</span><span class="o">+</span><span class="n">adj</span> <span class="o"><</span> <span class="mi">20</span> <span class="ow">and</span> <span class="bp">self</span><span class="o">.</span><span class="n">pos</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">adj</span><span class="p">]</span><span class="o">==</span><span class="n">piece</span><span class="p">:</span>
<span class="n">newmove</span> <span class="o">=</span> <span class="n">newmove</span><span class="p">[:</span><span class="n">i</span><span class="p">]</span> <span class="o">+</span> <span class="n">piece</span> <span class="o">+</span> <span class="n">newmove</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">:]</span>
<span class="k">if</span> <span class="n">newmove</span><span class="o">.</span><span class="n">count</span><span class="p">(</span><span class="s1">'0'</span><span class="p">)</span> <span class="o">!=</span> <span class="mi">2</span><span class="p">:</span> <span class="k">continue</span>
<span class="k">yield</span> <span class="n">PaPuzzle</span><span class="p">(</span><span class="n">newmove</span><span class="p">)</span>
<span class="k">if</span> <span class="vm">__name__</span> <span class="o">==</span> <span class="s1">'__main__'</span><span class="p">:</span>
<span class="kn">from</span> <span class="nn">pprint</span> <span class="k">import</span> <span class="n">pprint</span>
<span class="n">pprint</span><span class="p">(</span><span class="n">PaPuzzle</span><span class="p">()</span><span class="o">.</span><span class="n">solve</span><span class="p">())</span>
</pre></div>
</div>
<p>Output:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="p">[</span>
<span class="mi">1122</span>
<span class="mi">1133</span>
<span class="mf">45.</span><span class="o">.</span>
<span class="mi">6788</span>
<span class="mi">6799</span>
<span class="p">,</span>
<span class="mi">1122</span>
<span class="mi">1133</span>
<span class="mf">4.5</span><span class="o">.</span>
<span class="mi">6788</span>
<span class="mi">6799</span>
<span class="p">,</span>
<span class="o">--</span> <span class="o">...</span> <span class="o">---</span>
<span class="mi">7633</span>
<span class="mi">7622</span>
<span class="mi">1154</span>
<span class="mi">1199</span>
<span class="o">..</span><span class="mi">88</span>
<span class="p">,</span>
<span class="mi">7633</span>
<span class="mi">7622</span>
<span class="o">..</span><span class="mi">54</span>
<span class="mi">1199</span>
<span class="mi">1188</span>
<span class="p">]</span>
</pre></div>
</div>
</div>
<div class="section" id="core-logic">
<h2>Core Logic<a class="headerlink" href="#core-logic" title="Permalink to this headline">¶</a></h2>
<p>The only essential Python tool you need is <code class="docutils literal notranslate"><span class="pre">collections.deque()</span></code>,
the double ended queue.</p>
<p>For a breadth first search, we <em>pop</em> an unexplored positions off
of a deque. For each position, we generate the next possible
moves and <em>prepend</em> them to the deque of unexplored move.</p>
<p>For a depth first search, we <em>append</em> rather than prepend.</p>
<p>To make it possible to replay the sequence of moves,
we keep a <em>trail</em> dictionary that maps each move to
its predecessor.</p>
<p>As an optimization, we call an optional user supplied
<em>canonical()</em> method to see if the current position
is equivalent to one that we’ve already explored.</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">solve</span><span class="p">(</span><span class="n">pos</span><span class="p">,</span> <span class="n">depthFirst</span><span class="o">=</span><span class="kc">False</span><span class="p">):</span>
<span class="n">queue</span> <span class="o">=</span> <span class="n">deque</span><span class="p">([</span><span class="n">pos</span><span class="p">])</span>
<span class="n">trail</span> <span class="o">=</span> <span class="p">{</span><span class="n">intern</span><span class="p">(</span><span class="n">pos</span><span class="o">.</span><span class="n">canonical</span><span class="p">()):</span> <span class="kc">None</span><span class="p">}</span>
<span class="n">solution</span> <span class="o">=</span> <span class="n">deque</span><span class="p">()</span>
<span class="n">load</span> <span class="o">=</span> <span class="n">queue</span><span class="o">.</span><span class="n">append</span> <span class="k">if</span> <span class="n">depthFirst</span> <span class="k">else</span> <span class="n">queue</span><span class="o">.</span><span class="n">appendleft</span>
<span class="k">while</span> <span class="ow">not</span> <span class="n">pos</span><span class="o">.</span><span class="n">isgoal</span><span class="p">():</span>
<span class="k">for</span> <span class="n">m</span> <span class="ow">in</span> <span class="n">pos</span><span class="p">:</span>
<span class="n">c</span> <span class="o">=</span> <span class="n">m</span><span class="o">.</span><span class="n">canonical</span><span class="p">()</span>
<span class="k">if</span> <span class="n">c</span> <span class="ow">in</span> <span class="n">trail</span><span class="p">:</span>
<span class="k">continue</span>
<span class="n">trail</span><span class="p">[</span><span class="n">intern</span><span class="p">(</span><span class="n">c</span><span class="p">)]</span> <span class="o">=</span> <span class="n">pos</span>
<span class="n">load</span><span class="p">(</span><span class="n">m</span><span class="p">)</span>
<span class="n">pos</span> <span class="o">=</span> <span class="n">queue</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span>
<span class="k">while</span> <span class="n">pos</span><span class="p">:</span>
<span class="n">solution</span><span class="o">.</span><span class="n">appendleft</span><span class="p">(</span><span class="n">pos</span><span class="p">)</span>
<span class="n">pos</span> <span class="o">=</span> <span class="n">trail</span><span class="p">[</span><span class="n">pos</span><span class="o">.</span><span class="n">canonical</span><span class="p">()]</span>
<span class="k">return</span> <span class="nb">list</span><span class="p">(</span><span class="n">solution</span><span class="p">)</span>
</pre></div>
</div>
</div>
<div class="section" id="full-code-for-the-solver">
<h2>Full Code for the Solver<a class="headerlink" href="#full-code-for-the-solver" title="Permalink to this headline">¶</a></h2>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="sd">''' Generic Puzzle Solving Framework</span>
<span class="sd">License: MIT</span>
<span class="sd">Author: Raymond Hettinger</span>
<span class="sd">Simple Instructions:</span>
<span class="sd">====================</span>
<span class="sd">Create your puzzle as a subclass of Puzzle().</span>
<span class="sd">The first step is to choose a representation of the problem</span>
<span class="sd">state preferably stored as a string. Set 'pos' to the starting</span>
<span class="sd">position and 'goal' to the ending position. Create an __iter__()</span>
<span class="sd">method that computes all possible new puzzle states reachable from</span>
<span class="sd">the current state. Call the .solve() method to solve the puzzle.</span>
<span class="sd">Important Note:</span>
<span class="sd">The __iter__() method must return a list or generator of puzzle</span>
<span class="sd">instances, not their representations.</span>
<span class="sd">Advanced Instructions:</span>
<span class="sd">1. .solve(depthFirst=1) will override the default breadth first search.</span>
<span class="sd">Use depth first when the puzzle known to be solved in a fixed number</span>
<span class="sd">of moves (for example, the eight queens problem is solved only when</span>
<span class="sd">the eighth queen is placed on the board; also, the triangle tee problem</span>
<span class="sd">removes one tee on each move until all tees are removed). Breadth first</span>
<span class="sd">is ideal when the shortest path solution needs to be found or when</span>
<span class="sd">some paths have a potential to wander around infinitely (i.e. you can</span>
<span class="sd">randomly twist a Rubik's cube all day and never come near a solution).</span>
<span class="sd">2. Define __repr__ for a pretty printed version of the current position.</span>
<span class="sd">The state for the Tee puzzle looks best when the full triangle is drawn.</span>
<span class="sd">3. If the goal state can't be defined as a string, override the isgoal()</span>
<span class="sd">method. For instance, the block puzzle is solved whenever block 1 is</span>
<span class="sd">in the lower left, it doesn't matter where the other pieces are; hence,</span>
<span class="sd">isgoal() is defined to check the lower left corner and return a boolean.</span>
<span class="sd">4. Some puzzle's can be simplified by treating symmetric positions as</span>
<span class="sd">equal. Override the .canonical() method to pick one of the equilavent</span>
<span class="sd">positions as a representative. This allows the solver to recognize paths</span>
<span class="sd">similar ones aleady explored. In tic-tac-toe an upper left corner on</span>
<span class="sd">the first move is symmetrically equivalent to a move on the upper right;</span>
<span class="sd">hence there are only three possible first moves (a corner, a midde side,</span>
<span class="sd">or in the center).</span>
<span class="sd">'''</span>
<span class="kn">from</span> <span class="nn">collections</span> <span class="k">import</span> <span class="n">deque</span>
<span class="kn">from</span> <span class="nn">sys</span> <span class="k">import</span> <span class="n">intern</span>
<span class="kn">import</span> <span class="nn">re</span>
<span class="k">class</span> <span class="nc">Puzzle</span><span class="p">:</span>
<span class="n">pos</span> <span class="o">=</span> <span class="s2">""</span> <span class="c1"># default starting position</span>
<span class="n">goal</span> <span class="o">=</span> <span class="s2">""</span> <span class="c1"># ending position used by isgoal()</span>
<span class="k">def</span> <span class="nf">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">pos</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
<span class="k">if</span> <span class="n">pos</span><span class="p">:</span> <span class="bp">self</span><span class="o">.</span><span class="n">pos</span> <span class="o">=</span> <span class="n">pos</span>
<span class="k">def</span> <span class="nf">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="c1"># returns a string representation of the position for printing the object</span>
<span class="k">return</span> <span class="nb">repr</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">pos</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">canonical</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="c1"># returns a string representation after adjusting for symmetry</span>
<span class="k">return</span> <span class="nb">repr</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span>
<span class="k">def</span> <span class="nf">isgoal</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="k">return</span> <span class="bp">self</span><span class="o">.</span><span class="n">pos</span> <span class="o">==</span> <span class="bp">self</span><span class="o">.</span><span class="n">goal</span>
<span class="k">def</span> <span class="nf">__iter__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span> <span class="c1"># returns list of objects of this class</span>
<span class="k">if</span> <span class="mi">0</span><span class="p">:</span> <span class="k">yield</span> <span class="bp">self</span>
<span class="k">def</span> <span class="nf">solve</span><span class="p">(</span><span class="n">pos</span><span class="p">,</span> <span class="n">depthFirst</span><span class="o">=</span><span class="kc">False</span><span class="p">):</span>
<span class="n">queue</span> <span class="o">=</span> <span class="n">deque</span><span class="p">([</span><span class="n">pos</span><span class="p">])</span>
<span class="n">trail</span> <span class="o">=</span> <span class="p">{</span><span class="n">intern</span><span class="p">(</span><span class="n">pos</span><span class="o">.</span><span class="n">canonical</span><span class="p">()):</span> <span class="kc">None</span><span class="p">}</span>
<span class="n">solution</span> <span class="o">=</span> <span class="n">deque</span><span class="p">()</span>
<span class="n">load</span> <span class="o">=</span> <span class="n">queue</span><span class="o">.</span><span class="n">append</span> <span class="k">if</span> <span class="n">depthFirst</span> <span class="k">else</span> <span class="n">queue</span><span class="o">.</span><span class="n">appendleft</span>
<span class="k">while</span> <span class="ow">not</span> <span class="n">pos</span><span class="o">.</span><span class="n">isgoal</span><span class="p">():</span>
<span class="k">for</span> <span class="n">m</span> <span class="ow">in</span> <span class="n">pos</span><span class="p">:</span>
<span class="n">c</span> <span class="o">=</span> <span class="n">m</span><span class="o">.</span><span class="n">canonical</span><span class="p">()</span>
<span class="k">if</span> <span class="n">c</span> <span class="ow">in</span> <span class="n">trail</span><span class="p">:</span>
<span class="k">continue</span>
<span class="n">trail</span><span class="p">[</span><span class="n">intern</span><span class="p">(</span><span class="n">c</span><span class="p">)]</span> <span class="o">=</span> <span class="n">pos</span>
<span class="n">load</span><span class="p">(</span><span class="n">m</span><span class="p">)</span>
<span class="n">pos</span> <span class="o">=</span> <span class="n">queue</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span>
<span class="k">while</span> <span class="n">pos</span><span class="p">:</span>
<span class="n">solution</span><span class="o">.</span><span class="n">appendleft</span><span class="p">(</span><span class="n">pos</span><span class="p">)</span>
<span class="n">pos</span> <span class="o">=</span> <span class="n">trail</span><span class="p">[</span><span class="n">pos</span><span class="o">.</span><span class="n">canonical</span><span class="p">()]</span>
<span class="k">return</span> <span class="nb">list</span><span class="p">(</span><span class="n">solution</span><span class="p">)</span>
</pre></div>
</div>
</div>
</div>
</div>
</div>
<footer>
<div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
<a href="einstein.html" class="btn btn-neutral float-right" title="SAT Solvers" accesskey="n" rel="next">Next <span class="fa fa-arrow-circle-right"></span></a>
<a href="overview.html" class="btn btn-neutral" title="Overview" accesskey="p" rel="prev"><span class="fa fa-arrow-circle-left"></span> Previous</a>
</div>
<hr/>
<div role="contentinfo">
<p>
© Copyright 2019, Raymond Hettinger
</p>
</div>
Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/rtfd/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>.
</footer>
</div>
</div>
</section>
</div>
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT:'./',
VERSION:'',
LANGUAGE:'None',
COLLAPSE_INDEX:false,
FILE_SUFFIX:'.html',
HAS_SOURCE: true,
SOURCELINK_SUFFIX: '.txt'
};
</script>
<script type="text/javascript" src="_static/jquery.js"></script>
<script type="text/javascript" src="_static/underscore.js"></script>
<script type="text/javascript" src="_static/doctools.js"></script>
<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script type="text/javascript" src="_static/js/theme.js"></script>
<script type="text/javascript">
jQuery(function () {
SphinxRtdTheme.Navigation.enable(true);
});
</script>
</body>
</html>