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,
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,
NULL
, indicating "no solution found".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
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
fetchAUGame()
which uses an Australian web site, andfetchUKGame()
which uses a British web site.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.
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.