Solving Sudoku using APL

Contents

Solving Sudoku using APL

In the following article we'll develop an APL program to solve Sudoku puzzles. Along the way we'll see some of APL's greatest strengths:

APL is interactive, meaning that you can develop solutions in easy incremental stages. It's the perfect language for starting with something simple and then building it up slowly.
APL is an array language with a rich vocabulary of built-in functions and operators. We can spend more time thinking about the solution, and spend less time on the 'plumbing' compared to non-array languages.
APL is expressive and concise. Not counting comments, the entire Sudoku solution is only about 60 lines of APL code, easily understood by an experienced APL programmer.

New to APL?

If you are new to APL don't worry if you don't understand every intricacy of the APL code presented here. Instead it's hoped that you'll be able to follow the general outline and form an impression of APL's power.

If you are familiar with a conventional language like C# or Java you should be struck by how APL can perform operations on whole arrays at once. You'll also appreciate the interactive nature of APL which allows you to try out ideas rapidly - no project setup, no compile-link-debug cycles!

There's one thing you need to know before you get started: APL uses special symbols for many of its array operations, so you need to install a Unicode font which includes the APL character set before you can view any of the code on this Wiki.

The APL character set might seem off-putting for newcomers, but it's part of what makes APL so elegant. Think of it like learning to read music. At first the music notation is difficult to get used to, but once you know it you can write a symphony!

To verify that you have an APL font installed, check the following line of APL code:

      grids←4 4⍴⍋ ,2⌿2/2 2⍴⍳4

It should look similar to this screen shot:

If it looks much different to this then you don't have an APL font installed. See this page for details on how to obtain it.

Trying the code out

You may want to try the code out in an APL interpreter. It was developed using APLX but should work in any modern APL. You should note the following:

(a) The Index Origin needs to be set to 1:

      ⎕IO←1

(b) The explanation makes uses of the ⎕DISPLAY function to show the structure of arrays more clearly. This is specific to APLX, but other interpreters include something similar. See here for more information.

      ⎕IO←3

The Puzzle

As an example, let's start with the following 4 x 4 Sudoku puzzle. The algorithm for solving it is the same as for a 9 x 9 Sudoku, but the 4 x 4 puzzle will fit slightly better on the page. We'll adapt the solution to work for any N x N Sudoku as we progress.

+ - - +- - +
| 1 2 |. . |
| . 4 |. . |
+ - - +- - +
| 2 . |. . |
| . 1 |. 3 |
+ - - +- - +

We can type the puzzle directly into the APL session, usings 0s to represent blank squares. Here we type a list 1 2 0 etc, and reshape it into a 4 x 4 array:

      puzzle←4 4⍴1 2 0 0 0 4 0 0 2 0 0 0 0 1 0 3
      puzzle
1 2 0 0
0 4 0 0
2 0 0 0
0 1 0 3

Getting Started

We might start by thinking just about the first blank in the first row. What values could it take?

In the absence of any other information, it could be any of the numbers 1 - 4, which we'll store in the variable possibles:

      possibles←⍳4
      possibles
1 2 3 4

However, by the rules of Sudoku, no number can appear more than once in a row. We can remove the numbers which already appear in row 1 from the list of possibles:

     ⍝ List row 1 of puzzle
     row1←puzzle[1;]
     row1
1 2 0 0

      ⍝ Use APL's "without" function (~) to remove these numbers from possibles for blank square
      possibles←possibles~row1
      possibles
3 4

As this result shows, the first blank square in row 1 can take the number 3 or 4 : 1 and 2 are already used.

The Power of Arrays (Part 1)

Since APL is an array language we're not confined to thinking about each blank square one at a time. We can extend the method above to consider all the blank squares in row 1.

First let's create a list of initial possibilities for each square in row 1:

      possibles←4⍴⊂⍳4
      possibles
 1 2 3 4  1 2 3 4  1 2 3 4  1 2 3 4

This is a little clearer if we display it as follows. It's four copies of the numbers 1 2 3 4, the possible values for each of the four squares.

      ⎕display possibles
┌→────────────────────────────────────────┐
│ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │
│ │1 2 3 4│ │1 2 3 4│ │1 2 3 4│ │1 2 3 4│ │
│ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │
└∊────────────────────────────────────────┘

Now let's adopt the convention that the possibles variable only lists possibilities for squares which are still blank. For squares which are solved we'll set the entry in the possibles variable to be an empty list, represented by the APL symbol Zilde (⍬)

      ⍝ Which squares in row 1 already contain a number?      
      row1≠0
1 1 0 0
      ⍝ Set the corresponding 'possibles' entry to an empty list (⍬)
      ((row1≠0)/possibles)←⊂⍬

      possibles
     1 2 3 4  1 2 3 4

      ⎕display possibles
