More Sudoku solvers in k and q

I was informed by Attila that the Sudoku solver I mentioned in my previous post wasn’t the only version developed by Arthur. There’s a shorter one here: http://nsl.com/k/sudoku/aw3.k. In fact, in the same directory there are several other solvers by Arthur, Attila and Roger Hui.

So here is all 72-bytes (including the 2 trailing \n) of the shortest Sudoku solver I’ve seen to date:

p,:3/:_(p:9\:!81)%3
s:{*(,x)(,/{@[x;y;:;]'&21=x[&|/p[;y]=p]?!10}')/&~x}

and its translation to q:

P,:3 sv floor(P:9 vs til 81)%3
S:{first(enlist x)(raze@{@[x;y;:;]each where 21=x[where(or)over P[;y]=P]?til 10}')/where not x}

How does it work? Unlike the previous solver, there is considerable simplification.

  1. The P array now comprises of 3 lists: the row, column and sub-square. So P[;i] returns a 3 element vector containing the row, column and sub-square of position i.
  2. The S function is no longer recursive. Instead it iterates over the unfilled positions of the board (/where not x). At each iteration, “where(or)over P[;y]=P is used to identify those positions that lies on the same row, column and sub-square. The “?til 10” returns a list of those positions where the numbers 0 to 9 first appeared. As there are 21 positions, a value of 21 indicates that the corresponding number is missing. So “where 21=” identifies those missing numbers which are then exhaustively substituted using @[x;y;:;]. The “raze” is required to flatten the resulting nested list.

Here is the downloadable code: sudoku2_q.

Advertisements
Posted in k&q. Tags: , . 3 Comments »

3 Responses to “More Sudoku solvers in k and q”

  1. q easter egg? | me, q and kdb+ Says:

    […] seems that this behaviour was implemented to… solve sudoku. The lists it generates corresponds to sudoku array or more precisely – indices of rows and […]

  2. Markus Sieber Says:

    here a version of with 2 bytes less :)

    S:{first(enlist x)(raze@{@[x;y;:;]each where 21=x[where 0b or/P[;y]=P]?til 10}’)/where not x}

  3. Markus Sieber Says:

    without using the easter egg, one could write

    P,:3 sv floor(P:raze each (9#’til 9;9#enlist til 9))%3

    any better ideas?


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: