Solving Sudoku using APL
Contents

Solving Sudoku using APL
 New to APL?
 Trying the code out
 The Puzzle
 Getting Started
 The Power of Arrays (Part 1)
 The Power of Arrays (Part 2)
 Considering Columns
 Considering the Sub Grids
 Filling in known squares
 Time to write a function
 Trying the Sudoku Solver
 Every number must go somewhere
 Version 2 of our SudokuSolver
 Time to use brute force!
 The Final Function
 Does it work?
 Attached Workspace
 Some Additions
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 builtin functions and operators. We can spend more time thinking about the solution, and spend less time on the 'plumbing' compared to nonarray 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 compilelinkdebug 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 offputting 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.
(c) Under Dyalog APL the migration level needs to be set to 3 for maximum compatibility:
⎕ML←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. Note: What we type is indented 6 spaces to distinguish it from the computer’s response.
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 arrayoriented 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:
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. To do the columns we rearranged the puzzle so that the columns became rows, and hence reused 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 selfinverse!
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 userdefined 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 subgrids 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 hardcoding 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 subgrid (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 row which contains first such number, and its value (row val)← 1+ N N⊤¯1+(,num_lists)⍳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] ⍝ Make a copy of the puzzle, and patch in the trial number R←puzzle (pos⌷,R)←trial ⍝ Try to solve it 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 bruteforce 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 row which contains first such number, and its value (row val)← 1+ N N⊤¯1+(,num_lists)⍳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 deadend 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] ⍝ Make a copy of the puzzle, and patch in the trial number R←puzzle (pos⌷,R)←trial ⍝ Try so solve it 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
Some Additions
I have made some changes to Simon's code so that it can handle a wider variety of puzzles.
ShowGrid Annie +++  . .  . .   A N  . .  +++  N I  E .   . .  . .  +++ ShowGrid Judith +++  J U D  I T H   . . .  . . .  +++  . I .  D . .   . J U  . I .  +++  I T .  . . D   . . H  . . .  +++ ShowGrid Annabel +++  . . .  A .   ++   . .  N . .  ++++  . N  .  . L       A .  .  E .   ++ ++   .  . B .  .  ++++
Alphabetic puzzles
The first addition is to handle alphabetic puzzles.
∇r←Annie [1] ⍝ a 4x4 alphabetic Sudoku problem [2] r←4 4⍴16↑' AN NIE'
An alphabetic puzzle is easy to specify in APL, I solve it by converting it to numeric.
Numeric Annie 0 0 0 0 1 4 0 0 4 3 2 0 0 0 0 0 SudokuSolver Numeric Annie 3 2 1 4 1 4 3 2 4 3 2 1 2 1 4 3 (Alphabet Annie)Reformat SudokuSolver Numeric Annie IEAN ANIE NIEA EANI
The function Numeric does nothing, see line [3], if the puzzle is already numeric and then looks up each cell (square) against the alphabet used in the puzzle remembering to map blank onto zero. In Alphabet line [3] finds the characters used and [4] sorts them, the rest of the function copes when the puzzle is numeric or when you must provide a missing character. Once you know the alphabet it is easy to turn numbers back into letters.
∇pz←Numeric ch;a [1] ⍝ convert an alphabetic puzzle to numeric [2] pz←ch [3] →(0=1↑0⍴ch)↑0 [4] a←Alphabet ch [5] pz←¯1+(' ',a)⍳ch ∇a←Alphabet gr;n;g;f [1] ⍝ return alphabet used in puzzle grid [4] a←∪(,gr)~' ' ⍝ characters in grid [5] a←a[⍋a] Alphabet Annie AEIN Alphabet Sample4x4 1234 Alphabet Sample16x16 123456789ABCDEFG Alphabet 4 4⍴'simo' imos Alphabet 5 5⍴'simo' aimos Alphabet 5 5⍴'SIMO' AIMOS Alphabet 8 8⍴'12 abc AB' 12ABabcd (Alphabet Annie)[2 3⍴1 4 4 3 2 2] ANN IEE
Showing puzzles
My function ShowGrid is an alternative to Simon's ShowSoduko. It has to do so much more to handle irregular shaped boxes (subgrids) that it seemed better to start from scratch. ShowSudoku returns a matrix of mixed letters and integers and because of that handles large puzzles with ten or more rows effortlessly, the blanks between columns are provided by the session. ShowGrid returns a character matrix where the integers are replaced by single letters from the alphabet. ShowGrid also tries to preserve the appearance of the diagonals by using twice as many columns as rows, which is handy when you are looking at puzzles whose boxes are not square. The code to do this is included in the attached workspace, see #Additional Workspace below.
(ShowSudoku Annie) (ShowGrid Annie) +++ +++     . .  . .  AN   A N  . .  +++ +++ NIE   N I  E .      . .  . .  +++ +++ ⍴¨(ShowSudoku Annie) (ShowGrid Annie) 7 7 7 13 (ShowSudoku Sample4x4) (ShowGrid Sample4x4) +   +  + +++  1 2 . .   1 2  . .   . . . .   . .  . .  +   +  + +++  2 . . .   2 .  . .   . . . 3   . .  . 3  +   +  + +++ ⍴¨(ShowSudoku Sample4x4) (ShowGrid Sample4x4) 7 7 7 13
Rectangular Boxes
Allowing rectangular boxes lets you create a puzzle with a 6 letter alphabet, like the puzzle Judith. Judith returns two things, the first is a square matrix defining the puzzle, the second is scalar integer specifying how many rows a box has. SetBoxShape then works out the number of columns, resetting the number of rows if necessary.
∇r←Judith;g [1] ⍝ 6×6 alphabetic Sudoku problem [2] g←6 6⍴36↑'JUDITH I D JU I IT D H' [3] r←g 2 ⍝ puzzle has box shape 2 by 3 ⍴Judith ⍝ Judith returns two things ... 2 ⍴1⊃Judith ⍝ ... the first is a square matrix 6 6 2 SetBoxShape 6 6⍴0 2 3 0 SetBoxShape 6 6⍴0 2 3 0 SetBoxShape 12 12⍴0 3 4 2 SetBoxShape 12 12⍴0 2 6
Now we need to tell SudokuSolver about this box shape. I have renamed the original version SolveGrid and now SudokuSolver is a short cover function calling SolveGrid. Complete provides any missing box definition and Boxes is a generalisation of Simon's equation grids←(N N)⍴⍋ ,M⌿M/(M M)⍴⍳N.
∇R←SudokuSolver puzzle;g;b [1] ⍝ Calls Main Sudoku solving function with box definition [2] (g b)←Complete puzzle [3] R←(b Boxes↑⍴g)SolveGrid Numeric g ∇bx←b Boxes n;bs [1] ⍝ return the box indexes for a puzzle size ¨n¨ [6] bs←b SetBoxShape(n×n)⍴0 [7] bx←n n⍴⍋,(1⊃bs)⌿(2⊃bs)/(⌽bs)⍴⍳n
One of the most appealling aspects of Simon's solution was that Transform recognised that the tranformations of columns and boxes into rows are selfinverse. Sadly with rectangular boxes this is not true so Reverse works out the tranformation for boxes back into rows and Transform uses it as case 4. Both grids and rgrids are local to SolveGrid but not to Transform. Now, with these few changes to SolveGrid we are ready to solve Judith.
∇rgrids←Reverse grids [1] ⍝ reverse transformation for nonsquare boxes (subgrids) [2] rgrids←(⍴grids)⍴(,grids)⍳⍳×/⍴grids ∇R←trans Transform matrix [9] :Case 4 [10] R←(,matrix)[rgrids] ∇R←grids SolveGrid puzzle;⎕IO;N;M; ... [18] rgrids←Reverse grids [63] possibles←(trans+3=trans)Transform tposs SudokuSolver Judith 4 6 1 3 5 2 5 2 3 4 1 6 2 3 5 1 6 4 1 4 6 2 3 5 3 5 4 6 2 1 6 1 2 5 4 3
It is a tribute to Simon's design that so few changes to his solver were needed. As we saw with the puzzle Annie the command to show the solution to an alphabetic puzzle is lengthy. Solve is a new function that solves a puzzle and shows the result. Both Solve and ShowGrid have an optional left argument that allows you to choose the characters that mark the puzzle and box borders.
∇r←c Solve p;b;g [1] ⍝ Solve puzzle ¨p¨, and display solution under control of ¨c¨ [2] :If 2≠⎕nc 'c' ⋄ c←0 ⋄ :EndIf [3] r←SudokuSolver p [4] (g b)←Complete p [5] r←c ShowGrid((Alphabet g)Reformat r)b 2 Solve Judith ┌───────┬───────┐ │ J U D │ I T H │ │ T H I │ J D U │ ├───────┼───────┤ │ H I T │ D U J │ │ D J U │ H I T │ ├───────┼───────┤ │ I T J │ U H D │ │ U D H │ T J I │ └───────┴───────┘
Irregular Boxes
With an alphabet with a prime number of letters, like 5, you can not divide the grid into similar rectangles. Annabel returns two things, the first is a matrix defining the puzzle, the second defines the boxes  it has a box number for each cell of the grid. Boxes recognises when the box definition is not a number of rows and uses the setters definitions.
∇r←Annabel;b;c [1] ⍝ a 5×5 alphabetic Sudoku puzzle [2] b←5 5⍴1 1 1 2 2 1 1 2 2 2 3 3 4 5 5 3 3 4 5 5 3 4 4 4 5 [3] c←5 5⍴25↑' A N N LA E B' [4] r←c b ⍝ characters, boxes 2⊃Annabel ⍝ the box definitions 1 1 1 2 2 1 1 2 2 2 3 3 4 5 5 3 3 4 5 5 3 4 4 4 5 ∇bx←b Boxes n;bs [1] ⍝ return the box indexes for a puzzle size ¨n¨ [3] bx←n n⍴⍋,b ⍝ from box number to index [4] →(1<⍴,b)↑0 ⍝ user provided the box numbers 1 Solve Annabel ⌈^⊤  N L E  A B   ⌈⊥   B A  N L E  <+^>  E N  A  B L       A B  L  E N   ⌈⊥ ⌊⊤   L  E B N  A  ⌊∨∨⊥
CheckSolved gets the same treatment as SudokuSolver, the new version uses CheckBoxes to check the box definitions first.
∇R←CheckSolved puzzle;b;g [1] ⍝ Calls Main Sudoku checking function with box definition [2] (g b)←Complete puzzle [3] →(¯1=R←CheckBoxes b)↑0 [4] R←(b Boxes↑⍴g)CheckGrid Numeric g ∇c←CheckBoxes b;n;bn [1] ⍝ ¨b¨ to see if it is a valid box definition [7] c←¯1 [8] →(n=⍴bn←∪,b)↓0 ⍝ number of boxes? [9] →(^/n=+/bn∘.=,b)↓0 ⍝ cells in each box? [10] c←0 CheckBoxes 5 5 5 5 5/⍳5 0 CheckBoxes 4 6 5 5 5/⍳5 ¯1 CheckBoxes 9 9 9 9/⍳4 ¯1
CheckSolved works as before on the original puzzle, but must be provided with the right box definitions when you apply it to a solution. The solution to Judith is OK because it uses the default box size for a 36 cell grid, you will see that the Judith puzzle has no solution if the boxes have 3 rows.
(CheckSolved Annie) (CheckSolved SudokuSolver Annie) 0 1 (CheckSolved Judith) (CheckSolved SudokuSolver Judith) 0 1 CheckSolved (SudokuSolver Annabel) (2⊃Annabel) 1 CheckSolved (1⊃Judith) 3 ¯1
If you feel you need a function to help you here or would like a default box arrangement for a prime number of boxes, happy APL writing!
Additional Workspace
This is how I combined my functions with Simon's, note the P for Protect in the copy.
)load sudokua SAVED 20110309 14.28.55 InfoZ ⍝ describes this workspace )pcopy sudoku SAVED 20100323 17.40.05 NOT COPIED: CheckSolved SudokuSolver Transform )save sudokuz 20110309 14.30.21 TestAll All 5 tests pass OK
I have a simple test rig set up so I can run TestAll after making changes to check all is still well.
Sudokua.aws for the APLX workspace of additional functions described above.
Sudokuz.dws for the Dyalog APL version of the complete workspace created above.
Second Author: EllisMorgan