読者です 読者をやめる 読者になる 読者になる

毛のはえたようなもの

インターネット的なものをつらつらとかきつらねる。

N-queens問題(エイトクイーンズ問題)

Ruby

帰省したり旅行にいったりと2週間ほどUbuntu氏がネットにつながらない状況にあり、結局のところRuby(とこのブログ)を放置していたのでした。リハビリをかねて昔むかし解いたN-queens問題Rubyで書き直してみました。うむ、リハビリというほどRuby書いていないか。
書き直し自体よりも、Rubyで関数のオーバーロードができないということを調べるのに時間がかかりました。

ソース

ファイル名「queens.rb」でボードサイズ「8」ならば

$ ruby queens.rb 8

などすると動く。

class Queens 

  def initialize(n)
    @answer = 0
    @boardSize = n;
    @matrix = Array.new(@boardSize)
  end

  def get_answer
    @answer
  end

  def check(i,j)
    i.times{|k|
      if j==@matrix[k]||(i+j)==(k+@matrix[k])||(i-j)==(k-@matrix[k]) 
        return false
      end
    }
    return true
  end

  def calc(i)
    if i == @boardSize
#      print("    show_ans;[")
#      @boardSize.times{|k| printf("%s,",@matrix[k])}
#      print("]\n")
      @answer +=1
    else
      @boardSize.times{|k|
        if check(i,k) 
          @matrix[i] = k
          calc(i+1)
        end
      }
    end
  end

end

n =  ARGV[0].to_i
newGame = Queens.new(n)
newGame.calc(0)
p newGame.get_answer

本当ならcalcを多重定義して「newGame.calc」などと呼び出したかったのでした。
解決策があれば教えてください。


さて歯磨き粉買いに行こう