Scala筆記 21 - 組合搜尋以及N-Queens Problem

N-Queens Problem

西洋棋盤上的皇后可以直吃, 橫吃, 斜吃，所以有人無聊想找出在nxn棋盤上可以同時擺n個皇后但不會互相殘殺的方法？

一種簡單的擺法就是，依照row順序來擺，擺完之後檢查有沒有column/diagonal衝突？

如果每種擺法用一個list表示，每個element的list index當作棋盤的row index，而element的值就是column index:

solution = List(
last_row_column_index,
..
..
first_row_column_index)

上圖的List(0,3,1)的意思是List(row2_col0, row1_col3, row0_col1)
(註：後擺上的棋子放在list最前面，應該是為了scala list cons方便的關係）


最終要找出一個set，包含所有的解法：
all solutions = Set(
solution1,
solution2,
.
.
solution
)

利用For-Yield來找combinations

def queens(n: Int) = {

  def placeQueens(k: Int): Set[List[Int]] = {
    if (k == 0) Set(List())
    else      for {
        queens <- placeQueens(k - 1)
        col <- 0 until n
        if isSafe(col, queens)
      } yield col :: queens
  }

  placeQueens(n)
}

他假設我們已經知道利用placeQueens這個helper function放k-1個皇后在nxn棋盤上，那我們要怎麼放第k個皇后？

在for中，每個iteration我們都檢查某個 placeQueens(k-1)回傳的set of solution list (type List[Int]) 中的某個solution，這個solution已經放了k-1個皇后在前k-1個row，下一個row應該放在哪一個column呢？

所以for的第二個generator就是 0到n-1的所有的column index來檢查，是否isSafe?
如果滿足isSafe的column index ，就把這個column index append到這個solution list的最前面。

for會yield出一個collection，type會是跟第一個generator的collection同樣，也就是Set[List[Int]]。

如何寫isSafe?

def isSafe(col:Int, queens:List[Int]) : Boolean = {
  val row = queens.length
  val qrows = (row - 1 to 0 by -1) zip queens
  qrows forall {
    case (r,c) => col != c && math.abs(col-c) != row - r
  }

}

這邊稍微有點tricky，可以trace看看。


N-Queens的演算法說明了怎麼長出某個list的所有subset，不錯的練習。