#140 The n-Queens Problem / sdlong

[sdlong]

Consider the problem of placing n queens on an n × n chessboard so
that no two queens are in the same row, column, or diagonal. Design a
linear-time algorithm for finding a solution to this problem for any n > 3.

[sdlong]

class Board
  attr_accessor :n, :board

  # 建立一個棋盤, 並指定長寬為 n
  def initialize(n)
    @n = n
    @board = Array.new(n)
    @board.map! { Array.new(n, " .") }
  end

  # 將棋盤列印出來
  def print_board
    puts "Board:"
    board.each_index do |row|
      board.each_index do |col|
        print "#{board[row][col]}"
      end
      puts
    end
  end

  # 執行 N Queens 的解, 會從 0 ( first row of board ) 開始跑
  def solve
    do_solve(0)
  end

  private

  # 用回溯法 (backtracking) 的邏輯執行,
  # 每格都會驗證，只要上下左右對角驗證是 safe 就放一個 Queen
  # 放完最後一個 Queen, 就把 board 印出來, 然後跳下一個 col / row 去驗證
  def do_solve(row)
    0.upto(n-1) do |col|
      if safe(row, col)
        board[row][col] = " Q"
        if row == (n-1)
          print_board
        else
          do_solve(row+1)
        end
        board[row][col] = " ."
      end
    end
  end

  # 皇后的位置檢查
  def safe(suggested_row, suggested_col)

    # 檢查 row(橫線) 上面有沒有 Queen
    return false if !safe_row(suggested_row)
    # 檢查 col(直線) 上面有沒有 Queen
    return false if !safe_col(suggested_col)

    # 檢查 右上 有沒有 Queen
    return false if !safe_diag(suggested_row, suggested_col, 1, 1)
    # 檢查 右下 有沒有 Queen
    return false if !safe_diag(suggested_row, suggested_col, 1, -1)
    # 檢查 左上 有沒有 Queen
    return false if !safe_diag(suggested_row, suggested_col, -1, 1)
    # 檢查 左下 有沒有 Queen
    return false if !safe_diag(suggested_row, suggested_col, -1, -1)

    # 如果沒問題，這個欄位是一個解 (可以放 Queen)
    return true
  end

  # 檢查 suggested_row 上面每一個 col 有沒有 Queen
  def safe_row(suggested_row)
    0.upto(n-1) do |col|
      return false if board[suggested_row][col] == " Q"
    end

    return true
  end

  # 檢查 suggested_col 上面每一個 row 有沒有 Queen
  def safe_col(suggested_col)
    0.upto(n-1) do |row|
      return false if board[row][suggested_col] == " Q"
    end

    return true
  end

  # 檢查對角線上有沒有 Queen
  def safe_diag(suggested_row, suggested_col, row_mod, col_mod)
    row, col = suggested_row+row_mod, suggested_col+col_mod
    while true do

      # break 此 loop 的條件
      break if (row >= n) || (col >= n) || (row < 0) || (col < 0)

      # 檢查此線上面有沒有 Queen
      return false if board[row][col] == " Q"

      # 沿著對角線的方向移動，尋找下一個值
      row += row_mod
      col += col_mod
    end

    return true
  end
end

# N 皇后解的執行方法
board = Board.new(8).solve