LeetCode.N皇后II

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数 n，返回 n 皇后不同的解决方案的数量。提示：皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一或 N-1 步，可进可退。

示例:
输入: 4
输出: 2

回溯解法：

object NQueenII {
     def main(args: Array[String]): Unit = {
          println(totalNQueens(4))
     }

     def totalNQueens(n: Int): Int = {
          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 = Counter(0)
          backtrack(board, 0, res)
          res.get()
     }


     def backtrack(board: Array[Array[Char]], i: Int, res: Counter): Unit = {
          if (i >= board.length) {
               res.increase()
               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
     }

     case class Counter(value: Int) {

          private var _value = value

          def increase(): Unit = {
               _value += 1
          }

          def get(): Int = {
               _value
          }
     }

}