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.

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

2 Responses to “Sudoku solver translated from k to q”

  1. Ravi Annaswamy Says:

    very nice, for unravelling the q code, step by step, thank you. I really loved the way you broke and labeled expression
    chunks in the attached word doc. If you can take a snapshot image of that document and add it inline, here more people may notice it.

    as someone pointed out, the difficulty with apl, j, k, q and sometimes lisp from readability perspective arises from not knowing which part of the phrase to start reading the code with. there are no visual markers and reading-scaffolds to help us.

    c-inspired languages it is so easy to start. python for instance makes it very clear, the only times where we struggle a bit is list comprehensions involving nested generators.

    after you unraveled it, the algorithm seems to be the same brute force approach that is also extremely readable in python.
    by Bill Barksdale, who, incidently did a similar unravelling of a code-golfed python sudoku at

    http://stackoverflow.com/questions/201461/shortest-sudoku-solver-in-python-how-does-it-work

    golfed code original:

    def r(a):i=a.find(‘0’);~i or exit(a);[m
    in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
    j in range(81)]or r(a[:i]+m+a[i+1:])for m in’%d’%5**18]
    from sys import*;r(argv[1])

    and Bill Barksdale masterfully ungolfs it and improves it to:

    import sys

    def same_row(i,j): return (i/9 == j/9)
    def same_col(i,j): return (i-j) % 9 == 0
    def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)

    def r(a):
    i = a.find(‘0’)
    if i == -1:
    sys.exit(a)

    excluded_numbers = set()
    for j in range(81):
    if same_row(i,j) or same_col(i,j) or same_block(i,j):
    excluded_numbers.add(a[j])

    for m in ‘123456789’:
    if m not in excluded_numbers:
    # At this point, m is not excluded by any row, column, or block, so let’s place it and recurse
    r(a[:i]+m+a[i+1:])

    if __name__ == ‘__main__’:
    if len(sys.argv) == 2 and len(sys.argv[1]) == 81:
    r(sys.argv[1])
    else:
    print ‘Usage: python sudoku.py puzzle’
    print ‘ where puzzle is an 81 character string representing the puzzle read left-to-right, top-to-bottom, and 0 is a blank’

    —————————

    If the terseness does not buy much in terms of simplicity, and it makes it exponentially harder to understand,
    then it does not appeal to me, though it stretches my mind in new directions and inspires me to write elegant concise code.
    And it also provides an insight into the minimal thought process (shortcut) necessary to grasp a problem.

    learners prefer naming intermediate results and expressions as it helps cognition of code. (chunking and labeling helps
    short term memory limitations).

    from that perspective, I have noticed that some of the RosettaCode J contributions have more intermediate symbols.

    Ravi

  2. Ravi Annaswamy Says:

    I said:

    the difficulty with apl, j, k, q and sometimes lisp from readability perspective arises from not knowing which part of the phrase to start reading the code with

    I might have to take that back.

    Looks like the reading order is quite simple, start from the right and move towards the left, operator/expressoin by operator.

    I am beginning to like it. It is just one day since I heard J/K/Q and I like many things. Now the intermediate names for expressions seem like ‘crutches’ :)


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: