8女王問題 その１

８女王問題。
単純な(力技の)実装
セルを順番に試しておければ置いてみて、全て置ければ表示する。
全てのセルを試してみてダメだったら、１つ戻って(１つセルを取り除いて)リトライする。
アルゴリズムはsolveメソッドで実装している。

・・・但し重複を検出できないので同じ解が何度も出てくる。
解くには解けるが非常に間抜けな方法。
セル数が８×８だと結構待っても終わらない。

#!/usr/local/bin/ruby
# -*- coding: utf-8 -*-
#
# queen1.rb

#-- セルの数を表す。
#-- 縦、横同じ長さである。
NUMBEROFQUEEN = 8

#-- ボードを表す。
#-- 実際のデータは@boardに格納される。
#-- 空白セルは0、女王がいるセルは1で表す。
class Queen

  #-- 初期化
  #-- ボードを表す@boardに初期値を設定する。
  def initialize
    @board = []

    x = 0
    while x < NUMBEROFQUEEN do
      y = 0
      tmp = []
      while y < NUMBEROFQUEEN do
        tmp << 0
        y = y+1
      end

      @board << tmp
      x = x+1
    end

  end

  #-- 与えられた位置に女王が置けるかどうか調べる。
  #-- 置ければtrueを返す。
  def possible(row, col)
    @board[row][col] == 0 &&
    row_possible(row, col) &&
    col_possible(row, col) &&
    slant_possible(row, col)
  end

  #-- 指定されたセルを含む行に既に女王がいないかを確認する。
  #-- 1つもいなければtrueを返す。
  def row_possible(row, col)
    @board[row].each do |x|
      if x == 1
        return false
      end
    end
    true
  end

  #-- 指定されたセルを含む列に既に女王がいないかを確認する。
  #-- 1つもいなければtrueを返す。
  def col_possible(row, col)
    @board.each do |x|
      if x[col] == 1
        return false
      end
    end
    true
  end

  #-- 指定されたセルを含む斜めに既に女王がいないかを確認する。
  #-- 1つもいなければtrueを返す。
  #-- 斜めの4方向に力技で調べている。
  #-- もう少し効率的なやり方があるのでは。。。
  def slant_possible(row, col)

    x = row
    y = col
    while x >= 0 && y >= 0
      if @board[x][y] == 1
        return false
      end
      x = x-1
      y = y-1
    end

    x = row
    y = col
    while x >= 0 && y < NUMBEROFQUEEN
      if @board[x][y] == 1
         return false
      end
      x = x-1
      y = y+1
    end

    x = row
    y = col
    while x < NUMBEROFQUEEN && y >= 0
      if @board[x][y] == 1
        return false
      end
      x = x+1
      y = y-1
    end

    x = row
    y = col
    while x < NUMBEROFQUEEN && y < NUMBEROFQUEEN
      if @board[x][y] == 1
        return false
      end
      x = x+1
      y = y+1
    end

    true
  end

  #-- 自身のコピーを生成する。
  #-- 単なるdupだと、@boardはコピーされない。
  #-- 同じ@boardを2つのQueenオブジェクトが参照する異になってしまう。
  #-- そのため、@boradのコピーを明示的に生成する。
  #-- 1行目のsuperはこのメソッド(dup)を意味する。
  #-- 即ち、copyにQueenオブジェクトのコピーを生成する。
  #-- 更に2行目で@boardのコピーを生成し、新たに生成した@boardを
  #-- 元のQueenが参照するようにしている。
  #-- 新しく生成したQueenは元の@boardを参照している。
  #-- 2次元配列なので配列の配列をコピーするためwhile文で回して
  #-- 個々の要素をコピーしている。
  #-- 最後の行で生成したQueenオブジェクトを返す。
  def dup
    copy = super
    @board = @board.dup
    x = 0
    while x < NUMBEROFQUEEN do
      @board[x] = @board[x].dup
      x = x + 1
    end
    copy
  end




#-----------------------------------
#-- FOR DEBUG
#-----------------------------------

  #-- ボードを縦横並べて表示する。
  def print_board
    #print "-- print board --\n"
    @board.each do |x|
      x.each do |y|
        print y
      end
      #print "\n"
    end
    print "\n"
  end

  #-- していれたセルの値を表示する。
  def print_cell(row, col)
    print "cell[#{row}][#{col}] :  ", @board[row][col], "\n"
  end

  def set_cell(row, col, val)
    @board[row][col] = val
  end

end #-- END OF CLASS Queen



#-----------------------------------
#-- 片っ端から1つづつqueenを置いていく。
#-- あるセルにqueenが置けたら、更に次の1個を置くため
#-- 再帰的にこのメソッドを実行する。
#-- 全てのセルに試したらリターンする。
def solve(queen, num)

  #-- 全てのqueenをおいた状態ならばそれを表示してリターンする。
  if num >= NUMBEROFQUEEN
    queen.print_board
    return
  end

  x = 0
  while x < NUMBEROFQUEEN do
    y = 0
    while y < NUMBEROFQUEEN do
      # print "  num: ", num+1, " x: ", x, " y: ", y, "\n"
      if queen.possible(x, y)
        princess = queen.dup
        princess.set_cell(x, y, 1)
        # print "! num: ", num+1, " x: ", x, " y: ", y, "\n"
        solve(princess, num+1)
      end
      y = y + 1
    end
    x = x + 1
  end

 
end



# =====================================

a = Queen.new
solve(a, 0)