September 20, 2005Sudoku obsession
Have you been sucked into Sudoku yet? If not, here is your chance. Fill the grid above with numbers from 1 to 9, making sure that each row, each column and each box (the nine smaller 3x3 grids) contain each number exactly once. Sudoku is a fiendishly addictive puzzle that has been gaining an extraordinary popularity these past months. Three Sudoku books are listed in the New York Times' top 50 list, I have seen dozen of people playing Sudoku in buses and airports, but what really made me realize how big the craze was is when I asked my brother, who lives in France, if he had heard of it, and his answer was "Who hasn't?". I like solving Sudoku grids myself but I find the software challenges even more interesting. If you are up for a little exercise, here are a few problems for you to solve:
Happy hacking! Posted by cedric at September 20, 2005 09:39 AM Comments
I had thought sudoku was too much like minesweeper, but now it looks more interesting. Thanks for the post. Posted by: Ron at September 20, 2005 10:05 AMIt's funny we think about this in exactly the same way. I blogged about this last month at http://yoavs.blog[REMOVE]spot.com/2005/08/fosssoduko.html, It's funny we think about this in exactly the same way. I blogged about this last month at http://yoavs.blog[REMOVE]spot.com/2005/08/fosssoduko.html, I abandoned Sudoko quickly, not because I disliked it, but because I liked it too much. I wrote a bruteforce solver, and it did well enough, but I had to toss whole lot for fear of it taking over my life. Have fun! Posted by: Robert Konigsberg at September 20, 2005 11:36 AMCheck out http://www.sudokuprime.com and play multiuser sudoku with your friends. Have fun! Posted by: Olivier Verdin at September 20, 2005 12:53 PMOtaku, It this your game Sudoku? rgds, Hi Cedric, first of all thanks for your weblog, I read it since a long time and always enjoy it. I've got a little "story" about Sudoku. While in vacation, with a computer (but no Internet connection), my family would play Sudokus' in the newspaper, by hand. I saw it, and immediately thought: "hey, I could easily write a solver for this". So, during lunch time, when sun was really too hot, I booted my laptop and started a new IDEA project (yup, I'm not gone back to Eclipse yet ;) I did it relatively "cleanly", using interfaces (to allow me to quickly switch "solvers" algorithms and "board" representation), unit tests, etc. All in all, it took me 75 minutes, including manually encoding some 9x9 boards and their accepted solution. The most simple way to solve it (I only solved it, it was fun but I'm not going to spend hours and hours on this ;) is to use a trivial recursive algorithm (which uses backtracking and some pruning). So I used some pruning, but I didn't even bother to choose ways that would prune the search tree faster: "premature optimization bla bla bla..." ;) When I came back from vacation, I tried my solution with some supposedly "hard" sudoku for computers: my solver does less than 100ms on them (and some have solver much faster that). All this to say that your blog makes it sound like the solver needs bruteforce while the generator needs backtracking and I ticked when I read that: the easiest and most trivial way to write a solver *is* to use one backtracking algo (amongst many backtracking algo) that *does* brute force the problem. Now of course the definition of "brute force" can vary: a trivial backtracking algorithm will brute force its way through all partial valid boards until the correct one is found (brute forcing doesn't try all possible values: it only does so until it find (the) one that matches). It is clear that "brute forcing" a sudoku by trying Math.pow(9, 72) states isn't going to work... The main recursive loop I wrote is about 10 lines (and can possibly be shorter). The problem share some similarities to the "eight queens": you have a board, you place "something" on it and recurse... And "eigth queens" is solved by brute forcing it, using a backtracking algorithm (which really is some kind of depth first search). For example: http://spaz.ca/aaron/SCS/queens/ "Using recursion, the board can be solved from the top down, trying all possibilities and backtracking (known as a depth first search)." That's it, let's not enter into semantics debate, but I just wanted to clarify some things which I think weren't entirely clear in your weblog:  backtracking does brute force (by trying all possibilities, until it finds one that works)  backtracking is usually implemented using some pruning (Wikipedia has a nice entry on "backtracking")  backtracking is a depthfirstsearch  the most trivial way to write a Sudoku *solver* is to use backtracking
Go TopCoder! Go Google! (sponsoring TopCoder matches and the Google Code Jam, using TopCoder technology) Go fun algorithmic problem! And... Go Cedric's weblog! :) Posted by: somevisitor at September 24, 2005 08:01 AMIf you like sudoku but don't feel like making your own you can always try my site. ~john Posted by: John Reusing at September 29, 2005 08:46 AMHi! use Tk;
hi iwant su doku generator please hi! I want a clear step by step algorithm for solving this su doku, please provide me at arvind.mailup@gmail.com Posted by: arvind at October 10, 2005 06:30 PMI want to add some more challanges to the computer science tasks mentioned in this blog. Sudoku generation is quite simple, the problem is to generate puzzles with just one solution. This can be guaranteed by a logic solver but not by a solver that works with guessing and backtracking. Posted by: Blandi at October 12, 2005 10:20 AMYet another adress: Logic problems like Sudoku rely on there being one and only one correct value for each position. In order to be able to solve them at all, at any time there must be at least one position for which you can derive the answer. I wrote a solver that works by (1) eliminates from consideration any cell (and associated cells, row, column, and square) that has already been solved then (2) examines each row, column, and square to see if there is a value that can only occur in one position in the row/column/square, then iterates starting at 1. If you ever get to a point where you can't find one or more positions which have unique values the Sudoku can't be solved. It's simple loops, no recursion necessary. The generator is harder and I haven't solved that problem yet. Working on it though. Sudokus by Koalog: Checkout www.Printsudoku.com. It's a new website where you can find lots of sudokus in pdf format, and also you can play online. There is also Magic Sudokus. This site rocks! Posted by: meji at November 11, 2005 10:31 AMCOMPUTER AIDED SUDOKU is a free Excel game that you can download at http://perso.wanadoo.fr/sudoku.laviron COMPUTER AIDED SUDOKU is a free Excel game that you can download at http://perso.wanadoo.fr/sudoku.laviron Free download the new version of "Computer Aided Sudoku Excel" at http://perso.wanadoo.fr/sudoku.laviron/ hi there, my question is what is the condition to fine the one that works(a valid answer) from all of the probability? can anyone help me with this? I wrote my own version of an Excel Soduko trainer and solver a while back, but I didn't have a good way to generate them...until now. Here's the concept in the alogarithm that you can program yourself. Assuming a 3x3 grid WORKS EVERY TIME IF YOU APPLY THE LOGIC Posted by: Greg G at July 14, 2006 03:34 PMHeeellllllpppppp, I'm trying to find the best solution of the Sudoku problem. I used Mozart in solving it. Now my problem is, I want to implement a backtracking search on the tree using Mozart and the notion of computational spaces. Can anyone help me...i need the Mozart code for backtracking... email me at tantanix@yahoo.com Posted by: Christian at October 17, 2006 10:57 PMI liked a numeric crossword rather than Sudoku (it used to feature as the monthly prize competition in PC Pro, they had a program which could generate the crosswords.) (You can see an example at ils.unc.edu/~britd/math.htm) I ended up writing a program to solve them (it was a fun problem to solve). The clues are things like 1A = 3D * 6A, 2A = Prime, 3A = 6 Gross, so there are at least 2 values you can work out initially. Posted by: Neil Harding at November 3, 2009 06:15 PMPost a comment
