knitr::opts_chunk$set( collapse = TRUE, comment = "", fig.height = 5.5, fig.width = 5.5, fig.align = "center", out.width = "0.5\\textwidth") setHook("plot.new", list(family = function() par(family = "sans")), "replace")

A Sudoku design is an $n^2\times n^2$ Latin square design with the additional constraint that if the pattern is further subdivided into an $n \times n$ array of smaller $n \times n$ squares, then each of the smaller squares itself has a complete replicate of the symbols used in the design. Here $n$ is a positive integer, in practice $n > 1$ to avoid trivialities and $n < 6$ is usual.

This wordy description is more easily understood by showing an example for $n = 3$ and using the digits $1,2,\ldots,9$ as the symbols.

library(sudokuAlt) set.seed(2019) seedGame(3) %>% solve() %>% regulariseGame() %>% plot()

The example above is in a canonical form, or "regularised", by ensuring the symbols are labelled in such a way that those in the top left $3\times3$ sub-square are in lexicographical order by row.

In a Sudoku *puzzle* the player is given a partially completed Sudoku
design and the challenge is to fill out the vacant squares in such
a was that the constraints are satisfied. That is, after completion,

- Every row must contain a complete set of the $n^2$ symbols
- Every column must also contain a complete set of symbols, and
- Every $n \times n$ block must also contain a complete set.

The following example shows a typical puzzle where the supplied entries are shown in red and one possible completion shown in grey. This is for the typical case of $n = 3$.

g <- makeGame() %>% solve() %>% plot()

For larger examples, using letters for the symbols is more convenient. Here is an example for $n=4$, regularised:

set.seed(2019) g4 <- seedGame(4) %>% solve() %>% regulariseGame() %>% plot()

I have never seen the attraction of solving Sudoku puzzles *per se*, but
the more abstract programming problem of devising and implementing
an effective algorithm for doing so I find much more interesting.

The first `R`

package on `CRAN`

to offer a programming solution is the `sudoku`

package, due to David Brahm and Greg Snow, with contributions from
Curt Seeliger and Henrik Bengtsson.
It offered an ingenious iterative solution to the problem, (which I found
difficult to follow), mainly for the standard case of $n=3$.

This led me to consider the problem more actively.
It seemed to me an explicitly *recursive* solution would offer
more elegant code without too much overhead cost in computing time.
I am not sure the result is all that elegant, but it does seem to work
reasonably effectively.

Cases $n = 2$ or $n = 3$ are generally easy; the
cases $n = 4$ or $n = 5$ are not practical to solve in general, if the game
is set up in the same form as a typical puzzle, but curiously it is possible
to generate games, and hence complete Sudoku *designs*, by a technique outlined
below. Cases for $n > 5$ require a more sophisticated algorithm than the one
given in the present `sudokuAlt`

package.

In outline the solution method used here for a Sudoku game is as follows. It uses what I suspect is the standard way people do so by hand.

Given a game,

- Check to see if there are any gaps yet to be filled. If not, the task is complete, return the completed game and exit.
- For each gap in the game, establish a list of all possible symbols that may, at this stage, be considered as a possible entry.
- If any gap has no possible entries the game is insoluble. In this case return
`NULL`

, indicating "no solution found". - If all gaps have possible entries, select one with fewest possible completions. Loop over these possible entries, setting each possibility in turn as the entry, checking to see if a solution can be found by calling the procedure recursively with the current temporary entry fixed. If the loop is complete without a solution being found, the game is inconsistent and
`NULL`

is returned. If a solution to the entire problem is found, it will be returned prior to the loop ending.

In essence, "find the possible completion symbols, fix one and look again", but working systematically in such a way as ensure the process terminates, one way or another. The problem is mainly a curiosity but the programming strategy is of some possible pedagogical value, at least.

An obvious strategy to try to make a new Sudoku design (or puzzle) is

- Start with a design with all cells vacant
- Assign a single replicate of the $n^2$ symbols to the cells at random, giving Sudoku puzzle,
- Solve the puzzle to give a complete design.

While this is an obvious algorithm, what came as a surprise to me is just how well it works, at least for small-$n$ cases. It works well for $n = 2,3$, fairly well for $n=4$ and with difficulty for $n=5$.

Here is an example.

set.seed(1559347072) ## chosen after some experimentation... set.seed(1559368531) ## chosen after some experimentation... set.seed(1559686356) ## chosen after some experimentation...

set.seed(1559707151) g5 <- seedGame(5) %>% solve() %>% regulariseGame() plot(g5, cex = 1)

The function `seedGame()`

constructs the embryonic
puzzle, which is denoted by
the red symbols in the display.

If the Sudoku game is to be used formally as an experimental design, it
is convenient to have the information in `data.frame`

form rather than as
a `"sudoku"`

object. This conversion is achieved by the `designGame()`

function:

d5 <- designGame(g5) head(d5); tail(d5)

The package also contains a function `emptyGame(n)`

that supplies a Sudoku
object with all entries unfilled. This has been convenient for exploring
Sudoku designs with prescribed additional constraints or patterns.

For example, it is possible to devise a $4^4$ Sudoku pattern with the additional property that the leading diagonal is also a complete replicate of the 16 symbols:

g <- emptyGame(4) diag(g) <- LETTERS[1:16] g %>% solve() %>% plot() -> sg

There are no functions for the input of unsolved puzzles, but this
`emptyGame`

facility might help with manual input.

`print`

and `plot`

methodsThe package gives some attention to reasonably comprehensible presentation of Sudoku puzzles and designs.

The `plot`

method is shown above. It works reasonably well but may require
some adjustment of the `cex`

graphics parameter. It has the advantage
of being able to show the puzzle and its solution separately on the one
diagram.

The `print`

method is shown below. It can only show either the puzzle or
the solution, of course.

g <- emptyGame(3) g[1:3, 1:3] <- matrix(1:9, nrow = 3, byrow = TRUE) solve(g)

Both `plot`

and `print`

methods return the game itself (invisibly).

As mentioned above, not much effort has been given to input of particular
Sudoku puzzles, but the coercion function, `as.sudoku()`

can be useful in this
regard. It takes a square matrix as its input and returns a Sudoku object
that the methods of the package can recognize.

The `emptyGame()`

function could also be used for input, as mentioned above.

There are two functions which can access public websites to get daily Sudoku puzzles. These are

which uses an Australian web site, and`fetchAUGame()`

which uses a British web site.`fetchUKGame()`

This possibly explains why the package is listed as being for * spoiling*
Sudoku puzzles.

**Any scripts or data that you put into this service are public.**

Embedding an R snippet on your website

Add the following code to your website.

For more information on customizing the embed code, read Embedding Snippets.