Permutation-stream based n-queens solution

Following is a very crisp solution for solving n-queens problem in Racket programming language. The method is to get all permutations (so that no 2 queens are in same line) and to check these for any of them being on diagonals:

#lang racket

; FOLLOWING FN RETURNS TRUE IF QUEENS ARE ON DIAGONALS:
(define (check-diagonals bd)
(for/or ((r1 (length bd)))
(for/or ((r2 (range (add1 r1) (length bd))))
(= (abs (- r1 r2))
(abs(- (list-ref bd r1)
(list-ref bd r2)))))))

; SET BOARD SIZE:
(define N 8)

; 3-LINE SEARCH LOOP:
(for ((brd (in-permutations (range N))))
(when (not (check-diagonals brd))
(displayln brd)))


The in-permutations function returns a stream sending one permutation at a time, so it does not find all permutations in advance.

Can this code be further improved to increase its speed for larger numbers, especially by parallelization or concurrency? Thanks for your help.

(PS: I have also posted this at https://stackoverflow.com/questions/46144576/parallel-running-of-racket-code)

Variable Names

There is little reason not to give the variables clear meaningful names. Using abbreviations leads to using bd in check-diagonals and brd in the search loop. Calling the board board makes the code clearer. Similarly, the time a reader spends figuring out that r1 and r2 refer to rows is wasted time for every reader. It saved the programmer four keypresses once.

The size of the board is a natural number. The traditional notation for the Natural Numbers is n not N. It's why it's the 'n-queens' problem not the 'N-queens' problem.

Concurrency and Parallelization

Concurrency covers all problems where the execution can be logically simultaneous whether or not the implementation runs in parallel or not. Most concurrent processes do not run entirely in parallel. Parallelization is a way of executing a concurrent process. All concurrent processes are not run in parallel. All parallel processes are logically concurrent.

The n-queens problem

The solution space of n-queens problem is non-polynomial. The size is n!. Parallelization with p nodes still leaves the solution space non-polynomial, approximately n!/p. A solution that would take a 100 million years still takes an impractical time when spread across 1,000,000 nodes.

What makes the n-queens problem interesting is that it is non-polynomial and that it has symmetries that allow for the search space to be pruned. For example, many configrations are isomorphically related to other configurations by board rotation and mirroring.

Optimizing solutions to NP problems

There is no general algorithm for quickly solving non-polynomial problems. That's what makes them interesting/hard depending on one's perspective. Speeding up the code to a specific problem requires taking advantage of the problem specifics.

In the case of n-queens, pruning the search space of isomorphic non-solutions each time a non-solution is found. Optimization comes from writing code that coming across the the n=3 non-solution:

  a b c
1 Q Q
2
3


prunes the search space of isomorphic configurations such as:

  a b c
1   Q Q
2
3


and

  a b c
1     Q
2     Q
3


Other Strategies

An empty board has zero probability of being a solution. This is lower than a board with a queen randomly placed in each column. Though the probability of random placement producing a solution is slight, it is better than an empty board.

Gradient Descent Starting with a randomly populated board, an estimate of the distance from a solution is made. [1] Next each alternative position for each queen is examined and an estimate of the distance from a solution is made for each resulting configuration. The one move that results in minimizing the distance from the solution is made and the process repeats.

When no improvement is possible the solution may be abandoned [2] and a new random board generated. Generating and examining random boards is parallizable and typically done because the number of boards examined is often large.

[1]: Choosing how to measure the distance is art informed by science, not pure science except in so far as recognizing that the problem of measuring is still in NP.

[2]: More complex approaches may not always chose the configuration closest to a solution and/or backtrack when no improvement is possible. Again, optimization is based on understanding the particulars of the problem.

• Great insights on how to think intelligently and artfully for quicker solutions. – rnso Nov 19 '17 at 2:58
• @rnso this paper might be interesting. Partially because it is a reminder that good n-queens algorithms were literally "rocket science" not very long ago. – ben rudgers Nov 19 '17 at 5:19