SuDoku

by malcolm Mclean Homepage

Regular Sudoku (Windows Executable) Sudoku Icon

Killer Sudoku (Windows Executable) Killer Sukoku Icon

How to solve Sudoku

The game consists of a 9 x 9 grid of cells, which can contain a number from 1 - 9. A grid is acceptable is each row, each column, and each 3 x 3 cell contains all the digits 1 - 9. A few digits are given, and your task is to find the remaining ones.

The first stage is to contruct a list of "possibles" for each cell, and set them to the digits 1 - 9. Then we go to our given cells, and eliminate eight of the possibilities, setting them to a known value. The next stage is to go through the known cells, and eliminate that possibility from all other cells in the same row, column, and 3 x 3 cell.

A simple puzzle can be solved simply be repeating this process until all the cells are known. If the puzzle is harder, however, there may still some cells unknown at the end of the process. Therefore we have to take a guess, and repeat the elimination process. If some cells are still unknown, we quess again, and repeat until either the problem is solved, or some cells have zero possibilities. Zero possibilities indicate that our quess was wrong. Therefore we backtrack, guess the next number, and repeat, until either the problem is solved or it is known to be impossible.

The alogrithm is thus recursive.

Here is the important file
dosudoku.c

How to solve Killer Sudoku

The Killer Sudoku problem is the same as the Sudoku problem, in that the grid is 9 x 9 and all rows, colums, and 3 X 3 cells must contain all the digits 1-9. However instead of being given known cells, the Killer Sudoku problem gives you a series of boxes, with the sum of digits in each box. There is a bit of a dispute about digits are allowed to be repeated within boxes - The Times seems to think no.

The problem is much harder to solve than the Sudoku problem. With some boxes we know the combinations - if a box of three adds up to six then the numbers can only be 1,2,3, assuming the no repeats rule. If we allow repeats then it could also be 1, 1, 4. However for most boxes, there are quite a few combinations. Two boxes adding up to seven could be 1, 6; 2, 5; or 3, 4.

The first step therefore is to write a function that takes the number of cells and the box total, and lists all the possible combinations.

Then we proceed in the same manner as the regular Sudoku, making a list of allowed digits for each cell. If a digit does not appear in the list of combinations allowed for the box the cell belongs to, it is not a possibility.

As before, we can then eliminate recursively. If a cell is known, no others in the same row, column, or 3 x 3 can have the same digit. However we also have some extra contraints. If a cell is known, no cell in the same box can have that digit. Also, no box combination is allowed that does not contain that digit. Therefore if three cells add up to 15, allowed combinations are

1, 5, 9
1, 6, 8
2, 4, 9
2, 5, 8
2, 6, 7
3, 4, 8
3, 5, 7
4, 5, 6

If we know that that one digit is a one, that restricts us to the first two of these possibilities.

If a box is confined to one row, column, or 3 x 3 cell, and we know for certian that a digit is in that box, this allows us to eliminate that digit as possibles for all members of the row, column of 3 x 3 cell not in that box.

If no solution is found after eliminating all possibilites is necessary to proceed recursuvely, as before.

Here are the important files
killersudoku.c
getcombinations.c