Sudoku Solvers
The sudokubundle and lasudoku styles are ways to have some fun with LaTeX, and at the same time learn more about how packages are used and developed. Both packages were created based on a challenge in an early issue of The PracTeX Journal. sudokubundle was created by Peter Wilson of Herries Press, and lasudoku was written by Zachary Catlin of Purdue University. We will show how to use these packages to print a sudoku puzzle, and solve it. These packages use LaTeX only, with no help from outside programs or scripts.
In the 2005-4 issue of The PracTeX Journal the editors issued a challenge to create a TeX-based sudoku solver. You can see the challenge and some background on sudokus at http://tug.org/pracjourn/2005-4/distract/#sudoku. There were three contest levels, and the expert level asked for a TeX-based document that would read a sudoku puzzle file, format it, and then solve it. There were two contest entrants who sent working LaTeX-based solvers, Peter Wilson and Zachary Catlin. You can review their submissions at http://tug.org/pracjourn/2006-1/distract/sudoku_winners/answers.html.
The solvers introduce two commands, \sudoku and \sudokusolve. Each command accepts an argument, the name of a sudoku position file, and then prints and solves it. Zachary Catlin's solver is a LaTeX package called lasudoku. Peter Wilson's original submission was a LaTeX document that contained the sudoku printing and solving algorithms, but was not organized as a package. Later he developed this into a full package, and added a third utility to generate new puzzles. If you are interested in how a set of tools is eventually organized into a package, look at Peter's first effort and compare it with the eventual sudokubundle package.
In this article we will be using Peter Wilson's sudokubundle package, which was contributed to the TeX Archive (CTAN) and is part of the TeX Live distribution. Similar results can be had by using Zachary Catlin's lasudoku package. You may want to try both solvers and compare results. Keep in mind that they are able to solve a large number of easy and medium difficulty puzzles, but may not be able to solve all puzzles.
Download the sample files Unzip this file into a directory. Format sudokubundleTest.tex or lasudokuTest.tex with LaTeX to see how the packages work.
The starting position
To test these packages, find a sudoku puzzle to print or solve. Look for puzzles in your local newspaper or go to an online sudoku site, for example http://www.sudokusolver.co.uk. Here is a sample puzzle we will use in this article:
In order to print or solve a puzzle, it must be in a form that sudokubundle can use. One way to do this is to create a simple text file with the starting position.
64..139.. 1...264.. .29.457.. ..2...83. 86..37.19 7..2.9... ..13..69. 9364.8.2. ..5...... Easy sample sudoku from http://www.sudokusolver.co.uk
There are nine characters per line and nine lines, corresponding to the 9x9 sudoku grid. The numbers 1-9 are filled-in squares, and a period represents a blank square. After the ninth line you can add anything you want.
Write this text to a file. For this article we have created the file SudokuSolverSample.sud, which you can find in the sample files at the top of this article.
(There is another way to enter starting positions into the sudokubundle package. See the package documentation for this method, and for complete package information.)
Printing a puzzle
This requires just one command: \sudoku{SudokuSolverSample.sud}. The argument for this command, SudokuSolverSample.sud, is the file we made in the previous section. Here is a sample LaTeX document you can use to print a sudoku:
% Test the sudokubundle package
\documentclass{article}
\usepackage{createsudoku}
\begin{document}
\begin{center}
\sudoku{SudokuSolverSample.sud} % Print a puzzle
\end{center}
\end{document}
Format this document with LaTeX and it will print a puzzle position like this:
Solving a sudoku
This requires just one command: \sudokusolve{SudokuSolverSample.sud}. The argument for this command, SudokuSolverSample.sud, is the file we made in the first section. In the example LaTeX document above, substitute the following line for \sudoku{SudokuSolverSample.sud}.
\sudokusolve{SudokuSolverSample.sud} % Solve a puzzle
Run this document through LaTeX and it will print the puzzle as above followed by the solution:
For those who want to dissect the package, a good place to start is by examining the .log file, where the package writes notes as it solves puzzles.
Creating a sudoku
The sudokubundle package can generate a new puzzle from a solved puzzle. The command to do this is \generategrid[SudokuSolverSampleSolution.sud]. Note that the file name is optional and is in square brackets. The file is a sudoku position that was created the same way as in the first section, except that this file must be a valid solution position. You can type the position into a text file and save it.
However, there is another way to create a new puzzle without typing a solution file. Let the package solve a puzzle, and then let it create a new puzzle from this solved puzzle. (It writes the solution to a default solution file, sud.out, and then uses this position file.) Use the following sample LaTeX document to create a new puzzle:
% Test the sudokubundle package
\documentclass{article}
\usepackage{createsudoku}
\begin{document}
\begin{center}
\sudokusolve{SudokuSolverSample.sud} % Solve a puzzle
\generategrid % Use this solution to generate a new puzzle
\end{center}
\end{document}
Surprising that LaTeX can solve a sudoku
When the original suduko challenge was proposed, one of the editors wrote that he didn't think anyone would submit a solution. At first glance, it didn't even seem possible to write a TeX or LaTeX document that could do something that complex. But, in fact, TeX (LaTeX) is Turing complete which means it can solve any problem that other computing devices can solve. However, TeX isn't always the best tool to use to solve complex problems --- for specialized problems there are usually better tools. In any case, it's nice to know that the problem-solving power is there if you need it!