Generated on for Gecode by doxygen 1.17.0
fifteen-puzzle.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main author:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/driver.hh>
35#include <gecode/int.hh>
36#include <gecode/minimodel.hh>
37#include <gecode/search.hh>
38
39#include <algorithm>
40#include <cstdint>
41#include <array>
42#include <cstdlib>
43#include <iomanip>
44#include <iostream>
45#include <limits>
46
47using namespace Gecode;
48using Board = std::array<int,16>;
49
51class PuzzleOptions : public Options {
54public:
59 : Options("FifteenPuzzle"),
60 _scramble("scramble","number of random slides from the goal",12),
61 _limit("limit","maximum number of solution moves",12) {
62 add(_scramble);
63 add(_limit);
65 model(MODEL_OPEN,"open","construct states as the path grows");
66 model(MODEL_FIXED,"fixed","construct all bounded states initially");
68 branching(BRANCH_MIN,"min","try the lowest blank position first");
69 branching(BRANCH_MANHATTAN,"manhattan",
70 "try the slide with least Manhattan distance first");
72 search(SEARCH_BAB,"bab","depth-first branch and bound");
73#ifdef GECODE_HAS_EXPERIMENTAL
74 search(SEARCH_ASTAR,"astar","A* with Manhattan distance");
75 search(SEARCH_CABS,"cabs","complete anytime beam search");
76#endif
77 solutions(0);
78 seed(1);
79 }
80 unsigned int
81 scramble(void) const {
82 return _scramble.value();
83 }
84 int
85 limit(void) const {
86 Int::Limits::check(16*(static_cast<long long int>(_limit.value())+1),
87 "FifteenPuzzle::limit");
88 return static_cast<int>(_limit.value());
89 }
90};
91
92static Board
93goal(void) {
94 return {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};
95}
96
97static IntArgs
98neighbors(int blank) {
99 IntArgs result;
100 if (blank >= 4)
101 result << blank-4;
102 if (blank % 4 != 0)
103 result << blank-1;
104 if (blank % 4 != 3)
105 result << blank+1;
106 if (blank < 12)
107 result << blank+4;
108 return result;
109}
110
111static Board
112initial_board(const PuzzleOptions& opt) {
113 Board board = goal();
114 Rnd random(opt.seed());
115 int blank = 15;
116 int previous = -1;
117 for (unsigned int i=0; i<opt.scramble(); i++) {
118 IntArgs choices;
119 for (int neighbor : neighbors(blank))
120 if (neighbor != previous)
121 choices << neighbor;
122 int next = choices[random(static_cast<unsigned int>(choices.size()))];
123 std::swap(board[blank],board[next]);
124 previous = blank;
125 blank = next;
126 }
127 return board;
128}
129
130static int
131manhattan(const Board& board) {
132 int distance = 0;
133 for (int i=0; i<16; i++) {
134 if (board[i] != 0) {
135 const int target = board[i]-1;
136 distance += std::abs(i/4-target/4) + std::abs(i%4-target%4);
137 }
138 }
139 return distance;
140}
141
142static Board
143values(const IntVarArgs& tiles) {
144 Board result;
145 for (int i=0; i<16; i++)
146 result[i] = tiles[i].val();
147 return result;
148}
149
150// The assigned preceding board changes only at the blank and the moved tile.
151static int
152manhattan_value(const IntVarArgs& before, int blank, IntVar next) {
153 int best = next.min();
154 int best_change = std::numeric_limits<int>::max();
155 for (IntVarValues candidates(next); candidates(); ++candidates) {
156 const int position = candidates.val();
157 const int target = before[position].val()-1;
158 const int change =
159 std::abs(blank/4-target/4) + std::abs(blank%4-target%4) -
160 std::abs(position/4-target/4) - std::abs(position%4-target%4);
161 if (change < best_change) {
162 best = position;
163 best_change = change;
164 }
165 }
166 return best;
167}
168
169static void
170print_board(std::ostream& os, const Board& board) {
171 for (int i=0; i<16; i++) {
172 os << std::setw(3) << board[i];
173 if (i % 4 == 3)
174 os << '\n';
175 }
176}
177
178static void
179post_start(Home home, const IntVarArgs& tiles, IntVar blank,
180 const Board& initial) {
181 for (int i=0; i<16; i++)
182 rel(home,tiles[i] == initial[i]);
183 const int zero = static_cast<int>(
184 std::find(initial.begin(),initial.end(),0)-initial.begin());
185 rel(home,blank == zero);
186}
187
188// Swap the blank with an adjacent tile and preserve every other position.
189static void
190post_slide(Home home,
191 const IntVarArgs& before, IntVar old_blank,
192 const IntVarArgs& after, IntVar new_blank) {
193 static const TupleSet adjacent = [] {
194 TupleSet table(2);
195 for (int i=0; i<16; i++) {
196 for (int j : neighbors(i))
197 table.add(IntArgs({i,j}));
198 }
199 table.finalize();
200 return table;
201 }();
202 extensional(home,IntVarArgs({old_blank,new_blank}),adjacent);
203 rel(home,element(after,old_blank) == element(before,new_blank));
204 rel(home,element(after,new_blank) == 0);
205 for (int i=0; i<16; i++) {
206 rel(home,((old_blank != i) && (new_blank != i)) >>
207 (before[i] == after[i]));
208 }
209}
210
211// The last board must be solved; reaching the goal forbids a longer path.
212static void
213post_goal(Home home, const IntVarArgs& tiles, IntVar length,
214 int states) {
215 const Board target = goal();
216 BoolExpr matches(tiles[0] == target[0]);
217 for (int i=1; i<16; i++)
218 matches = matches && (tiles[i] == target[i]);
219 BoolVar solved = expr(home,matches);
220 rel(home,(length == states) >> solved);
221 rel(home,solved >> (length <= states));
222}
223
249class OpenPuzzle : public Script {
250 OpenIntVarList tiles;
251 OpenIntVarList path;
252public:
254 : Script(opt),
255 tiles(*this,IntSet(0,15),16*(opt.limit()+1)),
256 path(*this,IntSet(0,15),
257 [](Space& home, OpenIntVarList x, int i) {
258 static_cast<OpenPuzzle&>(home).transition(x,i);
259 },opt.limit()+1) {
260 const Board initial = initial_board(opt);
261 rel(*this,tiles.length() == 16*path.length());
262 IntVar start = path.get(*this,0);
263 post_start(*this,state(0),start,initial);
264 rel(*this,path.length() >= manhattan(initial)+1);
265 IntValBranch value_branch = INT_VAL_MIN();
266 if (opt.branching() == PuzzleOptions::BRANCH_MANHATTAN)
267 value_branch = INT_VAL([](const Space& home, IntVar next, int i) {
268 const OpenPuzzle& s = static_cast<const OpenPuzzle&>(home);
269 return manhattan_value(s.state(i-1),s.path[i-1].val(),next);
270 });
271 branch(*this,path,INT_VAR_NONE(),value_branch);
272 }
273
274 void
276 tiles.materialize(*this,16*(i+1));
277 if (failed())
278 return;
279 if (i > 0)
280 post_slide(*this,state(i-1),x[i-1],state(i),x[i]);
281 post_goal(*this,state(i),path.length(),i+1);
282 }
283
285 tiles.update(*this,s.tiles);
286 path.update(*this,s.path);
287 }
288 Space*
289 copy(void) override {
290 return new OpenPuzzle(*this);
291 }
293 state(int i) const {
294 IntVarArgs result(16);
295 for (int j=0; j<16; j++)
296 result[j] = tiles[16*i+j];
297 return result;
298 }
299 int
300 depth(void) const {
301 int i = 0;
302 while (i+1 < path.known_length() && path[i+1].assigned())
303 i++;
304 return i;
305 }
306 int
307 bound(void) const {
308 const int g = depth();
309 const int h = manhattan(values(state(g)));
310 return std::max(g+h,path.length().min()-1);
311 }
312 void
313 constrain(const Space& solution) override {
314 const OpenPuzzle& best = static_cast<const OpenPuzzle&>(solution);
315 rel(*this,path.length() < best.path.length().val());
316 }
317 void
318 print(std::ostream& os) const override {
319 os << "Moves: " << path.length().val()-1 << "\nBlank positions:";
320 for (int i=0; i<path.known_length(); i++)
321 os << ' ' << path[i].val();
322 os << '\n';
323 }
324};
325
335class FixedPuzzle : public Script {
336 IntVarArray tiles;
337 IntVarArray path;
338 IntVar length;
339public:
341 : Script(opt),
342 tiles(*this,16*(opt.limit()+1),0,15),
343 path(*this,opt.limit()+1,0,15),
344 length(*this,1,opt.limit()+1) {
345 const Board initial = initial_board(opt);
346 post_start(*this,state(0),path[0],initial);
347 post_goal(*this,state(0),length,1);
348 for (int i=1; i<=opt.limit(); i++) {
349 post_slide(*this,state(i-1),path[i-1],state(i),path[i]);
350 post_goal(*this,state(i),length,i+1);
351 }
352 rel(*this,length >= manhattan(initial)+1);
353 IntValBranch value_branch = INT_VAL_MIN();
354 if (opt.branching() == PuzzleOptions::BRANCH_MANHATTAN)
355 value_branch = INT_VAL([](const Space& home, IntVar next, int i) {
356 const FixedPuzzle& s = static_cast<const FixedPuzzle&>(home);
357 return manhattan_value(s.state(i-1),s.path[i-1].val(),next);
358 });
359 branch(*this,path,INT_VAR_NONE(),value_branch,
360 [](const Space& home, IntVar, int i) {
361 const FixedPuzzle& s = static_cast<const FixedPuzzle&>(home);
362 const int depth = s.depth();
363 return values(s.state(depth)) != goal() && i == depth+1;
364 });
365 }
366
368 tiles.update(*this,s.tiles);
369 path.update(*this,s.path);
370 length.update(*this,s.length);
371 }
372 Space*
373 copy(void) override {
374 return new FixedPuzzle(*this);
375 }
377 state(int i) const {
378 IntVarArgs result(16);
379 for (int j=0; j<16; j++)
380 result[j] = tiles[16*i+j];
381 return result;
382 }
383 int
384 depth(void) const {
385 int i = 0;
386 while (i+1 < path.size() && path[i+1].assigned())
387 i++;
388 return i;
389 }
390 int
391 bound(void) const {
392 const int g = depth();
393 const int h = manhattan(values(state(g)));
394 return std::max(g+h,length.min()-1);
395 }
396 void
397 constrain(const Space& solution) override {
398 const FixedPuzzle& best = static_cast<const FixedPuzzle&>(solution);
399 rel(*this,length < best.length.val());
400 }
401 void
402 print(std::ostream& os) const override {
403 os << "Moves: " << length.val()-1 << "\nBlank positions:";
404 for (int i=0; i<length.val(); i++)
405 os << ' ' << path[i].val();
406 os << '\n';
407 }
408};
409
410template<class Model>
411static void
412run(PuzzleOptions& opt) {
413 switch (opt.search()) {
416 break;
417#ifdef GECODE_HAS_EXPERIMENTAL
420 {
422 [](const Space& home) -> std::int64_t {
423 return static_cast<const Model&>(home).bound();
424 });
425 opt.guidance(&guidance);
426 if (opt.search() == PuzzleOptions::SEARCH_ASTAR)
428 else
430 }
431 break;
432#endif
433 }
434}
435
439int
440main(int argc, char* argv[]) {
441 PuzzleOptions opt;
442 opt.parse_strict(argc,argv);
443 if (opt.mode() == SM_SOLUTION) {
444 std::cout << "Initial board (seed " << opt.seed() << "):\n";
445 print_board(std::cout,initial_board(opt));
446 }
447 if (opt.model() == PuzzleOptions::MODEL_OPEN)
448 run<OpenPuzzle>(opt);
449 else
450 run<FixedPuzzle>(opt);
451 return 0;
452}
453
454// STATISTICS: example-any
FixedPuzzle(FixedPuzzle &s)
IntVarArgs state(int i) const
void constrain(const Space &solution) override
void print(std::ostream &os) const override
Print a solution to os.
Space * copy(void) override
FixedPuzzle(const PuzzleOptions &opt)
int depth(void) const
int bound(void) const
int size(void) const
Return size of array (number of elements).
Definition array.hpp:1606
void add(Driver::BaseOption &o)
Add new option o.
Definition options.cpp:537
Boolean expressions.
Boolean integer variables.
Definition int.hh:534
static void run(const Options &opt, Script *s=nullptr)
Unsigned integer option.
Definition driver.hh:244
Home class for posting propagators
Definition core.hpp:863
Passing integer arguments.
Definition int.hh:653
Integer sets.
Definition int.hh:179
Which values to select for branching first.
Definition int.hh:5969
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Value iterator for integer variables.
Definition int.hh:512
Integer variables.
Definition int.hh:390
int min(void) const
Return minimum of domain.
Definition int.hpp:62
int val(void) const
Return assigned value.
Definition int.hpp:56
Open list of integer variables.
Definition int.hh:1076
IntVar length(void) const
Return the eventual-length variable.
int model(void) const
Return model value.
Definition options.hpp:223
unsigned int seed(void) const
Return seed value.
Definition options.hpp:289
unsigned long long int solutions(void) const
Return number of solutions to search for.
Definition options.hpp:325
Options(const char *s)
Initialize options for script with name s.
Definition options.cpp:656
int search(void) const
Return search value.
Definition options.hpp:316
int branching(void) const
Return branching value.
Definition options.hpp:271
Random number generator.
Definition rnd.hpp:42
Guidance for heuristic search engines (experimental).
Definition search.hh:1259
Computation spaces.
Definition core.hpp:1787
Class representing a set of tuples.
Definition int.hh:2821
Example: solve the 15-puzzle with an open list of states
Space * copy(void) override
int main(int argc, char *argv[])
Main-function.
IntVarArgs state(int i) const
OpenPuzzle(OpenPuzzle &s)
int depth(void) const
int bound(void) const
void transition(OpenIntVarList x, int i)
OpenPuzzle(const PuzzleOptions &opt)
void print(std::ostream &os) const override
Print a solution to os.
void constrain(const Space &solution) override
Options for the initial scramble and bounded solution path.
int limit(void) const
unsigned int scramble(void) const
unsigned int seed
The random seed to be used.
Definition test.hh:138
std::array< int, 16 > Board
@ SM_SOLUTION
Print solution and some statistics.
Definition driver.hh:98
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
Definition driver.hh:1002
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition limits.hpp:46
ExecStatus zero(Space &home, const ViewArray< IntView > &x, const IntDistance &d, const IntSharedArray &r, bool &changed, bool &realized)
Enforce an actual zero-distance witness when the objective is zero.
Definition prop.hpp:93
Gecode toplevel namespace
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:988
IntValBranch INT_VAL(IntBranchVal v, IntBranchCommit c=nullptr)
Select value as defined by the value function v and commit function c Uses a commit function as defau...
Definition val.hpp:95
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition var.hpp:96
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
Definition element.cpp:39
void path(Home home, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a Hamiltonian path.
Definition circuit.cpp:169
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition aliases.hpp:143
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
Gecode::IntArgs i({1, 2, 3, 4})
double position(const Space &home, IntVar x, int i)
Definition ldsb.cpp:1266
Options opt
The options.
Definition test.cpp:163