Sudoku Solver in 140 bytes

https://gist.github.com/1230481/95f6facb74f51d089bea87eba0f470cf3bbed83a

by itamarb • 15 years ago

123 21 15 years ago

gist.github.com

0x12• 15 years ago

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.

snippyhollow• 15 years ago

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

ashishgandhi• 15 years ago

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)

alastairpat• 15 years ago

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.

sp332• 15 years ago

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!

po• 15 years ago

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

icebraining• 15 years ago

> 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/

thmzlt• 15 years ago

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

veyron• 15 years ago

What's the minimal `J` solution?

swannodette• 15 years ago

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...

phzbOx• 15 years ago

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

silentbicycle• 15 years ago

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.

todsul• 15 years ago

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.

T-hawk• 15 years ago

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...

makomk• 15 years ago

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.)

whatgoodisaroad• 15 years ago

I want to see a minimal solution in APL.

HankMcCoy2• 15 years ago

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

mrud• 15 years ago

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

rimantas• 15 years ago

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

HankMcCoy2• 15 years ago

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 ...

tikhonj• 15 years ago

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.

Sudoku Solver in 140 bytes

Related Stories