[David Easton] ''05 Jan 2005'' '''Sudoku''' is a puzzle included in '''The Times''' newspaper in the UK since November 2004. The rules are extremely simple: In a 3x3 grid of boxes, each with 3x3 cells, fill in the digits 1..9 so that each digit occurs exactly once in each row, column, and box. I have written a tool in Tcl that allows: * Sudoku puzzles to be generated * Sudoku puzzles to be played * Sudoku puzzles to be solved [DPE] ''25 Feb 2005'' Version 0.7 has been released as a Tcl/Tk starkit with no compiled extensions. [http://www.easton.me.uk/tcl/sudoku/sudoku1.gif] [http://www.easton.me.uk/tcl/sudoku/sudoku2.gif] [http://mini.net/files/sudoku.jpg] It is freely available from: http://www.easton.me.uk/tcl/sudoku/index.html [DPE] ''27 May 2005'' The above link fails each day when the 150Mb bandwidth limit is reached - sorry about that, it is a victim of its own success, so if it does not work, try it in the morning UK time. -[RS]: Or this backup: http://mini.net/files/sudoku.kit [DPE] ''07 June 2005'' Moved to a higher bandwidth server, so it should no longer be unavailable. ---- '''Sp!''' ''8th March 2005'' Thank you!!! I have been addicted to these puzzles for a while now and this is just brilliant. I generate half a dozen gifs and paste them into word to take to work with me. Took a little searching to find this wiki (found your home page first) but very glad I did. [AvL] ''March 21th 2005'': I join in to this praising. Anyway, I've also made some changes to my copy: changed gray and darkgrey both to blue (grey was too little contrast on my monitor), and I made bind'ings for digit-keys to invoke the respective button. Also, I've made the cells larger (from 25 to 35) and changed the buttons from image to penfont-text (-width 2). I've got some more "feature"-requests: * undo (at least one level: I often write a number to wrong cell, then have to erase it and try to restore what was in the cell before. * shading complete lines/rows/boxes (optionally) * right-click on buttons should toggle a disabled-state, so I can visually mark the digits that have already been placed 9 times. Upon new game or clear board, all shall be enabled. * reset to current game: just remove all gray (blue) numbers, but leave the black ones. These features do not give more extra help, than what one could do on paper. Plus another feature that *does* exceed the possibilities on paper: * optionally do auto-check after each big digit. I've not yet understood the prog well enough to implement these goodies myself. [DPE] ''21 April 2005'' I've only just noticed the above posts. Thanks for the positive feedback. Now that you've set me a challenge, I'll see if I can find some time to do some more improvements! ---- David, I am intending to port this to Mac OS X as a self-contained file, such that it can be simply double-clicked by the most ignorant of users. I couldn't find your email anywhere to obtain your permission to do so. If you have any qualms about this, please post them to this site. Thanks, Dan Schellenberg [DPE] ''21 April 2005'' Dan, feel free to use this as you wish - just reference this page or my web site somewhere. I can put a MAC executable on my web site if you think it would be of interest. [RAF] "21 August 2005" It would be nice for the MAC executable to be hosted here - meanwhile, it is on Dan's site here [http://www.educationaltechnology.ca/dan/archives/2005/04/22/sudoku-aka-su-doku-generator-and-solver-for-mac-os-x/] [PT] 19-May-2005: Very cool!! [RJ] 19-May-2005: VC indeed. David, I suggest that this starkit be included under Games at [sdarchive]. Very nice work. [DPE] ''27 May 2005'' Thanks. I'll soon release version 0.8 that allows a page of puzzles to be created as a PDF document - I'll try to get around to adding it to [sdarchive] at that time. ---- See also [Playing sudoku] for some mathematical musings. [http://mini.net/files/sudoku.tcl] is a compaction of v 0.7 (single Tcl file, no image loading or saving) tweaked to run on the [iPaq]. [http://mini.net/files/sudoku-ce.jpg] ---- [ABU] 10-sep-2005 Based on the original work of Dave (v 0.7), this my variant (v. 0.7.1) comes with a different, and I believe more comfortable, user interface. ... [http://web.tiscali.it/irrational/tcl/sudoku-0.7.1/sudoku.gif] Home page and download at [http://web.tiscali.it/irrational/tcl/sudoku-0.7.1/index.html] . ---- 28-Nov-2005, on [clt] Bernard Desgraupes announced a sudoku solver. [http://webperso.easyconnect.fr/bdesgraupes/DocHTML/sudokut.html] (bernard-01-12-2005) It is a command line sudoku solver written in Tcl and named [sudokut]. There is no GUI: just pass the sudoku 81 chars string as an argument to the ''sudokut'' command. Alternatively you can pass a sudoku file (one sudoku string per line) with the -f option to have all the sudokus in this file solved. There are several options. Internally it implements an exact cover algorithm based on D. Knuth's dancing links strategy. This guarantees to find all the solutions. I have also put the code on SourceForge [http://sourceforge.net/projects/sudokut/]. For instance: shell> sudokut ...3..8..64.8...5.875.....15...7.2.6....9....2.9.8...54.....769.2...8.13..7..5... Found 1 solution Solution 1: ----------------------- | 1 9 2 | 3 5 6 | 8 4 7 | | 6 4 3 | 8 1 7 | 9 5 2 | | 8 7 5 | 4 2 9 | 6 3 1 | |-------|-------|-------| | 5 8 4 | 1 7 3 | 2 9 6 | | 7 6 1 | 5 9 2 | 3 8 4 | | 2 3 9 | 6 8 4 | 1 7 5 | |-------|-------|-------| | 4 5 8 | 2 3 1 | 7 6 9 | | 9 2 6 | 7 4 8 | 5 1 3 | | 3 1 7 | 9 6 5 | 4 2 8 | ----------------------- (GWM) NB the main tool described on this page solves in a WYSIWIG manner a sudoku set to it. I also pondered how many games of Sudoku there could be. For example, suppose there is a Sudoku puzzle that is solvable; the following operations make the original puzzle look different but actually leave the puzzle the same: * swap any 2 rows in the top 3 rows (the columns have all 9 numbers, the rows are unchanged) * swap any 2 rows in the middle 3 rows * and of course swap 2 rows in the bottom 3 rows. Each of these 3 operations can be done in 6 different ways (choice of 3 first rows, 2 second = 3*2). So the 3 operations can be done in 216 (6^3) ways. The 3 big rows of 3 can also be placed in any order (top/mid/bottom; top/bottom/mid; mid/top/bottom; .... another 6 ways). Thus there are 6*216=1296 different puzzles just by swapping the rows of numbers. You can do the same operations with columns (swap any 2 columns in each group of 3), and sort left/right/middle column groups. Giving 1296 permutations of the columns times 1296 permutations of the rows - over 1 million topologically identical puzzles. I haven't included the option of changing all the 1s to 2s and 2s to 1s (9! further operations, possibly 362880 million puzzles) since I suspect we will be double counting some of the puzzles. So the compilers of puzzles only need 1 original puzzle and can spend the rest of their days (4600 years including leap days) regurgitating the same puzzle just passing it through a random swapping sieve. ---- For comparison: Christian Neukirchen's solver in Prolog: [http://chneukirchen.org/blog/#x-20051117-160643] and [http://chneukirchen.org/repos/blogcode/sudoku.pl]. ---- [[ [Category Games] ]]