Skip to content
I will do what queens do, I will rule.
Java
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
gradle/wrapper
src/main/java/nqueen
.gitignore
README.md
build.gradle
gradle.properties
gradlew
gradlew.bat
settings.gradle

README.md

N-queen

Run ./gradlew run --args="1 40" in order to generate N-queen boards from 1 to 40.

Example:

$ ./gradlew run --args="8 10"

> Task :run
Solving 8-queen problem:
 --  --   0  --  --  --  --  --
 --  --  --  --   1  --  --  --
 --  --  --  --  --  --  --   2
 --  --  --   3  --  --  --  --
  4  --  --  --  --  --  --  --
 --  --  --  --  --  --   5  --
 --   6  --  --  --  --  --  --
 --  --  --  --  --   7  --  --
Took 9ms
Solving 9-queen problem:
 --   0  --  --  --  --  --  --  --
 --  --  --   1  --  --  --  --  --
 --  --  --  --  --  --   2  --  --
  3  --  --  --  --  --  --  --  --
 --  --   4  --  --  --  --  --  --
 --  --  --  --  --  --  --  --   5
 --  --  --  --  --   6  --  --  --
 --  --  --  --  --  --  --   7  --
 --  --  --  --   8  --  --  --  --
Took 1ms
Solving 10-queen problem:
 --  --   0  --  --  --  --  --  --  --
 --  --  --  --   1  --  --  --  --  --
 --  --  --  --  --  --  --  --   2  --
  3  --  --  --  --  --  --  --  --  --
 --  --  --  --  --   4  --  --  --  --
 --  --  --  --  --  --  --  --  --   5
 --  --  --  --  --  --   6  --  --  --
 --   7  --  --  --  --  --  --  --  --
 --  --  --   8  --  --  --  --  --  --
 --  --  --  --  --  --  --   9  --  --
Took 4ms

BUILD SUCCESSFUL in 0s
2 actionable tasks: 1 executed, 1 up-to-date

High-level overview

We backtrack from row 0 to row n-1 trying to place a queen in every column.

At each row, we create a Forbidden, which is a HashSet containing all the forbidden cells. It also detects the case where any below row becomes impossible to place a queen; it'll halt immediately.

Anecdotally, it seems much better to not start brute-forcing by placing a queen at the corner.

I parallelized the code with Future but later decided to remove it. While it is faster, the code becomes more complex.

It seems there are a few hacks we can do in the future. I've noticed that the first n/4 queens can simply be placed without backtracking in a sliding down manner starting from (0, n/2). But I can't prove mathematically that this is the case.

Bonus

If you install Lilit's browser extension, you will have code intelligence while reading the code here on Github.

You can’t perform that action at this time.