Computer-assisted puzzle design

Abstract

One approach to game design is to start with existing ideas and to modify them in interesting new ways. This process of “creative plagiarism” is applied to the Japanese logic puzzle Sudoku to create a new variant called Ludoku, which simplifies some aspects of the original puzzle while adding new strategies without adding undue complexity. This paper describes the design process from initial conception to final product, and how computer analysis was crucial to its success.

Keywords

Japanese logic puzzle puzzle design computer-aided design Sudoku Ludoku

1. Introduction

In the practice of game design, truly original ideas that transform the design landscape are rare, and almost all new games are created by combining ideas from previous games in novel and interesting ways (Browne, 2016). One approach to game design is to start with existing ideas that have proven to be successful in the past (Browne, 2017) and methodically explore the surrounding design space for fruitful variations (Browne, 2015). This process of creative plagiarism (Kim, 2005) can be effective in producing new games with entertaining emergent properties from familiar bases.

The solitaire logic puzzle game Sudoku is an ideal starting point for such a process. Japanese logic puzzles (The Times Japanese Logic Puzzles, 2006) are enjoying increasing worldwide popularity, and Sudoku is the most well-known example that has already spawned many interesting variants (Sudoku Variants, 2006). Might there be room for another? Given that almost all existing Sudoku variants achieve novelty by adding additional rules or mapping the game to more complex geometries, I was intrigued by the following question:

Can Sudoku be simplified to produce a novel and worthwhile variant?

This paper describes the computer-assisted development of a new solitaire logic puzzle game called Ludoku, designed with this question in mind. While an earlier paper (Browne and Ludoku, 2017) focussed on the game design aspects of this exercise, this paper focusses on the computational aspects.

2. Simplifying sudoku

Figure 1 (left) shows a classic Sudoku challenge.1

¹
Except that this challenge is unusual in that the starting hints are not arranged symmetrically, which is the case with all Sudoku challenges from publisher Nikoli (Kanamoto, 2001).

This challenge was dubbed “The World’s Hardest Sudoku” (Collins, 2012), although this claim is dubious (Browne, 2013). The rules for classic Sudoku are shown in Table 1.

Figure 1 (right) shows a Sudoku variant called Diagonal Sudoku (Sudoku Variants, 2006). This is played according to the rules of classic Sudoku with the additional rule that no number may be repeated along either of the long diagonals (marked with dotted lines). This is a case of adding complexity – i.e. an extra rule – to embellish the basic design.

Fig. 1.

“The World’s Hardest Sudoku” (Collins, 2012) (left) and diagonal sudoku (right).

Table 1

Rules for classic Sudoku

Frame	$9 \times 9$ square grid subdivided into nine $3 \times 3$ subgrids.
Start	Some hint values (1..9) are shown.
Aim	Fill the grid with numbers 1..9 such that:
	1. No number is repeated in any row.
	2. No number is repeated in any column.
	3. No number is repeated in any $3 \times 3$ subgrid.

In order to reduce the complexity of the basic game, on the other hand, an obvious design option is to the remove the $3 \times 3$ subgrids so that the game is played within a plain $9 \times 9$ square grid, as described in Table 2 and shown in Fig. 2.

However, removing the subdivisions and playing the game without the $3 \times 3$ subgrid rule does not work well. It eliminates many strategies and brief testing will reveal that it makes the reduced game repetitive and tedious to play. So how can some strategic complexity be injected back into this simplified design?

Table 2

Reduced sudoku frame

Frame

9 \times 9

square grid.

Fig. 2.

Square $9 \times 9$ grid with no subdivisions.

3. Design #1: Fully diagonal sudoku

Table 3 shows the rules for an obvious extrapolation of Diagonal Sudoku called Fully Diagonal Sudoku, in which no number can be repeated along any diagonal line within the $9 \times 9$ grid. Note that rule #3 is identical to the original rule #3 for classic Sudoku, but with “any $3 \times 3$ subgrid” replaced by “any diagonal line”; this rule set has the benefit of incorporating additional strategies into the puzzle (i.e. diagonally based) without unduly complicating the original rules, as desired. Theoretically, Fully Diagonal Sudoku looks like an interesting variant.

Table 3
Rules for fully diagonal sudoku

Frame $9 \times 9$ square grid.

Start Some hint values (1..9) are shown.

Aim Fill the grid with numbers 1..9 such that:

1. No number is repeated in any row.

2. No number is repeated in any column.

3. No number is repeated along any diagonal line.

3.1. n-queens colouring problems

The astute reader may have recognised Fully Diagonal Sudoku as a disguised version of the n-queens colouring problem (Bell and Stevens, 2009). Figure 3 (left) shows a solution to the well known n-queens problem for a $5 \times 5$ grid,2

²
i.e. the placement of n queens on a board such that no queen directly attacks another.

Fig. 3 (middle) shows the assignment of the label “1” to “colour” this set of queens, and Fig. 3 (right) shows grid filled with five sets of five non-attacking queens, labelled “1” to “5”.

One complication is that Martin Gardner observed, without proof, that: “When the order of the board is not divisible by 2 or 3, it is possible to superimpose n solutions that completely fill all the cells” (Gardner, 1969, p. 191), meaning that no possible Fully Diagonal Sudoku solutions can be generated for the $9 \times 9$ square grid. This apparently meant that Fully Diagonal Sudoku could only be played on grids of $5 \times 5$ and $7 \times 7$ , too small to allow interesting challenges.

However, this claim was later shown by example to be true only for $n < 12$ , and n-queen colourings have been found for $n = 12, 14, 15, 16, 18, 20, 21, 22, 24, \dots$ (Chvátal, 2016). The $n = 16$ case is of interest here, being large enough to produce interesting challenges and being a square number that will be familiar to Sudoku enthusiasts, as the board dimension of the standard game is limited to square numbers (due to the $n \times n$ subgrids).

Fig. 3.

A 5-queens solution (left), equivalent placement of 1s (middle), and 5-queens colouring of number sets 1..5 (right).

Fig. 4.

A 16-queens colouring (left) and a $16 \times 16$ fully diagonal sudoku challenge derived from this packing (right).

3.2. Evaluation of

16 \times 16

fully diagonal sudoku

Figure 4 (left) shows a 16-queen colouring from (Chvátal, 2016) and Fig. 4 (right) shows a Fully Diagonal Sudoku challenge with initial hint set based on a subset of this packing. So $16 \times 16$ Fully Diagonal Sudoku is technically feasible, but unfortunately provides a poor game that is frustrating and tedious to play (just try the example).

While classic Sudoku has $9 + 9 + 9 = 27$ constraint regions to work with, $16 \times 16$ Fully Diagonal Sudoku has $16 + 16 + 2 \times 29 = 90$ constraint regions, many of which must be scanned and evaluated as the result of each move. Further, the large size of the $16 \times 16$ board makes checking even a single row, column or (longer) diagonal a tedious process, let alone the many others that must be checked as well. Fully Diagonal Sudoku fails as an entertaining game concept.

4. Design #2: Locally diagonal sudoku

The next design iteration was to modify rule #3 from “No number is repeated along any diagonal line” to “The diagonal neighbours of a number do not repeat that number”, as shown in Table 4. This has the effect of reducing the global diagonal constraint regions to local “X” shaped regions, as shown in Figs 6.

This design has the benefit of introducing new strategies to classic Sudoku (due to the local “X” regions) while simplifying the equipment. However, a problem immediately became apparent in that diagonally opposite neighbours within a local “X” region could be repeated according to this new rule set, as shown in Fig. 5 (right). This runs counter to the general “no repeated number within a region” theme of the Sudoku family of puzzles, and creates a cognitive dissonance that makes the player want to re-check the rules whenever this occurs. This rule set was therefore also workable but not satisfying as a game.

Table 4
Rules for locally diagonal sudoku

Frame $9 \times 9$ square grid.

Start Some hint values (1..9) are shown.

Aim Fill the grid with numbers 1..9 such that:

1. No number is repeated in any row.

2. No number is repeated in any column.

3. The diagonal neighbours of a number do not repeat that number.

Fig. 5.

Locally diagonal sudoku: Diagonal neighbours cannot repeat the same number (left) but diagonally opposite neighbours can (right) which intuitively feels wrong.

5. Design #3: Ludoku

The final iteration of the design involved changing rule #3 to qualify that the diagonal neighbours of a number “do not repeat that number or each other”, as summarised in Table 5 and shown in Fig. 6. This rule set solves the problems encountered with previous iterations, and represents a Sudoku variant that simplifies the classic grid design while adding new strategies without adding undue complexity to the rules.

This variant was named Ludoku as a contraction of “local Sudoku”. It does not have any known precedent, according to Sudoku publisher and proprietary owner Nikoli.3

³
Private communication with Nikoli’s chief editor Yoshinao Anpuku.

One design issue is that Ludoku contains 77 “X” regions – one centred on each cell minus the four corners (which are subsets of their diagonally adjacent neighbours) – giving a total of $9 + 9 + 77 = 95$ constraint regions for the overall puzzle. This is a far greater number than classic Sudoku’s 27 constraint regions, but the small size of each “X” region keeps this overhead manageable, although does make Ludoku harder than classic Sudoku.

Table 5

Rules for Ludoku

Frame	$9 \times 9$ square grid.
Start	Some hint values (1..9) are shown.
Aim	Fill the grid with numbers 1..9 such that:
	1. No number is repeated in any row.
	2. No number is repeated in any column.
	3. The diagonal neighbours of a number do not repeat that number or each other.

Fig. 6.

Ludoku: Diagonally opposite neighbours cannot be repeated.

6. Evaluation

Now that a viable rule set had been devised, computer analysis was used to evaluate its potential as a game and to generate interesting and aesthetically pleasing challenges. Challenges were evaluated based on the successive application of increasingly complex solution strategies.

6.1. Strategies

Several dozen different solution strategies are known for classic Sudoku (Stuart, 2013). Many of the most commonly used strategies can be collapsed into the following three basic strategy types, which were implemented in a Ludoku solver program.

(a) Naked( $n : n ⩾ 1$ ). For each region R, if any n cells are reduced to the same n candidates, then those candidates can be removed from all other cells in R.

The name refers to the fact that values are exposed by the absence of impossible candidates. Naked(1) instantiates values v by eliminating v from all other cells in a region. Naked(2) is equivalent to the “Naked Pairs” strategy used in standard Sudoku, Naked(3) is equivalent to the “Naked Triples” strategy, and Naked(4) is equivalent to the “Naked Quads” strategy (Stuart, 2013).

(b) Hidden( $n : n ⩾ 1$ ). For each region R, if exactly n cells contain the same n candidates among others, then those other candidates can be removed from those cells.

The name refers to the fact that superfluous values that hide valid candidates are eliminated. Hidden(1) instantiates values by eliminating all other values from cells. Hidden(2) is equivalent to the “Hidden Pairs” strategy used in classic Sudoku, Hidden(3) is equivalent to the “Hidden Triples” strategy, and Hidden(4) is equivalent to the “Hidden Quads” strategy (Stuart, 2013). Hidden strategies do not apply to regions that contain fewer than n elements, such as the local ‘X’ subregions.

(c) Cross( $n : n ⩾ 2$ ). If any subset of n regions ${R}$ each contain the same candidate value v exactly n times, then if any other region $R^{'}$ intersects every member of ${R}$ at a cell containing v, then v can be eliminated from all other cells in $R^{'}$ .

The name refers to the fact that regions cross-reference each other to eliminate impossible candidates. Cross(1) is not needed as the same result is given by applying Naked(1) and Hidden(1). Cross(2) is equivalent to the “X-Wing” strategy used in classic Sudoku, Cross(3) is equivalent to the “Swordfish” strategy, and Cross(4) is equivalent to the “Jellyfish” strategy (Stuart, 2013).

6.2. Deducibility

The solution strategies listed above were successively applied, in increasing order of complexity, using the steps outlined in Algorithm 1. Strategies were applied until either a unique solution was derived, in which case the challenge was deemed deducible, or no unique solution could be determined, in which case the challenge was deemed non-deducible.

The function hidden( $state$ , n) applies eliminations due to Hidden(n) strategies and returns whether any updates were made. The function naked( $state$ , n) applies eliminations due to Naked(n) strategies and returns whether any updates were made. The function cross( $state$ , n) applies eliminations due to State(n) strategies and returns whether any updates were made.

Algorithm 1

Deducibility test for Ludoku challenges

Note that the more sophisticated Deductive Search (DS) method that had previously been applied to similar logic puzzles (Browne, 2013) was not used here. While DS allows for deeper higher-level deductions to be made, this was found to be unnecessary for Ludoku, as it is inherently more difficult than classic Sudoku, and the base strategies outlined above allowed sufficient variety in solution for interesting challenges to occur and be detected.

Challenges were scored for quality by recording the sequence of strategies applied and performing the following calculation: $\begin{matrix} (1) & quality = variety + coverage - help \end{matrix}$ where variety is the number of times the player must apply a different strategy type to progress towards solution (to encourage interplay between strategies), coverage is the minimum number of times any one strategy is applied (to encourage the use of all strategies), and help is the number of starting hints (to encourage fewer starting hints).

This quality estimate gives some indication of the strategic depth of challenges but does not always capture how truly difficult a challenge is for the human player. Hence, the difficulty of each challenge was also estimated by its degree, given by the accumulated total of the parameter (1, 2 or 3) to each strategy that was successfully applied. The rationale behind this measurement is that deductions are harder for the human player the more regions are involved.

These measurements were used to automatically rank challenges for their potential to interest human players, with high-scoring examples then being hand-tested for more accurate evaluation. Notably, the solution process of Algorithm 1 tends to follow a similar series of deductive steps to when the same challenges are solved by hand, suggesting that the algorithm provides a fair model of how humans approach solving them.

7. Generation

We define an $n \times n$ Ludoku packing as a packing of the numbers $1.. n$ in an $n \times n$ grid such that the Ludoku rules are respected, i.e. no number is repeated within any row, column or local “X” region. Algorithm 2 shows the steps used to automatically generate Ludoku challenges.

Firstly, a random $n \times n$ Ludoku packing is generated on-the-fly. Then, starting with all hints visible, hints are iteratively removed until a final pattern of starting hints remains. Three types of hint patterns are generated:

purely random hint patterns (10% frequency),

based on pre-defined symmetric hint patterns (10% frequency), and

randomly removed in symmetric sets, for a symmetric result (80% frequency).

Hint patterns that produce a deducible challenge are measured for quality, ranked and stored for future testing. Purely random hint patterns are useful for finding edge cases, such as the 15-hint challenge4

⁴
By comparison, no deducible Sudoku challenge can have fewer than 17 hints (McGuire et al., 2013).

shown in Fig. 7. Deducible challenges with even fewer hints might be possible if additional strategies are used. The packing step typically takes less than 1s on a single i7 thread, then each evaluation during the hint removal process is measured in the milliseconds.

Algorithm 2

Generation of $n \times n$ Ludoku challenges

However, symmetrical hint patterns are generally preferred as they are more aesthetically pleasing, and suggest care and planning in their preparation that can give an impression of higher quality. The mere presence of symmetry in challenges can be enough to give puzzle solvers the impression that some automatically generated challenges were actually handcrafted by human designers (Browne, 2013).

Fig. 7.

A deducible 15-hint Ludoku challenge.

7.1. Pre-defined hint patterns

Figure 8 shows three of the pre-defined hint patterns. The number in each cell shows the total number of visible hints contained in regions passing through that cell, which gives an indication of the amount of constraint information available to each cell. Higher values indicate greater constraint, and in logic puzzles it is usually beneficial to focus on the point of most constraint at each step.

The different distributions of cell totals give each pattern a different character. The “diamond” pattern has a high-value cell at its centre with 12 shared hints that is likely to be deduced, but the available information dissipates quickly the farther a cell is from the centre. Challenges based on this pattern would typically be solved from the centre outwards. The “asymptotes” pattern, on the other hand, has a low-value centre cell surrounded by four high-value neighbours.

Fig. 8.

Pre-defined hint patterns: “diamond”, “asymptotes” and “circle”.

The “circle” pattern is more rounded, so to speak, with a reasonably homogenous distribution of cell totals over most of its area, apart from the outermost cells. This is the most pleasing design found so far, both aesthetically and in terms of deductive flow during the solution of the challenges that it produces.

The majority of the resulting highly ranked challenges are difficult and engaging – exactly what is required in this type of puzzle. Ludoku is more difficult than Sudoku, on average, with extreme examples taking an hour or more to solve. Figure 9 shows two of my favourite Ludoku challenges generated so far, with hints fortuitously placed to drip-feed enough information to the conscientious player to allow progress towards solution. For an easier example see (Browne and Ludoku, 2017).

Fig. 9.

Two of my favourite Ludoku challenges generated so far.

8. Conclusion

Ludoku is a new Sudoku variant that simplifies the board design and introduces new strategies without adding undue rule complexity. It has similar strategic depth to Sudoku, and while its greater number of local constraints makes it harder work and more difficult to solve, it answers the initial research question: Yes, Sudoku can be simplified to produce a novel and worthwhile variant.

Future work might involve evaluating the generated challenges through player testing, keeping an eye out for new strategies found by players and determining the accuracy of the quality and difficulty metrics. It would also be interesting to decompose and program the possible design features of Sudoku-like puzzles, so that the puzzle design process may be fully automated.

Footnotes

Acknowledgements

Thanks to Stephen Tavener, Néstor Romeral Andrés, Robin Barrett, Russell Williams, Richard Reilly and Craig Duncan for comments. Some of this work was conducted while the author was with the RIKEN Institute’s Advanced Intelligence Project (AIP) in Tokyo, Japan. The author is sponsored by ERC Consolidator Grant 771292 The Digital Ludeme Project.

References

Bell, J. & Stevens, B. (2009). A survey of known results and research areas for n-queens. Discrete Mathematics, 309, 1–31. doi:10.1016/j.disc.2007.12.043.

Browne, C. (2013). Deductive search for logic puzzles. In Proceedings of Computational Intelligence & Games (CIG ’13) (pp. 1–8). Niagara Falls: IEEE.

Browne, C. (2015). Explore the design space. Game & Puzzle Design, 1(2), 71–83.

Browne, C. (2016). Nothing new under the sun. Game & Puzzle Design, 2(2), 3–4.

Browne, C. (2017). Reinvent the wheel. Game & Puzzle Design, 3(1), 51–62.

Browne, C. (2017). Ludoku: A game design experiment. Game & Puzzle Design, 3(2), 35–46.

Browne, C. (2013). Metrics for better puzzles. In

M.S.

El-Nasr et al. (Eds.), Game Analytics: Maximizing the Value of Player Data (pp. 769–800). Berlin: Springer. doi:10.1007/978-1-4471-4769-5_34.

Chvátal, V. (2016). Colouring the Queen Graphs. http://users.encs.concordia.ca/~chvatal/queengraphs.html.

Collins, N. (2012). World’s Hardest Sudoku: Can You Crack It? The Telegraph: Science, 28.

10.

Gardner, M. (1969). The Unexpected Hanging and Other Mathematical Diversions. New York: Simon and Schuster.

11.

Kanamoto, N. (2001). A Well-Made Sudoku is a Pleasure to Solve. Nikoli. http://www.nikoli.co.jp/en/puzzles/why_hand_made.html.

12.

Kim, S. (2005). Creative plagiarism. In Shufflebrain Casual Games Conference, Seattle. http://slideplayer.com/slide/4347248/ .

13.

McGuire, G., Tugemanny, B. & Civario, G. (2013). There is No 16-Clue Sudoku. http://arxiv.org/pdf/1201.0749.pdf.

14.

Stuart, A. (2013). SudokuWiki.org: Strategies for Number Puzzles of All Kinds. http://www.sudokuwiki.org .

15.

Sudoku Variants. Sterling Publishing, New York (2006).

16.

The Times Japanese Logic Puzzles: Hitori, Hashi, Slitherlink and Mosaic. Harper Collins, London (2006).