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 # Example of the famous eight-queens problem solved with the `ai::backtrack` module.
13 # The game is to places n queens on a n*n chessboard.
14 # The constraint is that two queens cannot be on the same row, column or diagonal.
16 # Eg. a solution to the 8-queens problem is
29 # This program takes an integer n as argument then display all solutions for the
30 # n-queens proglem (ie. on a n*n board).
31 module queens
is example
35 # The (eight-)queens problem, modeled naively as a `BacktrackProblem`.
37 # The state (`S`) is a board, modeled as an array of occupied rows.
38 # The integer in each row indicates the column occupied by the queen.
39 # Since there can be only one queen by row, a single `Int` is
40 # enough for each row, and the whole board `rows` is just an `Array[Int]`.
41 # Only the occupied rows are stored, thus the length of `rows` indicates
42 # the number of occupied rows, the remaining virtual rows are considered free.
44 # An action (`A`) is the column where to put a queen in the first free row,
45 # so modeled as an Int.
46 # Actions are applied until all rows are occupied by a queen.
48 super BacktrackProblem[Array[Int], Int]
50 # The initial state has no queens; so, no occupied rows.
51 redef fun initial_state
do return new Array[Int]
54 # Hint: use 8 to be traditional.
57 # What are the available columns for a queen in the first free row?
58 # Just look at occupied rows above and cancel the possible columns one by one.
59 redef fun actions
(rows
, node
)
62 if rows
.length
>= size
then return null
64 # Available columns. At first, all are available.
65 var columns
= new Array[Bool].filled_with
(true, size
)
67 # Look at each occupied row and cancel columns
68 var i
= rows
.length
# delta for each diagonal
70 columns
[r
] = false # no queen under `r`
72 if d
>= 0 then columns
[d
] = false # no queen on the first diagonal
74 if d
< size
then columns
[d
] = false # no queen on the second diagonal
78 # Collect the remaining columns, those that were not cancelled.
79 var res
= new Array[Int]
80 for c
in [0..size
[ do if columns
[c
] then res
.add
(c
)
85 # The first free row become occupied with a queen placed where indicated.
86 redef fun apply_action
(rows
, column
)
91 # Just `free` the last occupied row.
92 redef fun backtrack
(rows
, column
)
97 # Are all rows are occupied?
98 redef fun is_goal
(rows
) do return rows
.length
>= size
101 fun print_state
(rows
: Array[Int])
104 for i
in [0..size
[ do printn
"-"
108 for i
in [0..r
[ do printn
"."
110 for i
in [r
+1..size
[ do printn
"."
113 for r
in [rows
.length
..size
[ do
115 for i
in [0..size
[ do printn
"."
119 for i
in [0..size
[ do printn
"-"
124 # just cont solutions (no not print them)
130 # Basic argument parsing
131 if args
.length
> 0 and args
.first
== "-q" then
135 if args
.length
> 0 then
136 size
= args
.first
.to_i
138 print
"usage: queens [-q] [size]\n -q for quiet"
143 print
"The {size}-queens problem"
144 var pb
= new QueenProblem(size
)
147 while s
.is_running
do
148 if s
.run
!= null then
149 if not quiet
then pb
.print_state
(s
.state
)
153 print
"Found {sols} solutions"