Arthur Whitney's one liner sudoku solver (2011)

Here is the line, it is written in K. K is a language created by the same person (Arthur Whitney) based on APL and Scheme.<p><pre><code> x(,&#x2F;{@[x;y;]&#x27;(!10)^x*|&#x2F;p[;y]=p,:,3&#x2F;:-3!p:!9 9}&#x27;)&#x2F;&amp;~*x</code></pre>

I&#x27;ll sometimes gauge code complexity by comparing the number of lines of code against the output of<p><pre><code> tar -cf - . | gzip | base64 | wc -l </code></pre> IE &quot;how much does it compress?&quot;<p>Looking at APL -- I&#x27;m reminded of what happens if I accidentally send the gzipped output to my tty...<p>I&#x27;m impressed that there&#x27;s anyone who can follow along (can you find the bug?) to code like<p>p←{(↑⍵)∘{(⍺∨.=⍵)&#x2F;⍳n×n∘}¨,⍵},(n*÷2){⍵,⍺⊥⌊⍵÷⍺}&#x27;⍳n n←⍴⍵<p>It really feels like compressed binary data where everyone&#x27;s got a copy of the dictionary already...

<p><pre><code> &gt; Advocates of the language emphasize its speed, facility in handling arrays, and expressive syntax. </code></pre> Indeed.<p><a href="https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;K_(programming_language)" rel="nofollow">https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;K_(programming_language)</a>

Lines of code is a poor metric, because languages use lines differently.<p>A much better measure would be the number of nodes in a parse tree, of semantically meaningful non-terminals like &quot;a constant&quot; or &quot;a function call&quot;.<p>An even better measure would also involve the depth and the branching factor of that tree.

I’ve often wondered about languages like APL&#x2F;k, are the programmers actually able to think about problems more efficiently?

Every K program ought to end in <i>QED</i>, and then I remember that KQED is also a thing, and I wonder if their two worlds have ever overlapped.<p>(KQED is the Bay Area PBS partner. PBS is the US public television org.)

For me one of the most important things here is the clarity of the problem -maker- at the top. That&#x27;s the difference between the &quot;Iversonian&quot; symbolic languages (J and K included) and others. It doesn&#x27;t have the elegance and power of a one line solution, but it&#x27;s just so clean and comprehensible even without the disciplined commenting. (Although I really think lamp is not a good comment glyph. Sorry about the sacred cow I just took a swipe at fellow array nerds.)<p>One line solutions are incredible, and tacit is mind-bendingly cool. To use the unique compactness of a glyph-based language as a way to efficiently describe and perform functional programming - then to do that all over arrays!? - whoever had these ideas [0] is utterly genius.<p>But as someone trying to make time to write a program ground up in APL, knowing that I won&#x27;t be able to make it just a set of really good one liners, that example is also significant for me.<p>[0] <a href="https:&#x2F;&#x2F;www.jsoftware.com&#x2F;papers&#x2F;fork.htm" rel="nofollow">https:&#x2F;&#x2F;www.jsoftware.com&#x2F;papers&#x2F;fork.htm</a>

Most people are put off by the symbols, that wasn&#x27;t really the issue I had.<p>So I do love APL and arraylangs, and learning them was really helpful in a lot of other languages.<p>But they never became a daily driver for me not because of the symbols, which were honestly fine if you stick with it long enough, but after about 3-4 years of dabbling on and off I hit a wall with APL I just couldn&#x27;t get past.<p>Most other languages I know there is a &quot;generic-ish&quot; approach to solving most problems, even if you have to cludge your way through suboptimally until you find &quot;the trick&quot; for that particular problem and then you can write something really elegant and efficient.<p>APL it felt like there was no cludge option -- you either knew the trick or you didn&#x27;t. There was no &quot;graceful degredation&quot; strategy I could identify.<p>Now, is this actually the case? I can&#x27;t tell if this is a case of &quot;yeah, thats how it is, but if you learn enough tricks you develop an emergent problem solving intuition&quot;, or if its like, &quot;no its tricks all the way down&quot;, or if its more like, &quot;wait you didn&#x27;t read the thing on THE strategy??&quot;.<p>Orrr maybe I just don&#x27;t have the neurons for it, not sure. Not ruling it out.

There is a video about this.<p><a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=DmT80OseAGs" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=DmT80OseAGs</a><p>You can try the solution at <a href="https:&#x2F;&#x2F;tryapl.org&#x2F;" rel="nofollow">https:&#x2F;&#x2F;tryapl.org&#x2F;</a>

It may be interesting to compare this one line to &quot;Code Golfed&quot; equivalents in different programming languages:<p><a href="https:&#x2F;&#x2F;codegolf.stackexchange.com&#x2F;questions&#x2F;tagged&#x2F;sudoku?tab=Votes" rel="nofollow">https:&#x2F;&#x2F;codegolf.stackexchange.com&#x2F;questions&#x2F;tagged&#x2F;sudoku?t...</a>

The LoC count and similar metrics have the advantage of an easy calculation.<p>Ultimately though,they are a proxy to a more relevant but difficult to determine attributes such as<p>Given a reasonably proficient engineer, the amount of time it would take them to resolve a bug in code written by someone else or alternatively extend its functionality in some way.

Not knowing K, am I correct in assuming this is a backtracking brute force solver?

For sudokus of size 9x9 and 16x16 almost any unoptimised DFS will work just fine (even for hard sudokus [0]). The real challenge is for sudokus of size 25x25 and above.<p>[0] <a href="https:&#x2F;&#x2F;cdn.aaai.org&#x2F;ocs&#x2F;2517&#x2F;2517-11201-1-PB.pdf" rel="nofollow">https:&#x2F;&#x2F;cdn.aaai.org&#x2F;ocs&#x2F;2517&#x2F;2517-11201-1-PB.pdf</a>

Much better than some of the garbage solutions I have seen, including from sources that should know better, like The Algorithm Design Handbook. Some really absurd approaches out there, so bad I wrote a blog post about it in 2015: <a href="https:&#x2F;&#x2F;www.grahamwheeler.com&#x2F;post&#x2F;sudoku&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.grahamwheeler.com&#x2F;post&#x2F;sudoku&#x2F;</a>

Well if we are showing off sudoku solvers, it would be a sin not to share this one:<p><pre><code> sudoku(Rows) :- length(Rows, 9), maplist(same_length(Rows), Rows), append(Rows, Vs), Vs ins 1..9, maplist(all_distinct, Rows), transpose(Rows, Columns), maplist(all_distinct, Columns), Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is], blocks(As, Bs, Cs), blocks(Ds, Es, Fs), blocks(Gs, Hs, Is). blocks([], [], []). blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :- all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]), blocks(Ns1, Ns2, Ns3). </code></pre> While not <i>one</i> line, to me it is pareto optimal for readable, elegant, and incredibly powerful thanks to the first class constraint solvers that ship with Scryer Prolog.<p>If you want to learn more about it or see more of Markus&#x27;s work:<p><a href="https:&#x2F;&#x2F;www.metalevel.at&#x2F;sudoku&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.metalevel.at&#x2F;sudoku&#x2F;</a><p><a href="https:&#x2F;&#x2F;youtu.be&#x2F;5KUdEZTu06o" rel="nofollow">https:&#x2F;&#x2F;youtu.be&#x2F;5KUdEZTu06o</a><p>More about Scryer Prolog (a modern , performant, ISO-compliant prolog written mostly in rust)<p><a href="https:&#x2F;&#x2F;www.scryer.pl&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.scryer.pl&#x2F;</a><p><a href="https:&#x2F;&#x2F;github.com&#x2F;mthom&#x2F;scryer-prolog">https:&#x2F;&#x2F;github.com&#x2F;mthom&#x2F;scryer-prolog</a>

