스칼라의 N-queens

Question

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

이 코드가 어떻게 작동하는지 이해할 수 없으며 Eclipse에서 디버깅하기가 어렵습니다. 이 코드를 단계별로 설명 할 수 있습니까? 그건 그렇고, 코드가 올바르게 작동합니다. 또한 n-queens 알고리즘을 이해하지만이 코드의 메커니즘을 이해하지 못합니다.

Answer 1

하자.

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

우리는 n의 * n 개의 체스 판에 N 여왕의 가능한 모든 위치를 반환하는 함수 queens(n: Int)을 정의합니다. 함수 queens은 매우 간단합니다. placeQueens이라는 내부 함수에 위임합니다.

placeQueens은 기본 케이스가 먼저 나열되어 있습니다. 우리가 0 * ​​0 체스 판에서 작동하고 0 명의 왕비를 배치한다면, 정확히 한 가지 (매우 사소한) 방법이 있습니다. 자,이 함수의 고기는 for-loop에 있습니다.

for { 
    queens <- placeQueens(k - 1) 
    column <- 1 to n 
    queen = (k, column) 
    if isSafe(queen, queens) 
} yield queen :: queens 

이 부분은 "for"루프처럼 읽을 수 있지만 그 중 일부는 그리 간단하지 않습니다. 스칼라의 for-loop는 Haskell의 Do-Loop 구문을 기반으로합니다.이 구문은 아마도 혼란을 설명 할 것입니다. 이를 읽는 방법은 다음과 같습니다.

// We're starting a for-loop 
for { 
    // Call placeQueens recursively. placeQueens returns a list of 
    // all possible results, so iterate over them. 
    queens <- placeQueens(k - 1) 
    // Iterate over each column that the kth queen could go in. 
    column <- 1 to n 
    // Assign the queen to that position. 
    queen = (k, column) 
    // If the position is safe, keep going. More precisely, if the position 
    // is NOT safe, stop. 
    if isSafe(queen, queens) 
// Put our new queen assignment at the beginning of the recursively computed list. 
} yield queen :: queens 

이러한 루프는 익숙해 져 있습니다. 그것이 의미하는 바를보기 위해 루프를 desugar (컴파일러가 어쨌든 수행하는 것입니다)하는 것이 교육적 일 수 있습니다. 번역 규칙 on the Scala website을 찾을 수 있습니다.