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 written 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
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 |. . |
| . . |. . |
+ - - +- - +
| 2 . |. . |
| . . |. 3 |
+ - - +- - +

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

      puzzle←4 4⍴ 1 2 0 0 0 0 0 0 2 0 0 0 0 0 0 3
      puzzle
1 2 0 0
0 0 0 0
2 0 0 0
0 0 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│ │1 2 3 4│ │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│ │1 2 3 4│ │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 0 0 0│ │0 0 0 0│ │0 0 0 0│ │0 0 0 0│ │
│ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │
│ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │
│ │2 0 0 0│ │2 0 0 0│ │2 0 0 0│ │2 0 0 0│ │
│ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │
│ ┌→──────┐ ┌→──────┐ ┌→──────┐ ┌→──────┐ │
│ │0 0 0 3│ │0 0 0 3│ │0 0 0 3│ │0 0 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 4│ │1 2 3 4│ │1 2 3 4│ │1 2 3 4│ │
│ └~──────┘ └~──────┘ └~──────┘ └~──────┘ │
│ ┌⊖┐       ┌→────┐   ┌→────┐   ┌→────┐   │
│ │0│       │1 3 4│   │1 3 4│   │1 3 4│   │
│ └~┘       └~────┘   └~────┘   └~────┘   │
│ ┌→────┐   ┌→────┐   ┌→────┐   ┌⊖┐       │
│ │1 2 4│   │1 2 4│   │1 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 4│ │1 3 4│ │1 2 3 4│ │1 2 4│ │
│ └~──┘ └~────┘ └~──────┘ └~────┘ │
│ ┌⊖┐   ┌→────┐ ┌→────┐   ┌→──┐   │
│ │0│   │1 3 4│ │1 3 4│   │1 4│   │
│ └~┘   └~────┘ └~────┘   └~──┘   │
│ ┌→┐   ┌→──┐   ┌→────┐   ┌⊖┐     │
│ │4│   │1 4│   │1 2 4│   │0│     │
│ └~┘   └~──┘   └~────┘   └~┘     │
└∊────────────────────────────────┘

PAGE UNDER CONSTRUCTION

Author: SimonMarsden