エイトクイーンパズルの解法について


「アルゴリズムとデータ構造」紀平拓男／春日伸弥 著
（<http://www.sbcr.jp/products/4797324198.html?sku=4797324198>）第10章において
エイトクイーンパズルをC言語で解いているのですが、

左上(0, 0)がクイーンの場合しか答えを出力しない

のはどうしてか教えてください。また、

他の91通りの解を出力するにはどのように修正すればよいか

も教えていただけないでしょうか？

ちなみに以下のコードは、本の解法をRuby版にかなり忠実に置き換えたものです。 （コードの重複等あるかと思いますが、あらかじめご了承ください。）

ご指摘や、コードの修正は、こちらのRuby版で行なっていただけると ありがたいです。

[code]

    @board = Array.new(8, false)
    @board.each_index do |i|
      @board[i] = Array.new(8, false)
    end
    
    # (x,y)にクィーンがあるかどうかチェック
    def check(x, y)
      # 左方向をチェック
      p = 0
      while p < x
        return false if @board[p][y]
        p += 1
      end  
      # 左上方向をチェック
      p, q = x, y
      while p > 0 && q > 0
        return false if @board[p -= 1][q -= 1]
      end 
      # 左下方向をチェック
      p, q = x, y
      while p > 0 && q < 7
        return false if @board[p -= 1][q += 1]
      end
    
      return true
    end
    
    def showBoard
      for y in (0..7)
        for x in (0..7)
          if @board[x][y]
            printf "Q "
          else
            printf ". "
          end
        end
        printf "\n"
      end
    end
    
    def solve(x)
      if x == 8
        return true
      end
    
      i = 0
      while i < 8
        if check(x, i)
          # (x,i)にクィーンがおけたら実際に置く
          @board[x][i] = true
          if solve(x + 1)
            # 次の列以降が成功ならこの列も成功
            return true
          else
            # 次の列以降が失敗ならクィーンを置き直す
            @board[x][i] = false
          end
        end
        i += 1
      end
      return false
    end
    
    if solve(0)
      showBoard
      puts "---------------"
    end
    
[/code]




質問のコードは `solve(x)` で`x`列目の上から`i`行目にクィーンをセットしてみて、 `solve(x + 1)` を呼び出し`x +
1`列より先にクィーンを配置することが可能かどうかを再帰的にテストしています。 `solve(x + 1)` が `false`
を返している場合は`i`番目に配置したクィーンを元に戻してから`i + 1` 番目をテストをしていますが、 `true`
が帰ってきた場合はそこで処理を終了してしまっているので、１つ解が見つかってしまえばそこで処理が終了してしまいます。

全ての解が求めたいのであれば、解が見つかった場合にも `false` の場合と同じように i 番目に配置したクィーンを元に戻して `i + 1`
番目に置いた場合も試すように変更してあげる必要があります。

solve が `x == 8` になり再帰の終端に達した時が、エイトクィーンの解が見つかった時なので `if x == 8`
の中で盤面を表示し、その回数を `num_results` で数えるように修正すればよいです。 この場合 `solve(x + 1)`
の返り値をチェックする必要は特にないので `solve` の返り値は不要です。
質問のオリジナルのコードをなるべく維持したまま修正するなら次のようになります。

[code]

    @board = Array.new(8, false)
    @board.each_index do |i|
      @board[i] = Array.new(8, false)
    end
    
    # (x,y)にクィーンがあるかどうかチェック
    def check(x, y)
      # 左方向をチェック
      p = 0
      while p < x
        return false if @board[p][y]
        p += 1
      end  
      # 左上方向をチェック
      p, q = x, y
      while (p > 0) && (q > 0)
        return false if @board[p -= 1][q -= 1]
      end
      # 左下方向をチェック
      p, q = x, y
      while p > 0 && q < 7
        return false if @board[p -= 1][q += 1]
      end
    
      return true
    end
    
    def showBoard
      for y in (0..7)
        for x in (0..7)
          if @board[x][y]
            printf "Q "
          else
            printf ". "
          end
        end
        printf "\n"
      end
    end
    
    $num_results = 0
    
    def solve(x)
      if x == 8
        # 解が１つ見つかった
        showBoard
        puts "---------------"
        $num_results += 1
      end
    
      i = 0
      while i < 8
        if check(x, i)
          # (x,i)にクィーンがおけたら実際に置く
          @board[x][i] = true
          # (x,i)にクィーンを置いた状態で x + 1 に解があるか調べる
          solve(x + 1)
          @board[x][i] = false
        end
        i += 1
      end
    end
    
    solve(0)
    puts $num_results
    
[/code]




質問のコードは `solve(x)` で`x`列目の上から`i`行目にクィーンをセットしてみて、 `solve(x + 1)` を呼び出し`x +
1`列より先にクィーンを配置することが可能かどうかを再帰的にテストしています。 `solve(x + 1)` が `false`
を返している場合は`i`番目に配置したクィーンを元に戻してから`i + 1` 番目をテストをしていますが、 `true`
が帰ってきた場合はそこで処理を終了してしまっているので、１つ解が見つかってしまえばそこで処理が終了してしまいます。

全ての解が求めたいのであれば、解が見つかった場合にも `false` の場合と同じように i 番目に配置したクィーンを元に戻して `i + 1`
番目に置いた場合も試すように変更してあげる必要があります。

solve が `x == 8` になり再帰の終端に達した時が、エイトクィーンの解が見つかった時なので `if x == 8`
の中で盤面を表示し、その回数を `num_results` で数えるように修正すればよいです。 この場合 `solve(x + 1)`
の返り値をチェックする必要は特にないので `solve` の返り値は不要です。
質問のオリジナルのコードをなるべく維持したまま修正するなら次のようになります。

[code]

    @board = Array.new(8, false)
    @board.each_index do |i|
      @board[i] = Array.new(8, false)
    end
    
    # (x,y)にクィーンがあるかどうかチェック
    def check(x, y)
      # 左方向をチェック
      p = 0
      while p < x
        return false if @board[p][y]
        p += 1
      end  
      # 左上方向をチェック
      p, q = x, y
      while (p > 0) && (q > 0)
        return false if @board[p -= 1][q -= 1]
      end
      # 左下方向をチェック
      p, q = x, y
      while p > 0 && q < 7
        return false if @board[p -= 1][q += 1]
      end
    
      return true
    end
    
    def showBoard
      for y in (0..7)
        for x in (0..7)
          if @board[x][y]
            printf "Q "
          else
            printf ". "
          end
        end
        printf "\n"
      end
    end
    
    $num_results = 0
    
    def solve(x)
      if x == 8
        # 解が１つ見つかった
        showBoard
        puts "---------------"
        $num_results += 1
      end
    
      i = 0
      while i < 8
        if check(x, i)
          # (x,i)にクィーンがおけたら実際に置く
          @board[x][i] = true
          # (x,i)にクィーンを置いた状態で x + 1 に解があるか調べる
          solve(x + 1)
          @board[x][i] = false
        end
        i += 1
      end
    end
    
    solve(0)
    puts $num_results
    
[/code]

