Skip to content

Instantly share code, notes, and snippets.

@pathikrit
Last active January 19, 2023 21:30
  • Star 52 You must be signed in to star a gist
  • Fork 6 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save pathikrit/6fa878fe87c6160a52c4c27dabbfa6df to your computer and use it in GitHub Desktop.
O(n!) solution to the n-Queen puzzle (https://en.wikipedia.org/wiki/Eight_queens_puzzle)
/**
* 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)
// 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---
*/
@xrisk
Copy link

xrisk commented Apr 10, 2016

So, is this bruteforce?

@justicezyx
Copy link

Please mark the solution as brute force.

@langley
Copy link

langley commented Apr 10, 2016

Sweet! VERY NICE example of using the great operators on scala collections. Thank You!

@shkesar
Copy link

shkesar commented Apr 10, 2016

How is this 4 lines?

@pathikrit
Copy link
Author

pathikrit commented Apr 10, 2016

The actual nQueen code is 4 lines. The code to pretty print does not count IMO

@pathikrit
Copy link
Author

@xrisk, @justicezyx : I say the solution is O(n!) - better than saying "brute force"

@shkesar
Copy link

shkesar commented Apr 10, 2016

@pathikrit : You switched from flatMap to foreach. I personally find the first version, which used for-comprehension, more readable.

@thriqon
Copy link

thriqon commented Apr 10, 2016

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

@kamronbatman
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment