O(n!) solution to the n-Queen puzzle (https://en.wikipedia.org/wiki/Eight_queens_puzzle)

NQueen.scala

/**
 * Solves the n-Queen puzzle in O(n!)
 * Let p[r] be the column of the queen on the rth row (must be exactly 1 queen per row)
 * There also must be exactly 1 queen per column and hence p must be a permuation of (0 until n)
 * There must be n distinct (col + diag) and n distinct (col - diag) for each queen (else bishop attacks)
 * @return returns a Iterator of solutions 
 *     Each solution is an array p of length n such that p[i] is the column of the queen on the ith row
 */
def nQueens(n: Int): Iterator[Seq[Int]] = 
  (0 until n)
     .permutations
     .filter(p => p.zipWithIndex.flatMap{case (c, d) => Seq(n + c + d, c - d)}.distinct.size == 2*n)

Output.scala

// print all 92 solutions for n=8
nQueens(8).zipWithIndex foreach {case (solution, num) => 
  println(s"Solution #${num + 1}:")
  val rows = solution.map(col => solution.indices.map(i => if (i == col) 'Q' else '-').mkString)
  rows foreach println
}

/*
Solution #1:
Q-------
----Q---
-------Q
-----Q--
--Q-----
------Q-
-Q------
---Q----

Solution #2:
Q-------
-----Q--
-------Q
--Q-----
------Q-
---Q----
-Q------
----Q---

Solution #3:
Q-------
------Q-
---Q----
-----Q--
-------Q
-Q------
----Q---
--Q-----

Solution #4:
Q-------
------Q-
----Q---
-------Q
-Q------
---Q----
-----Q--
--Q-----

Solution #5:
-Q------
---Q----
-----Q--
-------Q
--Q-----
Q-------
------Q-
----Q---

Solution #6:
-Q------
----Q---
------Q-
Q-------
--Q-----
-------Q
-----Q--
---Q----

Solution #7:
-Q------
----Q---
------Q-
---Q----
Q-------
-------Q
-----Q--
--Q-----

Solution #8:
-Q------
-----Q--
Q-------
------Q-
---Q----
-------Q
--Q-----
----Q---

Solution #9:
-Q------
-----Q--
-------Q
--Q-----
Q-------
---Q----
------Q-
----Q---

Solution #10:
-Q------
------Q-
--Q-----
-----Q--
-------Q
----Q---
Q-------
---Q----

Solution #11:
-Q------
------Q-
----Q---
-------Q
Q-------
---Q----
-----Q--
--Q-----

Solution #12:
-Q------
-------Q
-----Q--
Q-------
--Q-----
----Q---
------Q-
---Q----

Solution #13:
--Q-----
Q-------
------Q-
----Q---
-------Q
-Q------
---Q----
-----Q--

Solution #14:
--Q-----
----Q---
-Q------
-------Q
Q-------
------Q-
---Q----
-----Q--

Solution #15:
--Q-----
----Q---
-Q------
-------Q
-----Q--
---Q----
------Q-
Q-------

Solution #16:
--Q-----
----Q---
------Q-
Q-------
---Q----
-Q------
-------Q
-----Q--

Solution #17:
--Q-----
----Q---
-------Q
---Q----
Q-------
------Q-
-Q------
-----Q--

Solution #18:
--Q-----
-----Q--
-Q------
----Q---
-------Q
Q-------
------Q-
---Q----

Solution #19:
--Q-----
-----Q--
-Q------
------Q-
Q-------
---Q----
-------Q
----Q---

Solution #20:
--Q-----
-----Q--
-Q------
------Q-
----Q---
Q-------
-------Q
---Q----

Solution #21:
--Q-----
-----Q--
---Q----
Q-------
-------Q
----Q---
------Q-
-Q------

Solution #22:
--Q-----
-----Q--
---Q----
-Q------
-------Q
----Q---
------Q-
Q-------

Solution #23:
--Q-----
-----Q--
-------Q
Q-------
---Q----
------Q-
----Q---
-Q------

Solution #24:
--Q-----
-----Q--
-------Q
Q-------
----Q---
------Q-
-Q------
---Q----

Solution #25:
--Q-----
-----Q--
-------Q
-Q------
---Q----
Q-------
------Q-
----Q---

Solution #26:
--Q-----
------Q-
-Q------
-------Q
----Q---
Q-------
---Q----
-----Q--

Solution #27:
--Q-----
------Q-
-Q------
-------Q
-----Q--
---Q----
Q-------
----Q---

Solution #28:
--Q-----
-------Q
---Q----
------Q-
Q-------
-----Q--
-Q------
----Q---

Solution #29:
---Q----
Q-------
----Q---
-------Q
-Q------
------Q-
--Q-----
-----Q--

Solution #30:
---Q----
Q-------
----Q---
-------Q
-----Q--
--Q-----
------Q-
-Q------

Solution #31:
---Q----
-Q------
----Q---
-------Q
-----Q--
Q-------
--Q-----
------Q-

Solution #32:
---Q----
-Q------
------Q-
--Q-----
-----Q--
-------Q
Q-------
----Q---

Solution #33:
---Q----
-Q------
------Q-
--Q-----
-----Q--
-------Q
----Q---
Q-------

Solution #34:
---Q----
-Q------
------Q-
----Q---
Q-------
-------Q
-----Q--
--Q-----

Solution #35:
---Q----
-Q------
-------Q
----Q---
------Q-
Q-------
--Q-----
-----Q--

Solution #36:
---Q----
-Q------
-------Q
-----Q--
Q-------
--Q-----
----Q---
------Q-

Solution #37:
---Q----
-----Q--
Q-------
----Q---
-Q------
-------Q
--Q-----
------Q-

Solution #38:
---Q----
-----Q--
-------Q
-Q------
------Q-
Q-------
--Q-----
----Q---

Solution #39:
---Q----
-----Q--
-------Q
--Q-----
Q-------
------Q-
----Q---
-Q------

Solution #40:
---Q----
------Q-
Q-------
-------Q
----Q---
-Q------
-----Q--
--Q-----

Solution #41:
---Q----
------Q-
--Q-----
-------Q
-Q------
----Q---
Q-------
-----Q--

Solution #42:
---Q----
------Q-
----Q---
-Q------
-----Q--
Q-------
--Q-----
-------Q

Solution #43:
---Q----
------Q-
----Q---
--Q-----
Q-------
-----Q--
-------Q
-Q------

Solution #44:
---Q----
-------Q
Q-------
--Q-----
-----Q--
-Q------
------Q-
----Q---

Solution #45:
---Q----
-------Q
Q-------
----Q---
------Q-
-Q------
-----Q--
--Q-----

Solution #46:
---Q----
-------Q
----Q---
--Q-----
Q-------
------Q-
-Q------
-----Q--

Solution #47:
----Q---
Q-------
---Q----
-----Q--
-------Q
-Q------
------Q-
--Q-----

Solution #48:
----Q---
Q-------
-------Q
---Q----
-Q------
------Q-
--Q-----
-----Q--

Solution #49:
----Q---
Q-------
-------Q
-----Q--
--Q-----
------Q-
-Q------
---Q----

Solution #50:
----Q---
-Q------
---Q----
-----Q--
-------Q
--Q-----
Q-------
------Q-

Solution #51:
----Q---
-Q------
---Q----
------Q-
--Q-----
-------Q
-----Q--
Q-------

Solution #52:
----Q---
-Q------
-----Q--
Q-------
------Q-
---Q----
-------Q
--Q-----

Solution #53:
----Q---
-Q------
-------Q
Q-------
---Q----
------Q-
--Q-----
-----Q--

Solution #54:
----Q---
--Q-----
Q-------
-----Q--
-------Q
-Q------
---Q----
------Q-

Solution #55:
----Q---
--Q-----
Q-------
------Q-
-Q------
-------Q
-----Q--
---Q----

Solution #56:
----Q---
--Q-----
-------Q
---Q----
------Q-
Q-------
-----Q--
-Q------

Solution #57:
----Q---
------Q-
Q-------
--Q-----
-------Q
-----Q--
---Q----
-Q------

Solution #58:
----Q---
------Q-
Q-------
---Q----
-Q------
-------Q
-----Q--
--Q-----

Solution #59:
----Q---
------Q-
-Q------
---Q----
-------Q
Q-------
--Q-----
-----Q--

Solution #60:
----Q---
------Q-
-Q------
-----Q--
--Q-----
Q-------
---Q----
-------Q

Solution #61:
----Q---
------Q-
-Q------
-----Q--
--Q-----
Q-------
-------Q
---Q----

Solution #62:
----Q---
------Q-
---Q----
Q-------
--Q-----
-------Q
-----Q--
-Q------

Solution #63:
----Q---
-------Q
---Q----
Q-------
--Q-----
-----Q--
-Q------
------Q-

Solution #64:
----Q---
-------Q
---Q----
Q-------
------Q-
-Q------
-----Q--
--Q-----

Solution #65:
-----Q--
Q-------
----Q---
-Q------
-------Q
--Q-----
------Q-
---Q----

Solution #66:
-----Q--
-Q------
------Q-
Q-------
--Q-----
----Q---
-------Q
---Q----

Solution #67:
-----Q--
-Q------
------Q-
Q-------
---Q----
-------Q
----Q---
--Q-----

Solution #68:
-----Q--
--Q-----
Q-------
------Q-
----Q---
-------Q
-Q------
---Q----

Solution #69:
-----Q--
--Q-----
Q-------
-------Q
---Q----
-Q------
------Q-
----Q---

Solution #70:
-----Q--
--Q-----
Q-------
-------Q
----Q---
-Q------
---Q----
------Q-

Solution #71:
-----Q--
--Q-----
----Q---
------Q-
Q-------
---Q----
-Q------
-------Q

Solution #72:
-----Q--
--Q-----
----Q---
-------Q
Q-------
---Q----
-Q------
------Q-

Solution #73:
-----Q--
--Q-----
------Q-
-Q------
---Q----
-------Q
Q-------
----Q---

Solution #74:
-----Q--
--Q-----
------Q-
-Q------
-------Q
----Q---
Q-------
---Q----

Solution #75:
-----Q--
--Q-----
------Q-
---Q----
Q-------
-------Q
-Q------
----Q---

Solution #76:
-----Q--
---Q----
Q-------
----Q---
-------Q
-Q------
------Q-
--Q-----

Solution #77:
-----Q--
---Q----
-Q------
-------Q
----Q---
------Q-
Q-------
--Q-----

Solution #78:
-----Q--
---Q----
------Q-
Q-------
--Q-----
----Q---
-Q------
-------Q

Solution #79:
-----Q--
---Q----
------Q-
Q-------
-------Q
-Q------
----Q---
--Q-----

Solution #80:
-----Q--
-------Q
-Q------
---Q----
Q-------
------Q-
----Q---
--Q-----

Solution #81:
------Q-
Q-------
--Q-----
-------Q
-----Q--
---Q----
-Q------
----Q---

Solution #82:
------Q-
-Q------
---Q----
Q-------
-------Q
----Q---
--Q-----
-----Q--

Solution #83:
------Q-
-Q------
-----Q--
--Q-----
Q-------
---Q----
-------Q
----Q---

Solution #84:
------Q-
--Q-----
Q-------
-----Q--
-------Q
----Q---
-Q------
---Q----

Solution #85:
------Q-
--Q-----
-------Q
-Q------
----Q---
Q-------
-----Q--
---Q----

Solution #86:
------Q-
---Q----
-Q------
----Q---
-------Q
Q-------
--Q-----
-----Q--

Solution #87:
------Q-
---Q----
-Q------
-------Q
-----Q--
Q-------
--Q-----
----Q---

Solution #88:
------Q-
----Q---
--Q-----
Q-------
-----Q--
-------Q
-Q------
---Q----

Solution #89:
-------Q
-Q------
---Q----
Q-------
------Q-
----Q---
--Q-----
-----Q--

Solution #90:
-------Q
-Q------
----Q---
--Q-----
Q-------
------Q-
---Q----
-----Q--

Solution #91:
-------Q
--Q-----
Q-------
-----Q--
-Q------
----Q---
------Q-
---Q----

Solution #92:
-------Q
---Q----
Q-------
--Q-----
-----Q--
-Q------
------Q-
----Q---
*/

For reference, this is very similar: http://rosettacode.org/wiki/N-queens_problem#Python

Because a proper solution requires backtracking, the solution is not simply n!. I think the rooks problem has a time complexity solution of n!.