┌→────────────────────────────┐
│ ┌⊖┐ ┌⊖┐ ┌→──────┐ ┌→──────┐ │
│ │0│ │0│ │1 2 3 4│ │1 2 3 4│ │
│ └~┘ └~┘ └~──────┘ └~──────┘ │
└∊────────────────────────────┘

Now we can make 4 copies of row 1, and use the Without function (~) to remove one copy from each of the four sets of possibles. We use the APL Each operator (¨) to do this:

      possibles ← possibles ~ ¨ 4⍴⊂row1
      possibles
     3 4  3 4
      ⎕display possibles
┌→────────────────────┐
│ ┌⊖┐ ┌⊖┐ ┌→──┐ ┌→──┐ │
│ │0│ │0│ │3 4│ │3 4│ │
│ └~┘ └~┘ └~──┘ └~──┘ │
└∊────────────────────┘

Notice how this looks very like our original version possibles←possibles~row1, but now we're doing a whole row at a time.

The Power of Arrays (Part 2)

If you're wondering whether we need to work on the solution only one line at a time, you're ahead of me! Since APL is array-oriented we don't need to loop through the blank squares at all. We can do everything in one go with just three lines of APL code:

      possibles←4 4⍴⊂⍳4
      ((,puzzle≠0)/,possibles)←⊂⍬
      possibles←possibles~¨4/4 1⍴⊂[2]puzzle

Isn't that elegant? Let's unpack it a little bit and look at the intermediate results:

       ⍝ Each square starts off with possible values 1 2 3 4     
      possibles←4 4⍴⊂⍳4
      ⎕display possibles
┌→────────────────────────────────────────┐
↓ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │
│ │1 2 3 4│ │1 2 3 4│ │1 2 3 4│ │1 2 3 4│ │
│ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │
│ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │
│ │1 2 3 4│ │1 2 3 4│ │1 2 3 4│ │1 2 3 4│ │
│ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │
│ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │
│ │1 2 3 4│ │1 2 3 4│ │1 2 3 4│ │1 2 3 4│ │
│ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │
│ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │
│ │1 2 3 4│ │1 2 3 4│ │1 2 3 4│ │1 2 3 4│ │
│ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │
└∊────────────────────────────────────────┘

      ⍝ For squares which are already known, set list of possibles to empty
      ((,puzzle≠0)/,possibles)←⊂⍬
      ⎕display possibles
┌→────────────────────────────────────────┐
↓ ┌⊖┐       ┌⊖┐       ┌→──────┐ ┌→──────┐ │
│ │0│       │0│       │1 2 3 4│ │1 2 3 4│ │
│ └~┘       └~┘       └~──────┘ └~──────┘ │
│ ┌→──────┐ ┌⊖┐       ┌→──────┐ ┌→──────┐ │
│ │1 2 3 4│ │0│       │1 2 3 4│ │1 2 3 4│ │
│ └~──────┘ └~┘       └~──────┘ └~──────┘ │
│ ┌⊖┐       ┌→──────┐ ┌→──────┐ ┌→──────┐ │
│ │0│       │1 2 3 4│ │1 2 3 4│ │1 2 3 4│ │
│ └~┘       └~──────┘ └~──────┘ └~──────┘ │
│ ┌→──────┐ ┌⊖┐       ┌→──────┐ ┌⊖┐       │
│ │1 2 3 4│ │0│       │1 2 3 4│ │0│       │
│ └~──────┘ └~┘       └~──────┘ └~┘       │
└∊────────────────────────────────────────┘


      ⍝ The expression 4/4 1⍴⊂[2]puzzle gives four copies of each row of the puzzle:
      ⎕display 4/4 1⍴⊂[2]puzzle
┌→────────────────────────────────────────┐
↓ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │
│ │1 2 0 0│ │1 2 0 0│ │1 2 0 0│ │1 2 0 0│ │
│ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │
│ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │
│ │0 4 0 0│ │0 4 0 0│ │0 4 0 0│ │0 4 0 0│ │
│ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │
│ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │
│ │2 0 0 0│ │2 0 0 0│ │2 0 0 0│ │2 0 0 0│ │
│ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │
│ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │
│ │0 1 0 3│ │0 1 0 3│ │0 1 0 3│ │0 1 0 3│ │
│ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │
└∊────────────────────────────────────────┘


      ⍝ We can use this to simplify our 'possibles' array, eliminating numbers 
      ⍝ already used along each row
      possibles←possibles~¨4/4 1⍴⊂[2]puzzle
      ⎕display possibles
┌→────────────────────────────────┐
↓ ┌⊖┐     ┌⊖┐     ┌→──┐   ┌→──┐   │
│ │0│     │0│     │3 4│   │3 4│   │
│ └~┘     └~┘     └~──┘   └~──┘   │
│ ┌→────┐ ┌⊖┐     ┌→────┐ ┌→────┐ │
│ │1 2 3│ │0│     │1 2 3│ │1 2 3│ │
│ └~────┘ └~┘     └~────┘ └~────┘ │
│ ┌⊖┐     ┌→────┐ ┌→────┐ ┌→────┐ │
│ │0│     │1 3 4│ │1 3 4│ │1 3 4│ │
│ └~┘     └~────┘ └~────┘ └~────┘ │
│ ┌→──┐   ┌⊖┐     ┌→──┐   ┌⊖┐     │
│ │2 4│   │0│     │2 4│   │0│     │
│ └~──┘   └~┘     └~──┘   └~┘     │
└∊────────────────────────────────┘

Again, notice how the expression possibles←possibles~¨4/4 1⍴⊂[2]puzzle looks very like our original version possibles←possibles~row1, but now we're doing all the squares in the Sudoku puzzle in one hit!

Considering Columns

So far we have worked on the Sudoku puzzle by considering which numbers already appear in each row of the solution.

Now we can perform the same trick for the columns of the puzzle. A number cannot appear more than once in a column, so we can reduce the possibilities further.

An easy way to do this is to make use of the APL function called Transpose (or more colloquially 'flip'), which has the symbol ⍉. This will swap the rows and columns of a matrix:

By using flip we can swap over the rows and columns in the Sudoku puzzle and in the list of possible values for each square. We can then use our 'row' method to reduce the possibles, and finally flip back:

       ⍝ Flip puzzle and possibles
      tpuzz←⍉puzzle                                         
      tposs←⍉possibles  

      ⍝ No number can appear more than once in a row                                   
      tposs←tposs~¨4/4 1⍴⊂[2]tpuzz   

      ⍝ Flip back          
      possibles←⍉tposs                                     
      ⎕display possibles
┌→──────────────────────┐
↓ ┌⊖┐ ┌⊖┐ ┌→──┐   ┌→┐   │
│ │0│ │0│ │3 4│   │4│   │
│ └~┘ └~┘ └~──┘   └~┘   │
│ ┌→┐ ┌⊖┐ ┌→────┐ ┌→──┐ │
│ │3│ │0│ │1 2 3│ │1 2│ │
│ └~┘ └~┘ └~────┘ └~──┘ │
│ ┌⊖┐ ┌→┐ ┌→────┐ ┌→──┐ │
│ │0│ │3│ │1 3 4│ │1 4│ │
│ └~┘ └~┘ └~────┘ └~──┘ │
│ ┌→┐ ┌⊖┐ ┌→──┐   ┌⊖┐   │
│ │4│ │0│ │2 4│   │0│   │
│ └~┘ └~┘ └~──┘   └~┘   │
└∊──────────────────────┘

Considering the Sub Grids

The final rule in Sudoku is that no number can appear more than once in any of the sub grids. As a reminder, here's the original puzzle with the 2x2 sub grids shown:

+ - - +- - +
| 1 2 |. . |
| . 4 |. . |
+ - - +- - +
| 2 . |. . |
| . 1 |. 3 |
+ - - +- - +

You probably already have an idea of what we'd like to do next. To do the columns we rearranged the puzzle so that the columns became rows, and hence re-used our solving algorithm. Can we use the same trick again?

In other words, if we were to number all the squares like this:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

...then we want a transform that will arrange them like this, where each sub grid forms one row of the result:

 1  2  5  6
 3  4  7  8
 9 10 13 14
11 12 15 16

...which we can then use as follows:

       ⍝ Transform puzzle and possibles
      tpuzz←Transform puzzle                                         
      tposs←Transform possibles  

      ⍝ No number can appear more than once in a row                                   
      tposs←tposs~¨4/4 1⍴⊂[2]tpuzz   

      ⍝ Transform back          
      possibles←InverseTransform tposs 

      ⎕display possibles
┌→──────────────────────┐
↓ ┌⊖┐ ┌⊖┐ ┌→──┐   ┌→┐   │
│ │0│ │0│ │3 4│   │4│   │
│ └~┘ └~┘ └~──┘   └~┘   │
│ ┌→┐ ┌⊖┐ ┌→────┐ ┌→──┐ │
│ │3│ │0│ │1 2 3│ │1 2│ │
│ └~┘ └~┘ └~────┘ └~──┘ │
│ ┌⊖┐ ┌→┐ ┌→──┐   ┌→──┐ │
│ │0│ │3│ │1 4│   │1 4│ │
│ └~┘ └~┘ └~──┘   └~──┘ │
│ ┌→┐ ┌⊖┐ ┌→──┐   ┌⊖┐   │
│ │4│ │0│ │2 4│   │0│   │
│ └~┘ └~┘ └~──┘   └~┘   │
└∊──────────────────────┘

