--- title: "Sudoku Designs" author: "Bill Venables" date: 2019-05-31 output: pdf_document: keep_tex: true toc: true toc_depth: 3 number_sections: true includes: in_header: header.tex html_document: rmarkdown::html_vignette vignette: > %\VignetteIndexEntry{Sudoku Designs} %\VignetteAuthor{Bill Venables} %\VignetteEngine{knitr::rmarkdown} %\VignetteEncoding{UTF-8} --- ```{r, include = FALSE} 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") ``` # Introduction 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. ```{r setup} 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$. ```{r} g <- makeGame() %>% solve() %>% plot() ``` For larger examples, using letters for the symbols is more convenient. Here is an example for $n=4$, regularised: ```{r, fig.width=5, fig.height=5} set.seed(2019) g4 <- seedGame(4) %>% solve() %>% regulariseGame() %>% plot() ``` # Solving Sudoku puzzles and making new ones 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. ## The solution algorithm 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. ## Making Sudoku designs (or puzzles) 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. ```{r, eval=FALSE, echo=FALSE} set.seed(1559347072) ## chosen after some experimentation... set.seed(1559368531) ## chosen after some experimentation... set.seed(1559686356) ## chosen after some experimentation... ``` ```{r, fig.width=7.25, fig.height=7.25} 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: ```{r} d5 <- designGame(g5) head(d5); tail(d5) ``` ## Prescribed patterns 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: ```{r, fig.width=4.75, fig.height=4.75} 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` methods The 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. ```{r} 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). ## Input and frivolities 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, and * __`fetchUKGame()`__ which uses a British web site. This possibly explains why the package is listed as being for _**spoiling**_ Sudoku puzzles.