Skip to content

Instantly share code, notes, and snippets.

@firephil

firephil/NQueen.scala

Forked from pathikrit/NQueen.scala
Created March 11, 2021 22:31
Show Gist options
  • Save firephil/289a5b592d17b39b7747d7412ff0a7e8 to your computer and use it in GitHub Desktop.
Save firephil/289a5b592d17b39b7747d7412ff0a7e8 to your computer and use it in GitHub Desktop.
Download ZIP
O(n!) solution to the n-Queen puzzle (https://en.wikipedia.org/wiki/Eight_queens_puzzle)
Raw
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 Vector p of length n such that p[i] is the column of the queen on the ith row in a solution
*/
def nQueens(n: Int) =
(0 until n)
.permutations
.filter(p => p.zipWithIndex.flatMap{case (c, d) => Seq(n + c + d, c - d)}.distinct.size == 2*n)
Raw
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---
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment