Sudoku Solving
Three Algorithms for Solving Sudoku Puzzles.
I've applied these algorithms to sudoku's with letters as well as digits, and to layouts of 16x16 and 25x25 as well as the usual 9x9 layout.
Algorithm B
A simple algorithm to program is "brute force" which we will call "Algorithm B". We simply try every legal way of filling in the empty cells in the puzzle. Even written in a slow language like python, a brute force program will solve the usual 9x9 sudoku's, such as those you see in daily newspapers, in a reasonably short time.
The only subroutine you need for Algorithm B is one that computes all the legal ways of filling in an empty cell. Given an empty cell, you start with the list of all symbols (letters or digits) that appear in the sudoku. Then you delete from the list all the symbols in the same row as the given cell, then delete all symbols in the same column as the given cell, and then delete all the symbols in the same subblock as the given cell. The remaining symbols in the list are the legal ways of filling in the cell.
In a little more detail, the puzzle is represented as a two dimensional array filled with letters or digits and a sign for 'empty cell'. I usually use a dash (-) to stand for empty cell. If an empty cell has coordinates (x,y) in the two dimensional array, then the symbols in the same row consist of those with the same first coordinate 'x' as the empty cell, and the symbols in the same column consist of those with the same second coordinate 'y'as the empty cell. To find the symbols in the same subblock as the empty cell, you start by getting the coordinates of the upper left corner of the subblock containing the empty cell. In the case of a 9x9 sudoku, each subblock is 3x3. Therefore the first coordinate of the left corner is x minus the remainder of x divided by 3, and the second coordinate is y minus the remainder of y divided by 3. For example if the empty cell had coordinates (5,8) then the upper left corner of its subblock would have coordinates ( 5-(5 MOD 3), 8 - (8 MOD 3)) or (3,6). Note: we assume the array coordinates go from 0 to 8 in both the first and second coordinate indices. To get the symbols in the same block as the empty cell (5,8) you check all cells with coordinates equal to those of the upper left corner (3,6) plus 0,1 or 2 in either coordinate index.
Given the subroutine for finding all legal possibilities for filling in an empty cell, you step through each cell in the puzzle, filling in each empty cell with every legal possibility, and recording all the layouts that can be completely filled in. A straight-forward way to program this is to use a recursive function, that is a function that calls itself. Here is the pseudo-code for such a function, which we'll call "Fill-In". Fill-In takes a given cell in the puzzle as its input variable and if the cell is empty, loops through all possible legal ways to fill it in, calling itself in the middle of the loop with the next cell in the puzzle as the new input variable.
Fill_In( cell ):
IF cell is the final cell in the puzzle THEN:
IF cell is already filled in THEN the puzzle is solved
display the filled in sudoku
RETURN
ELSE call the subroutine to get legal ways of filling in cell (there should be at most one!)
IF no way to fill it in THEN RETURN
ELSE fill in cell
display the solution
reset cell to empty in case there are other solutions
RETURN
ELSE not final cell:
IF cell already filled in THEN
call Fill_in( next cell)
RETURN
ELSE call the routine that returns the legal ways of filling in cell
IF no way to fill in cell THEN RETURN
ELSE:
FOR each legal way 'w' to fill in cell:
fill in cell with 'w'
call Fill_In( next cell)
END FOR
reset cell to empty
RETURN
When the program starts, it calls Fill_In with the first cell in the puzzle as the input variable. When Fill_In returns from this call it will have displayed all solutions to the puzzle. If the puzzle was constructed correctly, there should be only one solution to display.
Given enough time Algorithm B will solve any sudoku. Unfortunately, there is not always enough time. Algorithm B works well for 9x9 sudoku puzzles with only one (or just a few) solutions, but it's not fast enough for most 16x16 or 25x25 puzzles. And of course, the results will not be good if you try Algorithm B on a 9x9 layout consisting of nothing but empty cells!
Algorithm F
Algorithm F, where "F" stands for "forced fill-in", is plenty fast, but it's not guaranteed to solve a sudoku puzzle even if the puzzle has only one solution. Algorithm F resembles the method by which many people solve sudoku's with pencil and paper. Algorithm F consists of scanning through the empty cells in the puzzle, filling in those that you can see have only one possibility. It may be that the subroutine constructed in Algorithm B that returns a list of all legal ways to fill in an empty cell only returns one symbol. It also may happen that there are several symbols on the list, but one of them does not appear on any other lists for the empty cells in the same row; or one of them does not appear in any other lists for the empty cells in the same column; or one of them does not appear in any other lists for the empty cells in the same subblock. Every time the program encounters an empty cell with only one possibility, it fills in that possibility and at the same time sets a flag that signals that it needs to scan through the empty cells at least one more time. Any cell that has been filled in may have set up more empty cells for filling in on the next scan.
Here's the pseudo code for Algorithm F:
set "redo flag" to 1
WHILE redo_flag is 1:
set redo_flag to 0
FOR EACH empty cell C in the puzzle:
call the subroutine that gets legal ways of filling in C.
IF no legal way to fill in C THEN current layout can't be solved. RETURN
IF just one way to fill in C THEN
fill in C
set redo_flag to 1
ELSE there is more than one legal way to fill in C
FOR EACH way 'w' of filling in C
get all legal ways of filling in the other empty cells in the ROW containing C
IF 'w' is not in any of these lists THEN:
fill in C with 'w'
set redo_flag to 1
EXIT ELSE (get next empty cell C)
get all legal ways of filling in the other empty cells in COLUMN containing C
IF 'w' is not in any of these lists THEN:
fill in C with 'w'
set redo_flag to 1
EXIT ELSE (get next empty cell C)
get all legal ways of filling in the other empty cells in SUBBLOCK containing C
IF 'w' is not in any of these lists THEN:
fill in C with 'w'
set redo_flag to 1
EXIT ELSE (get next empty cell C)
END FOR
END ELSE
END FOR
END WHILE
RETURN
Algorithm F sometimes solves even 25x25 layouts quickly, but it's not guaranteed to work. For example here is a 9x9 layout that has just one solution:
--A --- --W
--E O-- --L
--- --A E--
-O- --- ---
-ST E-- --M
--L --- N--
L-- --- --A
-N- --W M--
--O N-- LSE
Algorithm B, written in a slow language like python, will solve this in about three minutes even on a slow computer. But when we try Algorithm F we get (Note: rows and columns labeled 1 -9 instead of 0-8):
add N to row 3 column 9 extends column
add N to row 4 column 3 extends column
add N to row 7 column 8 extends column
add S to row 8 column 3 only legal possibility
add W to row 7 column 7 extends subblock
add W to row 3 column 3 extends column
add M to row 7 column 3 only legal possibility
add W to row 2 column 5 extends row
Forced filling gives:
- - A - - - - - W
- - E O W - - - L
- - W - - A E - N
- O N - - - - - -
- S T E - - - - M
- - L - - - N - -
L - M - - - W N A
- N S - - W M - -
- - O N - - L S E
But now Algorithm F is stuck.
Algorithm C
Algorithm B always gets the solution, but is too slow. Algorithm F is fast, but it doesn't always get the solution. We can try for the best of both worlds by combining algorithms B and F to get Algorithm C, ("C" stands for combined!)
In Algorithm C, we first apply Algorithm F to quickly fill in as much as possible. Then we call a modified "Fill-In" recursive function like that in Algorithm B. The modification consists of inserting a call to Algorithm F into the loop where we try every legal possibility for an empty cell. Since Algorithm F may fill in many empty cells ( and even get a complete solution!) we must save the current layout before we enter the loop. Each time the function returns to the loop we restore the saved layout before filling the empty cell with the next legal possibility. Here's the pseudo_code with the new lines indicated with asterisks.
Fill_In( cell ):
IF cell is the final cell in the puzzle THEN:
IF cell is already filled in THEN the puzzle is solved
display the filled in sudoku
RETURN
ELSE call the subroutine to get legal ways of filling in cell (there should be at most one!)
IF no way to fill it in THEN RETURN
ELSE fill in cell
display the solution
reset cell to empty in case there are other solutions
RETURN
ELSE not final cell:
IF cell already filled in THEN
call Fill_in( next cell)
RETURN
ELSE call the routine that returns the legal ways of filling in cell
IF no way to fill in cell THEN RETURN
ELSE:
save current layout *************************** (new line)
FOR each legal way 'w' to fill in cell:
fill in cell with 'w'
call Algorithm F ************************** (new line)
call Fill_In( next cell)
restore saved layout ********************** (new line)
END FOR
reset cell to empty
RETURN
When Algorithm C starts, it calls Algorithm F, then calls Fill_In with the first cell in the puzzle as the input variable. When Fill_In returns from this call it will have displayed all solutions to the puzzle. If the puzzle was constructed correctly, there should be only one solution to display.
In the 9x9 sudoku example above, that Algorithm F could not solve and that Algorithm B took 3 minutes to solve with a python program, Algorithm C found a solution in 2 seconds with a python program.
Algorithm C seems to work well on larger sudoku puzzles also. I wrote a javascript version and tried it on a 25x25 sudoku (with letters instead of digits of course!). This 25x25 layout could not be solved by Algorithm F, but Algorithm C solved it in 3 seconds using the Safari web browser to run the javascript program.