How can we write such a transform? Here's one way:

      ⍝ Generate a grid of index positions
      grids←4 4⍴1 2 5 6 3 4 7 8 9 10 13 14 11 12 15 16
      grids
 1  2  5  6
 3  4  7  8
 9 10 13 14
11 12 15 16

      ⍝ Transform so each sub grid of puzzle forms one row of tpuzz
      tpuzz←(,puzzle)[grids]

      ⍝ Reminder: Here's the original puzzle
      puzzle
1 2 0 0
0 4 0 0
2 0 0 0
0 1 0 3

      ⍝ And here's what it looks like after our transformation
      tpuzz
1 2 0 4
0 0 0 0
2 0 0 1
0 0 0 3

How about the inverse transformation, which will convert tpuzz back into puzzle ? A little thought shows us that we don't need to write one - our transform is self-inverse!

Having got an idea of what we want to do, can we tidy the transformation up a bit? That line grids←4 4⍴1 2 5 6 3 4 7 8 9 10 13 14 11 12 15 16 won't generalise to 3 x 3 or N x N grids. How can we generate the index numbers?

Consider this array in which each square is numbered with its sub grid number:

If we turn this into a simple list and then make use of APL's Sort function (⍋) we get the answer we want:

      ,2⌿2/2 2⍴⍳4
1 1 2 2 1 1 2 2 3 3 4 4 3 3 4 4

     ⍋ ,2⌿2/2 2⍴⍳4
1 2 5 6 3 4 7 8 9 10 13 14 11 12 15 16

This works because Sort returns the index positions of the numbers when sorted into ascending order. (The first 1 comes first, the second 1 comes second, the first 2 comes fifth, etc).

Thus we can write the following expression for our 4 x 4 Sudoku puzzle. It's easily generalised to N x N:

      grids←4 4⍴⍋ ,2⌿2/2 2⍴⍳4
      grids
 1  2  5  6
 3  4  7  8
 9 10 13 14
11 12 15 16

Filling in known squares

So far we've managed to reduce the possible values which can go in each blank square. Currently we have:

      ⎕display possibles
┌→──────────────────────┐
↓ ┌⊖┐ ┌⊖┐ ┌→──┐   ┌→┐   │
│ │0│ │0│ │3 4│   │4│   │
│ └~┘ └~┘ └~──┘   └~┘   │
│ ┌→┐ ┌⊖┐ ┌→────┐ ┌→──┐ │
│ │3│ │0│ │1 2 3│ │1 2│ │
│ └~┘ └~┘ └~────┘ └~──┘ │
│ ┌⊖┐ ┌→┐ ┌→──┐   ┌→──┐ │
│ │0│ │3│ │1 4│   │1 4│ │
│ └~┘ └~┘ └~──┘   └~──┘ │
│ ┌→┐ ┌⊖┐ ┌→──┐   ┌⊖┐   │
│ │4│ │0│ │2 4│   │0│   │
│ └~┘ └~┘ └~──┘   └~┘   │
└∊──────────────────────┘

Notice that for some squares only one possibility remains. For example the top right square must contain the number 4. We're now ready to insert a 4 into the puzzle array.

First we want to find out which squares only have one remaining possibility. These squares will have a list of possibles that's only 1 item long:

      ⍝ How many possibilities remain for each square?
      ⍴¨possibles
 0  0  2  1
 1  0  3  2
 0  1  2  2
 1  0  2  0

      ⍝ Which squares only have one possibility?
      ⍝  (The ↑¨ turns an array of lists into a flat array of numbers)
      solved ← 1=↑¨⍴¨possibles
      solved
0 0 0 1
1 0 0 0
0 1 0 0
1 0 0 0

We can use this information to insert the corresponding numbers into the puzzle:

       ⍝ Reminder: Here's the original puzzle
      puzzle
1 2 0 0
0 4 0 0
2 0 0 0
0 1 0 3

      ⍝ Form a mask to control the insertion of numbers
      mask←∊ solved
      mask
0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0

      ⍝ In they go     
      (mask/,puzzle)←∊ mask/,possibles

      ⍝ Here's the updated puzzle 
      puzzle
1 2 0 4
3 4 0 0
2 3 0 0
4 1 0 3

We must also update our list of possible values to remove the squares which are now solved:

      (mask/,possibles)←⊂⍬

Time to write a function

