Sudoku solver in kona!

[douglas mennella]

With this post on thesweeheng's blog I was able to work out how to make this work in kona.  It's a few more lines because k4 seems to have some magic in it to handle some edge cases in the processing.

sv:{:[0=#y;0;{z+x*y}[x]/y]}
vs:{{*|{~0=*x}{(*x%y;(*x!y),*|x)}[;y]/x}[;x](y;())}
fl: {(#x)!@[y#z;!#x;:;x]}

p:sv[3]'(p1:fl[;2;0]'vs[9]'!81)%3
p:+{(*x),*|x}'+(p;p1)
s:{{*1#{0<#&~x[0]}{{@[x;y;:;]'&21=x[&|/p[;y]=p]?/:!10}[(*1#x)][*&~(*1#x)],1_ x}/x}@,x}

I've added both sv and vs to the Idioms page.  I can write up how it's different from what's described on thesweeheng's blog if there's interest, but mostly it's that this code explicitly builds a queue of possible partial solutions and ends when it finds a solution at the top of the queue.  I don't really understand how that's handled in the k4 code.

[Kevin Lawler]

once upon a time k4 had a feature built into it that supported only
the fixed size particular to sudoku grids

re: sv, vs; compare: _sv, _vs https://github.com/kevinlawler/kona/wiki

> --
> You received this message because you are subscribed to the Google Groups "Kona Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to kona-user+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/kona-user/579b09ec-d8d1-4e74-b66e-2d884ebb295dn%40googlegroups.com.

[douglas mennella]

FWIW, I think I've deciphered how the original version worked.  My post above uses backtracing.  It builds up a priority queue of possible completions prioritizing the lowest numbered fill for the most completed grid.  I.e. it follows a single attempt at a solution until it fails and then tries the next option from the point of failure backing up one step if there are no options left.  The original instead builds up the tree of all possible solutions and follows them all simultaneously.  As a given branch reaches a dead end, that branch dies and in the end we're left only with the branch that has the solution.  Here it is in kona:

  x:.:'"200370009009200007001004002050000800008000900006000040900100500800007600400089001"
  p,:,_sv[3]'+_(p:+!9 9)%3;
  *{,/{@[x;y;:;]'&21=x[&|/p[;y]=p]?/:!10}[;y]'x}/[,x;m]
2 0 0 3 7 0 0 0 9 0 0 9 2 0 0 0 0 7 0 0 1 0 0 4 0 0 2 0 5 0 0 0 0 8 0 0 0 0 8 0 0 0 9 0 0 0 0 6 0 0 0 0 4 0 9 0 0 1 0 0 5 0 0 8 0 0 0 0 7 6 0 0 4 0 0 0 8 9 0 0 1

Here we use !9 9 instead of _sv[9]'!81 not only because it's shorter, but because we always get two element lists.  Anyhow, I wanted to close this loop.  Hopefully people find it interesting.

[douglas mennella]

Whoops..  Here m should be &~x.  I was playing to figure out how it worked...

  m:&~x

  *{,/{@[x;y;:;]'&21=x[&|/p[;y]=p]?/:!10}[;y]'x}/[,x;m]

2 8 4 3 7 5 1 6 9 6 3 9 2 1 8 4 5 7 5 7 1 9 6 4 3 8 2 1 5 2 4 9 6 8 7 3 3 4 8 7 5 2 9 1 6 7 9 6 8 3 1 2 4 5 9 6 7 1 4 3 5 2 8 8 1 3 5 2 7 6 9 4 4 2 5 6 8 9 7 3 1