3033


「アルゴリズムとデータ構造」紀平拓男／春日伸弥 著
（<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]


CC BY-SA 3.0
2015-01-04T08:41:13.077
3021
2015-01-05T15:40:25.470
2015-01-05T06:34:34.113
2079
5363
question
ruby アルゴリズム
エイトクイーンパズルの解法について


質問のコードは `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]


CC BY-SA 3.0
2015-01-04T09:36:45.323
3033
2015-01-05T15:40:25.470
2015-01-05T15:40:25.470
5575
5575
3021
answer


質問文にあるコードでは、大きく２つの問題があります。

１．howBoard 一回しか よばれていません。 solve(x) の中で x == 8 の時は
すべての列にクィーンが置けた状態になったので、、その時点で showBoard することが必要です。

  2. solve(x) の中で x == 8 の時に true を返しており、次のクィーンの置き方を試すようになっていません。

これらを修正する、コードの重複を除去する、 8-クィーンだけでなく4-クィーンなど他の N-クィーン問題も解けるようにする などの変更をしてみました。
(さらに少しの工夫を加えることで、ボードを回転させた時に同じになる解を取り除くことも可能です) 実行すると 92 個も解が表示されます。

[code]

    # coding: utf-8
    
    # See https://ja.stackoverflow.com/questions/3021  エイトクイーンパズルの解法について
    
    # ボードの 1 辺のサイズ
    N = 8 # 4
    
    # 解の数を 0 に設定する。
    @count = 0
    
    # ボードを空に設定する。
    @board = Array.new(N) { Array.new(N, false) }
    
    # ボード上のクィーンの配置を表示する。
    def showBoard
      (0..N - 1).each do |y|
        (0.. N - 1).each do |x|
          printf @board[x][y]? 'Q ' : '. '
        end
        printf "\n"
      end
    end
    
    # (x, y) にクィーンが置けるかどうかチェック
    def check(x, y)
    
      dys = [
        -1,   # 左上方向を調べるための行位置の変化
        0,    # 左方向を調べるための　行位置の変化
        1     # 左下方向を調べるための行位置の変化
      ]
      dys.each do |dy|
        (1..x).each do |dx|
          x1 = x - dx
          y1 = y + dy * dx
          return false if (0 <= y1) && (y1 < N) && @board[x1][y1]
        end
      end
      true
    end
    
    def solve(x)
      if x == N
        # すべての列にクィーンを置けたので、解を表示する。
        @count += 1
        printf "#{@count} --------\n"
        showBoard
      else
        # (x, 0) ... (x, N-1) にクィーンを置くことを試していく。
        (0..N - 1).each do |i|
          if check(x, i)
            # (x, i) にクィーンが置けるので、実際に置く。
            @board[x][i] = true
    
            # 次の列に進む
            solve(x + 1)
    
            # (x, i) に置いたクィーンを取り除く。
            @board[x][i] = false
          end
        end
      end
    end
    
    # N  クィーン問題を解く。
    solve(0)
    
[/code]


CC BY-SA 3.0
2015-01-04T11:24:59.330
3050
2015-01-04T11:24:59.330
2987
3021
answer