Randomized N Queens in k

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.

Posted in k&q. Tags: , . Leave a Comment »