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.
