51. N-Queens

Then-queens puzzle is the problem of placingn_queens on an_n×_n_chessboard such that no two queens attack each other.

Given an integern, return all distinct solutions to then-queens puzzle.

Each solution contains a distinct board configuration of then-queens' placement, where'Q'and'.'both indicate a queen and an empty space respectively.

Example:

Input:
 4

Output:
 [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Explanation:
 There exist two distinct solutions to the 4-queens puzzle as shown above.

Solution

(1) Java

(2) Python

class Solution:
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        def buildBoard(colSet):
            board = []
            for i in range(n):
                row = ""
                for j in range(n):
                    if j == colSet[i]:
                        row += "Q"
                    else:
                        row += "."
                board.append(row)
            rst.append(board)
        def dfs(colSet, row):
            if row == n:
                buildBoard(colSet)
                return
            for i in range(n):
                if i in colSet:
                    continue
                j = row-1
                k = i-1
                while j >= 0 and k >= 0:
                    if colSet[j] == k:
                        break
                    j = j-1
                    k = k-1
                if j >= 0 and k >= 0:
                    continue
                j = row-1
                k = i+1
                while j >= 0 and k < n:
                    if colSet[j] == k:
                        break
                    j = j-1
                    k = k+1
                if j >= 0 and k < n:
                    continue
                colSet.append(i)
                dfs(colSet, row+1)
                colSet.remove(i)
        colSet = []
        rst = []
        dfs(colSet, 0)
        return rst

Improve code:

class Solution:
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        def dfs(colSet, lCross, rCross):
            if len(colSet) == n:
                sol = ["."*j + "Q" + "."*(n-j-1) for j in colSet]
                rst.append(sol)
                return
            for i in range(n):
                if i in colSet:
                    continue
                row = len(colSet)
                if (row-i) in lCross:
                    continue
                if (row+i) in rCross:
                    continue
                colSet.append(i)
                lCross.append(row-i)
                rCross.append(row+i)
                dfs(colSet, lCross, rCross)
                colSet.remove(i)
                lCross.remove(row-i)
                rCross.remove(row+i)
        rst = []
        dfs([], [], [])
        return rst

(3) Scala

object Solution {
    def solveNQueens(n: Int): List[List[String]] = {
        val queens = placeQueens(n, n)
        return output(queens, n)
    }

    def placeQueens(k: Int, n: Int): List[List[Int]] = k match {
        case 0 => List(List())
        case _ => for {
          colSet <- placeQueens(k-1, n)
          col <- 0 until n
          if isOK(colSet, col)
        } yield colSet :+ col
    }

    def isOK(colSet: List[Int], col: Int): Boolean = {
        val row = colSet.length
        colSet.zipWithIndex.forall{
          case (c, r) => c != col && math.abs(c-col) != math.abs(r-row)
        }
    }

    def output(queensList: List[List[Int]], n: Int): List[List[String]] = {
        import scala.collection.mutable.ListBuffer
        var solutions = new ListBuffer[List[String]]()
        queensList.zipWithIndex.foreach(sol=>{
          var solution = new ListBuffer[String]()
          sol._1.foreach(col=>{ solution += Vector.fill(n){"."}.updated(col, "Q").mkString })
          solutions += solution.toList
        })
        return solutions.toList
    }
}