NAME
Regexp::Sudoku - Solve Sudokus with regular expressions.
SYNOPSIS
use Regexp::Sudoku;
my $sudoku = Regexp::Sudoku:: -> new -> init (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";
}
}DESCRIPTION
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 and initializing a sudoku object using new and init (see below), the object can be queried with subject and pattern. subject returns a string, while pattern returns a pattern (as a string).
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 "%{^CAPTURE}" in perlvar).
The init method takes the following named parameters:
clues => STRING | ARRAYREF
The clues parameter is used to pass in the clue (aka givens) of a suduko. 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 than9 x 9, capital letters are used, up to'Z'for a35 x 35sudoku. '.',0,"", C << undef >>-
These values indicate the sudoku does not have a clue for the corresponding cell: the cell is blank.
""andundefcan 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 least15 x 15), and is different from'e'). 'o'-
This indicates the cell should have an odd number in its solution. (Note that
'O'indicates a clue (if the size is at least25 x 25), and is different from'o').
size => INTEGER
This is used to indicate the size of a sudoku. The default size is a 9 x 9 sudoku. A size which exceeds 35 is a fatal error.
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:
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 5Sizes which are perfect squares (marked with * in the table above) lead to square boxes.
houses => MASK
For sudoku variants with extra houses, this parameter is used to indicate which extra houses are used. 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.
We recognize the following values (imported from Regexp::Sudoku::Constants):
$NRC-
An NRC sudoku has four additional houses, indicated below with the numbers
1 .. 4. This variant is only defined for9 x 9sudokus:. . . . . . . . . . 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 . . . . . . . . . .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.
$ASTERISK-
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 9sudokus:. . . . . . . . . . . . . * . . . . . . * . . . * . . . . . . . . . . . . * . . * . . * . . . . . . . . . . . . * . . . * . . . . . . * . . . . . . . . . . . . . $GIRANDOLA-
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 9sudokus:* . . . . . . . * . . . . * . . . . . . . . . . . . . . . . . . . . . . . * . . * . . * . . . . . . . . . . . . . . . . . . . . . . . * . . . . * . . . . . . . * $CENTER_DOT-
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, and35; see the table with sizes above). For a9 x 9sudoku, this looks like:. . . . . . . . . . * . . * . . * . . . . . . . . . . . . . . . . . . . . * . . * . . * . . . . . . . . . . . . . . . . . . . . * . . * . . * . . . . . . . . . .
diagonals => MASK
The diagonals parameter is used to indicate the sudoku has one or more constraints on diagonals: all values on the given diagonal(s) should be unique. There are many possible diagonals (34 for a 9 x 9 sudoku, in general, 4 * N - 2 for an N x N sudoku. For a full explanation of all diagonals, see Regexp::Sudoku::Constants.
Here, we will list a couple of the most common ones:
$MAIN-
The main diagonal is the diagonal which runs from the top left to the bottom right. All values on this diagonal should be unique.
* . . . . . . . . . * . . . . . . . . . * . . . . . . . . . * . . . . . . . . . * . . . . . . . . . * . . . . . . . . . * . . . . . . . . . * . . . . . . . . . * $MINOR-
The minor diagonal is the diagonal which runs from the bottom left to the top right. All values on this diagonal should be unique.
. . . . . . . . * . . . . . . . * . . . . . . . * . . . . . . . * . . . . . . . * . . . . . . . * . . . . . . . * . . . . . . . * . . . . . . . * . . . . . . . . $CROSS-
This is a combination of main and minor diagonal constaints. The values on each of diagonals should be unique.
* . . . . . . . * . * . . . . . * . . . * . . . * . . . . . * . * . . . . . . . * . . . . . . . * . * . . . . . * . . . * . . . * . . . . . * . * . . . . . . . * $DOUBLE-
$DOUBLEis used for a sudoku variant with four diagonals having unique values: the diagonals just above/below the main and minor diagonals:. * . . . . . * . * . * . . . * . * . * . * . * . * . . . * . * . * . . . . . * . * . . . . . * . * . * . . . * . * . * . * . * . * . . . * . * . * . . . . . * . $ARGYLE-
Argyle sudokus have eight diagonals on which the values should be unique. 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.
. 1 . . 5 . . 3 . 2 . 1 6 . 5 3 . 4 . 2 6 1 . 3 5 4 . . 6 2 . 1 . 4 5 . 6 . . 2 . 1 . . 5 . 7 3 . 2 . 1 8 . . 3 7 4 . 2 8 1 . 3 . 4 7 . 8 2 . 1 . 4 . . 7 . . 2 .
constraints => MASK
Some variants have additional constraints, which apply to all cells in the sudoku. We recognize the following values (imported from Regexp::Sudoku::Constants):
$ANTI_KNIGHT-
An anti knight constraint implies that two cells which are a knights move 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 markedO.. . . . . . . . . . . . . . . . . . . . * . * . . . . . * . . . * . . . . . . O . . . . . . * . . . * . . . . . * . * . . . . . . . . . . . . . . . . . . . . . . $ANTI_KING-
Also known as the no touch constraint.
An anti king constraint implies that two cells which are a king move 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 restrictive than the anti knights move restriction.
In the diagram below,
*marks all the cells which are a kings move away from the cell markedO.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . * * * . . . . . . * O * . . . . . . * * * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
BUGS
There are no known bugs.
TODO
Disjoint Groups
Jigsaw
Battenburg
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
German Whisper
Clones
Quadruple
Killer Sudoku
Little Killer Sudoku
Frame Sudoku
Arrow Sudoku
Sandwich
Clock Sudoku
SEE ALSO
DEVELOPMENT
The current sources of this module are found on github, git://github.com/Abigail/Regexp-Sudoku.git.
AUTHOR
Abigail, mailto:cpan@abigail.freedom.nl.
COPYRIGHT and LICENSE
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.
INSTALLATION
To install this module, run, after unpacking the tar-ball, the following commands:
perl Makefile.PL
make
make test
make install