1  # N Queens: A probabilistic approach.
   2  #           by Frank W.
   3  
   4  class Board
   5  
   6    attr_reader :tries
   7  
   8    def initialize(size)
   9      @board = []
  10      size.times { @board << [ false ] * size }
  11  
  12      @rows = (0...size).to_a
  13      @size = size
  14      @to_try = @size / 2
  15      
  16      @tries = 0
  17    end
  18  
  19    def solve
  20      while @rows.length != 0 do
  21        row = @rows.pop
  22        place_row( row )
  23      end
  24    end
  25  
  26    def place_row(row)
  27      # Try a few random placements
  28      @to_try.times do
  29        @tries += 1
  30        col = rand( @size )
  31        if good_place(row, col) then
  32          @board[row][col] = true
  33          return
  34        end
  35      end
  36  
  37      # Place anyway, and remove conflicts (attackers)
  38      col = rand( @size )
  39      remove_conflicts(row, col)
  40      @board[row][col] = true
  41    end
  42  
  43    def good_place(row, col)
  44      # Test if row and col is a legal placement.
  45      # This means no other queen is attacking that spot.
  46      conflicts(row, col) do |r, c|
  47        return false # Any conflicts is an instant false
  48      end
  49  
  50      return true # No conflicts means we are ok
  51    end
  52  
  53    def remove_conflicts(row, col)
  54      # Remove all queens which are attacking the spot
  55      # at row, col. Put them back on the @rows queue.
  56      conflicts(row, col) do |r, c|
  57        @board[r][c] = false
  58        @rows.unshift( r )
  59      end
  60    end
  61  
  62    def conflicts(row, col)
  63      # Yield each row and column pair that
  64      # conflicts with the given row and column
  65  
  66      # These 3 column index vars will count the
  67      # 2 diagonals and center column while the
  68      # row counts up
  69      cl = col - row
  70      cc = col
  71      cr = col + row
  72  
  73      (0...@size).each do |r|
  74  
  75        my_cl = cl + r
  76        my_cc = cc
  77        my_cr = cr - r
  78  
  79        if my_cl >= 0 && my_cl < @size then
  80          yield(r, my_cl) if @board[r][my_cl]
  81        end
  82        
  83        yield(r, my_cc) if @board[r][my_cc]
  84  
  85        if my_cr >= 0 && my_cr < @size then
  86          yield(r, my_cr) if @board[r][my_cr]
  87        end
  88      end
  89    end
  90    
  91    def to_s
  92      @board.collect do |row|
  93        row.collect { |col| col ? "Q" : "." }.join(" ")
  94      end.join("\n")
  95    end
  96  
  97  end
  98  
  99  def usage
 100    puts "Usage: nqueens <n> with 4 <= n <= 100 (4 and 1 are trivial, 2 and 3 are impossible)"
 101    exit 1
 102  end
 103  
 104  def main
 105    usage if ARGV.length != 1
 106    
 107    size = ARGV.pop.to_i
 108    usage if size < 4 || size > 100
 109    
 110    b = Board.new(size)
 111  
 112    b.solve
 113  
 114    puts "#{size} queens in #{b.tries} tries:"
 115    puts b
 116  end
 117  
 118  main