NAME

Regexp::Sudoku - Solve Sudokus with regular expressions.

SYNOPSIS

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";
   }
}

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

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

For regular, 9 x 9 Sudokus, one would just call new, init and set_clues. Various variants need to call different methods.

Unless specified otherwise, all the methods below return the object it was called with; this methods can be chained.

Main methods

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

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

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 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.
'.', 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').
'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').

Additional Houses

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.

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

. . .  . . .  . . .
. * .  . * .  . * .
. . .  . . .  . . .

. . .  . . .  . . .
. * .  . * .  . * .
. . .  . . .  . . .

. . .  . . .  . . .
. * .  . * .  . * .
. . .  . . .  . . .

Calling the set_center_dot_house () sets up those houses.

Diagonals

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.

 . \ .  . . .  . . .            . . .  . . .  . / .
 . . \  . . .  . . .            . . .  . . .  / . .
 \ . .  \ . .  . . .            . . .  . . /  . . /

 . \ .  . \ .  . . .            . . .  . / .  . / .
 . . \  . . \  . . .            . . .  / . .  / . .
 . . .  \ . .  \ . .            . . /  . . /  . . .

 . . .  . \ .  . \ .            . / .  . / .  . . .
 . . .  . . \  . . \            / . .  / . .  . . .
 . . .  . . .  \ . .            . . /  . . .  . . .

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

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.

Crosses and other diagonal sets

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

. \ .  . . .  . / .
\ . \  . . .  / . /
. \ .  \ . /  . / .

. . \  . 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 ().

. \ .  . X .  . / .
\ . \  / . \  / . /
. \ /  \ . /  \ / .

. / \  . X .  / \ .
X . .  X . X  . . X
. \ /  . X .  \ / .

. / \  / . \  / \ .
/ . /  \ . /  \ . \
. / .  . X .  . \ .

   Argyle Pattern

Global constraints

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

 . . *  . * .  . . .
 . . .  . . .  . . .
 . . .  . . .  . . .

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

Restricted lines and areas

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

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.

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.

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.

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.

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.

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.

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.

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

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.

BUGS

There are no known bugs.

TODO

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

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

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

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.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)

NAME

SYNOPSIS

DESCRIPTION

Main methods

new ()

init ()

set_clues (STRING | ARRAYREF)

Additional Houses

set_nrc_houses ()

set_asterisk_house ()

set_girandola_house ()

set_center_dot_house ()

Diagonals

set_diagonal_main ()

set_diagonal_minor ()

set_diagonal_main_super_1 () .. set_diagonal_main_super_34 ()

set_diagonal_main_sub () .. set_diagonal_main_sub ()

set_diagonal_minor_super_1 () .. set_diagonal_minor_super_34 ()

set_diagonal_minor_sub () .. set_diagonal_minor_sub ()