--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# This file is free software, which comes along with NIT. This software is
+# distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+# without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
+# PARTICULAR PURPOSE. You can modify it is you want, provided this header
+# is kept unaltered, and a notification of the changes is added.
+# You are allowed to redistribute it and sell it, alone or is a part of
+# another product.
+
+# The N-puzzle problem, modeled naively as a `SearchProblem`.
+#
+# A square grid, made of tiles represented with a letter, is scrambled.
+# A missing tile, the hole, represented with a dot, is used to move them.
+#
+# The goal is to found a plan, made of the four basic movements up, down,
+# left, and right, that move each letter to its correct position: the solved
+# grid list letters alphabetically from left to right then top to bottom.
+# The hole must be in the last position (bottom-right).
+#
+# The argument of the program is a initial position, the program then find
+# the best plan to solve the puzzle.
+#
+# ## Example:
+#
+# The argument "abcd.fgeh" is the grid
+#
+# ~~~
+# abc
+# d.f
+# geh
+# ~~~
+#
+# The goal is:
+#
+# ~~~
+# abc
+# def
+# gh.
+# ~~~
+#
+# The shortest plan, in two steps, is to move *up* the tile under the hole (e),
+# then to move *left* the tile after the hole (h).
+import ai::search
+
+# The state (`S`) is a square grid, modeled as a one-dimensional array of Tile.
+# read from left to right then top to bottom.
+#
+# An action (`A`) is the relative position of the tile to swap with the hole.
+# Therefore, `-1` for left, `1` for right, `-width` for up and `width` for down.
+class PuzzleProblem
+ super SearchProblem[ArrayCmp[Tile], Int]
+
+ # The initial grid. use letters for tiles, and . for the hole.
+ var initial_grid: String
+
+ # The width of the grid.
+ # Eg. 3 for a 8-puzzle grid
+ var width: Int is noinit
+
+ # Construct a state form `initial_grid`
+ redef fun initial_state do
+ var g = initial_grid
+ var len = g.length
+ var width = len.sqrt.to_i
+ self.width = width
+ if width * width != len then
+ print "Error: {g} has {len} tiles. A square number, like {width*width} is needed"
+ exit 1
+ end
+ var res = new ArrayCmp[Tile]
+ for i in [0..g.length[ do
+ var c = g.chars[i]
+ if c == ' ' or c == '.' then
+ var hole = new Tile('.', -1)
+ self.hole = hole
+ res.add hole
+ else if c >= '1' and c <= '9' then
+ var t = new Tile(c, '1'.distance(c))
+ res.add t
+ else if c >= 'a' and c <= 'z' then
+ var t = new Tile(c, 'a'.distance(c))
+ res.add t
+ else if c >= 'A' and c <= 'Z' then
+ var t = new Tile(c, 'A'.distance(c))
+ res.add t
+ else
+ print "Error: illegal tile {c} in {g}"
+ exit 1
+ end
+ end
+ return res
+ end
+
+ # Get the four available movements, or 3 on a edge, or 2 in a corner.
+ redef fun actions(state)
+ do
+ var h = get_hole(state)
+ var x = h % width
+ var y = h / width
+ var res = new Array[Int]
+ if x >= 1 then res.add(-1)
+ if x < width-1 then res.add(1)
+ if y >= 1 then res.add(-width)
+ if y < width-1 then res.add(width)
+ return res.as_random.take_all
+ end
+
+ # Return the state where the tile at hole+action has moved
+ redef fun apply_action(state, action)
+ do
+ # Copy the state
+ var res = new ArrayCmp[Tile].with_capacity(state.length)
+ res.add_all(state)
+
+ # Get the hole and the tile next to it
+ var h = get_hole(res)
+ var t = h + action
+
+ # Move (by swapping the tile and the hole)
+ res[h] = res[t]
+ res[t] = hole
+
+ return res
+ end
+
+ # The special empty tile for fast retrieval.
+ var hole: Tile is noinit
+
+ # What is the position of the hole?
+ fun get_hole(state: Array[Tile]): Int
+ do
+ return state.index_of(hole)
+ end
+
+ # Each tile is at its correct position
+ redef fun is_goal(state)
+ do
+ for i in [0..state.length[ do
+ var t = state[i]
+ if t != hole and t.goal_idx != i then return false
+ end
+ return true
+ end
+
+ # The sum of the Manhattan distances of each tile to its goal
+ # Not the best heuristic but the simplest to implement among the good ones.
+ redef fun heuristic(state)
+ do
+ var p = 0
+ var i = -1
+ for t in state do
+ i += 1
+
+ # The hole does not count
+ if t == hole then continue
+
+ var dx = (i % width - t.goal_idx % width).abs
+ var dy = (i / width - t.goal_idx / width).abs
+
+ # Add Manhattan distance
+ p += dx + dy
+ end
+ return p.to_f
+ end
+
+ # Print the grid
+ fun print_state(state: Array[Tile])
+ do
+ for i in [0..state.length[ do
+ var t = state[i]
+ if t == hole then
+ printn "."
+ else
+ printn t.symbol
+ end
+ if (i+1) % width == 0 then print ""
+ end
+ end
+
+ # Print the plan with words.
+ fun print_plan(plan: Sequence[Int])
+ do
+ var s = new Array[String]
+ for i in plan do
+ if i == -1 then
+ s.add "right(>)"
+ else if i == 1 then
+ s.add "left(<)"
+ else if i == -width then
+ s.add "down(v)"
+ else if i == width then
+ s.add "up(^)"
+ else
+ abort
+ end
+ end
+ print "Solution in {plan.length} moves: {s.join(" ")}"
+ end
+
+ redef fun make_memory do
+ var res = super
+ res.add new RBTreeMap[ArrayCmp[Tile], SearchNode[ArrayCmp[Tile], Int]]
+ res.add new BinTreeMap[ArrayCmp[Tile], SearchNode[ArrayCmp[Tile], Int]]
+ return res
+ end
+end
+
+# A movable tile
+# A simple class to encapsulate the symbol and the goal position.
+class Tile
+ super Comparable
+ redef type OTHER: Tile is fixed
+
+ # The symbol written on the tile
+ var symbol: Char
+
+ # The expected position in the grid
+ var goal_idx: Int
+
+ redef fun to_s do return symbol.to_s
+ redef fun ==(o) do return o isa Tile and goal_idx == o.goal_idx
+ redef fun <(o) do return goal_idx < o.goal_idx
+ redef fun <=>(o) do return goal_idx <=> o.goal_idx
+end
+
+var configs = false
+
+if not args.is_empty then
+ if args.first == "--configs" then
+ configs = true
+ args.shift
+ end
+end
+
+if args.is_empty then
+ print """
+Usage: puzzle [--configs] initial...
+
+--configs: search and time solutions with various configurations of solvers.
+initial: an initial configuration (letters for the tiles, and dot for the hole). eg:
+
+ 8-puzzle:
+
+ goal (0): abcdefgh.
+ easy (4): abce.fdgh
+ medium (10): eabf.cdgh
+ hard (20): feacbh.dg
+ harder (31): hfgbedc.a
+
+ 15-puzzle:
+ goal (0): abcdefghijklmno.
+ easy (30): bacdefghijlkmno.
+ medium (40): fg.jacoheldnibmk
+ hard (55): kleg.mondcafjhbi
+ harder (61): lomgkcend.afjhbi
+
+ 24-puzzle:
+ goal (0): abcdefghijklmnopqrstuvwx.
+ easy (55): giabcjekmdhrtflqsownpuv.x
+ medium (75): giabcjekmdrtwulhs.vnqofpx
+ hard (79): giabcjekmdrtw.uhsvnlqofpx
+ harder (80): giabcjekmdrt.wuhsvnlqofpx
+"""
+ exit 0
+end
+
+
+for arg in args do
+ var pb = new PuzzleProblem(arg)
+ print "Initial: {arg}"
+ pb.print_state(pb.initial_state)
+
+ if configs then
+ pb.run_configs(1000000)
+ continue
+ end
+
+ var c = new Clock
+ var s = pb.astar
+ s.memorize = true
+ var r = s.run
+ if r == null then
+ print "No solution."
+ break
+ end
+
+ print "Solved, after looking at {r.steps} positions during {c.lapse}"
+ pb.print_plan(r.plan)
+end
nitlanguage / nit.git / commitdiff