lib/ai/examples/queens.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 # Example of the famous eight-queens problem solved with the `ai::backtrack` module.
  12 #
  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.
  15 #
  16 # Eg. a solution to the 8-queens problem is
  17 # ~~~raw
  18 # +--------+
  19 # |Q.......|
  20 # |....Q...|
  21 # |.......Q|
  22 # |.....Q..|
  23 # |..Q.....|
  24 # |......Q.|
  25 # |.Q......|
  26 # |...Q....|
  27 # +--------+
  28 #
  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
  32
  33 import ai::backtrack
  34
  35 # The (eight-)queens problem, modeled naively as a `BacktrackProblem`.
  36 #
  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.
  43 #
  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.
  47 class QueenProblem
  48         super BacktrackProblem[Array[Int], Int]
  49
  50         # The initial state has no queens; so, no occupied rows.
  51         redef fun initial_state do return new Array[Int]
  52
  53         # The board size.
  54         # Hint: use 8 to be traditional.
  55         var size: Int
  56
  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)
  60         do
  61                 # No more than 8 rows
  62                 if rows.length >= size then return null
  63
  64                 # Available columns. At first, all are available.
  65                 var columns = new Array[Bool].filled_with(true, size)
  66
  67                 # Look at each occupied row and cancel columns
  68                 var i = rows.length # delta for each diagonal
  69                 for r in rows do
  70                         columns[r] = false # no queen under `r`
  71                         var d = r - i
  72                         if d >= 0 then columns[d] = false # no queen on the first diagonal
  73                         d = r + i
  74                         if d < size then columns[d] = false # no queen on the second diagonal
  75                         i -= 1
  76                 end
  77
  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)
  81
  82                 return res
  83         end
  84
  85         # The first free row become occupied with a queen placed where indicated.
  86         redef fun apply_action(rows, column)
  87         do
  88                 rows.add column
  89         end
  90
  91         # Just `free` the last occupied row.
  92         redef fun backtrack(rows, column)
  93         do
  94                 rows.pop
  95         end
  96
  97         # Are all rows are occupied?
  98         redef fun is_goal(rows) do return rows.length >= size
  99
 100         # Draw a nice board
 101         fun print_state(rows: Array[Int])
 102         do
 103                 printn "+"
 104                 for i in [0..size[ do printn "-"
 105                 print "+"
 106                 for r in rows do
 107                         printn "|"
 108                         for i in [0..r[ do printn "."
 109                         printn "Q"
 110                         for i in [r+1..size[ do printn "."
 111                         print  "|"
 112                 end
 113                 for r in [rows.length..size[ do
 114                         printn "|"
 115                         for i in [0..size[ do printn "."
 116                         print  "|"
 117                 end
 118                 printn "+"
 119                 for i in [0..size[ do printn "-"
 120                 print "+"
 121         end
 122 end
 123
 124 # just cont solutions (no not print them)
 125 var quiet = false
 126
 127 # The board size
 128 var size = 8
 129
 130 # Basic argument parsing
 131 if args.length > 0 and args.first == "-q" then
 132         args.shift
 133         quiet = true
 134 end
 135 if args.length > 0 then
 136         size = args.first.to_i
 137         if size <= 0 then
 138                 print "usage: queens [-q] [size]\n -q for quiet"
 139                 exit 1
 140         end
 141 end
 142
 143 print "The {size}-queens problem"
 144 var pb = new QueenProblem(size)
 145 var s = pb.solve
 146 var sols = 0
 147 while s.is_running do
 148         if s.run != null then
 149                 if not quiet then pb.print_state(s.state)
 150                 sols += 1
 151         end
 152 end
 153 print "Found {sols} solutions"