バックトラック法と幅優先探索

• バックトラック法
• 幅優先探索法

バックトラック法

基本的な考え方

　再帰を用いて試行錯誤を漏れなく行うアルゴリズム。

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

queen = EightQueen.new
if queen.solve(0)
  queen.showBoard
end

【冨倉メモ】
　上記のスクリプトでは、開始の位置が(0,0)の場合は、解を発見できるけれど、それ以外の開始位置では正しい解が発見できない。僕の記述が悪いのかと思ったのだけれど、書籍の Java コードでも同様の問題が発生してしまっている。うーん。

幅優先探索法

基本的な考え方

1. 1回の試行錯誤で実現できる全てのパターンを試してみる
2. 次に2回目の試行錯誤で実現できる全てのパターンを試してみる
3. 同様に、出現できる全てのパターンを順に試していく

　キューを用いて実装することが一般的。

class Pattern
  attr_reader :hash, :patternFrom
  def initialize( hash, patternFrom )
    # 今までに現れた局面を記録するクラス
    # このクラスの配列はキュー代わりにも使われる
    @hash = hash
    @patternFrom = patternFrom
  end
end

class SevenPuzzle
  def initialize
    @history = Array.new
    @queueBottom = 0    # キューの末尾位置
  end
  
  # 局面と対応する数字を作り出す関数
  def makeHash( pattern )
    hash = 0
    i = 0
    while i < 8
      hash |= ((pattern[7 - i].to_i) << (i * 4)).to_f
      i += 1
    end
    return hash
  end
  
  # 数字から局面を復元する関数
  def patternFromHash( pattern, hash )
    i = 0
    while i < 8
      pattern[7 - i] = ((hash >> (i * 4)) & 0xf).to_s
      i += 1
    end
  end
  
  def saveHistory( pattern, patternFrom )
    hash = makeHash(pattern)
    i = 0
    while i < @history.size
      if @history[i].hash == hash
        return
      end
      i += 1
    end
    @history.push( Pattern.new(hash, patternFrom) )
  end
  
  def solve7Puzzle()
    pattern = Array.new(8)
    @queueBottom = 0
    solve = makeHash(["1","2","3","4","5","6","7","0"])
    
    while @queueBottom != @history.size
      hash = @history[@queueBottom].hash
      
      # 解にたどり着いたら終了
      return true if hash == solve
      
      patternFromHash(pattern, hash)
      
      blankPos = 0
      while blankPos < 8
        break if pattern[blankPos].to_i == 0
        blankPos += 1
      end
      
      if blankPos > 3
        # 上から空いている場所へ移動
        pattern[blankPos] = pattern[blankPos - 4]
        pattern[blankPos - 4] = 0
        # 新しいパネル配置を保存した後、元の位置に戻す
        saveHistory(pattern, @queueBottom)
        patternFromHash(pattern, hash)
      end
      if blankPos < 4
        # 下から空いている場所へ移動
        pattern[blankPos] = pattern[blankPos + 4]
        pattern[blankPos + 4] = 0
        saveHistory(pattern, @queueBottom)
        patternFromHash(pattern, hash)
      end
      if blankPos != 0 && blankPos != 4
        # 左から空いている場所へ移動
        pattern[blankPos] = pattern[blankPos -1]
        pattern[blankPos - 1] = 0
        saveHistory(pattern, @queueBottom)
        patternFromHash(pattern, hash)
      end
      if blankPos != 3 && blankPos != 7
        # 右から空いている場所へ移動
        pattern[blankPos] = pattern[blankPos + 1]
        pattern[blankPos + 1] = 0
        saveHistory(pattern, @queueBottom)
        patternFromHash(pattern, hash)
      end
      @queueBottom += 1
    end
    # 解が見つからなかった
    return false
  end
  
  def main()
    pattern = [2, 7, 4, 1, 5, 0, 3, 6]
    # 最初の1つ目のパターンを記録
    saveHistory(pattern, -1)
    if solve7Puzzle() == false
      puts "解が見つからなかった"
    else
      puts "解が見つかった"
      # 解を表示する
      last = -1
      while last != @queueBottom
        i = @queueBottom
        while @history[i].patternFrom != last
          i = @history[i].patternFrom
        end
        last = i
        
        # パネルを表示
        patternFromHash(pattern, @history[last].hash)
        i = 0
        while i < 8
          if pattern[i] != 0
            printf "#{pattern[i]} "
          else
            printf "  "
          end
          if i % 4 == 3
            printf "¥n"
          end
          i += 1
        end
        gets()
      end
    end
  end
end

seven = SevenPuzzle.new
seven.main