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 »

Sudoku solver translated from k to q

Many months ago I came across a Sudoku solver written in k by Arthur Whitney:

p:+{(=x)x}'p,,3/:_(p:,/'+:\9#'!9)%3
f:{$[&/x;,x;,/f'@[x;i;:;]'&27=x[,/p i:x?0]?!10]}

Amazingly it is only 2 lines of code. I decided to see if I can translate it into q. The translation was relatively painless as the two languages are so similar. Here it is in q:

P:flip{(group x)x}each P,enlist 3 sv floor(P:raze each flip scan 9#'til 9)%3
F:{$[min x;enlist x;raze F each@[x;i;:;]each where 27=x[raze P i:x?0]?til 10]}

Still 2 lines of code. But the real question is: how does it work? There was no explanation where I found the k code and so I have to go through it line by line (literally speaking).

Here’s a quick summary of how it works:

  1. Treat the 9 x 9 Sudoku board as an array of 81 squares indexed from 0 to 80. So every position on the board corresponds to a number between 0 and 80 inclusive.
  2. Each position has a row , column and sub-square number (0 to 8 inclusive). These are computed inside the expression for P as intermediate values. They are then reorganized such that positions from the same row, column and sub-square are grouped together. The end-effect is that for any position i on the board, P[i] returns a list comprising
    • a list of positions on the same row as i,
    • a list of positions on the same column as i, and
    • a list of positions on the same sub-square as i.
  3. The second line of code is a recursive function F. If the input Sudoku board does not have an empty position (indicated by 0), F returns the board as it is already solved. If there is an empty position at i, F uses P to identify all positions sharing the same row, column and sub-square as i. The numbers from 1 to 9 which did not appear in these positions are exhaustively substituted into position i and the function F is invoked on the newly-updated board.

A clearer and more illustrative explanation of the algorithms is available in this code: sudoku_q. (It is tedious to write q on WordPress. So I’ve moved the explanation into the code instead.)

Update: I’ve written an article on an even shorter implementation here.

Posted in k&q. Tags: , . 2 Comments »