Solving Sudoku using APL

In the following article we'll look at how a Sudoku algorithm might be developed in APL. 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.

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.

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 it 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

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

Let's unpack this 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:

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

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. We were able to rearrange the puzzle so that the columns became rows, and hence re-use 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:

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

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:

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

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

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:

┌→──────────────────────────────────────────────────────────────────┐
│ ┌⊖┐ ┌→──┐ ┌→────────┐ ┌→────┐ ┌⊖┐ ┌→──────┐ ┌→────────┐ ┌→──┐ ┌⊖┐ │
│ │0│ │3 6│ │1 2 3 6 8│ │3 4 8│ │0│ │3 4 6 8│ │2 3 4 6 8│ │2 6│ │0│ │
│ └~┘ └~──┘ └~────────┘ └~────┘ └~┘ └~──────┘ └~────────┘ └~──┘ └~┘ │
└∊──────────────────────────────────────────────────────────────────┘

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

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_columns;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←M⌿M/(M M)⍴⍳N
grids←(N N)⍴⍋,grids

⍝ Set up list of possible values for each cell
possibles←(N N)⍴⊂⍳N
((,puzzle≠0)/,possibles)←⊂⍬

:Repeat
  no_progress←1
  
  :For method :In 1 2
  
    ⍝ Look across rows/columns/grids to remove numbers in use
    :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!
        
        ⍝ Which numbers are still unplaced in each row? Get a list
        unplaced_numbers←∊¨⊂[2]tposs
        
        ⍝ How many different columns could each unplaced number go in?
        num_columns←+/¨unplaced_numbers∘.=⍳N
        
        ⍝ Are there any numbers that can only go in one column?
        :If 1 ∊ num_columns
          ⍝ Yes. Find first row which contains a number which can only go in one column
          row←(<\1=,num_columns)/N/⍳N
          
          ⍝ What's the number?
          val←(,num_columns[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 

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