Solving Sudoku using APL

PAGE UNDER CONSTRUCTION

Contents

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.

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 puzzle will fit slightly better on the page. (The final solution listed at the end of this page will work for any N x N Sudoku).

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

We can type it directly into the APL session, usings 0s to represent blank squares:

      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 some numbers 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 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│ │
│ └~┘ └~┘ └~──┘ └~──┘ │
└∊────────────────────┘

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 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│     │
│ └~──┘   └~┘     └~──┘   └~┘     │
└∊────────────────────────────────┘

Considering Columns

So far we have worked on the Sudoku puzzle by considering which numbers already appear in each row of the solution. Since a number can't appear more than once in a row, we've removed them from the list of possible values for the blank squares.

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. 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:

 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

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

      ⍝ 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←(,puzzle)[grids]
      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

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.

Now 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 performs the actual Sudoku solving, as far as we've developed it so far:

R←SudokuSolver puzzle;grids;possibles;trans;tpuzz;tposs

⍝ Precalculate the cell positions of each of the sub grids
⍝ Only need to do this once
grids←4 4⍴⍋ ,2⌿2/2 2⍴⍳4

⍝ Set up list of possible values for each cell
possibles←4 4⍴⊂⍳4

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

⍝ 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 any number is already used in row, it can't be used again elsewhere
  tposs←tposs~¨4/4 1⍴⊂[2]puzzle

  ⍝ Transform back
  possibles←trans Transform tposs
:EndFor

⍝ Temporarily return 'possibles' as result
R←possibles

WORK IN PROGRESS - HERE I AM

The Final Function

Finally, here's the Sudoku solver generalised to solve any N x N Sudoku puzzle.

R←SudokuSolver puzzle;⎕IO;side;sub;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.
⍝ 'side' is the number of columns in the puzzle
⍝ 'sub' is the number of columns in each sub grid
⍝
⍝ For example, for a 9 x 9 puzzle: side=9, sub=3
side←1↑⍴puzzle
sub←⌊side*0.5

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

⍝ Set up list of possible values for each cell
possibles←(side,side)⍴⊂⍳side
((,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~¨side/(side,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∘.=⍳side
        
        ⍝ 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)/side/⍳side
          
          ⍝ 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
 
⍝ No solution!
R←(side,side)⍴0

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

PAGE UNDER CONSTRUCTION

Author: SimonMarsden