← 都来码 / Dolaima← 例程索引ruby/school/n-queens.rb 原文

ruby/school/n-queens.rb · 1441 字节 · 下载原文

# 1. Divide n by 12. Remember the remainder (n is 8 for the eight queens
#    puzzle).
# 2. Write a list of the even numbers from 2 to n in order.
# 3. If the remainder is 3 or 9, move 2 to the end of the list.
# 4. Append the odd numbers from 1 to n in order, but, if the remainder is 8,
#    switch pairs (i.e. 3, 1, 7, 5, 11, 9, …).
# 5. If the remainder is 2, switch the places of 1 and 3, then move 5 to the
#    end of the list.
# 6. If the remainder is 3 or 9, move 1 and 3 to the end of the list.
# 7. Place the first-column queen in the row with the first number in the
#    list, place the second-column queen in the row with the second number in
#    the list, etc.


def n_queens(n)
  if n == 1
    return "Q"
  elsif n < 4
    puts "no solutions for n=#{n}"
    return ""
  end
 
  evens = (2..n).step(2).to_a
  odds = (1..n).step(2).to_a
 
  rem = n % 12  # (1)
  nums = evens  # (2)
 
  nums.rotate if rem == 3 or rem == 9  # (3)
 
  # (4)
  if rem == 8
    odds = odds.each_slice(2).flat_map(&:reverse)
  end
  nums.concat(odds)
 
  # (5)
  if rem == 2
    nums[nums.index(1)], nums[nums.index(3)] = nums[nums.index(3)], nums[nums.index(1)]
    nums << nums.delete(5)
  end
 
  # (6)
  if rem == 3 or rem == 9
    nums << nums.delete(1)
    nums << nums.delete(3)
  end
 
  # (7)
  nums.map do |q|
    a = Array.new(n,".")
    a[q-1] = "Q"
    a*(" ")
  end
end
 
(1 .. 15).each {|n| puts "n=#{n}"; puts n_queens(n); puts}