■

エイトクイーンパズル、昨日の続き。答えが合わないと思ったのは探索の途中で解を表示させていたせいだった。バックトラック法なので、最後に生成したクイーンを置く位置を探すときに、既に置かれているクイーンの位置が変わることがあるのだった。
探索が終わってから表示させたらちゃんと正しい解が求まっていた。
以下、修正版。

#!/usr/bin/ruby -Ks
# 8 queen problem

$n = 8
$ini_row = 1

class Queen
  def initialize(col, neighbor)
    @row = $ini_row
    @col = col
    @neighbor = neighbor
  end

  def show
    print "|", "_|"*(@row-1), "Ｑ", "_|"*($n-@row), " (#@row, #@col)\n"
  end

  def findSolution
    while @neighbor and @neighbor.canAttack?(@row, @col)
      unless advance
        return false
      end
    end
    true
  end

  def canAttack?(row, col)
    if (row == @row) or ((@col-col).abs == (@row-row).abs)
      return true
    end
    @neighbor and @neighbor.canAttack?(row, col)
  end

  def advance
    if @row < $n
      @row += 1
      return findSolution
    elsif @neighbor and (not @neighbor.advance)
      return false
    end
    @row = 1
    return findSolution
  end
end

queens = []
lastQueen = nil
(1..$n).each do |i|
  lastQueen = Queen.new(i, lastQueen)
  lastQueen.findSolution
  queens << lastQueen
end

queens.each {|q| q.show}