The N-Queens Problem in Scala

Recently at my office I had a discussion about algorithms and the N-Queens problem came up. I didn’t know about it, so I decided to check it out and then I felt like I wanted to write an implementation in Scala. This blog post documents all of this.

The Problem

The N-Queens problem has the following definition:

Given a positive number N, position this many queens on a chess board of size NxN in a way that no two queens can attack each other.

The Solution

I started thinking about the possible solution. Like almost any algorithmic challenge, the best way to do this is to write it on paper first. A few things became apparent:

1. You can’t have 2 queens on the same row – there must be exactly 1 queen on each row.
2. You can’t have 2 queens on the same column – there must be exactly 1 queen on each column.
3. You can’t have 2 queens on the same diagonal – there must be exactly 1 queen on each diagonal.

Now things started getting some shape and ideas started coming into my head. A very simple solution directly comes to mind, which involves having N nested loops. This doesn’t sound great and it would waste time on lots of unnecessary computations.

Another idea came to mind, where you generate all combinations of single queen per row and column and then check the diagonals. This can be done nicely using bit operations with N bit numbers. For example:

If N=4, then you will need to compute all the permutations of the numbers 1 (0001), 2 (0010), 4 (0100) and 8 (1000). These are all powers of 2 – from 0 to N-1. The number of permutations of those 4 numbers is 4!, which is 1*2*3*4 = 24. This is already a big improvement to the initial idea, which was proposing nested loops with 4*4*4*4 = 256 solutions.

Backtracking

This blog post will focus on another solution – backtracking. It is basically a recursive method where we position queens in each column one by one until they don’t threaten each other or it’s not possible to do so. If not, then we backtrack a step at a time until we’ve found a solution or we’ve exhausted all possible solutions. It is an interesting method, so I will show the code for it here.

First of all, here is the implementation of a method that checks if it is safe to position a queen at a given position. Just because we position our queens column by column, we only need to check the left side and the upper left and lower left diagonals:

def isSafe(board: Array[Array[Int]], row: Int, col: Int): Boolean =
  (0 to col).forall(i => board(row)(i) == 0) && // row to the left
    (row to math.max(0, row - col) by -1).zip(col to math.max(0, col - row) by -1).forall { case (i, j) => board(i)(j) == 0 } && // left upper diagonal
    (row to math.min(num - 1, row + col)).zip(col to math.abs(math.min(0, num - 1 - col - row)) by -1).forall { case (i, j) => board(i)(j) == 0 } // left lower diagonal

After we have defined this method, we can actually implement our backtracking algorithm:

def performSolve(board: Array[Array[Int]], col: Int): Boolean =
  if (col >= num) {
    true
  } else {
    (0 until num).exists(row => {
      if (isSafe(board, row, col)) {
        board(row)(col) = 1
        val s = performSolve(board, col + 1)
        if (!s) {
          board(row)(col) = 0 // backtrack
        }
        s
      } else {
        false
      }
    })
  }

This really is the main method in our program. Below follows a full program that uses the above methods and prints a solution:

package com.ivan.nikolov

import scala.io.StdIn

class QueensSolver(num: Int) {

  def getSolution(): Option[Array[Array[Int]]] = {
    val board = Array.fill(num)(Array.fill(num)(0))
    if (performSolve(board, 0)) {
      Some(board)
    } else {
      None
    }
  }

  def isSafe(board: Array[Array[Int]], row: Int, col: Int): Boolean =
    (0 to col).forall(i => board(row)(i) == 0) && // row to the left
      (row to math.max(0, row - col) by -1).zip(col to math.max(0, col - row) by -1).forall { case (i, j) => board(i)(j) == 0 } && // left upper diagonal
      (row to math.min(num - 1, row + col)).zip(col to math.abs(math.min(0, num - 1 - col - row)) by -1).forall { case (i, j) => board(i)(j) == 0 } // left lower diagonal

  def performSolve(board: Array[Array[Int]], col: Int): Boolean =
    if (col >= num) {
      true
    } else {
      (0 until num).exists(row => {
        if (isSafe(board, row, col)) {
          board(row)(col) = 1
          val s = performSolve(board, col + 1)
          if (!s) {
            board(row)(col) = 0 // backtrack
          }
          s
        } else {
          false
        }
      })
    }
}

object QueensSolver {
  val BOARD_SIZE_MESSAGE = "Please enter the board size:"

  def main(args: Array[String]): Unit = {
    println("=====================================")
    println("Welcome to the Queens problem solver")
    val size = Iterator.continually({
      println(BOARD_SIZE_MESSAGE)
      StdIn.readInt()
    }).dropWhile(_ <= 0)
      .take(1)
      .next()
    println(s"Positioning $size queens on a ${size}x${size} board.")
    printSolution(new QueensSolver(size))
  }

  def printSolution(solver: QueensSolver): Unit = {
    val text = solver.getSolution()
      .map(solution => s"Solution:\n${solution.map(_.mkString(", ")).mkString("\n")}")
      .getOrElse("Solution does not exist!")
    println(text)
  }
}

Below is a snippet of an example run of the program:

=====================================
Welcome to the Queens problem solver
Please enter the board size:
8
Positioning 8 queens on a 8x8 board.
Solution:
1, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 1, 0
0, 0, 0, 0, 1, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 1
0, 1, 0, 0, 0, 0, 0, 0
0, 0, 0, 1, 0, 0, 0, 0
0, 0, 0, 0, 0, 1, 0, 0
0, 0, 1, 0, 0, 0, 0, 0

This calculation came back almost instantly.

Conclusion

Here I presented a backtracking solution to the N-Queens problem implemented in Scala. I also mentioned about another solution using binary numbers and permutations to generate possible solutions and check them. In a future post I will write an implementation of the binary solution and will compare both methods against each other.