What is Digg?59 Comments
- Philodox, on 10/12/2007, -2/+32I don't think it's fair to say the program is four lines long when there are many end of line delimiters (semicolons) per line.
- rpike, on 10/12/2007, -1/+28That's not the point. It is more a test of programming ability than anything.
- MarkByers, on 10/12/2007, -3/+25Hey get off my server, it's burning!!! Can someone mirror this please! :)
- dspickes, on 10/12/2007, -0/+19It's not about doing the Sudoku. It's about simplicity of programming. Getting the most functionality out of the smallest amount of code is a challenge and an honor among programming circles. The prize is particularly juicy for more trivial tasks that tax the human brain, such as Sudokus and Rubiks' Cubes.
That is a beautiful bit of coding. - geocar, on 10/12/2007, -1/+19proof that even python can look like ass if you really try...
- jswan, on 10/12/2007, -2/+17def r(a):i=a.find('0');~i or exit(a);[m
in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import*;r(argv[1]) - Dracker, on 10/12/2007, -1/+9It's not the lines that really matter in this kind of challenge, it's the # of characters. "Lines" in the context of this competition mean 80 characters, the typical number for a line in a command prompt. Historically, a certain number of 80 column lines has been the limit for several of these competitions.
You can't call 1,000 characters on a single line "a line" in this context. - adidax, on 10/12/2007, -3/+11agreed, why the hell would you want to make code nearly unreadable for the sake of it being able to fit on 4 lines?
- Mach5, on 10/12/2007, -2/+10the first thing i think of when i see a sudoku puzzle is "hey, i bet i can code something to solve that"
- asteron, on 10/12/2007, -4/+11Inefficient solutions (a simple backtracking brute force search), are trivial for sudoku. That he can make it in 178 bytes of jibberish is not a good skill for a language designed for ease of readability.
- thegreatsam, on 10/12/2007, -2/+9Uhhh...it's not stealing content. Virtually nothing on Digg is "original", its all a link to some other work. Digg is more like a table of contents page than anything else.
- MarkByers, on 10/12/2007, -1/+7Google Cache: http://64.233.183.104/search?q=cache:LQo2W5kV0XEJ:markbyers.com/moinmoin/moin.cgi/ShortestSudokuSolver+shortest+sudoku+solver&hl=da&gl=dk&ct=clnk&cd=2&client=firefox-a
- giantrobot, on 10/12/2007, -2/+8I would like to see a sudoku solver written in *****
http://en.wikipedia.org/wiki/*****
The amazing, stickiest of the sticky Turing Tarpit languages, if you ask me. - bstock, on 10/12/2007, -2/+8Mirror: http://www.duggmirror.com/programming/Even_Shorter_Sudoku_Solver_-_In_Python/
- inactive, on 10/12/2007, -1/+6Never thought I'd see the day when I'd be looking at obfuscated Python...
- HiddenS3crets, on 10/12/2007, -3/+7Definately have to agree with that. Anyone could write what is supposed to be 100+ lines of code on one line and say that his/her program does this and that, etc. and it's only one line long.
- MarkByers, on 10/12/2007, -3/+7There are three semicolons (line delimiters).
- lnxaddct, on 10/12/2007, -3/+7Errand,
Sudoku is a game of applied logic, no guessing required (at least in valid puzzles) - OrangeTide, on 10/12/2007, -0/+3Think of it as a meta-puzzle. You're solving a problem (the sudoku puzzle) by solving a problem that solves it (the program). Programmers get a huge kick out of this.
One of my goals is to write a program that *generates* other programs to solve puzzles :) - eczarny, on 10/12/2007, -1/+4A lot of Sudoku solvers use a recursive back-tracking algorithm to find a solution, it's the first that comes to mind when trying to implement your own. Although, I read in Dr. Dobb's about a Sudoku solver algorithm based on graph theory, but the mathematics were a little beyond me... That, and I couldn't find any overviews of how fast it was (O(1), O(n), O(nlogn), etc...). It would be nice to find a list of some other Sudoku algorithms out there, anybody know of some others?
- eczarny, on 10/12/2007, -1/+4I found one yesterday written in Perl, 3 lines of code, longest line is 73 characters...
http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html - eczarny, on 10/12/2007, -1/+3Semi-colons don't necessarily delimit end of lines, in terms of the compiler/interpreter it simply means the end of an expression (or statement, or something similar). Some languages require them (C for example), while others do not (Ruby).
- inactive, on 10/12/2007, -1/+3Some days I feel like I should've kept up with those computer classes. That looks like alien text to me.
- chesterjosiah, on 10/12/2007, -2/+4God bless you.
- mozzep, on 10/12/2007, -1/+3"It's not about doing the Sudoku. It's about simplicity of programming. Getting the most functionality out of the smallest amount of code is a challenge and an honor among programming circles."
uTorrent must be the mesiah. - eczarny, on 10/12/2007, -1/+3There is room to make the Perl one even smaller, at least that's what the author says.
- Raybdbomb, on 10/12/2007, -2/+3There's nothing about efficiency in here. I'd like to see an nlgn algorithm or less do it.
- dougal1985, on 10/12/2007, -1/+2 I'd be interested in the bigO values for these algorithms also, something that I haven't found on any of the examples I've seen so far
After a quick google I found a 100 line python solver that uses search combined with constraint propagation combined with search: http://norvig.com/sudoku.html
Interesting read. - asteron, on 10/12/2007, -1/+2While computer solutions that make logical deductions are not very hard to do... it is much shorter to program a brute force trial and error type search. There are large groups of puzzles for which no 'logical' solution is known and can only be solved by guessing a number and trying to see if a contradiction arizes. Of course guess and check can be argued as a type of logic but is certainly not as intelligent as most of the set-theoretic deductions humans employ to eliminate canidates.
For more information on logical sudoku solvers see the sudoku programming forum at
http://www.setbb.com/phpbb/index.php?mforum=sudoku - MarkByers, on 10/12/2007, -0/+1Update: after receiving some feedback, the shortest Sudoku solver is now a *2-line* Ruby program. I have updated the web-page.
- dougal1985, on 10/12/2007, -1/+2 Very nice page! Good to see the code and the command lines for running each of the perl and python solvers. They run fairly fast too (Macbook 2.0Ghz) and use very little memory. By looking at the code (I know little of Perl or Python) they seem to use a brute-force style technique. Not the fastest, but nice nonetheless.
- trutwin, on 10/12/2007, -1/+2Or better yet - whitespace:
http://compsoc.dur.ac.uk/whitespace/ - eczarny, on 10/12/2007, -0/+1@IronKurton
You can easily take the 3 lines of code and format it to your liking in less time it took to write your comment. Sure, clean code is important. However, the idea behind this Sudoku solver is being as short as possible. It isn't a hack, it's a full-fledged solution... A lot of thinking was involved.
Besides, a lexical scanner would LOVE this code. - recursive, on 10/12/2007, -0/+1Since Soduku puzzles are a fixed size, I'm confused how you measure "Big O" execution time. What would n be? Typically, n is the size of the input, but the input (Sudoku puzzle specification) is always the same size.
- Drakazz, on 10/12/2007, -0/+0Wow, this is very impressibe how short you can make it ;)
I'd take ages to do it.. - kungPow, on 10/12/2007, -1/+1this is the best use of python I've seen yet
- epheterson, on 10/12/2007, -1/+1Haha, I put their test one in my cell phone sudoku game, and it's been sitting there for a good hour and a half trying to solve it :-p
- jeruvin, on 10/12/2007, -2/+2That explains why I can't see the code. Perhaps you can post it in a comment on here for us.
- boblabla, on 10/12/2007, -1/+1The reason programmers do this is so that they can move onto bigger, harder problems. And in order to solve something like this, the problem has to be understood entirely. Once that is accomplished and one knows all there is to know about the sudoku system, there is nothing more to be gained from working puzzles.
- ErrandboyOfDoom, on 10/12/2007, -1/+1@ Inxad:
Guess and check is a type of applied logic, it's basically a series of proofs by contradiction. It doesn't make it a fine art.
Do you really think solving Sudoku involves more creativity and analytical skill than programming? - lnxaddct, on 10/12/2007, -1/+1eczamy,
Here is something I've written that might interest you: http://krenzel.info/?p=12 . Solve any sudoku puzzle using only two rules. It is based off of graph theory as well. There is no formal mathematical proof provided but it works. - midtown, on 10/12/2007, -2/+1hahaha. i know what you mean
- eczarny, on 10/12/2007, -3/+2Oops, wait. Nevermind. Found a copy of the Python solver. Definitely is shorter. Bury if you want.
- IronKurton, on 10/12/2007, -2/+1I agree. This is retarded. How about writing well-structured code with comments, that is easily readable and maintanable by the intended audience of the code?? IMHO, that is far more impressive than just some hack put together in 2 lines of code. Yes, the problem is simple enough that you don't _need_ much structure or many comments, but the same principle applies to bigger programming challenges where lack of structure and comments unnecessarily extend the lifecycle of the project.
- rhyno2000, on 10/12/2007, -2/+1Link still dead as of 2pm EDT
- hydrokayak, on 10/12/2007, -3/+1Dead link. 12:46 ET 7/13
- micro506, on 10/12/2007, -4/+1Ha! I'll bet perl can do it in 2.
- vees, on 10/12/2007, -3/+0Coming up 404 now (12:25 ET 7/13).
- ceeam, on 10/12/2007, -5/+2It could, but in all fairness it still looks perfectly readable (save some math maybe).
- dggoldst, on 10/12/2007, -4/+0Ha! I'll bet Sudokython can handle it in 1.
-
Show 51 - 59 of 59 discussions
Check out the new & improved 
© Digg Inc. 2009
— Content created and posted by Digg users is