【Ruby】【アルゴリズム】エイトクイーン問題を解く。全答列挙Ver

みんな大好き、師匠からメールが来たよ。

sekai-san
I read recent entries at your blog.
You have studied very hard, it is a great effort.
I am worrying  you to push yourself.
However, as a reader of your blog,
I want to hear your voice.
･･･

なんで英語メール？（しかもカタコト）
って突っ込む元気すらない。

そんなのいいからRailsの勉強しようぜー！

とかいつも言ってるあたり、
この人、わたしが本気なのがわかってないなー
と疑ってたけど。

エイトクイーン問題とは

チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。
クイーンの動きは、上下左右斜めの8方向に、遮る物がない限り進める。

https://ja.wikipedia.org/wiki/%E3%82%A8%E3%82%A4%E3%83%88%E3%83%BB%E3%82%AF%E3%82%A4%E3%83%BC%E3%83%B3

はまったところ

多重配列を複製するときは、dup,cloneでは浅いコピーとなるためNG！
中々気づけず嵌ってしまいました。。。

コード

def make_board(size)
  Array.new(size).map! { Array.new(size, 0) }
end

#表示用
def show_board(boards)
  boards.each do |board|
    board.each {|line| p line}
    puts "----\r\n"
  end
end

#自分の左側,斜め左上,斜め左下を確認
#自分より右側の列には駒は存在しない
def isOK(m, n, board)
  i = n - 1
  while i >= 0
    return false if board[m][i] == 1
    i -= 1
  end
  j = 1
  while m-j >= 0 && n-j >= 0
    return false if board[m-j][n-j] == 1
    j += 1
  end
  k = 1
  while m+k < board.length && n-k >= 0
    return false if board[m+k][n-k] == 1
    k += 1
  end
  true
end

def solve(column, board, results)
  return results if column >= board.length

  i = 0
  while i < board.length
    copy =  Marshal.load(Marshal.dump(board)) # <- ポイント！
    if isOK(i, column, copy)
      copy[i][column] = 1
      results << copy if column == board.length - 1
      solve(column + 1, copy, results)
    end
    i += 1
  end
  results
end

board = make_board(8)

#1列目から順にクイーンを置く
results = solve(0, board, [])
if results.length > 0
  show_board(results) 
  p results.length
else
   p "arimasen"
end

　
■実行結果

･･･
----
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
----
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[1, 0, 0, 0, 0, 0, 0, 0]
----
92

解の総数は 92（＝8×11＋4）になる。

https://ja.wikipedia.org/wiki/%E3%82%A8%E3%82%A4%E3%83%88%E3%83%BB%E3%82%AF%E3%82%A4%E3%83%BC%E3%83%B3

やったーー！！