Sudoku Solver in 140 bytes | Hacker News Reader

Sudoku Solver in 140 bytes

gist.github.com

123 pointsitamarb21 comments

For those of you who haven't heard of code golf, you should check out http://140byt.es/ The point is more to learn more about the language than to make something practical so come at it in a lighthearted way. In this case, the problem is actually pretty damn hard.

140 Bytes is Jed Schmidt's side project where people compete to make useful functions as small as possible. Jed is kind of a Javascript powerhouse and also happens to be a really nice guy.

https://github.com/jed

https://github.com/jed/140bytes/wiki/Byte-saving-techniques

Edited to add.. As a curiosity, Jed might have the most-forked gist on github: https://gist.github.com/962807

> For those of you who haven't heard of code golf, you should check out http://140byt.es/

The Code Golf SE site is nice too: http://codegolf.stackexchange.com/

Here's one half the size in k:

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

http://thesweeheng.wordpress.com/2008/11/30/more-sudoku-solv...

It would be great to have a javascript translation to compare it. This is still pretty amazing.

You'd have to translate k's entire data model first. It's based on data-parallel, implicit looping over vectors -- like multiplying an entire vector by a constant in linear algebra.

For an open-source implementation of a k-like language, check out Kona (https://github.com/kevinlawler/kona). (Full disclosure, I'm a contributor.) It's still a work in progress, but it's pretty far along.

That's really neat, a sudoku solver that fits in a tweet.

The license is even nicer, that's a real gem, and I think it ought to be submitted for formal approval as an open source license.

It is http://www.gnu.org/licenses/license-list.html#WTFPL . The WTFPL is from an ex-Debian project leader, also one of the original authors of VLC: http://en.wikipedia.org/wiki/Sam_Hocevar

A fork for 139 byes: https://gist.github.com/1247640

And I had never heard of "DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE". (http://en.wikipedia.org/wiki/WTFPL)

I like that the OSI raised the WTFPL licence at a 2009 Board Meeting. I feel the outcome, 'Reject', is a loss for open source software - I'd love to see a programme with LICENCE.TXT containing that.

As snippyhollow pointed out above, the FSF recognizes it as a free license. http://www.gnu.org/licenses/license-list.html#WTFPL It's even GPL compatible!

This won't work for anything but the most basic puzzles. Brute force just constitutes basic gameplay. To solve a moderately advanced Sudoku puzzle you need to compare potential candidates in groups. Then it gets even more advanced with a handful of trial and error techniques.

This is not correct. If a Sudoku puzzle has one and only one solution, brute force can always find it. It is trial-and-error for every single cell and every possible value, which is guaranteed to succeed eventually. Sounds crazy for a human, but a 3 GHz computer microprocessor can rip through that in a second or two.

http://en.wikipedia.org/wiki/Sudoku_algorithms#Solving_Sudok...

Well, a few seconds unless someone goes and feeds you a worst-case puzzle like the one in that wikipedia page anyway. (Yes, that is an entirely valid sudoku with a unique solution. In theory it can even be solved by hand quite easily by applying a simple set of rules. I checked both of these, though not manually.)

Could someone help with the syntax on line 24:

g&&R(a)

I simply don't understand it as a statement and I don't get in the context of the for-loop

if g is true call the function R with the parameter a

http://en.wikipedia.org/wiki/Short-circuit_evaluation The same applies to i--||+a in the first loop.

4clojure has a code golf league for its exercise: http://4clojure.com/

I want to see a minimal solution in APL.

I have to admit, I have never seen

.) for-loops used this way

.) an OR-operator in a for loop

.) +a as a shortcut for a.toString()

.) syntax like g&&R(a) (line 24)

.) syntax like a[j^i==j] (line 29)

Where can I learn/read about advanced stuff like this, searching for this information on google is very hard, as I lack the correct terms ...

I think most of that syntax isn't so much "advanced" as simply not used in practice--it's too hard too read. Additionally, it uses basic operators which you should know (except maybe for "^" which is bitwise xor).

The best thing to do would be go through the basics of JavaScript and learn exactly how everything behaves. You should be able to answer questions like "is 24&&4 === true?" pretty easily.

If you have a bit of time on your hands, reading the standard will teach you all you need to know.

Of course, from a purely professional stand point, this is probably not the best use of your time (although knowing the language inside-out is important); using code like this in production code is a bad idea--it makes maintenance much more difficult.

What's the minimal `J` solution?

Reply on news.ycombinator.com