Skip to content

n-Queens [Completion] problem solver implemented as multithreaded randomized non-recursive backtracking algorithm with dam-pruning

License

Notifications You must be signed in to change notification settings

zubetto/QueensPuzzle

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

13 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

n-Queens [Completion] problem solver

The class QPSDamDetect contains n-Queens [Completion] problem solver implemented as multithreaded randomized non-recursive backtracking algorithm with dam-pruning

The randomization stands for shuffling of the array of free rows before start of the solving and helps to avoid of "dead" patterns.

The dam stands for a column or row which are not occupied by any queen yet, but at the same time queen placed on any cell of that column or row will be under attack. With sequentially filling of at least one coordinate (columns in this case) the dam detection allows eliminate a searching branch in advance (in the pic. below, the next positions (38,21); (38,31); (38,35) are allowed but position (37,40) is rejected as it causes formation of the dam)

Solutions Distribution

Some interesting results were obtained, playing with this solver. The following plots represent distribution of the solutions number depending on the arrangement of a subset of queens. This distribution is built by iterating the possible permutations of such a subset and counting the number of all solutions containing the current permutation (i.e. by solving n-Queens Completion problem for each permutation). In this particular case, subset consists of three queens that occupy the first three adjacent columns and only the permutations without overlaps (no one attacks each other) are enumerated. The subset length affects the resolution of the plot but not the general nature of the distribution.

plot.ly data 8-12
plot.ly data 13-17

About

n-Queens [Completion] problem solver implemented as multithreaded randomized non-recursive backtracking algorithm with dam-pruning

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages