---
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.