It may surprise you to realise that we've come this far without actually writing a function ! So far we've just been typing expressions into the APL session window and noodling around, experimenting until we've got something useful. However, now that we've solved part of the puzzle we may be able to repeat the steps to solve more. Time for a function.

Let's write two user-defined functions. The first is a more general version of our Transform function above. We'll make it take a left argument which specifies the type of transform to apply. Here's a function listing

R←trans Transform matrix
:Select trans
:Case 1
  R←matrix
:Case 2
  R←⍉matrix
:Case 3
  R←(,matrix)[grids]
:EndSelect

Here's a demonstration of the Transform function in use:

      puzzle
1 2 0 0
0 4 0 0
2 0 0 0
0 1 0 3

      ⍝ Left argument of 1 doesn't do anything - i.e. it's the Identity transform
      1 Transform puzzle
1 2 0 0
0 4 0 0
2 0 0 0
0 1 0 3

      ⍝ Left argument of 2 transposes rows and columns
      2 Transform puzzle
1 0 2 0
2 4 0 1
0 0 0 0
0 0 0 3

      ⍝ Left argument of 3 lists sub-grids one per row
      3 Transform puzzle
1 2 0 4
0 0 0 0
2 0 0 1
0 0 0 3

The second function contains the skeleton of the actual Sudoku solving code, as far as we've developed it at the moment. It also adds some refinements:

An outer loop :Repeat ... :Until no_progress keeps repeating the solver until we can't determine any more squares
An inner loop :For trans in 1 2 3 tries each of the three transforms in order to look at the rows, columns, and sub grids.
Instead of hard-coding the dimensions of a 4x4 grid, the code has been generalised to handle N x N by introducing two variables: N is the length N of the side of the puzzle (4 in our examples above), and M is the length of the M x M sub-grid (2 in our examples)

R←SudokuSolver puzzle;N;M;grids;possibles;no_progress;trans;tpuzz;tposs;solved;mask

⍝ Get useful dimensions.
⍝ 'N' is the number of columns in the puzzle
⍝ 'M' is the number of columns in each sub grid
⍝
⍝ For example, for a 9 x 9 puzzle: N=9, M=3
N←↑⍴puzzle
M←⌊N*0.5


⍝ Precalculate the cell positions of each of the sub grids
⍝ Only need to do this once
grids←(N N)⍴⍋ ,M⌿M/(M M)⍴⍳N

⍝ Set up list of possible values for each cell
possibles←(N N)⍴⊂⍳N

⍝ For squares which are already known, set list of possibles to empty
((,puzzle≠0)/,possibles)←⊂⍬

:Repeat
  no_progress←1
  
  :For trans :In 1 2 3
    ⍝ Transform so each group of numbers forms a row
    tpuzz←trans Transform puzzle
    tposs←trans Transform possibles
    
    ⍝ If any number is already used in row, it can't be used again elsewhere
    tposs←tposs~¨N/(N 1)⍴⊂[2]tpuzz  

    ⍝ Transform back
    possibles←trans Transform tposs
  :EndFor
  
  ⍝ Found any squares which only have one remaining possibility?
  solved←1=↑¨⍴¨possibles

  :If 1 ∊ solved
    ⍝ Yes. Copy them in
    mask←∊solved
    (mask/,puzzle)←∊mask/,possibles
    (mask/,possibles)←⊂⍬ 
     
    ⍝ Go again from the start of the outer solving loop
    no_progress←0
  :EndIf
  
:Until no_progress

⍝ Return completed puzzle as result
⍝ (NB: May not be complete!)
R←puzzle

Trying the Sudoku Solver

Let's see how the Sudoku solver gets on with our first puzzle:

      puzzle←4 4⍴1 2 0 0 0 4 0 0 2 0 0 0 0 1 0 3
      puzzle
1 2 0 0
0 4 0 0
2 0 0 0
0 1 0 3
      SudokuSolver puzzle
1 2 3 4
3 4 1 2
2 3 4 1
4 1 2 3

Success ! However, before reaching for the champagne we should check some other examples. How about a 9 x 9 Sudoku?

      puzzle←5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0
      puzzle←puzzle, 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6
      puzzle←puzzle, 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9
      puzzle←9 9 ⍴ puzzle

      puzzle
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

      SudokuSolver puzzle
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

This also looks good, but how about this example:

      StarBurst←9 0 0 1 0 4 0 0 2 0 8 0 0 6 0 0 7 0 0 0 0 0 0 0 0 0 0
      StarBurst←StarBurst, 4 0 0 0 0 0 0 0 1 0 7 0 0 0 0 0 3 0 3 0 0 0 0 0 0 0 7
      StarBurst←StarBurst, 0 0 0 0 0 0 0 0 0 0 3 0 0 7 0 0 8 0 1 0 0 2 0 9 0 0 4
      StarBurst←9 9 ⍴ StarBurst

      StarBurst
