lib/ai/examples/puzzle.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   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
   9 # another product.
  10
  11 # The N-puzzle problem, modeled naively as a `SearchProblem`.
  12 #
  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.
  15 #
  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).
  20 #
  21 # The argument of the program is a initial position, the program then find
  22 # the best plan to solve the puzzle.
  23 #
  24 # ## Example:
  25 #
  26 # The argument "abcd.fgeh" is the grid
  27 #
  28 # ~~~
  29 # abc
  30 # d.f
  31 # geh
  32 # ~~~
  33 #
  34 # The goal is:
  35 #
  36 # ~~~
  37 # abc
  38 # def
  39 # gh.
  40 # ~~~
  41 #
  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).
  44 import ai::search
  45
  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.
  48 #
  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.
  51 class PuzzleProblem
  52         super SearchProblem[ArrayCmp[Tile], Int]
  53
  54         # The initial grid. use letters for tiles, and . for the hole.
  55         var initial_grid: String
  56
  57         # The width of the grid.
  58         # Eg. 3 for a 8-puzzle grid
  59         var width: Int is noinit
  60
  61         # Construct a state form `initial_grid`
  62         redef fun initial_state do
  63                 var g = initial_grid
  64                 var len = g.length
  65                 var width = len.sqrt.to_i
  66                 self.width = width
  67                 if width * width != len then
  68                         print "Error: {g} has {len} tiles. A square number, like {width*width} is needed"
  69                         exit 1
  70                 end
  71                 var res = new ArrayCmp[Tile]
  72                 for i in [0..g.length[ do
  73                         var c = g.chars[i]
  74                         if c == ' ' or c == '.' then
  75                                 var hole = new Tile('.', -1)
  76                                 self.hole = hole
  77                                 res.add hole
  78                         else if c >= '1' and c <= '9' then
  79                                 var t = new Tile(c, '1'.distance(c))
  80                                 res.add t
  81                         else if c >= 'a' and c <= 'z' then
  82                                 var t = new Tile(c, 'a'.distance(c))
  83                                 res.add t
  84                         else if c >= 'A' and c <= 'Z' then
  85                                 var t = new Tile(c, 'A'.distance(c))
  86                                 res.add t
  87                         else
  88                                 print "Error: illegal tile {c} in {g}"
  89                                 exit 1
  90                         end
  91                 end
  92                 return res
  93         end
  94
  95         # Get the four available movements, or 3 on a edge, or 2 in a corner.
  96         redef fun actions(state)
  97         do
  98                 var h = get_hole(state)
  99                 var x = h % width
 100                 var y = h / width
 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)
 106                 return res.as_random.take_all
 107         end
 108
 109         # Return the state where the tile at hole+action has moved
 110         redef fun apply_action(state, action)
 111         do
 112                 # Copy the state
 113                 var res = new ArrayCmp[Tile].with_capacity(state.length)
 114                 res.add_all(state)
 115
 116                 # Get the hole and the tile next to it
 117                 var h = get_hole(res)
 118                 var t = h + action
 119
 120                 # Move (by swapping the tile and the hole)
 121                 res[h] = res[t]
 122                 res[t] = hole
 123
 124                 return res
 125         end
 126
 127         # The special empty tile for fast retrieval.
 128         var hole: Tile is noinit
 129
 130         # What is the position of the hole?
 131         fun get_hole(state: Array[Tile]): Int
 132         do
 133                 return state.index_of(hole)
 134         end
 135
 136         # Each tile is at its correct position
 137         redef fun is_goal(state)
 138         do
 139                 for i in [0..state.length[ do
 140                         var t = state[i]
 141                         if t != hole and t.goal_idx != i then return false
 142                 end
 143                 return true
 144         end
 145
 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)
 149         do
 150                 var p = 0
 151                 var i = -1
 152                 for t in state do
 153                         i += 1
 154
 155                         # The hole does not count
 156                         if t == hole then continue
 157
 158                         var dx = (i % width - t.goal_idx % width).abs
 159                         var dy = (i / width - t.goal_idx / width).abs
 160
 161                         # Add Manhattan distance
 162                         p += dx + dy
 163                 end
 164                 return p.to_f
 165         end
 166
 167         # Print the grid
 168         fun print_state(state: Array[Tile])
 169         do
 170                 for i in [0..state.length[ do
 171                         var t = state[i]
 172                         if t == hole then
 173                                 printn "."
 174                         else
 175                                 printn t.symbol
 176                         end
 177                         if (i+1) % width == 0 then print ""
 178                 end
 179         end
 180
 181         # Print the plan with words.
 182         fun print_plan(plan: Sequence[Int])
 183         do
 184                 var s = new Array[String]
 185                 for i in plan do
 186                         if i == -1 then
 187                                 s.add "right(>)"
 188                         else if i == 1 then
 189                                 s.add "left(<)"
 190                         else if i == -width then
 191                                 s.add "down(v)"
 192                         else if i == width then
 193                                 s.add "up(^)"
 194                         else
 195                                 abort
 196                         end
 197                 end
 198                 print "Solution in {plan.length} moves: {s.join(" ")}"
 199         end
 200
 201         redef fun make_memory do
 202                 var res = super
 203                 res.add new RBTreeMap[ArrayCmp[Tile], SearchNode[ArrayCmp[Tile], Int]]
 204                 res.add new BinTreeMap[ArrayCmp[Tile], SearchNode[ArrayCmp[Tile], Int]]
 205                 return res
 206         end
 207 end
 208
 209 # A movable tile
 210 # A simple class to encapsulate the symbol and the goal position.
 211 class Tile
 212         super Comparable
 213         redef type OTHER: Tile is fixed
 214
 215         # The symbol written on the tile
 216         var symbol: Char
 217
 218         # The expected position in the grid
 219         var goal_idx: Int
 220
 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
 225 end
 226
 227 var configs = false
 228
 229 if not args.is_empty then
 230         if args.first == "--configs" then
 231                 configs = true
 232                 args.shift
 233         end
 234 end
 235
 236 if args.is_empty then
 237         print """
 238 Usage: puzzle [--configs] initial...
 239
 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:
 242
 243  8-puzzle:
 244
 245  goal (0):    abcdefgh.
 246  easy (4):    abce.fdgh
 247  medium (10): eabf.cdgh
 248  hard (20):   feacbh.dg
 249  harder (31): hfgbedc.a
 250
 251  15-puzzle:
 252  goal (0):    abcdefghijklmno.
 253  easy (30):   bacdefghijlkmno.
 254  medium (40): fg.jacoheldnibmk
 255  hard (55):   kleg.mondcafjhbi
 256  harder (61): lomgkcend.afjhbi
 257
 258  24-puzzle:
 259  goal (0):    abcdefghijklmnopqrstuvwx.
 260  easy (55):   giabcjekmdhrtflqsownpuv.x
 261  medium (75): giabcjekmdrtwulhs.vnqofpx
 262  hard (79):   giabcjekmdrtw.uhsvnlqofpx
 263  harder (80): giabcjekmdrt.wuhsvnlqofpx
 264 """
 265         exit 0
 266 end
 267
 268
 269 for arg in args do
 270         var pb = new PuzzleProblem(arg)
 271         print "Initial: {arg}"
 272         pb.print_state(pb.initial_state)
 273
 274         if configs then
 275                 pb.run_configs(1000000)
 276                 continue
 277         end
 278
 279         var c = new Clock
 280         var s = pb.astar
 281         s.memorize = true
 282         var r = s.run
 283         if r == null then
 284                 print "No solution."
 285                 break
 286         end
 287
 288         print "Solved, after looking at {r.steps} positions"
 289         pb.print_plan(r.plan)
 290 end