5 ms·

Sudoku Solver in 140 bytes

123 points by itamarb 15y ago

thmzlt 15y ago
4clojure has a code golf league for its exercise: http://4clojure.com/ http://4clojure.com/
veyron 15y ago
What's the minimal `J` solution?
swannodette 15y 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-solvers-in-k-and-q/ http://thesweeheng.wordpress.com/2008/11/30/more-sudoku-solv...
- phzbOx 15y ago
  It would be great to have a javascript translation to compare it. This is still pretty amazing.
  - silentbicycle 15y 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 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 15y 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 15y 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_Sudokus_by_a_brute-force_algorithm http://en.wikipedia.org/wiki/Sudoku_algorithms#Solving_Sudok...
  - makomk 15y 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 15y ago
I want to see a minimal solution in APL.
HankMcCoy 15y 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 15y ago
  if g is true call the function R with the parameter a
- rimantas 15y ago
  http://en.wikipedia.org/wiki/Short-circuit_evaluation http://en.wikipedia.org/wiki/Short-circuit_evaluation The same applies to i--||+a in the first loop.
HankMcCoy 15y 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 15y 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.
0x12 15y 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 15y ago
  It is http://www.gnu.org/licenses/license-list.html#WTFPL 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 http://en.wikipedia.org/wiki/Sam_Hocevar
ashishgandhi 15y ago
A fork for 139 byes: https://gist.github.com/1247640 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 http://en.wikipedia.org/wiki/WTFPL)
- alastairpat 15y 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 15y ago
    As snippyhollow pointed out above, the FSF recognizes it as a free license. http://www.gnu.org/licenses/license-list.html#WTFPL http://www.gnu.org/licenses/license-list.html#WTFPL It's even GPL compatible!
po 15y ago
For those of you who haven't heard of code golf, you should check out http://140byt.es/ 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 https://github.com/jed/140bytes/wiki/Byte-saving-techniques 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 https://gist.github.com/962807
- icebraining 15y ago
  > For those of you who haven't heard of code golf, you should check out http://140byt.es/ http://140byt.es/ The Code Golf SE site is nice too: http://codegolf.stackexchange.com/ http://codegolf.stackexchange.com/

123 points by itamarb 15y ago

thmzlt 15y ago

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

veyron 15y ago

What's the minimal `J` solution?

swannodette 15y 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-solvers-in-k-and-q/ http://thesweeheng.wordpress.com/2008/11/30/more-sudoku-solv...

phzbOx 15y ago
It would be great to have a javascript translation to compare it. This is still pretty amazing.
- silentbicycle 15y 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 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 15y 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 15y 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_Sudokus_by_a_brute-force_algorithm http://en.wikipedia.org/wiki/Sudoku_algorithms#Solving_Sudok...
- makomk 15y 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 15y ago

I want to see a minimal solution in APL.

HankMcCoy 15y 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 15y ago
if g is true call the function R with the parameter a
rimantas 15y ago
http://en.wikipedia.org/wiki/Short-circuit_evaluation http://en.wikipedia.org/wiki/Short-circuit_evaluation The same applies to i--||+a in the first loop.

HankMcCoy 15y 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 15y 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.

0x12 15y 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 15y ago
It is http://www.gnu.org/licenses/license-list.html#WTFPL 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 http://en.wikipedia.org/wiki/Sam_Hocevar

ashishgandhi 15y ago

A fork for 139 byes: https://gist.github.com/1247640 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 http://en.wikipedia.org/wiki/WTFPL)

alastairpat 15y 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 15y ago
  As snippyhollow pointed out above, the FSF recognizes it as a free license. http://www.gnu.org/licenses/license-list.html#WTFPL http://www.gnu.org/licenses/license-list.html#WTFPL It's even GPL compatible!

po 15y ago

For those of you who haven't heard of code golf, you should check out http://140byt.es/ 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 https://github.com/jed/140bytes/wiki/Byte-saving-techniques 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 https://gist.github.com/962807

icebraining 15y ago
> For those of you who haven't heard of code golf, you should check out http://140byt.es/ http://140byt.es/ The Code Golf SE site is nice too: http://codegolf.stackexchange.com/ http://codegolf.stackexchange.com/