9 0 0 1 0 4 0 0 2
0 8 0 0 6 0 0 7 0
0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 1
0 7 0 0 0 0 0 3 0
3 0 0 0 0 0 0 0 7
0 0 0 0 0 0 0 0 0
0 3 0 0 7 0 0 8 0
1 0 0 2 0 9 0 0 4

      SudokuSolver StarBurst
9 0 0 1 0 4 0 0 2
0 8 0 0 6 0 0 7 0
0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 1
0 7 0 0 0 0 0 3 0
3 0 0 0 0 0 0 0 7
0 0 0 0 0 0 0 0 0
0 3 0 0 7 0 0 8 0
1 0 0 2 0 9 0 0 4

Ooops! This solution still has some zeros in it. Clearly our Sudoku solver is not finished yet!

Every number must go somewhere

If we print out the final possibles array for the last example, we can spot how to proceed. To save space, here is just the first row:

      ⎕display possibles[1;]
┌→────────────────────────────────────────────────────────┐
│ ┌⊖┐ ┌→──┐ ┌→──────┐ ┌⊖┐ ┌→────┐ ┌⊖┐ ┌→──────┐ ┌→──┐ ┌⊖┐ │
│ │0│ │5 6│ │3 5 6 7│ │0│ │3 5 8│ │0│ │3 5 6 8│ │5 6│ │0│ │
│ └~┘ └~──┘ └~──────┘ └~┘ └~────┘ └~┘ └~──────┘ └~──┘ └~┘ │
└∊────────────────────────────────────────────────────────┘

Notice that the number '7' is only included in one list of possibilities - i.e. the only blank square on the first row where a '7' would be legal is square 3.

How can we find which number(s) appear in only one list? First let's look at how to answer the question just for the first row (We'll generalise do doing all rows at once in a moment):

      ⍝ List of all numbers which appear anywhere in the lists of possibles for the first row
      unplaced_numbers←∊possibles[1;]
      unplaced_numbers
5 6 3 5 6 7 3 5 8 3 5 6 8 5 6

      ⍝ How many lists does each number 1 - 9 appear in?      
      num_lists ← +⌿unplaced_numbers ∘.= ⍳9
      num_lists  
0 0 3 0 5 4 1 2 0                ⍝ Interpretation: The numbers 1 and 2 appear 0 times, 3 appears 3 times, etc

      ⍝ Which is the first number that only appears in one list?
      val←num_lists⍳1
      val
7
      ⍝ Which list does it appear in? i.e. which column in row 1 should we put the number into?
      val ∊ ¨possibles[1;]
0 0 1 0 0 0 0 0 0
      col←(val ∊ ¨possibles[1;])⍳1
      col
3

Version 2 of our SudokuSolver

Here's a listing of a revised version of the Sudoku solver which incorporates our 'Every number must go somewhere' technique.

The new function loops (:For method in 1 2) to try both methods of solving the Sudoku (Every number can only appear once, Every number must go somehere)
The new "Every number must go somewhere" method has been generalised to consider all the rows of the puzzle at the same time

R←SudokuSolver puzzle;N;M;grids;possibles;no_progress;trans;tpuzz;tposs;solved;mask;method;unplaced_numbers;num_lists;row;col;val

⍝ Get useful dimensions.
⍝ 'N' is the number of columns in the puzzle
⍝ 'M' is the number of columns in each sub grid
⍝
⍝ For example, for a 9 x 9 puzzle: N=9, M=3
N←↑⍴puzzle
M←⌊N*0.5


⍝ Precalculate the cell positions of each of the sub grids
⍝ Only need to do this once
grids←(N N)⍴⍋ ,M⌿M/(M M)⍴⍳N

⍝ Set up list of possible values for each cell
possibles←(N N)⍴⊂⍳N

⍝ For squares which are already known, set list of possibles to empty
((,puzzle≠0)/,possibles)←⊂⍬

