FC2ブログ
QLOOK ANALYTICS

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

エイト・クイーン問題(n-Queens Question)

学校でエイト・クイーン問題を扱ったので、Rubyの勉強がてらプログラムを作ってみた。


<仕様>

・(メモリが無限にあれば)任意の自然数nのn-Queens問題の解を得る(実際には10ちょいくらいが限界)

n-Queens問題のすべての解を求める

・計算効率についてはあまり考えないことにする

(各列にクイーンは必ず1つ置かれるということを用いてパターンをn^nにした程度で、

深さ優先探索によりすべてのノードを調べる)


以上の仕様でプログラムを作った。

結果としては、例えば

>ruby queens.rb 8

コマンドライン引数に任意の自然数を与えて実行すると

8-Queens問題を解いて92通りの全ての解をテキストファイルに出力し、

標準出力に計算時間を表示するようになっている。


また、コマンドライン引数に複数の値をくれてやれば一度に複数の問題を解いてくれる。

>ruby queens.rb 5 8

こんな感じで。


ソースファイル queens.zip

出力サンプル queens_output.zip


↓以下プログラム

require 'benchmark'class Queens  # n-Queens問題を‚’  # 深さ優先探索によってすべての解を求める    attr_accessor :size    #------------------------------------------------------------  # ● オブジェクト初期化  #------------------------------------------------------------  def initialize    @size = 8    init  end  #------------------------------------------------------------  # ● 初期化  #------------------------------------------------------------  def init    @field = Array.new(@size){Array.new(@size,false)}    @queens = Array.new(@size){Array.new(2,-1)}    @q_num = 0    @answers = []    @i = 0    @j = 0  end  #------------------------------------------------------------  # ● 深さ優先探索  #------------------------------------------------------------  def solve    init # 初期化    catch(:end) do    loop do # 解をすべて求めるループ      loop do # 解の一つを求めるループ        unless check(@i,@j) # クイーンが置けない           nextstep # 次のステップ        else # クイーンが置ける          # 位置設定          @field[@i][@j] = true          @queens[@q_num] = [@i, @j]          @q_num += 1          # 次の行          @i += 1          @j = 0        end        if @q_num == @size # クイーンが全て置けた          @answers.push(@queens.dup) # 解を追加          nextstep # 次の解を求める        end      end    end    end    output # すべての解を出力  end  #------------------------------------------------------------  # ● クイーンが置けるかチェック  #------------------------------------------------------------  def check(x,y)    # 縦と横のチェック    (0...@size).each do |z|      if z != y        return false if @field[x][z]      end      if z != x        return false if @field[z][y]      end    end    # 斜めのチェック    (@size - [x,y].max - 1).times do |n|      return false if @field[x+n+1][y+n+1]    end    ([@size-x-1,y].min).times do |n|      return false if @field[x+n+1][y-(n+1)]    end    ([x,@size-y-1].min).times do |n|      return false if @field[x-(n+1)][y+n+1]    end    ([x,y].min).times do |n|      return false if @field[x-(n+1)][y-(n+1)]    end  end  #------------------------------------------------------------  # ● 次のステップ  #------------------------------------------------------------  def nextstep    @j += 1    while(@j >= @size or @i >= @size) # 縦か横が範囲を超えてる間ループ      throw :end if @i == 0 # 全ての探索が終了      # 一行戻る      @q_num -= 1      @i, @j = @queens[@q_num]      @field[@i][@j] = false      @j += 1      @queens[@q_num] = [-1,-1]    end  end  #------------------------------------------------------------  # ● 解を文字列に整形  #------------------------------------------------------------  def ans2str(ans)    str = ""    (0...@size).each do |i|      str << sprintf("+%s\n", " - +"*@size)      pos = Array.new(@size){|n| ans[i][1] == n ? "*" : " " }      str << sprintf("| %s |\n",pos.join(" | "))    end    str << sprintf("+%s\n", " - +"*@size)    str << sprintf("=%s\n","===="*@size)    return str  end  #------------------------------------------------------------  # ● 解をファイル出力  #------------------------------------------------------------  def output    open("#{@size}-Queens Answers.txt","w") do |f|      f.puts "###########################"      f.puts " #{@size}-Queens Question"      f.puts "---------------------------"      f.puts "  Number of Answers : #{@answers.size}"      f.puts "###########################"      @answers.each_with_index do |ans, i|        f.puts "No.#{i+1}:Queens Location"        f.puts ans.inspect,"\n"        f.print ans2str(ans)      end    end  endendbegin # 実行  if ARGV.size == 0    puts "Please input Command line arguments."  else    question = Queens.new    Benchmark.bm do |b|      ARGV.each do |s|        n = s.to_i        b.report("#{n}-Queens"){          question.size = n          question.solve        }      end    end  endrescue Exception  puts $!.messageend
 
関連記事

tag : Ruby エイト・クイーン問題

コメントの投稿

非公開コメント

プロフィール

gentlawk

Author:gentlawk
「BlueRedZone」を運営
Rubyが大好き
主にゲームプログラミングに取り組む
拍手がつくと地味に喜ぶ

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
検索フォーム
RSSリンクの表示
リンク
Twitter
QRコード
QR
ブロとも申請フォーム

この人とブロともになる

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。