8皇后

西洋棋中的皇后可以直線前進，吃掉遇到的所有棋子，如果棋盤上有八個皇后，則這八個皇后如何相安無事的放置在棋盤上，1970年與1971年， E.W.Dijkstra與N.Wirth曾經用這個問題來講解程式設計之技巧。

解法
關於棋盤的問題，都可以用遞迴求解，然而如何減少遞迴的次數？在八個皇后的問題中，不必要所有的格子都檢查過，例如若某列檢查過，該該列的其它格子就不用再檢查了，這個方法稱為分支修剪。
八個皇后


所以檢查時，先判斷是否在已放置皇后的可行進方向上，如果沒有再行放置下一個皇后，如此就可大大減少遞迴的次數，例如以下為修剪過後的遞迴檢查行進路徑：
八個皇后

八個皇后的話，會有92個解答，如果考慮棋盤的旋轉，則旋轉後扣去對稱的，會有12組基本解。

class Queen
  def initialize
    @queen=Array.new(8+1,0)
    @colum=Array.new(8+1,0)
    @rup=Array.new(2*8+1,0)
    @lup=Array.new(2*8+1,0)
  end

  def backtrack
    for i in 1..8
      @colum[i]=1
    end
    for j in 1..2*8
      @rup[j]=1
      @lup[j]=1
    end
    _backtrack(1)
  end

  def  _backtrack(i)
    if i>8
      _print
    else
      for j in 1..8
        if @colum[j]==1 && @rup[i+j]==1 && @lup[i-j+8]==1
          @queen[i]=j
          @colum[j]=0
          @rup[i+j]=0
          @lup[i-j+8]=0
          _backtrack(i+1)
          @colum[j]=1
          @rup[i+j]=1
          @lup[i-j+8]=1
        end
      end
    end

  end

  def _print
    for y in 1..8
      for x in 1..8
        if @queen[y]==x
          print "Q"
        else
          print "."
        end
      end
      puts "\n"
    end
    puts "\n"
  end
end

queen=Queen.new
queen.backtrack