Regexp::Sudoku - Solve Sudokus with regular expressions.
use Regexp::Sudoku; my $sudoku = Regexp::Sudoku:: -> new -> init -> set_clues (<<~ '--'); 5 3 . . 7 . . . . 6 . . 1 9 5 . . . . 9 8 . . . . 6 . 8 . . . 6 . . . 3 4 . . 8 . 3 . . 1 7 . . . 2 . . . 6 . 6 . . . . 2 8 . . . . 4 1 9 . . 5 . . . . 8 . . 7 9 -- my $subject = $sudoku -> subject; my $pattern = $sudoku -> pattern; if ($subject =~ $pattern) { for my $row (1 .. 9) { for my $col (1 .. 9) { print $+ {"R${r}C${c}"}, " "; } print "\n"; } }
This module takes a Sudoku (or variant) as input, calculates a subject and pattern, such that, if the pattern is matched agains the subject, the match succeeds if, and only if, the Sudoku has a solution. And if it has a solution %+ is populated with the values of the cells of the solved Sudoku.
%+
After constructing, initializing and constructing a Sudoku object using new, init and various set_* methods (see below), the object can be queried with subject and pattern. subject returns a string, while pattern returns a pattern (as a string).
new
init
set_*
subject
pattern
Once the subject has been matched against the pattern, 81 (or rather N ** 2 for an N x N Sudoku) named captures will be set: R1C1 .. R1C9 .. R9C1 .. R9C9. These correspond to the values of the cells of a solved Sudoku, where the cell in the top left is named R1C1, the cell in the top right R1C9, the cell in the bottom left R9C1 and the cell in the bottom right R9C9. In general, the cell on row r and column c is named RrCc. Named captures are available in %+ (see perlvar).
N ** 2
N x N
R1C1
R1C9
R9C1
R9C9
r
c
RrCc
For regular, 9 x 9 Sudokus, one would just call new, init and set_clues. Various variants need to call different methods.
9 x 9
set_clues
Unless specified otherwise, all the methods below return the object it was called with; this methods can be chained.
new ()
This is a class method called on the Regexp::Sudoku package. It takes no arguments, and just returns an uninitialized object. (Basically, it just calls bless for you).
Regexp::Sudoku
bless
init ()
init initializes the Sudoku object. This method must be called on the return value of new before calling any other methods.
init takes one, optional, (named) argument.
size => INTEGER
Usually, Sudokus are 9 x 9. For a Sudoku of a different size, we need to pass in the size. Smallest size for which Sudokus exist, is 4. Largest size we accept is 35. For a Sudoku with a size exceeding 9, we will letters as values. (So, for a 12 x 12 Sudoku, we have 1 .. 9, 'A', 'B' as values.)
4
35
12 x 12
1 .. 9, 'A', 'B'
The size directly influences the size of the boxes (the rectangles where each of the numbers appears exactly once). For a size N, the size of a box will be those integers p and q where N = p * q, and which minimizes abs (p - q). Common sizes lead to the following box sizes:
N
p
q
N = p * q
abs (p - q)
size (N x N) | box size (width x height) =============+========================== 4 * | 2 x 2 6 | 3 x 2 8 | 4 x 2 9 * | 3 x 3 (Default) 10 | 5 x 2 12 | 4 x 3 15 | 5 x 3 16 * | 4 x 4 24 | 6 x 4 25 * | 5 x 5 30 | 6 x 5 35 | 7 x 5
Sizes which are perfect squares (marked with * in the table above) lead to square boxes.
*
A size which is a prime number leads to boxes which are identical to rows -- you would need to configure different boxes.
set_clues (STRING | ARRAYREF)
The set_clues method is used to pass in the clues (aka givens) of a Suduko. Most Sudokus will have at least one clue, but there are a few variants which allow clueless Sudokus. For a standard 9 x 9 Sudoku, the minimum amount of clues is 17.
The clues are either given as a string, or a two dimensional arrayref.
In the case of a string, rows are separated by newlines, and values in a row by whitespace. The first line of the string corresponds with the first row of the Sudoku, the second line with the second row, etc. In each line, the first value corresponds with the first cell of that row, the second value with the second cell, etc. In case of an arrayref, the array consists of arrays of values. Each array corresponds with a row, and each element of the inner arrays corresponds with a cell.
The values have the following meaning:
'1' .. '9', 'A' .. 'Z'
This corresponds to a clue/given in the corresponding cell. For standard Sudokus, we use '1' .. '9'. Smaller Sudokus use less digits. For Sudokus greater than 9 x 9, capital letters are used, up to 'Z' for a 35 x 35 Sudoku.
'1' .. '9'
'Z'
35 x 35
'.'
0
""
undef
These values indicate the Sudoku does not have a clue for the corresponding cell: the cell is blank. "" and undef can only be used if the array form is being used.
'e'
This indicates the cell should have an even number in its solution. (Note that 'E' indicates a clue (if the size is at least 15 x 15), and is different from 'e').
'E'
15 x 15
'o'
This indicates the cell should have an odd number in its solution. (Note that 'O' indicates a clue (if the size is at least 25 x 25), and is different from 'o').
'O'
25 x 25
A house is a region which contains each of the numbers 1 .. 9 (or 1 .. N for an N x N sized Sudoku) exactly once. With a standard Sudoku, each row, each column, and each 3 x 3 box is a house.
1 .. 9
1 .. N
3 x 3
Some variants have additional houses, next to the rows, columns and boxes. In this section, we describe the methods which can be used to configure the Sukodu to have additional houses.
set_nrc_houses ()
An NRC Sudoku has four additional houses, indicated below with the numbers 1 .. 4. This variant is only defined for 9 x 9 Sudokus:
1 .. 4
. . . . . . . . . . 1 1 1 . 2 2 2 . . 1 1 1 . 2 2 2 . . 1 1 1 . 2 2 2 . . . . . . . . . . . 3 3 3 . 4 4 4 . . 3 3 3 . 4 4 4 . . 3 3 3 . 4 4 4 . . . . . . . . . .
Calling the set_nrc_houses () sets up those houses.
The NRC Sudoku is named after the Dutch newspaper NRC, which first publishes such a Sudoku and still publishes one daily. It is also known under the names Windoku and Hyper Sudoku.
set_asterisk_house ()
An asterisk Sudoku has an additional house, roughly in the shape of an asterisk, as indicated below. This variant is only defined for 9 x 9 Sudokus:
. . . . . . . . . . . . . * . . . . . . * . . . * . . . . . . . . . . . . * . . * . . * . . . . . . . . . . . . * . . . * . . . . . . * . . . . . . . . . . . . .
Calling the set_asterisk_house () sets up those houses.
set_girandola_house ()
An girandola Sudoku has an additional house, roughly in the shape of a windmill pinwheel (a childs toy), as indicated below. This variant is only defined for 9 x 9 Sudokus:
* . . . . . . . * . . . . * . . . . . . . . . . . . . . . . . . . . . . . * . . * . . * . . . . . . . . . . . . . . . . . . . . . . . * . . . . * . . . . . . . *
Calling the set_girandola_house () sets up those houses.
set_center_dot_house ()
A center dot house is an additional house which consists of all the center cell of all the boxes. This is only defined for Sudokus where the boxes have odd sizes. (Sizes 9, 15, 25, and 35; see the table with sizes above). For a 9 x 9 Sudoku, this looks like:
9
15
25
. . . . . . . . . . * . . * . . * . . . . . . . . . . . . . . . . . . . . * . . * . . * . . . . . . . . . . . . . . . . . . . . * . . * . . * . . . . . . . . . .
Calling the set_center_dot_house () sets up those houses.
A common constraint used in variant Sudokus is uniqueness of one or more diagonals: all the values on each of the marked diagonals should be unique.
The main diagonal of a Sudoku is the diagonal which runs from the top left to the bottom right. The minor diagonal the diagonal which runs from the top right to the bottom left.
\ . . . . . . . . . . . . . . . . / . \ . . . . . . . . . . . . . . / . . . \ . . . . . . . . . . . . / . . . . . \ . . . . . . . . . . / . . . . . . . \ . . . . . . . . / . . . . . . . . . \ . . . . . . / . . . . . . . . . . . \ . . . . / . . . . . . . . . . . . . \ . . / . . . . . . . . . . . . . . . \ / . . . . . . . . Main Diagonal Minor Diagonal
A super diagonal is a diagonal which parallel and above of the main or minor diagonal. A sub diagonal is a diagonal which runs parallel and below the main or minor diagonal. Super and sub diagonals have an offset, indicating their distance from the main or minor diagonal. The super and sub diagonal directly next to the main and minor diagonals have an offset of 1. The maximum offset for an N x N Sudoku is N - 1, although such an offset reduces the diagonal to a single cell.
N - 1
. \ . . . . . . . . . . . . . . / . . . \ . . . . . . . . . . . . / . . \ . . \ . . . . . . . . . . / . . / . \ . . \ . . . . . . . . / . . / . . . \ . . \ . . . . . . / . . / . . . . . \ . . \ . . . . / . . / . . . . . . . \ . . \ . . / . . / . . . . . . . . . \ . . \ / . . / . . . . . . . . . . . \ . . . . / . . . . . . Super and sub diagonals Super and sub diagonals off the main diagonal off the minor diagonal
In total, an N x N Sudoku can have 4 * N - 2 diagonals (34 for a standard 9 x 9 Sudoku).
4 * N - 2
There will be a method to set uniqness for each possible diagonal.
set_diagonal_main ()
This method sets a uniqness constraint on the main diagonal.
set_diagonal_minor ()
This method sets a uniqness constraint on the minor diagonal.
set_diagonal_main_super_1 () .. set_diagonal_main_super_34 ()
These methods set uniqness constraints on super diagonals parallel to the main diagonal, with the given offset. If the offset equals or exceeds the size of the Sudoku, the diagonal falls completely outside of the Sudoku, and hence, does not add a constraint.
set_diagonal_main_sub () .. set_diagonal_main_sub ()
These methods set uniqness constraints on sub diagonals parallel to the main diagonal, with the given offset. If the offset equals or exceeds the size of the Sudoku, the diagonal falls completely outside of the Sudoku, and hence, does not add a constraint.
set_diagonal_minor_super_1 () .. set_diagonal_minor_super_34 ()
These methods set uniqness constraints on super diagonals parallel to the minor diagonal, with the given offset. If the offset equals or exceeds the size of the Sudoku, the diagonal falls completely outside of the Sudoku, and hence, does not add a constraint.
set_diagonal_minor_sub () .. set_diagonal_minor_sub ()
These methods set uniqness constraints on sub diagonals parallel to the minor diagonal, with the given offset. If the offset equals or exceeds the size of the Sudoku, the diagonal falls completely outside of the Sudoku, and hence, does not add a constraint.
It is quite common for variants which have constraints on diagonals to do so in a symmetric fashion. To avoid having to call multiple set_diagonal_* methods, we provide a bunch of wrappers which set uniqness constraints on two or more diagonals.
set_diagonal_*
set_cross ()
A common variant has uniqness constraints for both the main and minor diagonal -- this variant is widely known under the name X-Sudoku. set_cross () sets the uniqness constraints for both the main and minor diagonals:
\ . . . . . . . / . \ . . . . . / . . . \ . . . / . . . . . \ . / . . . . . . . X . . . . . . . / . \ . . . . . / . . . \ . . . / . . . . . \ . / . . . . . . . \ Cross constraints
set_cross_1 () .. set_cross_34 ()
Each of the set_cross_N () methods enable a uniqness constraint on four diagonals: the super and sub diaganols (relative to both the main and minor diagonals) with offset N. Note that if N is equal, or exceeds the size of the Sudoku, all the diagonals lie fully outside the Sudoku, rendering the method useless.
set_cross_N ()
set_diagonal_double ()
This method enables a uniqness constraints on the diagonals parallel, and directly next to the main and minor diagonals. This is method is equivalent to set_cross_1.
set_cross_1
. \ . . . . . / . \ . \ . . . / . / . \ . \ . / . / . . . \ . X . / . . . . . X . X . . . . . / . X . \ . . . / . / . \ . \ . / . / . . . \ . \ . / . . . . . \ . Diagonal Double
set_diagonal_triple ()
This methods enables uniqness constraints on six diagonals: the main and minor diagonals, and the diagonals parallel to them, and directly next to them. Calling this method is equivalent to calling both set_cross () and set_diagonal_double ().
\ \ . . . . . / / \ \ \ . . . / / / . \ \ \ . / / / . . . \ X X X / . . . . . X X X . . . . . / X X X \ . . . / / / . \ \ \ . / / / . . . \ \ \ / / . . . . . \ \ Diagonal Triple
set_argyle ()
The Argyle Sudoku variant has uniqness constraints on eight diagonals. This is named after a pattern consisting of lozenges, which itself was named after the tartans of the Clan Cambell in Argyll in the Scottish highlands.
Calling set_argyle () is equivalent to calling set_cross_1 () and set_cross_4 ().
set_cross_1 ()
set_cross_4 ()
. \ . . X . . / . \ . \ / . \ / . / . \ / \ . / \ / . . / \ . X . / \ . X . . X . X . . X . \ / . X . \ / . . / \ / . \ / \ . / . / \ . / \ . \ . / . . X . . \ . Argyle Pattern
There are Sudoku variants which enable specific constraints on all the cells in the Sudoku.
set_anti_knight_constraint ()
An anti knight constraint implies that two cells which are a knights move (as in classical Chess) apart must have different values. (A knights move is first two cells in an orthognal direction, then one cell perpendicular). For each cell, this puts a restriction to up to eight different cells. In the diagram below, * marks all the cells which are a knights move away from the cell marked O.
O
. . . . . . . . . . . . . . . . . . . . * . * . . . . . * . . . * . . . . . . O . . . . . . * . . . * . . . . . * . * . . . . . . . . . . . . . . . . . . . . . . Anti Knight Constraint
set_anti_king_constraint ()
Also known as the no touch constraint.
An anti king constraint implies that two cells which are a kings move (as in classical Chess) apart must have different values. (A kings move is one step in any of the eight directions).
For each cell, this puts a restriction to up to eight different cells. Four of them are already restricted because they are one the same row or columns. And at least one kings move will end in the same box. So, this restriction is far less restrictive than the anti knights move restriction.
In the diagram below, * marks all the cells which are a kings move away from the cell marked O.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . * * * . . . . . . * O * . . . . . . * * * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Anti King Constraint
set_renban (LIST)
A Renban line (or area) consist of a number of cells where all the values should form a consecutive sets of numbers. The numbers do not have to be in order. For example, a Renban area of size four may contain the numbers 5-7-4-6 or 2-3-4-5, but not 2-3-5-6.
5-7-4-6
2-3-4-5
2-3-5-6
This method takes a list of cell names as argument, where each name is of the form RxCy, with 1 <= x, y <= N, where N is the size of the Sudoku.
RxCy
1 <= x, y <= N
No validation of cell names is performed. Names which aren't of the form RxCy, or which are outside of the Sudoku have no effect. A Renban area with more cells than the size of the Sudoku leads to an unsolvable Sudoku.
This method can be called more than once, and should be called more than once if a Sudoku has more than one Renban line/area.
set_german_whisper (LIST)
A German Whisper line consists of two and more cells, where two consecutive cells should differ by at least 5 (or, for Sudoku's which aren't of size 9, at least half the size). So, a 7 may be next to a 1 or 2, but not next to any other number. The order of the cells matter: they should be in the same order as the German Whisper line.
7
1
2
The same number may appear more than once on a German Whisper line, if it doesn't violate any other constraint. The length of a German Whisper line is at least 2, but it can be longer than the size of the Sudoku.
No validation of cell names is performed. Names which aren't of the form RxCy, or which are outside of the Sudoku have no effect.
This method can be called more than once, and should be called more than once if a Sudoku has more than one German Whisper line.
set_battenburg (LIST)
set_anti_battenburg (LIST)
A Battenburg is a 2 x 2 block of cells with the odd and evens in an Batterburg pattern: one diagonal has two cells with even values; the other diagonal has two cells with odd values.
2 x 2
An anti-Battenburg is a 2 x 2 block of cells which does not have a Battenburg pattern for the odd and even cells. (That is, it either has a diagonal with an even and an odd cell, or all the cells have the same parity).
Battenburgs and anti-Battenburgs are identified by their top-left cell:
set_battenburg ("R3C5")
signals that the four cells R3C5, R3C6, R4C6, and R4C5 have their odd and even cells in a Battenburg pattern. Hence, either R3C5 and R4C6 are odd and R3C6 and R4C5 are even, or R3C5 and R4C6 are even and R3C6 and R4C5 are odd.
R3C5
R3C6
R4C6
R4C5
set_anti_battenburg ("R6C3", "R7C6")
signals that the four cells R6C3, R6C4, R7C4 and R7C3 do not form a Battenburg pattern with their odd and even values, and that the same is true for the four cells R7C6, R7C7, R8C7, and R8C6.
R6C3
R6C4
R7C4
R7C3
R7C6
R7C7
R8C7
R8C6
set_quadruples (HASH)
A quadruple constraint is a set of one to four numbers which must appear on a 2 x 2 block. The set of numbers may contain duplicates, but a number appearing three times or more is impossible, as each 2 x 2 block is covered by no more than two rows (and two columns) and values should be unique in each row and column.
The 2 x 2 blocks are identified by the name of their upper left corner cell. The HASH which is taken as an argument to this method maps cell names (the ones identifying the 2 x 2 block) to an arrayref containing the values.
HASH
set_quadruples (R2C2 => [6, 7], R6C5 => [3, 4, 5, 5])
This means the that at least one of the cells R2C2, R2C3, R2C3 and R3C3 contain the number 6, and the same set of cells contains at least one 7. And the set of cells R6C5, R6C6, R7C5, and R7C6 contain a 3, a 4 and two 5's.
R2C2
R2C3
R3C3
6
R6C5
R6C6
R7C5
3
5
There are no known bugs.
Disjoint Groups
Jigsaw
Greater Than
Thermo
Slow Thermo
Rossini
Consecutive Sudoku
Non-consecutive Sudoku
Kropki
Absolute difference = 1
Other differences
Ratio 1:2
Other ratios
XV Sudoku
CL Sudoku
Outsize Sudoku
Young Tableaux
Palindromes
Renban lines
Nabner
Clones
Killer Sudoku
Little Killer Sudoku
Frame Sudoku
Arrow Sudoku
Sandwich
Clock Sudoku
The current sources of this module are found on github, git://github.com/Abigail/Regexp-Sudoku.git.
Abigail, mailto:cpan@abigail.freedom.nl.
Copyright (C) 2021-2022 by Abigail.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
To install this module, run, after unpacking the tar-ball, the following commands:
perl Makefile.PL make make test make install
To install Regexp::Sudoku, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Regexp::Sudoku
CPAN shell
perl -MCPAN -e shell install Regexp::Sudoku
For more information on module installation, please visit the detailed CPAN module installation guide.