48using Board = std::array<int,16>;
60 _scramble(
"scramble",
"number of random slides from the goal",12),
61 _limit(
"limit",
"maximum number of solution moves",12) {
70 "try the slide with least Manhattan distance first");
73#ifdef GECODE_HAS_EXPERIMENTAL
82 return _scramble.value();
87 "FifteenPuzzle::limit");
88 return static_cast<int>(_limit.value());
94 return {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};
113 Board board = goal();
117 for (
unsigned int i=0;
i<
opt.scramble();
i++) {
119 for (
int neighbor : neighbors(blank))
120 if (neighbor != previous)
122 int next = choices[random(
static_cast<unsigned int>(choices.
size()))];
123 std::swap(board[blank],board[next]);
131manhattan(
const Board& board) {
133 for (
int i=0;
i<16;
i++) {
135 const int target = board[
i]-1;
136 distance += std::abs(i/4-target/4) + std::abs(i%4-target%4);
145 for (
int i=0;
i<16;
i++)
146 result[i] = tiles[i].val();
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;
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) {
163 best_change = change;
170print_board(std::ostream& os,
const Board& board) {
171 for (
int i=0;
i<16;
i++) {
172 os << std::setw(3) << board[
i];
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);
193 static const TupleSet adjacent = [] {
195 for (
int i=0;
i<16;
i++) {
196 for (
int j : neighbors(i))
205 for (
int i=0;
i<16;
i++) {
206 rel(home,((old_blank != i) && (new_blank != i)) >>
207 (before[i] == after[i]));
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]);
220 rel(home,(length == states) >> solved);
221 rel(home,solved >> (length <= states));
255 tiles(*this,
IntSet(0,15),16*(opt.limit()+1)),
258 static_cast<OpenPuzzle&
>(home).transition(x,i);
260 const Board initial = initial_board(opt);
263 post_start(*
this,
state(0),start,initial);
264 rel(*
this,
path.length() >= manhattan(initial)+1);
269 return manhattan_value(s.
state(i-1),s.path[i-1].val(),next);
276 tiles.materialize(*
this,16*(i+1));
280 post_slide(*
this,
state(i-1),x[i-1],
state(i),x[i]);
281 post_goal(*
this,
state(i),path.length(),i+1);
285 tiles.update(*
this,s.tiles);
286 path.update(*
this,s.path);
295 for (
int j=0; j<16; j++)
296 result[j] = tiles[16*i+j];
302 while (i+1 < path.known_length() && path[i+1].assigned())
308 const int g =
depth();
310 return std::max(g+h,path.length().min()-1);
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();
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);
352 rel(*
this,length >= manhattan(initial)+1);
357 return manhattan_value(s.
state(i-1),s.path[i-1].val(),next);
368 tiles.update(*
this,s.tiles);
369 path.update(*
this,s.path);
370 length.update(*
this,s.length);
379 for (
int j=0; j<16; j++)
380 result[j] = tiles[16*i+j];
386 while (i+1 < path.
size() && path[i+1].assigned())
392 const int g =
depth();
394 return std::max(g+h,length.min()-1);
399 rel(*
this,length < best.length.
val());
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();
413 switch (
opt.search()) {
417#ifdef GECODE_HAS_EXPERIMENTAL
422 [](
const Space& home) -> std::int64_t {
423 return static_cast<const Model&
>(home).bound();
425 opt.guidance(&guidance);
442 opt.parse_strict(argc,argv);
444 std::cout <<
"Initial board (seed " << opt.
seed() <<
"):\n";
445 print_board(std::cout,initial_board(opt));
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 size(void) const
Return size of array (number of elements).
void add(Driver::BaseOption &o)
Add new option o.
Boolean integer variables.
static void run(const Options &opt, Script *s=nullptr)
Home class for posting propagators
Passing integer arguments.
Which values to select for branching first.
Passing integer variables.
Value iterator for integer variables.
int min(void) const
Return minimum of domain.
int val(void) const
Return assigned value.
Open list of integer variables.
IntVar length(void) const
Return the eventual-length variable.
int model(void) const
Return model value.
unsigned int seed(void) const
Return seed value.
unsigned long long int solutions(void) const
Return number of solutions to search for.
Options(const char *s)
Initialize options for script with name s.
int search(void) const
Return search value.
int branching(void) const
Return branching value.
Guidance for heuristic search engines (experimental).
Class representing a set of tuples.
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)
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.
unsigned int scramble(void) const
unsigned int seed
The random seed to be used.
std::array< int, 16 > Board
@ SM_SOLUTION
Print solution and some statistics.
Driver::ScriptBase< Driver::IgnoreStepOption< Space > > Script
Base-class for scripts.
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.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
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.
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.
Gecode toplevel namespace
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
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...
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
void path(Home home, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a Hamiltonian path.
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Gecode::IntArgs i({1, 2, 3, 4})
double position(const Space &home, IntVar x, int i)