うなぎのアレ

7-queen.rb

# 自分の実装のあまりの酷さに絶望し、
# kumagi様の実装を参考に実装しなおして冗長にコメントつけてみる
# https://gist.github.com/3047253

# boardはqueenがあるcolの配列, rowは新規にqueenを置く行
def find_rest board, row
  # 終了条件
  return if row == 7

  # 各列についてqueenを(置けたら)置く
  7.times do |col|

    # いずれかのqueenとかち合う場合はすぐ次の行へ
    next if board.map.with_index{ |q_col, q_row|
      col - q_col == 0 || # queenの真下に置こうとしている
        # dx = ±dy
        col - q_col == (row - q_row) || # queenの右下に置こうとしている
        col - q_col == - (row - q_row) # queenの左下に置こうとしている
    }.any?

    # boardにqueenを置く
    board << col

    # 最終行かつ問題の条件に当てはまるとき
    if row == 6 && board[2] == 2 && board[4] == 3
      #mapしてsortして出力
      p board.map.with_index{ |row, col|
          [row + 1, col + 1]
        }.sort{ |l, r|
          (l[0]*l[1]) <=> (r[0]*r[1])
        }

      exit #答えが得られたので終了
    end

    # 次のrowを探す
    find_rest board, row + 1

    # 1手戻る
    board.pop
  end
end

# 最初の行からスタート
find_rest [], 0