Dancing Links Sudoku is Java and open source

Pete

I've just released my implementation of Knuth's Algorithm X (Dancing Links) under the name Dancing Links Sudoku.

It's a sudoku generator and solver. It also uses the same code to solve pentomino puzzles. (Only the node generation is specific to each kind of puzzle).

I'm calling it a beta release. It's in Java, so it's platform independent. It's been tested under Windows XP, Vista, and Linux. You can run the sudoku generator and solver on the Web at http://www.jfasttrack.com/demos/sudoku/

You can also download it and run sudoku and pentominoes as applications. To do this, you will also need the Java Runtime Environment (available at http://java.sun.com/javase/downloads/index.jsp).

It can be downloaded from SourceForge: http://sourceforge.net/projects/dancinglinks/ It's all available under the GPL.

This is a first (beta) release, so I have just the basic features:
. Basic GUI
. Dancing Links sudoku generator
. Dancing Links solvers for sudoku and pentominoes
. Sudoku solvers:
. . Naked single
. . Hidden single
. . Intersections
. . Naked pairs
. Hints for each solver
. Undo and redo

tech_cheetah · Posted: Sun Oct 12, 2008 9:48 am Post subject:

Great Job

Pete · Posted: Tue Nov 11, 2008 12:15 am Post subject:

I've just put up a new release. The links to run and download the program are the same as in my previous post in this thread.

For the users:
* Naked subsets have been finished. Naked triplets and naked quads are now supported.
* Hidden subsets (pairs, triplets, and quads) have been implemented.
* The fish family of solvers has been started with the addition of X wings.
* A GUI has been added to the pentomino solver. It can now be run as either an applet or an application.
* Duplicate solutions (caused by rotation/inversion of the entire grid) have been removed from the pentomino solver.

For the programmers:
* Node creation for sudoku puzzles has been moved out of the solver class and into the houses. (This was a "to do" item listed in the source code of the first release.) This will make it much easier to provide additional houses (for example, diagonals or windoku). It will also help the program accommodate different kinds of constraints (for example, sum cages for killer sudoku).
* Some of the existing code (e.g., menus) has been refactored.

tech_cheetah · Posted: Sun Feb 15, 2009 5:22 am Post subject:

thats cool

onthink · Posted: Sun Mar 29, 2009 12:35 pm Post subject:

that 's nice

Pete · Posted: Sun May 31, 2009 10:36 pm Post subject:

My third release of this program is now up. Here's what I've done:

* The program now has the timer that a couple of users requested. It's down in the lower-right corner of the program window. It pauses when the user leaves the program page (applet) or when the program window is minimized (application). It can be turned on and off using the Options menu.
* The program can now create sudoku of different sizes, from 4x4 up to 16x16.
* The notes for the second release (November, 2008) said that node generation was moved out of the DLX solver and into the houses. The program can now generate sudoku with irregular houses (e. g., jigsaw) and additional houses (e. g., diagonals.) No, the jigsaw generator does not use DLX.
* The File menu has a new option for generating sudoku. The F2 menu item generates sudoku using the most recently selected options. The F3 menu item opens a dialog that lets users select the grid size, the block type, and whether diagonals are used.
* The original design for the sudoku generator created a new DLX solver for each iteration. That was fine for 9x9 grids, but proved to be just too slow for the larger sizes. Some time was spent optimizing the DLX code. The main improvement was reuse of the same DLX solver throughout each phase of generation.
* The solving menu is now better organized, with solvers grouped by type.
* The selections in the highlight bar have been limited. Users can now select only those values that appear as candidates in unsolved cells.
* There is a new solver for the rest of the fish family (swordfish, jellyfish, and squirmbags).
* There is a new solver for the law of leftovers.
* The X-wing solver has been completely rewritten. It now allows for X-wings to use cells that are on the diagonals, as well as rows and columns.
* Added the code needed for this program to run on a Mac.

You can run it on the Web at http://www.jfasttrack.com/demos/sudoku/

It's all available for download from SourceForge: http://sourceforge.net/projects/dancinglinks/ under the GPL.