Solving the Sudoku puzzle by logic only

Up: Puzzle solving by computer  
Prev: The hexiamond puzzle  

This page describes how to solve a Sudoku puzzle. It's a puzzle in a 9x9 grid where each number (from 1 to 9) has to appear exactly once in each row, column and exactly once in each of the nine 3x3 squares. If you've never heard of it, search the web, there are plenty of examples.

It's an intriguing puzzle because it can seem at once very simple and very, very difficult. I wrote a solution finder that simply tried each number in each position but that takes forever. I didn't let it finish, I have a sneaking suspicion it's end-of-the-universe type stuff.

The solution

So, my final solution ended up being a bit smarter. It employs three kinds of tricks:
  1. Firstly, it goes though each cell and determines if there is only one possible number that can be placed there. This is the simplest and most simple puzzles found in newspapers can be solved with this method alone. It just takes a bit of time, although it's trivial for a computer.
  2. Secondly, it checks each cell to see if there is a number possible there that is not possible in any other cell in the row, column or box. This is a slightly more sophisticated method although you can apply it very easily when you're looking at the grid yourself. It gets you out of stuck spots where the first method can't proceed.
  3. Thirdly, it tries the method known as locked candidates. It's the technique where if a number in any row or column is only present in a single box, you can exclude it from the rest of the box. The site given has abetter explanation.
  4. The final method is one that simply count the number of distinct number in a group of cells and if that number is the same as the number of cells you've made a subgroup, This restricts the contens of other cells and may lead to a solution.
The program basically keeps applying the first method until it stops working. It then applies the second method and tries the first again. It only tries the later methods if the earlier ones don't make progress. The solver never guesses though it could easily be made to do so. If it can't sole it it shows you where it got upto and stops. Usually I can't solve the resulting grid either which means I can't really fix it either.

The implementation

The grid is stored as a two dimensional array. The cells are referenced by Row and Col numbers from 1 to 9. The cell either contains a number or is unbound (represented by '_' in Prolog). The important basic predicates are: After seeing the above basic predicates you can see how the solving might proceed. Note, the built-in findall/3 predicate is used a lot to find all possible solutions.

Discovered values are stored in the form of [Row,Col,Value]. If in an intermediate stage with multiple possible values, we use [Row,Col,[Values]]. The predicate assign/3 applies the found results to the grid. It fails if there is nothing to apply, so each individual step doesn't need to explicitly check if it didn't find anything.

If none of the above work we've either solved the puzzle or got stuck. In either case, print the result and stop.

Speed

Basically, it solves the puzzle quicker than you can type it in. The problems in the file I've put in the predicate problem/2 so you basically say:
   > problem(1,X), solve(X).
This will solve the first puzzle in the file. I defined 7. Ideally it should read from a file but I havn't done that yet.

It prints out each step along the way along with which each type of method it used. You could turn this off if you want. It's probably fast enough to create a puzzle setter. solve/2 will fail outright if the puzzle is inconsistent and return an incomplete grid if there is not enough information. You could score the different methods of solving to try and make harder-to-solve puzzles.

Download: sudoku3.plg


Up: Puzzle solving by computer  
Prev: The hexiamond puzzle  
By Martijn van Oosterhout (kleptog (at) svana.org)
Copyright © 2000-2006 - Last modified 3/04/2006