--- /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.
+
+# Example of the famous eight-queens problem solved with the `ai::backtrack` module.
+#
+# The game is to places n queens on a n*n chessboard.
+# The constraint is that two queens cannot be on the same row, column or diagonal.
+#
+# Eg. a solution to the 8-queens problem is
+# ~~~
+# +--------+
+# |Q.......|
+# |....Q...|
+# |.......Q|
+# |.....Q..|
+# |..Q.....|
+# |......Q.|
+# |.Q......|
+# |...Q....|
+# +--------+
+#
+# This program takes an integer n as argument then display all solutions for the
+# n-queens proglem (ie. on a n*n board).
+module queens
+
+import ai::backtrack
+
+# The (eight-)queens problem, modeled naively as a `BacktrackProblem`.
+#
+# The state (`S`) is a board, modeled as an array of occupied rows.
+# The integer in each row indicates the column occupied by the queen.
+# Since there can be only one queen by row, a single `Int` is
+# enough for each row, and the whole board `rows` is just an `Array[Int]`.
+# Only the occupied rows are stored, thus the length of `rows` indicates
+# the number of occupied rows, the remaining virtual rows are considered free.
+#
+# An action (`A`) is the column where to put a queen in the first free row,
+# so modeled as an Int.
+# Actions are applied until all rows are occupied by a queen.
+class QueenProblem
+ super BacktrackProblem[Array[Int], Int]
+
+ # The initial state has no queens; so, no occupied rows.
+ redef fun initial_state do return new Array[Int]
+
+ # The board size.
+ # Hint: use 8 to be traditional.
+ var size: Int
+
+ # What are the available columns for a queen in the first free row?
+ # Just look at occupied rows above and cancel the possible columns one by one.
+ redef fun actions(rows, node)
+ do
+ # No more than 8 rows
+ if rows.length >= size then return null
+
+ # Available columns. At first, all are available.
+ var columns = new Array[Bool].filled_with(true, size)
+
+ # Look at each occupied row and cancel columns
+ var i = rows.length # delta for each diagonal
+ for r in rows do
+ columns[r] = false # no queen under `r`
+ var d = r - i
+ if d >= 0 then columns[d] = false # no queen on the first diagonal
+ d = r + i
+ if d < size then columns[d] = false # no queen on the second diagonal
+ i -= 1
+ end
+
+ # Collect the remaining columns, those that were not cancelled.
+ var res = new Array[Int]
+ for c in [0..size[ do if columns[c] then res.add(c)
+
+ return res
+ end
+
+ # The first free row become occupied with a queen placed where indicated.
+ redef fun apply_action(rows, column)
+ do
+ rows.add column
+ end
+
+ # Just `free` the last occupied row.
+ redef fun backtrack(rows, column)
+ do
+ rows.pop
+ end
+
+ # Are all rows are occupied?
+ redef fun is_goal(rows) do return rows.length >= size
+
+ # Draw a nice board
+ fun print_state(rows: Array[Int])
+ do
+ printn "+"
+ for i in [0..size[ do printn "-"
+ print "+"
+ for r in rows do
+ printn "|"
+ for i in [0..r[ do printn "."
+ printn "Q"
+ for i in [r+1..size[ do printn "."
+ print "|"
+ end
+ for r in [rows.length..size[ do
+ printn "|"
+ for i in [0..size[ do printn "."
+ print "|"
+ end
+ printn "+"
+ for i in [0..size[ do printn "-"
+ print "+"
+ end
+end
+
+# just cont solutions (no not print them)
+var quiet = false
+
+# The board size
+var size = 8
+
+# Basic argument parsing
+if args.length > 0 and args.first == "-q" then
+ args.shift
+ quiet = true
+end
+if args.length > 0 then
+ size = args.first.to_i
+ if size <= 0 then
+ print "usage: queens [-q] [size]\n -q for quiet"
+ exit 1
+ end
+end
+
+print "The {size}-queens problem"
+var pb = new QueenProblem(size)
+var s = pb.solve
+var sols = 0
+while s.is_running do
+ if s.run != null then
+ if not quiet then pb.print_state(s.state)
+ sols += 1
+ end
+end
+print "Found {sols} solutions"
nitlanguage / nit.git / commitdiff