forked from aaronbloomfield/pdr
-
Notifications
You must be signed in to change notification settings - Fork 228
/
Copy pathindex.html
555 lines (554 loc) · 28.3 KB
/
index.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
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>PDR: Laboratory 11: Graphs</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
span.underline{text-decoration: underline;}
div.column{display: inline-block; vertical-align: top; width: 50%;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
ul.task-list{list-style: none;}
.display.math{display: block; text-align: center; margin: 0.5rem auto;}
</style>
<link rel="stylesheet" href="../../markdown.css" />
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<h1 id="pdr-laboratory-11-graphs">PDR: Laboratory 11: Graphs</h1>
<p><a href="../index.html">Go up to the Labs table of contents
page</a></p>
<h3 id="objective">Objective</h3>
<p>To become familiar with representing graphs in general, directed
acyclic graphs (DAGs), topological sorting, traveling salesperson
problem, and other related algorithms.</p>
<h3 id="background">Background</h3>
<p>A graph is a set of vertices connected by edges. In a directed graph,
an edge is an ordered pair of vertices, where you can follow an edge
from one vertex to another. In a directed acyclic graph (DAG), no path
starts and ends at the same vertex. A topological sort orders the
vertices in a DAG such that any edge from vertex i to vertex j satisfies
i < j.</p>
<h3 id="tutorial">Tutorial</h3>
<p>Go through the <a
href="../../tutorials/11-doxygen/index.html">Doxygen tutorial</a>, which
is a program that allows you to generate documentation for your
code.</p>
<h3 id="recommended-readings">Recommended Readings</h3>
<ol type="1">
<li>The <a
href="https://en.wikipedia.org/wiki/Topological_sorting">Wikipedia page
on Topological sort</a></li>
<li>The <a
href="https://en.wikipedia.org/wiki/Travelling_salesman_problem">Wikipedia
page on the Traveling Salesperson problem</a></li>
<li><a href="../../slides/11-graphs.html">The slides on graphs</a></li>
</ol>
<h2 id="procedure">Procedure</h2>
<h3 id="pre-lab">Pre-lab</h3>
<ol type="1">
<li>Understand and document the <a
href="middleearth.h.html">middleearth.h</a> (<a
href="middleearth.h">src</a>) and <a
href="middleearth.cpp.html">middleearth.cpp</a> (<a
href="middleearth.cpp">src</a>) files</li>
<li>Write a program to compute a topological sort of a graph</li>
<li>Document your topological.cpp with doxygen comments</li>
<li>Write a Makefile to compile your code and generate
documentation</li>
<li>Files to download: <a
href="prelab-test-full.txt">prelab-test-full.txt</a>, <a
href="prelab-test-small.txt">prelab-test-small.txt</a>, <a
href="middleearth.h.html">middleearth.h</a> (<a
href="middleearth.h">src</a>), <a
href="middleearth.cpp.html">middleearth.cpp</a> (<a
href="middleearth.cpp">src</a>), <a
href="fileio2.cpp.html">fileio2.cpp</a> (<a
href="fileio2.cpp">src</a>)</li>
<li>Files to submit: topological.cpp, middleearth.h/cpp, Makefile,
Doxyfile</li>
</ol>
<h3 id="in-lab">In-lab</h3>
<ol type="1">
<li>Implement a brute-force traveling salesperson solution</li>
<li>Document your C++ files with doxygen commands</li>
<li>Write a Makefile to compile your code and generate
documentation</li>
<li>Files to download: <a
href="traveling-skeleton.cpp.html">traveling-skeleton.cpp</a> (<a
href="traveling-skeleton.cpp">src</a>) (which you’ll have to rename to
traveling.cpp), and your commented middleearth.h / middleearth.cpp code
from the pre-lab</li>
<li>Files to submit: traveling.cpp, middleearth.h, middleearth.cpp,
Makefile, Doxyfile</li>
</ol>
<h3 id="post-lab">Post-lab</h3>
<ol type="1">
<li>Write an 8-Puzzle solver using BFS</li>
<li>Files to download: none</li>
<li>Files to submit: Makefile, Doxyfile, and any source code required to
run the solver.</li>
</ol>
<hr />
<h2 id="pre-lab-1">Pre-lab</h2>
<h3 id="good-code-documentation">Good code documentation</h3>
<p>For this lab, any code you submit must be properly documented using
doxygen.<br />
This includes the <a href="middleearth.h.html">middleearth.h</a> (<a
href="middleearth.h">src</a>) and <a
href="middleearth.cpp.html">middleearth.cpp</a> (<a
href="middleearth.cpp">src</a>) files, which you should understand and
document as part of the pre-lab.</p>
<p>There are many doxygen commands, and we expect for you to use more
than just those that were provided in the tutorial.
<strong>Specifically, the grader will look that you’ve incorporated at
least two additional doxygen tags that are NOT in the
tutorial.</strong></p>
<h3 id="topological-sort">Topological sort</h3>
<p>Recall from lecture that given a graph <em>G</em> =
(<em>V</em>,<em>E</em>), a topological sort of a directed acyclic graph
is a linear listing of the vertices such that, for all pairs of vertices
<em>v</em>,<em>w</em> ∈ <em>V</em>, <em>v</em> is listed before
<em>w</em> in the topological sort if (<em>v</em>,<em>w</em>) ∈
<em>E</em> (i.e. if there is an edge from <em>v</em> to <em>w</em> in
the graph, then <em>v</em> must be listed before <em>w</em> in the
topological sort). This implies that if there is a <em>path</em> from
<em>v</em> to <em>w</em> (not just an edge), then <em>v</em> must still
list before <em>w</em> in the topological sort.</p>
<p>For the programming part of this lab, you will need to write a
program that can perform a topological sort. This problem is specified
in the next section. The specification is similar to that found in the
<a href="https://icpc.baylor.edu/">International Collegiate Programming
Contests</a> – a problem description, followed by a detailed explanation
of the input and the output.</p>
<p>How you represent your graph is up to you – choices include:
node-with-pointers, adjacency list, adjacency matrix, and others. Just
keep in mind that you will have to do a topological sort on this graph.
The program must read in a list of directed edges from a file and
(internally) generate the graph from it.</p>
<p>To read in strings from a file in the C++ manner, see the <a
href="fileio2.cpp.html">fileio2.cpp</a> (<a href="fileio2.cpp">src</a>)
file.</p>
<h3 id="makefile">Makefile</h3>
<p>The first target in your Makefile can be named anything you want, but
should do <strong>two</strong> things: compile your code, and run
doxygen. You can have two tabbed lines after the target specifier, which
is the easiest way to accomplish this. In other words, we are just going
to call <code>make</code>, and we want it to both compile your code and
create your doxygen documentation. You are welcome to have additional
targets, such as <code>clean</code>, if you would like.</p>
<hr />
<h2 id="pre-lab-problem-topological-sort">Pre-lab Problem: Topological
Sort</h2>
<p>It turns out that one of our teaching assistants did not take all of
the pre-requisite computer science courses! That TA is all ready to
graduate, but it turns that CS 1110 was never taken. The department came
down hard, and decided to make that TA take all of the courses over
again, to have the proper pre-requisite classes completed for each
successive class. But the TA just got a job at Microsoft, and can only
take one course a semester while working full time. In what order should
the teaching assistant take the list of required courses to properly
fulfill the pre-requisites this time around?</p>
<p>Given the following course pre-requisite graph:</p>
<figure>
<img src="pre-reqs.svg" alt="pre-reqs.svg" />
<figcaption aria-hidden="true">pre-reqs.svg</figcaption>
</figure>
<p>There are multiple valid orders that the courses can be taken in;
each is a valid topological sort:</p>
<ul>
<li>cs1110 cs2110 cs2102 cs3330 cs2150 cs4414</li>
<li>cs1110 cs2110 cs2102 cs2150 cs3330 cs4414</li>
<li>cs1110 cs2102 cs2110 cs3330 cs2150 cs4414</li>
<li>cs1110 cs2102 cs2110 cs2150 cs3330 cs4414</li>
<li>cs1110 cs2110 cs3330 cs2102 cs2150 cs4414</li>
</ul>
<p>For this lab, you can print out <strong>ANY</strong> valid
topological sort for credit.</p>
<h3 id="input">Input</h3>
<p>The program will consist of a single file,
<code>topological.cpp</code>, and take a single command-line parameter.
This parameter will specify the file name that contains the input.</p>
<p>The input file will consist of a series of lines that each designate
a directed edge. Each line will have two vertex names, separated by a
single space; the edge is directed from the first to the second listed
vertex name on a given line. Every vertex name is a series of
alphanumeric characters only (a-z, A-Z, 0-9) without any spaces or
punctuation. Note that case is relevant, so vertex <code>abc</code> is
distinct from vertex <code>ABC</code>. The edges can be listed in any
order.</p>
<p>The end of the input file is signified by two 0s on the same line,
separated by a single space.</p>
<p>You can assume that the provided graph is a directed acyclic graph,
that it is weakly connected, and thus that there is at least one valid
topological sort. You can further assume that there will not be more
than 100 vertices in the graph.</p>
<h3 id="output">Output</h3>
<p>The output is a valid topological sort of the vertices, each
separated by one space, and all on one line.</p>
<h3 id="sample-execution-run">Sample Execution Run</h3>
<p>Below is a sample execution run to show you the input and output
format we are looking for.</p>
<p>Given the input file:</p>
<pre><code>cs2110 cs2150
cs2102 cs2150
cs1110 cs2110
cs3330 cs4414
cs2150 cs4414
cs2110 cs3330
cs1110 cs2102
0 0</code></pre>
<p>Output (<em>NOTE: This is just one of many valid topological
sorts</em>):</p>
<pre><code>cs1110 cs2102 cs2110 cs2150 cs3330 cs4414</code></pre>
<hr />
<h2 id="in-lab-1">In-lab</h2>
<h3 id="the-traveling-salesperson">The Traveling Salesperson</h3>
<p>You are going to implement a program that will find a solution to the
<a href="https://www-e.ovgu.de/mertens/TSP/TSP.html">traveling
salesperson problem</a>. This problem is known to be <a
href="https://en.wikipedia.org/wiki/NP-completeness">NP-complete</a>,
which means that there is no known efficient solution to the problem.
Thus, we will be implementing a rather inefficient solution – a
brute-force method that tries every possible path combination.</p>
<p>The traveling salesperson problem is as described in lecture. In
brief, you start from a given city (your “home” city), and have to
travel to a number of other cities before returning home. There is a
fixed cost between any two cities (miles traveled, dollars spent, time
taken, etc). The goal of this algorithm is to find the least costly path
that travels to each of the cities, in any order.</p>
<p>The world we have chosen is <a
href="https://en.wikipedia.org/wiki/Middle-earth">Middle-Earth</a>, the
location of J.R.R. Tolkien’s Hobbit and Lord of the Rings books and
movies. The middleearth.h and middleearth.cpp files contain a class that
will create a random 2-dimensional world. The “randomness” means that it
will pick a given number of cities (or places), and randomly place them
in the “world”. You can travel from any city to any other city, for a
given cost (the distance). The city names are all from the books and
movies, and can be seen at the beginning of the middleearth.cpp file –
there is a textual description in the code as to what all the places
are. The randomness of the world means that cities that are nowhere near
each other in the books/movies might be right next to each other in the
random world.</p>
<p>When your program is completed, you will need to specify five
command-line parameters to execute the traveling salesperson problem.
The parameters are, in order:</p>
<ol type="1">
<li>The x-size (i.e. width) of the world. We’ll use 20 throughout this
lab.</li>
<li>The y-size (i.e. height) of the world. We’ll use 20 throughout this
lab.</li>
<li>The number of cities in the world. There are currently 40 names
specified at the top of middleearth.cpp, so you can’t specify more than
40 cities.</li>
<li>The random seed. If you specify a given number, the same world will
be created each time – we’ll use this, below, when we talk about
debugging. Supplying -1 will create a different random world each time
the program is run.</li>
<li>The number of cities to visit, other than the “home” city – this can
be as low as 1.</li>
</ol>
<p>The skeleton code provided (<a
href="traveling-skeleton.cpp.html">traveling-skeleton.cpp</a> (<a
href="traveling-skeleton.cpp">src</a>)) already parses the command-line
parameters properly.</p>
<h3 id="stl-helper-functions">STL Helper Functions</h3>
<p>There are a number of STL functions that will help you in writing
this program. All of these algorithms (and more!) are provided in the
<code><algorithm></code> header file. This file is already
included by traveling-skeleton.cpp.</p>
<p>First, take a look at the <code>shuffle()</code> method in
middleearth.cpp:</p>
<pre><code>shuffle(cities.begin(), cities.end(), gen);</code></pre>
<p>This method takes a vector and a random number generator, and will
randomly shuffle the vector, similar to Java’s
<code>Collections.shuffle()</code>. The parameters specify the amount of
the vector that we want to shuffle. Because we want to shuffle the
entire vector, we specify the beginning and end of the list. We define
our own custom <code>shuffle</code> implementation rather than using the
STL’s to provide the same results regardless of what OS you are
using.</p>
<p>The <code>sort()</code> method takes in vector iterators as well, and
sorts the list. It is similar to Java’s <code>Collections.sort()</code>
method. It returns no value.</p>
<p>The <code>next_permutation()</code> method will cycle through each
and every permutation of the passed vector. <strong><em>It must start
out with a sorted vector</em></strong>, and will move through each and
every possible list ordering until the vector ends up in reverse sorted
order. It takes the same parameters as <code>sort()</code>. Note that it
does not return a new permutation, but instead modifies the vector that
is passed in. It returns <code>true</code> if it found another
permutation and <code>false</code> if there are no more permutations to
provide. Thus, it is often put into a do-while loop. For an example of
using <code>next_permutation()</code> in a while loop, see <a
href="https://en.cppreference.com/w/cpp/algorithm/next_permutation">here</a>.
This is a good way to iterate through each possible combination of
cities to travel to.</p>
<h3 id="middle-earth-methods">Middle-Earth methods</h3>
<p>The MiddleEarth class provides a number of methods to help you write
your brute-force solution. The constructor is called by the skeleton
code, and uses the parameters read in from the command line. The
<code>print()</code> method will print out statistics of the world.</p>
<p>The <code>printTable()</code> method will print out a table of the
distances between all cities. Different random seeds will produce
different tables, obviously. This will be useful to help you debug your
program. Redirect it to a file, and then load it up in a spreadsheet
program.</p>
<p>The <code>getDistance()</code> method will return the distance, as a
float, between the two provided cities. In an effort to make your code
as efficient as possible, <code>getDistance()</code> has the same
expected running time as a hash table. Lastly,
<code>getItinerary()</code> will return a vector of the cities that you
must visit. The first city provided is the start (and thus end) city –
you should remove this from the vector before you consider all possible
cycles through the graph.</p>
<h3 id="how-to-proceed">How to proceed</h3>
<p>We provide the skeleton code for the algorithm – your job is to
complete traveling.cpp.</p>
<ol type="1">
<li>First complete <code>printRoute()</code>, as that will be useful
when debugging your code. It should print a route in the form:
<code>Gladden Fields -> Bywater -> Dagorlad -> Pelennor Fields
-> Cirith Ungol -> Gladden Fields</code>. Note that we aren’t
picky about exactly how it’s printed, as long as it prints all the
cities.</li>
<li>Next, complete <code>computeDistance()</code>. You can create a
sample string vector to test it, and verify it against the distances in
the output of <code>printTable()</code>.</li>
<li>Start on the <code>main()</code> method. Make sure that you can
print out all the permutations of the list of destinations. Note that
for n cities, there are n! possible permutations. Remember that the
start city should not be permuted!</li>
<li>At this point, you can now compute the distance and keep track of
the minimum cycle length.</li>
</ol>
<p>Your final program should should print out the shortest path as the
last thing printed. You can print out multiple paths as you find the
shortest one, but you should <strong>NOT</strong> print out
<em>every</em> path you try.</p>
<p>Note that you are determining a cycle of cities to visit. So if your
cycle has the cities in reverse, then it’s still a valid solution.</p>
<h3 id="getting-your-itinerary-correct">Getting your itinerary
correct</h3>
<p>The starting city is <strong>not to be permuted</strong>, as you will
always start (and end) at that city. It’s the <em>other</em> cities that
are going to be permuted through the calls to
<code>next_permutation()</code>.</p>
<h3 id="timing-your-code">Timing your code</h3>
<p>Keep in mind that as you increase the size of the city tour, the
running time increases exponentially. Modern-day computers can probably
compute about 200,000 routes per second (with well written and optimized
code). Our 10-route cycle took 18 seconds. A 15 route cycle would take
2.5 months. A 20 route cycle would take 385,734 years! Realistically,
you shouldn’t be trying anything with an itinerary greater than 9 or
10.</p>
<p>And when you are planning on testing long paths, you should really
compile your code with the <code>-O2</code> compiler option. It can
speed up the program by a factor of two.</p>
<p>To time your code, enter <code>time</code> before the command on the
command-line. For example:</p>
<pre><code>student@cassiopeia:~/labs/lab11$ time ./a.out 20 20 20 14 8
./a.out 20 20 20 14 8
Minimum path has distance 62.9931: Barad-Dur -> Helm's Deep -> Minas Tirith -> The Old Forest -> Dagorlad ->
Dunharrow -> Rivendell -> Entwash River -> Trollshaws -> Barad-Dur
real 0m0.105s
user 0m0.076s
sys 0m0.020s
student@cassiopeia:~/labs/lab11$ </code></pre>
<p>The time we are looking at is the “user” time; this is how long it
took to run the user’s program. The “sys” line is how much time the
system was doing things during the program execution, such as I/O. The
“real” time is the “wall time” – meaning if you had a stop watch, it
would report the “real” time. The “real” time includes many other
things, such as other tasks you are doing on the computer – if you have
an animation running in a web browser, for example, it will increase the
“real” time, as the system is spending some effort rendering those
animations. We’ll only use the “user” time for this lab.</p>
<h3 id="sample-output">Sample output</h3>
<p>For this lab, we will keep the size of the 2-D world fixed at
(20,20). These are the first two command line parameters. We’ll also
create a world of 20 cities (chosen from the 40 names in
middleearth.cpp) – this is the third command line parameter.</p>
<p>If the random seed (the fourth parameter) is 14, then the path
lengths and paths for the various itinerary lengths are listed below.
Because we are explicitly setting the random seed, it should produce the
exact same results each time – and thus your code should also produce
the same results.</p>
<p>The results for a random seed of 14, world size of 20x20 with 20
cities, and various path lengths:</p>
<ol type="1">
<li>Minimum path has distance 19.2463: Barad-Dur -> Trollshaws ->
Barad-Dur</li>
<li>Minimum path has distance 47.0356: Barad-Dur -> Dagorlad ->
Trollshaws -> Barad-Dur</li>
<li>Minimum path has distance 47.73: Barad-Dur -> Helm’s Deep ->
Dagorlad -> Trollshaws -> Barad-Dur</li>
<li>Minimum path has distance 61.1471: Barad-Dur -> Helm’s Deep ->
Dagorlad -> Entwash River -> Trollshaws -> Barad-Dur</li>
<li>Minimum path has distance 61.1496: Barad-Dur -> Helm’s Deep ->
The Old Forest -> Dagorlad -> Entwash River -> Trollshaws ->
Barad-Dur</li>
<li>Minimum path has distance 62.0552: Barad-Dur -> Helm’s Deep ->
The Old Forest -> Dagorlad -> Dunharrow -> Entwash River ->
Trollshaws -> Barad-Dur</li>
<li>Minimum path has distance 62.2792: Barad-Dur -> Helm’s Deep ->
The Old Forest -> Dagorlad -> Dunharrow -> Rivendell ->
Entwash River -> Trollshaws -> Barad-Dur</li>
<li>Minimum path has distance 62.9931: Barad-Dur -> Helm’s Deep ->
Minas Tirith -> The Old Forest -> Dagorlad -> Dunharrow ->
Rivendell -> Entwash River -> Trollshaws -> Barad-Dur</li>
<li>Minimum path has distance 71.335: Barad-Dur -> Helm’s Deep ->
Emyn Muil -> Dagorlad -> Dunharrow -> Rivendell -> Entwash
River -> Trollshaws -> The Old Forest -> Minas Tirith ->
Barad-Dur</li>
<li>Minimum path has distance 72.0124: Barad-Dur -> Helm’s Deep ->
Emyn Muil -> Dagorlad -> Dunharrow -> Misty Mountains ->
Rivendell -> Entwash River -> Trollshaws -> The Old Forest
-> Minas Tirith -> Barad-Dur</li>
</ol>
<p>Your final program needs to both be able to compile and run with the
specified command-line parameters.</p>
<h3 id="makefile-1">Makefile</h3>
<p>Your Makefile should have <strong>only one</strong> target, which you
can name anything you want. This target should do <strong>two</strong>
things: compile your code, and run doxygen. You can have two tabbed
lines after the target specifier, which is the easiest way to accomplish
this. In other words, we are just going to call <code>make</code>, and
we want it to both compile your code and create your doxygen
documentation. The in-lab Makefile should have the same dual-purpose
target.</p>
<hr />
<h2 id="post-lab-1">Post-lab</h2>
<p>Consider the <a
href="https://en.wikipedia.org/wiki/15_puzzle">Sliding 8-Puzzle</a>
game, depicted in the image below. If you’d like, you can play the
puzzle <a
href="http://www.artbylogic.com/puzzles/numSlider/numberShuffle.htm?rows=3&cols=3&sqr=1">HERE</a>
to get a better sense for how the game works.</p>
<figure>
<img src="8Puzzle.png" alt="8-puzzle" />
<figcaption aria-hidden="true">8-puzzle</figcaption>
</figure>
<p>In this 3x3 grid of numbers, the goal is to slide numbers into the
empty square until the end game state is reached. As can be seen above,
our end game state is a sorted board. The hole in the board can move in
any direction, but cannot “wrap around” from one side to the other (or
from top to bottom, etc.).</p>
<p>Your task for this lab is to implement a solution to the 8 puzzle
problem described above: given an input board, find the minimum number
of moves required to reach the end state, or if it is impossible to
reach it.</p>
<h3 id="storing-the-puzzle">Storing the Puzzle</h3>
<p>The simplest way to store the puzzle would be with either a 1D or 2D
array, where the hole is represented by a 0 (zero). Then, if you wanted
to move the hole around the “board”, you would simply swap its position
in the array with an adjacent tile. Consider making an object (or
struct) that stores a single configuration of the board.</p>
<h3 id="solving-the-puzzle">Solving the Puzzle</h3>
<p>Once you have an object for storing a single configuration of the
puzzle, you can start thinking about this as a graph problem. Consider
each unique configuration (one instance of your object) to be a node in
the graph. There exists an edge between two configurations in the graph
if you can reach configuration <em>B</em> from configuration <em>A</em>
by only sliding one tile.</p>
<p>Once you have represented this problem as a start state (input that
is given to you) and goal state (the final solved puzzle) with edges
(moves) in between, you can solve this problem by finding the
<strong>shortest path</strong> between the start state and the solved
state. Use one of the algorithms from class to find the shortest path.
You should probably choose <strong>breadth-first search</strong>…you can
use <em>Dijkstra’s Algorithm</em>, but because edge weights are all
<em>1</em> here, it is pointless to add the extra complexity.</p>
<h3 id="testing-for-solvability">Testing for Solvability</h3>
<p>If your search algorithm goes through all configurations of the
possible without ever reaching the goal state, than that starting
configuration is impossible to solve.</p>
<p>There is an easy way to check if an 8-puzzle is solvable or not by
using inversions. An inversion is a pair of tiles that are in reverse
order to their appearance in the goal state. If an 8-puzzle has an
<strong>even</strong> number of inversions, then the puzzle is
<strong>solvable</strong>. If an 8-puzzle has an <strong>odd</strong>
number of inversions, then the puzzle is <strong>unsolvable</strong>.
For example, the following 8-puzzle has 3 inversions, and is thus
impossible to solve. You can watch <a
href="https://www.youtube.com/watch?v=YI1WqYKHi78">this video</a> for a
slightly more detailed description if you are interested.</p>
<p>Another, but less elegant, way of testing for impossibility</p>
<pre><code>2 1 3
4 0 5
8 6 7</code></pre>
<p>The inversions in this example are (2,1), (8,6), and (8,7).</p>
<h3 id="input-1">Input</h3>
<p>The input to this program will be three lines of three numbers, each
representing a tile of the 8-puzzle.</p>
<h3 id="sample-execution-run-1">Sample Execution Run</h3>
<p>Below is a sample execution run to show you the input and output
format we are looking for.</p>
<pre><code>Enter puzzle
3 6 4
1 2 5
7 8 0
Solving puzzle
18</code></pre>
<p>Here is another example showing how your output should look for an
impossible puzzle.</p>
<pre><code>Enter puzzle
2 1 3
4 0 5
8 6 7
Solving puzzle
IMPOSSIBLE</code></pre>
<h3 id="submission">Submission</h3>
<p>You should submit any files required for your 8 puzzle solver to run
as well as a Makefile that prodcues an <code>a.out</code>
executable.</p>
<h3 id="makefile-2">Makefile</h3>
<p>Your Makefile should have <strong>only one</strong> target, which you
can name anything you want. This target should do <strong>two</strong>
things: compile your code, and run doxygen. You can have two tabbed
lines after the target specifier, which is the easiest way to accomplish
this. In other words, we are just going to call <code>make</code>, and
we want it to both compile your code and create your doxygen
documentation. The post-lab Makefile should have the same dual-purpose
target.</p>
<h3 id="hints">Hints</h3>
<h4 id="where-do-i-get-started">Where do I get Started?</h4>
<p>There are a lot of steps to this lab, and it is important to
partition the work and only focus on one component at a time. Start out
by working on how you will represent a puzzle: as a class, an array with
helper methods, etc. Once you can read in a puzzle and manipulate it at
will, you are ready to move on to the actual solving portion of the
lab.</p>
<h4 id="too-many-permutations-which-ones-should-i-look-at-first">Too
Many Permutations! Which Ones Should I Look at First?</h4>
<p>There aren’t <strong>that</strong> many permutations of this puzzle
(there are 9! = 362,880). However, it is beneficial to only create /
store the nodes that you are actually using as you go. For example:
suppose I have the following starting grid:</p>
<pre><code>2 1 0
4 3 5
8 6 7</code></pre>
<p>When the code begins, this will be the <strong>only</strong> node in
the graph. As I begin my breadth-first search, we can generate
neighboring nodes on the fly. For example, when I do the next step of
search, I can call a method called <em>generateNeighbors()</em>, that
given the node above as input, returns the following states that can be
reached by a single move (sliding the 1 to the right or sliding the 5
up):</p>
<pre><code>2 0 1 2 1 5
4 3 5 4 3 0
8 6 7 8 6 7</code></pre>
<p>Now, my graph has 3 total nodes. As I continue my search, I can do
the following: for a given node I’m searching, generate the neighbors of
that node, check if the neighbor has already been search (a hash table
is useful here). If the neighbor has already been searched, discard it
(don’t want to duplicate work over and over). If it has not been seen,
add it to my BFS queue and continue.</p>
<p>Good luck!!</p>
</body>
</html>