LeetCode.N皇后

n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数n，返回所有不同的n皇后问题的解决方案。每一种解法包含一个明确的n皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

• 示例：
  输入：4
  输出：[
   [“.Q..”, // 解法 1
   ”…Q”,
   ”Q…”,
   ”..Q.”],
   [“..Q.”, // 解法 2
   ”Q…”,
   ”…Q”,
   ”.Q..”]
  ]

回溯解法：

object NQueen {
     def main(args: Array[String]): Unit = {
          solveNQueens(4).foreach(println)
     }

     def solveNQueens(n: Int): List[List[String]] = {
          val board = new Array[Array[Char]](n)
          for (i <- 0 until n) {
               board(i) = new Array[Char](n)
               for (j <- 0 until n) {
                    board(i)(j) = '.'
               }
          }

          val res = ListBuffer[List[String]]()
          backtrack(board, 0, res)
          res.toList
     }

     def backtrack(board: Array[Array[Char]], i: Int, res: ListBuffer[List[String]]): Unit = {
          if (i >= board.length) {
               res += board.map(_.mkString("")).toList
               return
          }
          for (j <- 0 until board.length) {
               if (isValid(board, i, j)) {
                    board(i)(j) = 'Q'
                    backtrack(board, i + 1, res)
                    board(i)(j) = '.'
               }
          }
     }

     def isValid(array: Array[Array[Char]], i: Int, j: Int): Boolean = {
          //检查同一列是否冲突
          for (l <- 0 until array.length) {
               if (l != i && array(l)(j) == 'Q') {
                    return false
               }
          }

          var tmpi = i
          var tmpj = j
          //检查左上角是否冲突
          while ((i > j && tmpj >= 0) || (i <= j && tmpi >= 0)) {
               if (tmpi != i && array(tmpi)(tmpj) == 'Q') {
                    return false
               }
               tmpi -= 1
               tmpj -= 1
          }

          tmpi = i
          tmpj = j
          //检查右上角是否冲突
          while (tmpj < array.length && tmpi >= 0) {
               if (tmpi != i && array(tmpi)(tmpj) == 'Q') {
                    return false
               }
               tmpi -= 1
               tmpj += 1
          }
          true
     }
}