It has strong perl vibes and it brings back ptsd :D. Maybe this overshortification of things is a personnel or intelligence indicator of some sorts.

So how to feed in the instance if code is only<p>Nebulous1:<p>Here is the line, it is written in K. K is a language created by the same person (Arthur Whitney) based on APL and Scheme. x(,&#x2F;{@[x;y;]&#x27;(!10)^x<i>|&#x2F;p[;y]=p,:,3&#x2F;:-3!p:!9 9}&#x27;)&#x2F;&amp;~</i>x

I put 2011 in the title above because <a href="https:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20110813135700&#x2F;https:&#x2F;&#x2F;dfns.dyalog.com&#x2F;n_sudoku.htm" rel="nofollow">https:&#x2F;&#x2F;web.archive.org&#x2F;web&#x2F;20110813135700&#x2F;https:&#x2F;&#x2F;dfns.dyal...</a> appears to have the main thing - is there a better year?

The discussions around “line noise”-languages are always intersting.<p>Most programmers would agree the ‘&#x2F;’ symbol is at least as clear as writing ‘divideBy’. The question is how often the symbols are used and if their frequency in code justifies learning them.

The k code explained: <a href="https:&#x2F;&#x2F;chatgpt.com&#x2F;share&#x2F;67036e8e-17dc-800f-96c4-1fac8b291f43" rel="nofollow">https:&#x2F;&#x2F;chatgpt.com&#x2F;share&#x2F;67036e8e-17dc-800f-96c4-1fac8b291f...</a>

It&#x27;s cool in a novelty way that it’s so short, but I would infinitely prefer something like this for actual work and understanding:<p><pre><code> def solve(grid): def find_empty(grid): for r in range(9): for c in range(9): if grid[r][c] == 0: return r, c return None def is_valid(grid, num, pos): r, c = pos if num in grid[r]: return False if num in [grid[i][c] for i in range(9)]: return False box_r, box_c = r &#x2F;&#x2F; 3 * 3, c &#x2F;&#x2F; 3 * 3 for i in range(box_r, box_r + 3): for j in range(box_c, box_c + 3): if grid[i][j] == num: return False return True def backtrack(grid): empty = find_empty(grid) if not empty: return True r, c = empty for num in range(1, 10): if is_valid(grid, num, (r, c)): grid[r][c] = num if backtrack(grid): return True grid[r][c] = 0 return False backtrack(grid) return grid</code></pre>

Someone should collate exceptional human coding achievements to test future AI.<p>AFAICT AI cannot replicate this, yet, will be interesting when that day comes.

I thought it was written by Ursula K. Le guin.<p>Not sure where I got that from.

&quot;one line in your custom language&quot; is not one line at all lol

Does anyone have any thoughts on what motivates people to play sudoku or write solvers for sudoku ? I have trouble finding motivation to solve artificial problems. That said I sink hundreds of hours into factorio.

What baud is that? &#x2F;s

Sudoku was always a meditative thing for me. It’s impossible not to win so long as you pay attention. Optimizing solutions seems contrary to the point to me.