:Repeat
  no_progress←1
  
  :For method :In 1 2
  
    :For trans :In 1 2 3
      ⍝ Transform so each group of numbers forms a row
      tpuzz←trans Transform puzzle
      tposs←trans Transform possibles
    
      :If method=1
        ⍝ If any number is already used in row, it can't be used again elsewhere
        tposs←tposs~¨N/(N 1)⍴⊂[2]tpuzz  
      :Else
        ⍝ Every number has to be used *somewhere* in the row!
        
        ⍝ For each row, list all numbers which appear anywhere in the lists of possibles
        unplaced_numbers←∊¨⊂[2]tposs
        
        ⍝ For each row, how many lists does each number 1 - N appear in?
        num_lists←+/¨unplaced_numbers∘.=⍳N
        
        ⍝ Are there any numbers that can only go in one column?
        :If 1 ∊ num_lists
          ⍝ Yes. Find first row which contains a number which can only go in one column
          row←(<\1=,num_lists)/N/⍳N
          
          ⍝ What's the number?
          val←(,num_lists[row;])⍳1
          
          ⍝ Which is the column it can go in?
          col←(,val∊¨tposs[row;])⍳1
          
          ⍝ Update list of possibilities
          tposs[row;col]←⊂,val 
        :EndIf
      :EndIf

      ⍝ Transform back
      possibles←trans Transform tposs
    :EndFor
  
    ⍝ Found any squares which only have one remaining possibility?
    solved←1=↑¨⍴¨possibles

    :If 1 ∊ solved
      ⍝ Yes. Copy them in
      mask←∊solved
      (mask/,puzzle)←∊mask/,possibles
      (mask/,possibles)←⊂⍬ 
     
      ⍝ Go again from the start of the outer solving loop
      no_progress←0
      :Leave
    :EndIf
  :EndFor
  
:Until no_progress

⍝ Return completed puzzle as result
⍝ (NB: May not be complete!)
R←puzzle

Time to use brute force!

How does the revised Sudoku solver do with the StarBurst puzzle?

      SudokuSolver StarBurst
9 0 7 1 8 4 3 0 2
0 8 0 0 6 0 0 7 0
0 0 0 0 0 0 0 0 8
4 0 0 0 0 0 0 0 1
8 7 0 0 0 0 0 3 0
3 0 0 0 0 0 0 0 7
7 0 0 0 0 0 0 0 3
0 3 0 0 7 0 0 8 0
1 0 8 2 3 9 7 0 4

Certainly an improvement, but there are still some unsolved squares!

There are other techniques we could use. For example if the exact possibility (1 2) appears for two squares in the same row, we can determine that one of the squares must be a 1 and the other must be a 2. We can thus remove 1 and 2 from the list of possibilities for any other square in the row.

However, there comes a time when you need to use brute force!

What we want to do is pick the square with the fewest remaining possibilities and then speculatively try them one at a time. If we guess right our guesses will eventually lead to the solution; if we guess wrong we end up with a Sudoku that has no solution.

Here are some of the bits we need:

      ⍝ How many possibilities remain for each square on the board?
      unsolved←∊⍴¨possibles

      ⍝ What's the index position of the square with the least remaining possibilities,
      ⍝ excluding squares with 0 possibilities (i.e. already solved)?
      pos←unsolved⍳⌊/unsolved~0

      ⍝ What possible values could the square take?      
      ⊃(,possibles)[pos]

This enables us to try each of the values in turn, patching them into the puzzle and recursively invoking SudokuSolver to attempt to solve the modified puzzle:

unsolved←∊⍴¨possibles
pos←unsolved⍳⌊/unsolved~0
:For trial :In ⊃(,possibles)[pos]
  R←puzzle
  (pos⌷,R)←trial
  R←SudokuSolver R
  :If ~0∊R
    ⍝ Puzzle completed. Return result
    :Return
  :EndIf
:EndFor

The recursion technique also requires a couple of minor changes to our earlier code because during recursion we may be trying to solve a puzzle which may have no solution.

You may be wondering why we don't just use brute force all the time. The answer is that a brute-force only technique is very slow for certain Sudoku puzzles like the Easter Monster listed at the end of this article. By contrast, our intelligent Sudoku solver handles Easter Monster in under a second.

The Final Function

Here's the final version of the Sudoku solver:

R←SudokuSolver puzzle;⎕IO;N;M;grids;possibles;no_progress;method;trans;tpuzz;tposs;row;col;val;unplaced_numbers;num_lists;solved;mask;unsolved;pos;trial
⎕IO←1

⍝ Get useful dimensions.
⍝ 'N' is the number of columns in the puzzle
⍝ 'M' is the number of columns in each sub grid
⍝
⍝ For example, for a 9 x 9 puzzle: N=9, M=3
N←↑⍴puzzle
M←⌊N*0.5


⍝ Precalculate the cell positions of each of the sub grids
⍝ Only need to do this once
grids←(N N)⍴⍋ ,M⌿M/(M M)⍴⍳N

⍝ Set up list of possible values for each cell
possibles←(N N)⍴⊂⍳N

⍝ For squares which are already known, set list of possibles to empty
((,puzzle≠0)/,possibles)←⊂⍬

