Skip to content

Instantly share code, notes, and snippets.

@pathikrit

pathikrit/NQueen.scala

Last active January 19, 2023 21:30
Show Gist options
  • Save pathikrit/6fa878fe87c6160a52c4c27dabbfa6df to your computer and use it in GitHub Desktop.
Save pathikrit/6fa878fe87c6160a52c4c27dabbfa6df to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. pathikrit revised this gist Jan 19, 2023. 1 changed file with 3 additions and 2 deletions.
    5 changes: 3 additions & 2 deletions NQueen.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -3,9 +3,10 @@
    * 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
    * @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) =
    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)
  2. pathikrit revised this gist Dec 12, 2019. 1 changed file with 4 additions and 3 deletions.
    7 changes: 4 additions & 3 deletions NQueen.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -5,6 +5,7 @@
    * 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
    }
    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)
  3. pathikrit revised this gist Aug 16, 2016. 2 changed files with 7 additions and 7 deletions.
    4 changes: 2 additions & 2 deletions NQueen.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -1,9 +1,9 @@
    /**
    * 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 i)
    * 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 a Vector p of length n such that p[i] is the column of the queen on the ith row
    * @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
    10 changes: 5 additions & 5 deletions Output.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -1,10 +1,10 @@
    for ((solution, num) <- nQueens(8).zipWithIndex) { // print all 92 solutions for n=8
    // print all 92 solutions for n=8
    nQueens(8).zipWithIndex foreach {case (solution, num) =>
    println(s"Solution #${num + 1}:")
    solution foreach {col =>
    val row = solution.indices.map(i => if (i == col) 'Q' else '-')
    println(row.mkString)
    }
    val rows = solution.map(col => solution.indices.map(i => if (i == col) 'Q' else '-').mkString)
    rows foreach println
    }

    /*
    Solution #1:
    Q-------
  4. pathikrit revised this gist Apr 14, 2016. 2 changed files with 928 additions and 9 deletions.
    9 changes: 0 additions & 9 deletions NQueen.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -8,12 +8,3 @@
    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
    }
    /*************************************** [Printing code below] *************************************************/
    for ((solution, num) <- nQueens(8).zipWithIndex) {
    println(s"Solution #${num + 1}:")
    solution foreach {col =>
    val row = solution.indices.map(i => if (i == col) 'Q' else '-')
    println(row.mkString)
    }
    }
    // Feel free to run this code on http://scalafiddle.net
    928 changes: 928 additions & 0 deletions Output.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,928 @@
    for ((solution, num) <- nQueens(8).zipWithIndex) { // print all 92 solutions for n=8
    println(s"Solution #${num + 1}:")
    solution foreach {col =>
    val row = solution.indices.map(i => if (i == col) 'Q' else '-')
    println(row.mkString)
    }
    }
    /*
    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---
    */
  5. pathikrit revised this gist Apr 14, 2016. 1 changed file with 10 additions and 5 deletions.
    15 changes: 10 additions & 5 deletions NQueen.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,12 @@
    def nQueens(n: Int) = (0 until n).permutations filter {col => // col[r] = column of queen on r-th row
    val p = col.zipWithIndex.toSet // col[] must be a permutation of (0 until n) because of rook attacks
    p.map{case (c, d) => c + d}.size == n && // No 2 queens can have same col + diag because of left-bishop attacks
    p.map{case (c, d) => c - d}.size == n // No 2 queens can have same col - diag because of right-bishop attacks
    /**
    * 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 i)
    * There must be n distinct (col + diag) and n distinct (col - diag) for each queen (else bishop attacks)
    * @return a Vector p of length n such that p[i] is the column of the queen on the ith row
    */
    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
    }
    /*************************************** [Printing code below] *************************************************/
    for ((solution, num) <- nQueens(8).zipWithIndex) {
    @@ -11,4 +16,4 @@ for ((solution, num) <- nQueens(8).zipWithIndex) {
    println(row.mkString)
    }
    }
    // Feel free to run this code on http://scalafiddle.net
    // Feel free to run this code on http://scalafiddle.net
  6. pathikrit revised this gist Apr 10, 2016. 1 changed file with 6 additions and 5 deletions.
    11 changes: 6 additions & 5 deletions NQueen.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -1,13 +1,14 @@
    def nQueens(n: Int) = (0 until n).permutations filter {p =>
    val i = p.zipWithIndex.toSet // p[x] is the column of the queen on xth row (must be a permutation of 0 until n)
    i.map{case (c, d) => c + d}.size == n && // No 2 queens can have same col + diag
    i.map{case (c, d) => c - d}.size == n // No 2 queens can have same col - diag
    def nQueens(n: Int) = (0 until n).permutations filter {col => // col[r] = column of queen on r-th row
    val p = col.zipWithIndex.toSet // col[] must be a permutation of (0 until n) because of rook attacks
    p.map{case (c, d) => c + d}.size == n && // No 2 queens can have same col + diag because of left-bishop attacks
    p.map{case (c, d) => c - d}.size == n // No 2 queens can have same col - diag because of right-bishop attacks
    }
    /*************************************** [Printing code below] *************************************************/
    for ((solution, num) <- nQueens(8).zipWithIndex) {
    println(s"Solution #${num + 1}:")
    solution foreach {col =>
    solution foreach {col =>
    val row = solution.indices.map(i => if (i == col) 'Q' else '-')
    println(row.mkString)
    }
    }
    // Feel free to run this code on http://scalafiddle.net
  7. pathikrit revised this gist Apr 10, 2016. 1 changed file with 5 additions and 2 deletions.
    7 changes: 5 additions & 2 deletions NQueen.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -1,10 +1,13 @@
    def nQueens(n: Int) = (0 until n).permutations filter {p =>
    val i = p.zipWithIndex.toSet // p[i] is the column of the queen on ith row (must be a permutation of 0 until n)
    val i = p.zipWithIndex.toSet // p[x] is the column of the queen on xth row (must be a permutation of 0 until n)
    i.map{case (c, d) => c + d}.size == n && // No 2 queens can have same col + diag
    i.map{case (c, d) => c - d}.size == n // No 2 queens can have same col - diag
    }
    /*************************************** [Printing code below] *************************************************/
    for ((solution, num) <- nQueens(8).zipWithIndex) {
    println(s"Solution #${num + 1}:")
    solution foreach {col => println(solution.indices.map(i => if (i == col) 'Q' else '-').mkString)}
    solution foreach {col =>
    val row = solution.indices.map(i => if (i == col) 'Q' else '-')
    println(row.mkString)
    }
    }
  8. pathikrit revised this gist Apr 10, 2016. No changes.
  9. pathikrit revised this gist Apr 10, 2016. 1 changed file with 3 additions and 6 deletions.
    9 changes: 3 additions & 6 deletions NQueen.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -3,11 +3,8 @@ def nQueens(n: Int) = (0 until n).permutations filter {p =>
    i.map{case (c, d) => c + d}.size == n && // No 2 queens can have same col + diag
    i.map{case (c, d) => c - d}.size == n // No 2 queens can have same col - diag
    }
    /***********************************************************/
    /*************************************** [Printing code below] *************************************************/
    for ((solution, num) <- nQueens(8).zipWithIndex) {
    println(s"Solution #${num + 1}:")
    for {
    col <- solution
    row = solution.indices.map(i => if (i == col) 'Q' else '-')
    } println(row.mkString)
    println(s"Solution #${num + 1}:")
    solution foreach {col => println(solution.indices.map(i => if (i == col) 'Q' else '-').mkString)}
    }
  10. pathikrit revised this gist Apr 10, 2016. 1 changed file with 0 additions and 3 deletions.
    3 changes: 0 additions & 3 deletions NQueen.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -11,6 +11,3 @@ for ((solution, num) <- nQueens(8).zipWithIndex) {
    row = solution.indices.map(i => if (i == col) 'Q' else '-')
    } println(row.mkString)
    }



  11. pathikrit revised this gist Apr 10, 2016. 1 changed file with 10 additions and 6 deletions.
    16 changes: 10 additions & 6 deletions NQueen.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -3,10 +3,14 @@ def nQueens(n: Int) = (0 until n).permutations filter {p =>
    i.map{case (c, d) => c + d}.size == n && // No 2 queens can have same col + diag
    i.map{case (c, d) => c - d}.size == n // No 2 queens can have same col - diag
    }
    /***********************************************************/
    for ((solution, num) <- nQueens(8).zipWithIndex) {
    println(s"Solution #${num + 1}:")
    for {
    col <- solution
    row = solution.indices.map(i => if (i == col) 'Q' else '-')
    } println(row.mkString)
    }

    for {
    (solution, num) <- nQueens(8).zipWithIndex
    _ = println(s"Solution #${num + 1}:")
    col <- solution
    row = solution.indices.map(i => if (i == col) 'Q' else '-')
    } println(row.mkString)


  12. pathikrit revised this gist Apr 10, 2016. 1 changed file with 4 additions and 3 deletions.
    7 changes: 4 additions & 3 deletions NQueen.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,7 @@
    def nQueens(n: Int) = (0 until n).permutations filter {p => // p[i] is the column of the queen on ith row (must be a permutation of 0 until n)
    val i = p.zipWithIndex.toSet
    i.map{case (c, d) => c + d}.size == n && i.map{case (c, d) => c - d}.size == n // No 2 queens can have same col + diag or col - diag
    def nQueens(n: Int) = (0 until n).permutations filter {p =>
    val i = p.zipWithIndex.toSet // p[i] is the column of the queen on ith row (must be a permutation of 0 until n)
    i.map{case (c, d) => c + d}.size == n && // No 2 queens can have same col + diag
    i.map{case (c, d) => c - d}.size == n // No 2 queens can have same col - diag
    }

    for {
  13. pathikrit created this gist Apr 10, 2016.
    11 changes: 11 additions & 0 deletions NQueen.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,11 @@
    def nQueens(n: Int) = (0 until n).permutations filter {p => // p[i] is the column of the queen on ith row (must be a permutation of 0 until n)
    val i = p.zipWithIndex.toSet
    i.map{case (c, d) => c + d}.size == n && i.map{case (c, d) => c - d}.size == n // No 2 queens can have same col + diag or col - diag
    }

    for {
    (solution, num) <- nQueens(8).zipWithIndex
    _ = println(s"Solution #${num + 1}:")
    col <- solution
    row = solution.indices.map(i => if (i == col) 'Q' else '-')
    } println(row.mkString)