1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # This file is free software, which comes along with NIT. This software is
4 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
5 # without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
6 # PARTICULAR PURPOSE. You can modify it is you want, provided this header
7 # is kept unaltered, and a notification of the changes is added.
8 # You are allowed to redistribute it and sell it, alone or is a part of
11 # The N-puzzle problem, modeled naively as a `SearchProblem`.
13 # A square grid, made of tiles represented with a letter, is scrambled.
14 # A missing tile, the hole, represented with a dot, is used to move them.
16 # The goal is to found a plan, made of the four basic movements up, down,
17 # left, and right, that move each letter to its correct position: the solved
18 # grid list letters alphabetically from left to right then top to bottom.
19 # The hole must be in the last position (bottom-right).
21 # The argument of the program is a initial position, the program then find
22 # the best plan to solve the puzzle.
26 # The argument "abcd.fgeh" is the grid
42 # The shortest plan, in two steps, is to move *up* the tile under the hole (e),
43 # then to move *left* the tile after the hole (h).
46 # The state (`S`) is a square grid, modeled as a one-dimensional array of Tile.
47 # read from left to right then top to bottom.
49 # An action (`A`) is the relative position of the tile to swap with the hole.
50 # Therefore, `-1` for left, `1` for right, `-width` for up and `width` for down.
52 super SearchProblem[ArrayCmp[Tile], Int]
54 # The initial grid. use letters for tiles, and . for the hole.
55 var initial_grid
: String
57 # The width of the grid.
58 # Eg. 3 for a 8-puzzle grid
59 var width
: Int is noinit
61 # Construct a state form `initial_grid`
62 redef fun initial_state
do
65 var width
= len
.sqrt
.to_i
67 if width
* width
!= len
then
68 print
"Error: {g} has {len} tiles. A square number, like {width*width} is needed"
71 var res
= new ArrayCmp[Tile]
72 for i
in [0..g
.length
[ do
74 if c
== ' ' or c
== '.' then
75 var hole
= new Tile('.', -1)
78 else if c
>= '1' and c
<= '9' then
79 var t
= new Tile(c
, '1'.distance
(c
))
81 else if c
>= 'a' and c
<= 'z' then
82 var t
= new Tile(c
, 'a'.distance
(c
))
84 else if c
>= 'A' and c
<= 'Z' then
85 var t
= new Tile(c
, 'A'.distance
(c
))
88 print
"Error: illegal tile {c} in {g}"
95 # Get the four available movements, or 3 on a edge, or 2 in a corner.
96 redef fun actions
(state
)
98 var h
= get_hole
(state
)
101 var res
= new Array[Int]
102 if x
>= 1 then res
.add
(-1)
103 if x
< width-1
then res
.add
(1)
104 if y
>= 1 then res
.add
(-width
)
105 if y
< width-1
then res
.add
(width
)
109 # Return the state where the tile at hole+action has moved
110 redef fun apply_action
(state
, action
)
113 var res
= new ArrayCmp[Tile].with_capacity
(state
.length
)
116 # Get the hole and the tile next to it
117 var h
= get_hole
(res
)
120 # Move (by swapping the tile and the hole)
127 # The special empty tile for fast retrieval.
128 var hole
: Tile is noinit
130 # What is the position of the hole?
131 fun get_hole
(state
: Array[Tile]): Int
133 return state
.index_of
(hole
)
136 # Each tile is at its correct position
137 redef fun is_goal
(state
)
139 for i
in [0..state
.length
[ do
141 if t
!= hole
and t
.goal_idx
!= i
then return false
146 # The sum of the Manhattan distances of each tile to its goal
147 # Not the best heuristic but the simplest to implement among the good ones.
148 redef fun heuristic
(state
)
155 # The hole does not count
156 if t
== hole
then continue
158 var dx
= (i
% width
- t
.goal_idx
% width
).abs
159 var dy
= (i
/ width
- t
.goal_idx
/ width
).abs
161 # Add Manhattan distance
168 fun print_state
(state
: Array[Tile])
170 for i
in [0..state
.length
[ do
177 if (i
+1) % width
== 0 then print
""
181 # Print the plan with words.
182 fun print_plan
(plan
: Sequence[Int])
184 var s
= new Array[String]
190 else if i
== -width
then
192 else if i
== width
then
198 print
"Solution in {plan.length} moves: {s.join(" ")}"
201 redef fun make_memory
do
203 res
.add
new RBTreeMap[ArrayCmp[Tile], SearchNode[ArrayCmp[Tile], Int]]
204 res
.add
new BinTreeMap[ArrayCmp[Tile], SearchNode[ArrayCmp[Tile], Int]]
210 # A simple class to encapsulate the symbol and the goal position.
213 redef type OTHER: Tile is fixed
215 # The symbol written on the tile
218 # The expected position in the grid
221 redef fun to_s
do return symbol
.to_s
222 redef fun ==(o
) do return o
isa Tile and goal_idx
== o
.goal_idx
223 redef fun <(o
) do return goal_idx
< o
.goal_idx
224 redef fun <=>(o
) do return goal_idx
<=> o
.goal_idx
229 if not args
.is_empty
then
230 if args
.first
== "--configs" then
236 if args
.is_empty
then
238 Usage: puzzle [--configs] initial...
240 --configs: search and time solutions with various configurations of solvers.
241 initial: an initial configuration (letters for the tiles, and dot for the hole). eg:
247 medium (10): eabf.cdgh
249 harder (31): hfgbedc.a
252 goal (0): abcdefghijklmno.
253 easy (30): bacdefghijlkmno.
254 medium (40): fg.jacoheldnibmk
255 hard (55): kleg.mondcafjhbi
256 harder (61): lomgkcend.afjhbi
259 goal (0): abcdefghijklmnopqrstuvwx.
260 easy (55): giabcjekmdhrtflqsownpuv.x
261 medium (75): giabcjekmdrtwulhs.vnqofpx
262 hard (79): giabcjekmdrtw.uhsvnlqofpx
263 harder (80): giabcjekmdrt.wuhsvnlqofpx
270 var pb
= new PuzzleProblem(arg
)
271 print
"Initial: {arg}"
272 pb
.print_state
(pb
.initial_state
)
275 pb
.run_configs
(1000000)
287 print
"Solved, after looking at {r.steps} positions"
288 pb
.print_plan
(r
.plan
)