:Repeat
  no_progress←1
  
  :For method :In 1 2
  
    :For trans :In 1 2 3
      ⍝ Transform so each group of numbers forms a row
      tpuzz←trans Transform puzzle
      tposs←trans Transform possibles
    
      :If method=1
        ⍝ If any number is already used in row, it can't be used again elsewhere
        tposs←tposs~¨N/(N 1)⍴⊂[2]tpuzz
      :Else
        ⍝ Every number has to be used *somewhere* in the row!
        
        ⍝ For each row, list all numbers which appear anywhere in the lists of possibles
        unplaced_numbers←∊¨⊂[2]tposs
        
        ⍝ For each row, how many lists does each number 1 - N appear in?
        num_lists←+/¨unplaced_numbers∘.=⍳N
        
        ⍝ Are there any numbers that can only go in one column?
        :If 1 ∊ num_lists
          ⍝ Yes. Find first row which contains a number which can only go in one column
          row←(<\1=,num_lists)/N/⍳N
          
          ⍝ What's the number?
          val←(,num_lists[row;])⍳1
          
          ⍝ Which is the column it can go in?
          col←(,val∊¨tposs[row;])⍳1
          
          ⍝ Update list of possibilities
          tposs[row;col]←⊂,val 
        :EndIf
      :EndIf

      ⍝ Transform back
      possibles←trans Transform tposs
    :EndFor
    
    ⍝ Found any squares which only have one remaining possibility?
    solved←1=↑¨⍴¨possibles

    :If 1 ∊ solved
      ⍝ Commit first one. Can't do more than one at a time
      ⍝ because the values may be mutually incompatible if we're trying
      ⍝ a puzzle with no solution (e.g. by brute force recursion)
      mask←<\∊solved      
      (mask/,puzzle)←∊mask/,possibles
      (mask/,possibles)←⊂⍬ 

      
      ⍝ Go again from the start of the outer solving loop
      no_progress←0
      :Leave
      
    :EndIf
  :EndFor
:Until no_progress


⍝ Did we find a solution (or maybe grind to a halt if recursing down a dead-end path)?
unsolved←∊⍴¨possibles
:If 0=⌈/unsolved
 ⍝ Yes, all done
  R←puzzle
  :Return
:EndIf

⍝ Use brute force!
⍝ Find position with least remaining possibilities,
⍝ Loop/recurse to try all possible values
pos←unsolved⍳⌊/unsolved~0
:For trial :In ⊃(,possibles)[pos]
  R←puzzle
  (pos⌷,R)←trial
  R←SudokuSolver R
  :If ~0∊R
    ⍝ Puzzle completed. Return result
    :Return
  :EndIf
:EndFor

Does it work?

Time to test our final version. Looks good!

      SudokuSolver StarBurst
9 5 7 1 8 4 3 6 2
2 8 1 9 6 3 4 7 5
6 4 3 7 2 5 1 9 8
4 9 6 3 5 7 8 2 1
8 7 5 4 1 2 9 3 6
3 1 2 8 9 6 5 4 7
7 2 9 5 4 8 6 1 3
5 3 4 6 7 1 2 8 9
1 6 8 2 3 9 7 5 4

Attached Workspace

The attached APLX workspace contains the Sudoku solver code together with some test puzzles. For example you might want to try solving the 'Easter Monster', shown here together with its solution

      ShowSudoku EasterMonster
+ - - - + - - - + - - - +
| 1 . . | . . . | . . 2 |
| . 9 . | 4 . . | . 5 . |
| . . 6 | . . . | 7 . . |
+ - - - + - - - + - - - +
| . 5 . | 9 . 3 | . . . |
| . . . | . 7 . | . . . |
| . . . | 8 5 . | . 4 . |
+ - - - + - - - + - - - +
| 7 . . | . . . | 6 . . |
| . 3 . | . . 9 | . 8 . |
| . . 2 | . . . | . . 1 |
+ - - - + - - - + - - - +

      ShowSudoku SudokuSolver EasterMonster
+ - - - + - - - + - - - +
| 1 7 4 | 3 8 5 | 9 6 2 |
| 2 9 3 | 4 6 7 | 1 5 8 |
| 5 8 6 | 1 9 2 | 7 3 4 |
+ - - - + - - - + - - - +
| 4 5 1 | 9 2 3 | 8 7 6 |
| 9 2 8 | 6 7 4 | 3 1 5 |
| 3 6 7 | 8 5 1 | 2 4 9 |
+ - - - + - - - + - - - +
| 7 1 9 | 5 4 8 | 6 2 3 |
| 6 3 5 | 2 1 9 | 4 8 7 |
| 8 4 2 | 7 3 6 | 5 9 1 |
+ - - - + - - - + - - - +

Author: SimonMarsden