8女王問題 その２

８女王問題の解法その２
１つの列には１つ以上女王を置けず、かつ１つは女王を置かないといけないという事実からのアルゴリズム。
その１よりかなり効率的。
但し、回転や反転対称は重複して解として出力する。

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

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

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

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

    x = 0
    while x < NUMBEROFQUEEN do
      @board << -1
      x = x+1
    end

  end



  #-- 自身のコピーを生成する。
  def dup
    copy = super
    @board = @board.dup
    copy
  end


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


	#-- row番目にcolを入れられるかどうか調べる。
	#-- 入れられればtrue、入れれらなければfalseを返す。
	#-- row以前にcolと同じ値がないことを確認する。
	#-- row以前にcolと斜めでぶつかる値がないかを確認する。
	def check(row, col)
		diff = 0

		row.downto(0){ |x|
			if @board[x] == col
				return false
			end

			if @board[x] == col + diff
				return false
			end

			if @board[x] == col - diff
				return false
			end
			diff = diff+1
		}

		true
	end


  #-- ボードを縦横並べて表示する。
  def print_board
  	print @board, "\n"
  end

end #-- END OF CLASS Queen


#-----------------------------------
#-- 再帰的にsolveを呼び出し、解を見つける。
#-- 女王が置けたら女王を置いた盤を生成し更にsolveを実行する。
def solve(queen, row)

	if (row >= NUMBEROFQUEEN)
		print "Solved!! "
		queen.print_board
		return
	end

	NUMBEROFQUEEN.times{ |col|
		tmp = queen.dup

		if (tmp.check(row, col))
			tmp.set(row, col)
			solve(tmp, row+1)
		end

	}
end


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

a = Queen.new
solve(a, 0)