Skip to content

Latest commit

 

History

History
86 lines (71 loc) · 1.83 KB

README.md

File metadata and controls

86 lines (71 loc) · 1.83 KB
Raw

Introduction

This is a command line program to find all possible placements of N queens on an NxN chessboard such that:

  1. None of the queens can attack each other
  2. No three queens are in a straight line at ANY angle

It implements three methods to find possible solutions:

  1. Permutation: All possible permutations of queen placements are generated and evaluated
  2. Elimination: Starting from the top of the board, possible queen placements are iteratively generated row by row, removing configurations that would allow the queens to attack each other
  3. Multithreaded Elimination: Similar to method 2 but uses multiple threads to generate the placements for improved execution speed

Prerequisites

  • Java version >= 9
  • Gradle version >= 6.2
  • Currently only OSX 10.14+ (Mojave or later) is officially supported

Building

$ git clone https://github.com/ediril/queen-placer.git
$ cd queen-placer
$ gradle jar

Running tests

$ gradle test

Usage

queen-placer [-h] [-d] [-p | -mt] board_size

positional arguments:
  board_size

named arguments:
  -h, --help             show this help message and exit
  -d, --display
  -p, --permuting
  -mt, --multithreaded

Example outputs

$ java -jar build/libs/queen-placer.jar 4 -p -d
Using 'permutation' method
. . Q .
Q . . .
. . . Q
. Q . .

. Q . .
. . . Q
Q . . .
. . Q .

24 possibilities evaluated
2 solutions found
$ time java -jar build/libs/queen-placer.jar 14
Using 'elimination' method
27358552 solution nodes generated
365596 possibilities evaluated
4416 solutions found

real	0m25.639s
user	2m22.655s
sys	0m1.991s
$ time java -jar build/libs/queen-placer.jar 14 -mt
Using 'multithreaded elimination' method
27358552 solution nodes generated
365596 possibilities evaluated
4416 solutions found

real	0m15.854s
user	0m29.597s
sys	0m11.104s