Example: solve the 15-puzzle with an open list of states More...
Public Member Functions | |
| OpenPuzzle (const PuzzleOptions &opt) | |
| void | transition (OpenIntVarList x, int i) |
| OpenPuzzle (OpenPuzzle &s) | |
| Space * | copy (void) override |
| IntVarArgs | state (int i) const |
| int | depth (void) const |
| int | bound (void) const |
| void | constrain (const Space &solution) override |
| void | print (std::ostream &os) const override |
| Print a solution to os. | |
| Public Member Functions inherited from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > > | |
| ScriptBase (const Options &opt) | |
| Constructor. | |
| ScriptBase (ScriptBase &e) | |
| Constructor used for cloning. | |
| virtual void | compare (const Space &home, std::ostream &os) const |
| Compare with s. | |
| Public Member Functions inherited from Gecode::Driver::IgnoreStepOption< BaseSpace > | |
| IgnoreStepOption (const Options &) | |
| Constructor. | |
| IgnoreStepOption (BaseSpace &e) | |
| Constructor used for cloning. | |
Related Symbols | |
(Note that these are not member symbols.) | |
| int | main (int argc, char *argv[]) |
| Main-function. | |
Additional Inherited Members | |
| Static Public Member Functions inherited from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > > | |
| static std::ostream & | select_ostream (const char *sn, std::ofstream &ofs) |
| Choose output stream according to sn. | |
| static void | run (const Options &opt, Script *s=nullptr) |
Detailed Description
Example: solve the 15-puzzle with an open list of states
Start from a solvable board obtained by randomly sliding from the goal. Each path variable records the blank position in one board. The tile list holds sixteen variables per board. The transition on the path constructs and constrains the next board when that position is materialized. Each new board uses the same slide and goal constraints as the fixed representation. Propagation determines how much of the path is constructed; the initial Manhattan distance bounds the number of moves from below. With A* and CABS, the moves so far plus the Manhattan distance of the current board is the bound.
The goal closes the path. Length counts states including the start, so branch and bound minimizes moves by minimizing length minus one. The independent move limit bounds search and need not equal the scramble. Defaults use twelve slides, seed one, and a twelve-move limit. Select -model fixed to compare with an array representation; -scramble, -seed, and -limit control the instance and search bound independently. -branching min (default) tries blank positions in numerical order; -branching manhattan tries the slide with the lowest resulting Manhattan distance, breaking ties by the lowest position.
Definition at line 249 of file fifteen-puzzle.cpp.
Constructor & Destructor Documentation
◆ OpenPuzzle() [1/2]
|
inline |
Definition at line 253 of file fifteen-puzzle.cpp.
◆ OpenPuzzle() [2/2]
|
inline |
Definition at line 284 of file fifteen-puzzle.cpp.
Member Function Documentation
◆ transition()
|
inline |
Definition at line 275 of file fifteen-puzzle.cpp.
◆ copy()
|
inlineoverride |
Definition at line 289 of file fifteen-puzzle.cpp.
◆ state()
|
inline |
Definition at line 293 of file fifteen-puzzle.cpp.
◆ depth()
|
inline |
Definition at line 300 of file fifteen-puzzle.cpp.
◆ bound()
|
inline |
Definition at line 307 of file fifteen-puzzle.cpp.
◆ constrain()
|
inlineoverride |
Definition at line 313 of file fifteen-puzzle.cpp.
◆ print()
|
inlineoverridevirtual |
Print a solution to os.
Reimplemented from Gecode::Driver::ScriptBase< Driver::IgnoreStepOption< Space > >.
Definition at line 318 of file fifteen-puzzle.cpp.
Friends And Related Symbol Documentation
◆ main()
|
Main-function.
Definition at line 440 of file fifteen-puzzle.cpp.
The documentation for this class was generated from the following file:
- examples/fifteen-puzzle.cpp
