ai :: QueenProblem
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.
ai $ QueenProblem :: SELF
Type of this instance, automatically specialized in every classai $ QueenProblem :: actions
What are the available columns for a queen in the first free row?ai $ QueenProblem :: apply_action
The first free row become occupied with a queen placed where indicated.ai $ QueenProblem :: initial_state
The initial state has no queens; so, no occupied rows.ai :: BacktrackProblem :: actions
The available and applicable actions for a given stateai :: BacktrackProblem :: apply_action
Modifystate
by applying action
core :: Object :: class_factory
Implementation used byget_class
to create the specific class.
core :: Object :: defaultinit
ai :: BacktrackProblem :: defaultinit
ai :: QueenProblem :: defaultinit
ai :: BacktrackProblem :: initial_state
The starting state of the problem.core :: Object :: is_same_instance
Return true ifself
and other
are the same instance (i.e. same identity).
core :: Object :: is_same_serialized
Isself
the same as other
in a serialization context?
core :: Object :: is_same_type
Return true ifself
and other
have the same dynamic type.
core :: Object :: output_class_name
Display class name on stdout (debug only).S
) and actions (A
).
# 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
lib/ai/examples/queens.nit:35,1--122,3