In an earlier post, I described an N Queens solver that returned all solutions for a given board size N. However that approach is too slow for large N due to the enormous search space. For large N, it seemed more appropriate to construct one solution at a time. The following is k code does that:

row:{&~(!y)in,/x+|-1 0 1*/:1+!#x} rnd:{(-#x)?x} rqn:{$[y=#x;x;do[#a:rnd row[x]y;$[y>#b:.z.s[x,*a]y;a_:0;:b]]]}()

Explanation:

- The row() function returns the available positions in the next row.
- The rnd() returns a random permutation of its input.
- The rqn() function solves the problem by recursively iterating over all available positions in the next row. It returns only when a solution is found (y=#x).

The updated code is here: qns2_k.

Advertisements