Polyform Puzzler — Frequently Asked Questions

Author: David Goodger <goodger@python.org>
Date: 2016-11-29
Revision: 636
Web site:http://puzzler.sourceforge.net/
Copyright: © 1998-2016 by David J. Goodger
License:GPL 2
images/puzzler.png

Also see:

Contents

1   The Project

1.1   What is "Polyform Puzzler"?

Polyform Puzzler is a set of solvers for many polyform puzzles (like Pentominoes and Soma Cubes), and a software toolkit for exploring & solving polyform puzzles. It consists of a set of front-end applications for specific polyform puzzles and a Python library that does the heavy lifting. New polyforms and new puzzles can easily be defined and added to the core.

1.2   How did Polyform Puzzler begin?

I first discovered Pentominoes in Arthur C. Clarke's novel Imperial Earth, probably around the time I was 11 or 12 years old. I picked up a pentominoes puzzle ("Hexed", by Gabriel Toys) at a local hobby store and spent many hours discovering solutions.

In university, probably while avoiding legitimate study, I wrote the first implementation of a Pentominoes-solving project, in Object Pascal. I developed an algorithm that solved the puzzle using brute force with some intelligence applied:

  • Place each pentomino in every possible location.
  • Confirm that the remaining empty spaces all have areas that are a multiple of 5 squares.
  • For areas of exactly 5 squares, determine the piece that fits and confirm its availability.
  • Check for bottlenecks that force a subset of the remaining space to accept only a single specific piece, and confirm its availability.

When I first learned Python, I reimplemented this as a practical learning exercise. I improved the algorithm a bit and got it to work pretty well, if not completely bug-free. It was a fun and interesting exercise, but the code was complicated and ran slow. (It didn't help that I only had a 66MHz computer at the time.)

I even went so far as to register the "puzzler" project on SourceForge, but didn't take it any further at that time. I had scratched my itch enough, and another itch became more persistent...

While writing the second implementation and learning Python I discovered Python docstrings and started looking around for auto-documentation systems to exploit them. I couldn't find anything that worked well for me, so I started scratching that itch, and eventually reStructuredText & Docutils were born. You could say that Polyform Puzzler spawned Docutils.

In the summer of 2006 I discovered a new approach for solving polyform puzzles, Donald Knuth's "Dancing Links Algorithm X" ("DLX") approach to the "exact cover" problem, described below. This approach was so different from what I'd done previously, and so obviously superior, that my old itch resurfaced. Polyform Puzzler is the result.

1.3   Can others contribute?

Most definitely, yes! See the next question for how.

1.4   How can others contribute?

Python programmers
Please jump right in, there's a lot to do! Patches are welcome, as are new project members (see the next question).
Programmers who don't know Python

Have you considered learning Python? It's a great language, focused on programmer productivity. Python excels at the rapid creation of maintainable code. It's scalable. And it's fun. Give it a try!

There is one area where Python doesn't shine: raw speed. But that can be solved with extension modules written in C. The workhorse of the Polyform Puzzler project, the ExactCover class (implemented in the puzzler.exact_cover_dlx and puzzler.exact_cover_x2 modules), should be rewritten as an extension module in C for speed. See section 4, The Code, for an introduction.

Non-programmers
Have you considered learning to program? It's not as difficult as you think, and it can be loads of fun! Here are some guides for beginners to get you started.
Puzzlers
Use the project, and report on any issues you find. Run a puzzle marked "solutions incomplete" and send me the output. Let me know if you use and enjoy Polyform Puzzler!
Anyone

Do you enjoy Polyform Puzzler and want to say thanks? Is there a puzzle or a feature you'd like to see implemented? (Yes, I can be bribed!) Well, I love real-world, physical polyform puzzles too, and I'd love to receive some! Here's my wish list:

Plus, I have a wish list on Amazon.ca with a bunch of unrelated DVDs and books. My address is available on my résumé.

1.5   Can others join the project?

Most certainly, yes! All you need is a SourceForge account, and they're free. Just click the "Create Account" link on the project page or any SourceForge page.

2   Polyforms

2.1   What are "Polyforms"?

The word "polyform" can be defined from its parts:

poly-
more than one; many
form
shape

According to the Wikipedia definition,

a polyform is a plane figure constructed by joining together identical basic polygons

Wolfram MathWorld's definition:

A plane figure or solid consisting of multiple connected copies of a given base shape.

Regular polygons which tile the plane (fill, without gaps or overlap; a tessellation) are the most satisfying basic polygons for polyform puzzles, and there are three: the equilateral triangle, the square, and the hexagon. Other polygons can be used though. With a given polygon, the set of polyforms of order N is defined by constructing all possible combinations of N copies of that polygon, joined edge to edge, without overlapping. Duplicates (from rotation or reflection) are typically ignored (the "free polyforms"), although some puzzles explicitly treat reflections separately ("one-sided polyforms").

For example, 5 squares can be combined in 12 different ways, resulting in the "pentominoes":

images/ominoes/pentominoes.png

The 12 pentominoes, with their common names.

Many sets of polyforms can combine to fill certain areas or volumes. These can be called "polyform puzzles" or "combinatoric dissection puzzles". For example, the pentominoes can fill a 6x10 rectangle:

images/ominoes/pentominoes6x10.png

One 6×10 pentominoes solution.

There are 2339 distinct ways to fit the pentominoes into a 6x10 rectangle. Polyform Puzzler can find them all.

The definition of polyforms above can be generalized to include:

  • Solids (polyhedra) joined face to face. Regular (Platonic) solids that fill space are the most satisfying, but there is only one Platonic solid that fills space: the cube. Tetrahedra and octahedra together can fill space though. In addition, the truncated octahedron (a semi-regular, Archimedian solid) and the rhombic dodecahedron can each individually fill space, as can other, less regular polyhedra.
  • Line segments of a grid (polysticks, polytrigs, & polytwigs).
  • Two-dimensional squares in a three-dimensional grid: polyominoids.

The sky's the limit!

2.2   What polyforms are there?

There are many possible families of polyforms, with new ones being invented all the time. Polyform Puzzler only deals with a limited number of polyforms; in my opinion the most aesthetically pleasing ones. Polyform families are given descriptive names:

[1]Brian R. Barwell, "Polysticks," Journal of Recreational Mathematics volume 22 issue 3 (1990), p.165-175

2.3   How many of each type of polyform are there?

Hyperlinks in parentheses are to the relevant entries in The On-Line Encyclopedia of Integer Sequences.

2.5   Where can I find physical polyform puzzles?

For a wide variety via internet/mail order, I highly recommend Kadon Enterprises (see my wish list). PuzzleMaster.ca also has a small selection of polyforms, plus a huge selection of other types of puzzles (like the Hanayama "cast puzzle" series, very cool).

I also recommend doing research on the web, then checking out your local toy, game, and puzzle specialty stores. If they don't stock what you want, ask them to get it for you! Here are some sources that I know of:

  • "Blokus" board games:
    • The 21 polyominoes of order 1-5 are used as the playing pieces in the original "Blokus" board game.
    • The 22 polyiamonds of order 1-6 are used as the playing pieces in the "Blokus Trigon" board game.
    • The 11 polycubes of order 2-4 are used as the playing pieces in the "Blokus 3D" board game.
  • Solid pentominoes are commonly available in the "Pocket Play" series by Shoptaugh Games (distributed in Canada and elsewhere by Family Games).
  • Soma Cubes are sold under the name "Block By Block" by ThinkFun.
  • The 24 polysticks of order 1-4 are used as the playing pieces in the "Nexos" board game, designed by the designer of the "Blokus" games.
  • In Japan, many polyform puzzles are available from Tenyo.
  • If you're a puzzle afficionado and happen to find yourself in Tokyo, Japan, Puzzle Shop Torito near Akihabara station is a must-visit. Plan on spending a few hours there (and bring plenty of cash!). They also do internet/mail order, and list their wares on Amazon Japan (where I discovered them).

2.6   Why do you like polyforms so much?

I love challenges. I love solving puzzles. Be it a Rubik's Cube or a logic puzzle or a wire puzzle, I find puzzles hard to resist.

I also love geometrical forms: polygons (especially regular polygons and polygons that tile the plane), polyhedra (especially Platonic and Archimedean solids, space-filling solids, and stellations), geometrical sculpture, and more.

Polyforms combine the challenge of puzzles with the beauty of geometrical forms. Polyforms are constructed by joining together identical basic geometrical units. That the complete sets of various polyforms make beautiful, challenging puzzles is a delight to me.

The fact that all 12 possible forms constructed from 5 squares joined at their edges (the pentominoes) can fill a 6×10 rectangle, is simply a wonder of nature. That there are 2,339 unique solutions is a delight. The 12 solid pentomines (pentominoes 1 unit thick) can form a 3×4×5 solid (consecutive numbers! Pythagorean triangle lengths!) in 3,940 unique ways — but it's a real challenge to find just one.

I love polyforms because of their beauty. It's the beauty of the inner workings of mathematics and geometry, the beauty of the natural world. I get the same delight from polyforms as I get from fractals and snowflakes. The beauty of polyforms is similar to the beauty of crystals, flowers, and galaxies.

images/iamonds/heptiamonds-snowflake-2.png

Heptiamonds snowflake — a beautiful, delightful challenge

3   Polyform Puzzles & Solutions

3.1   What polyform puzzles are supported?

Many polyomino, polyiamond, polyhex, polycube, polystick, polytrig, and polytwig puzzles are supported. For a full list, see the Puzzles & Solutions document. My bias is for regular unit shapes and symmetrical puzzles. More polyform puzzles are to come:

  • other polyominoes (notes)
  • other polycubes (notes)
  • other polyiamonds (notes)
  • other polyhexes (notes)
  • other polysticks (notes)
  • other polytrigs (notes)
  • other polytwigs (notes)
  • and puzzles of new polyforms!

3.2   Why aren't all solutions provided for all puzzles?

Short answer: limited time, space, and interest.

Time: It can take a long time to find all the solutions to a puzzle. Many puzzles have a lot of solutions: thousands, millions, billions... Sometimes I allow puzzles to run to completion even though it takes days or weeks, but usually I don't allow that much time.

Space: The Polyform Puzzler project has limited space for its files. Large numbers of solutions take up a lot of disk space. I will often truncate solution files to save space on the host servers.

Interest: For most puzzles I don't care what the actual number of solutions is. I am content just to know that there are many solutions. I only find and publish a small sample.

If a puzzle has a finite and reasonable number of solutions, say 10000 or fewer, I may find and publish all the solutions (often truncated). If a puzzle has a known number of solutions, I will often find all of them to verify the software and confirm the published number.

If you would like to have all the solutions for a particular puzzle, I encourage you to use the Polyform Puzzler software on your own computer. Some puzzles are already optimized to find unique solutions only, but many are not. See Preventing Duplicates in How to Extend Polyform Puzzler.

3.3   How do you choose puzzle shapes? (What criteria do you use for selecting puzzles to implement?)

My puzzle selection criteria are entirely subjective: I choose to implement the puzzles that I find particularly beautiful or interesting. Beauty, of course, is in the eye of the beholder. I especially like highly symmetrical puzzles.

I welcome suggestions for new puzzles, but I cannot guarantee that I will implement any or all of them.

3.4   How should the solution files be interpreted?

The solution files are text files that all follow a common pattern. The first line states the puzzle matrix class (from a module in the puzzler.puzzles package) being solved:

Solving Pentominoes6x10Matrix:

Some puzzles are split up into several matrices. After all the solutions for one matrix are exhausted, the name of the next matrix will be given.

Each solution record contains three parts. First, the solution header with the solution number:

solution 1:

The second part of the solution record lists the solution coordinates, one piece per line, with the piece name last:

1,1 2,0 2,1 2,2 3,1 X
0,0 0,1 0,2 0,3 1,0 L
3,0 4,0 4,1 4,2 5,1 F
5,0 6,0 6,1 6,2 7,0 T
1,2 1,3 2,3 3,2 3,3 U
0,4 0,5 1,4 1,5 2,4 P
2,5 3,5 4,5 5,5 6,5 I
5,2 5,3 6,3 7,3 7,4 Z
3,4 4,3 4,4 5,4 6,4 Y
7,5 8,5 9,3 9,4 9,5 V
7,1 7,2 8,0 8,1 9,0 W
8,2 8,3 8,4 9,1 9,2 N

The interpretation of coordinates varies by polyform family. See the section below for the specific polyform family you're interested in.

In some puzzles, like the 6x6 tetrasticks, one or more pieces are either omitted from each solution (old style) or placed adjacent to the solution (new style). In old-style solutions such omitted pieces are listed with "!" in place of the coordinates list:

! H

If there are omitted pieces, a notice is prefixed to the visual representation:

(H omitted)

The third part of the solution record is a visual representation of the solution:

P P I I I I I V V V
P P P Y Y Y Y Z N V
L U U U Y Z Z Z N V
L U X U F Z T W N N
L X X X F F T W W N
L L X F F T T T W W

Finally, the number of solutions, the number of searches (software operations executed), and the duration (time taken to complete the execution) are listed:

2339 solutions, 906813 searches, duration 0:19:10.133000

3.5   How should polyomino solution files be interpreted?

See "How should the solution files be interpreted?" above for an overview of solution files.

Polyominoes use a 2-dimensional X,Y cartesian coordinate system.

The visual representation consists of piece names (letters) in a 2-D grid. Imagine each letter as a square, with adjacent like-labelled squares joined. Example (with the x- and y-coordinates also shown):

  5   N Z I I I I I U U U
  4   N Z Z Z P P P U W U
  3   N N T Z X P P W W L
  2   V N T X X X W W F L
  1   V T T T X Y F F F L
y=0   V V V Y Y Y Y F L L

    x=0 1 2 3 4 5 6 7 8 9

In the solution above, the V piece is at (x,y) coordinates (0,0), (0,1), (0,2), (1,0), and (2,0). Its corresponding coordinate line is:

0,0 0,1 0,2 1,0 2,0 V

In Polyform Puzzler:

3.6   How should polycube solution files be interpreted?

See "How should the solution files be interpreted?" above for an overview of solution files.

Polycubes (solid pentominoes, Soma cubes) use a 3-dimensional X,Y,Z cartesian coordinate system.

The visual representation consists of piece names (letters) in multiple layers, each a 2-D slice of a 3-D space. (See "How should polyomino solution files be interpreted?" above to interpret the X & Y coordinates of each slice.) Imagine the layers stacked up from left to right, with each letter as a cube, with adjacent like-labelled cubes joined (z-coordinates of layers shown):

U V V V N    U W T T T    U W Z L Y
U W Z V N    X W Z T Y    U F Z L Y
X W Z V N    X P P T N    X F F L Y
I I I I I    X P P P N    F F L L Y

z=0          z=1          z=2

In the solution above, the U piece is at (x,y,z) coordinates (0,2,0), (0,3,0), (0,3,1), (0,2,2), and (0,3,2). Its corresponding coordinate line is:

0,2,0 0,2,2 0,3,0 0,3,1 0,3,2 U

Some polycube puzzles, like the solid pentomino ring puzzles, are equivalent to a 2-dimensional puzzle folded into 3 dimensions. These puzzles' visual representations consist of the view from each side of the solution, with corners duplicated between adjacent sides:

U U V    V Z Y Y Y Y W T F    F L L    U X P P P L L L L
X U V    V Z Z Z Y W W T F    F F F    X X X P P N N N F
U U V    V V V Z W W T T T    T F N    U X I I I I I N N

In the solution to the 3x3x9 solid pentomino ring puzzle above, the left wall is shown first, then the front wall, then the right wall, then the back wall. The back wall is shown with the same orientation as the front wall.

In Polyform Puzzler:

3.7   How should polyhex solution files be interpreted?

See "How should the solution files be interpreted?" above for an overview of solution files.

Polyhexes use a 2-dimensional skewed (X,Y) cartesian coordinate system. The X and Y axes are 60° apart instead of 90°.

The visual representation is an ASCII-art drawing of the solution, with the Y-axis vertical and the X-axis sloping up. Example (with coordinates):

                        __   3
                     __/  \
                  __/  \  /  2
               __/   __/  \
            __/     /   __/  1
         __/  \__   \  /  \
      __/   __   \__/  \  /  y=0
     /  \  /  \__/  \__/  \
  3  \  /  \__    __/   __/
     /  \__/  \  /   __/
  2  \  /     /  \__/    6
     /  \     \__/    5
  1  \  /   __/    4
     /  \__/    3
y=0  \__/    2
          1
     x=0

In Polyform Puzzler:

3.8   How should polyiamond solution files be interpreted?

See "How should the solution files be interpreted?" above for an overview of solution files.

Polyiamonds use a pseudo-3-dimensional skewed (X,Y,Z) cartesian coordinate system. The X and Y axes are 60° apart instead of 90°, and the Z dimension is used to represent the orientation of triangles:

           ____
    /\     \  /
z=0/__\  z=1\/

The visual representation is an ASCII-art drawing of the solution, with the X-axis horizontal and the Y-axis sloping to the right. Example (with coordinates):

              x=0  1   2   3   4   5   6   7   8
             ____________________________________
            /   /           /    \      /       /
        3  /   /___________/   ___\    /       /
          /       /    \      /   /    \  /\  /
      2  /_______/      \____/   /______\/  \/
        /       /\      /   /\       \      /
    1  /   ____/  \____/   /  \_______\    /
      /   /        \       \          /   /
y=0  /___/__________\_______\________/___/

     x=0  1   2   3   4   5   6   7   8

In Polyform Puzzler:

3.9   How should polystick solution files be interpreted?

See "How should the solution files be interpreted?" above for an overview of solution files.

Polysticks use a pseudo-3-dimensional (X,Y,Z) cartesian coordinate system, but the line segments of the grid are significant, not the squares. The Z dimension is used to represent the direction of line segments: 0=horizontal, 1=vertical. Horizontal line segments "x,y,0" start at (x,y) and end at (x+1,y), one unit to the right. Vertical line segments "x,y,1" start at (x,y) and end at (x,y+1), one unit up. (The Z dimension corresponds to the index of the dimension that increases.) In earlier versions of Polyform Puzzler, internal intersections (where grid lines cross) were also shown (in the form "x,yi") but these can be ignored.

The visual representation consists of piece names (letters) in an ASCII-art drawing of the 2-D grid. Imagine that all adjacent line segments with the same labels are joined. Example (with coordinates):

  4 ->   -R-- -T-- -T-- -r--
        y    R    T    r    Y
        |    |    |    |    |
  3 ->   -y-- -R-- -r-- -Y--     ---- z=0
        y    R    T    r    Y
        |    |    |    |    |       |
  2 ->   -H-- -H-- -h-- -h--        | z=1
        y    H    X    h    Y
        |    |    |    |    |
  1 ->   -H-- -X-- -X-- -h--
        F    F    X    f    f
        |    |    |    |    |
y=0 ->   -F-- -F-- -f-- -f--

        ^    ^    ^    ^    ^
      x=0    1    2    3    4

The solution above is from the 5x5 welded one-sided tetrasticks puzzle. Lowercase piece names indicate flipped pieces in one-sided puzzles (asterisk ["*"] suffixes were used to show flipped pieces in earlier versions of Polyform Puzzler).

In Polyform Puzzler:

3.10   How should polytrig solution files be interpreted?

See "How should the solution files be interpreted?" above for an overview of solution files.

Polytrig solutions are similar to polystick solutions, except on a triangular grid like polyiamonds. The Z dimension is used to represent the direction of line segments: 0 = 0° horizontal; 1 = 60° counter-clockwise, up and to the right; 2 = 120° counter-clockwise, up and to the left.

The visual representation consists of piece names (letters & numbers) in an ASCII-art drawing of the triangular 2-D grid. Example (with coordinates):

                  x=0     1     2     3     4

              4   __U3__
                 /U3   /U3
               T3  \ Y3  \                    z=2  z=1
           3   /_Y3_\/_L3_\                     \  /
              /T3   /Y3   /L3                    \/___ z=0
            T3  \ I3  \ P3  \                   (x,y)
        2   /_Z3_\/    \/_J3_\
           /Z3   /      P3   /L3
         C3  \ I3        \ J3  \
     1   /_Z3_\/_S3____P3_\/_O3_\
         C3   /E3   /S3   /O3   /
          \ I3  \ E3  \ J3  \ O3
y=0        \/_C3_\/_E3_\/_S3_\/

  x=0     1     2     3     4

In Polyform Puzzler:

3.11   How should polytwig solution files be interpreted?

See "How should the solution files be interpreted?" above for an overview of solution files.

Polytwig solutions are similar to polystick solutions, except on a hexagonal grid like polyhexes. The Z dimension is used to represent the direction of line segments: 0 = 0° horizontal to the right; 1 = 120° counter-clockwise, up and to the left; 2 = 240° counter-clockwise, down and to the left.

The visual representation consists of piece names (letters & numbers) in an ASCII-art drawing of the hexagonal 2-D grid. Example (with coordinates):

  z=1                               \__  y=5
    \                               /
(x,y)\____z=0                 \__
     /                        /
    /                   \__         \__  4
  z=2                   /           /
                  \__         \__
                  /           /
            \__         \__         \__  3
            /           /           /
       _P5_       \__         \__
  5   P5   P5     /           /
     /      \_U5_       \__         \__  2
     P5     U5   U5     /           /
      \_U5_/      \_U5_       \__
  4   P5   X5     X5   L5     /
     /      \_X5_/      \_L5_       \__  1
     I5     X5   X5     L5   R5     /
      \_T5_/      \_L5_/      \_R5_
  3   I5   T5     L5   W5     R5   R5
     /      \_T5_/      \_Y5_/      \    y=0
     I5     T5   T5     W5   Y5     R5
      \_H5_/      \_S5_/      \_Y5_/
  2   I5   H5     S5   W5     Y5
     /      \_H5_/      \_Y5_/       5
     I5     H5   S5     W5
      \_C5_/      \_W5_/       4
  1   C5   H5     S5
     /      \_S5_/       3
     C5     C5
      \_C5_/       2
y=0
             1

    x=0

In Polyform Puzzler:

4   The Code

4.1   How are the polyform puzzles solved?

Polyform Puzzler works by reducing puzzles into "exact cover" problems. Briefly, to solve an exact cover problem, given a matrix of 0s and 1s, we must find a set of rows which, when combined, contain exactly one 1 in each column. To find every solution we must find all such sets of rows.

We construct a two-dimensional matrix with named columns. The first row consists of the column names: first the puzzle piece names, then the coordinates of the solution space as text strings. For example, in a puzzle with three pieces to be placed in a 3x3 grid, we'd have 12 columns:

A  B  C    0,0  1,0  2,0    0,1  1,1  2,1    0,2  1,2  2,2

We determine every possible position of each puzzle piece in the puzzle, and construct one row for each position. Starting with a row of 0s, put a 1 in the column for the puzzle piece name and in each column corresponding to the position of the puzzle piece. For example, puzzle piece A covering coordinates (0,0), (0,1), and (1,1) would create this row in the matrix:

1  0  0    1  0  0    1  1  0    0  0  0

Note

Polyform Puzzler doesn't actually use 1s in its internal matrices, it uses the column titles (the piece names and coordinate strings) instead. For example, the row above is actually represented in the internal matrix as follows:

['A', 0, 0, '0,0', 0, 0, '0,1', '1,1', 0, 0, 0, 0]

This redundancy makes debugging easier, makes individual rows intelligible without having to refer to the header row, and is a shortcut when reporting solutions.

Polyform Puzzler is written using the Python programming language, and in Python any non-zero number or non-empty text string (even a text string like '0,0' or even '0') is the equivalent of a "True" boolean value, equivalent to the number 1. This representation doesn't affect the operation of the exact cover algorithm.

Once all the rows have been constructed (there may be many), the solutions can be found by identifying sets of rows that, combined, have exactly one 1 (or equivalent) in each column. For example, this is one such solution:

1  0  0    1  0  0    1  1  0    0  0  0
0  1  0    0  1  1    0  0  1    0  0  0
0  0  1    0  0  0    0  0  0    1  1  1

The puzzler.exact_cover_dlx module implements Donald E. Knuth's Dancing Links approach to his Algorithm X ("DLX"). For a complete description of DLX, see Knuth's paper (compressed PostScript original or PDF version).

The puzzler.exact_cover_x2 module implements Knuth's Algorithm X using a high-level native data structure technique devised by Ali Assaf. This implementation runs about 3 times faster than DLX in native Python.

4.2   How are Sudoku puzzles solved?

Sudoku can be reduced to the same kind of exact cover problem as polyform puzzles, and the same algorithm can be used to solve both types of puzzles. It's just a matter of identifying the constraints.

Here's a 4x4 Sudoku puzzle we'll use to illustrate:

1 . | . 4
. 4 | . 2
----+----
2 3 | . 1
. . | 2 .

Each row, column, and block must contain the digits (1, 2, 3, 4) exactly once. We have four sets of constraints:

  1. There are 4 blocks, numbered 0, 1, 2, & 3. Each block must contain the digits (1, 2, 3, 4) exactly once. We can name each exact cover matrix column with the combination of digit value and block number:

    1b0 2b0 3b0 4b0 1b1 2b1 3b1 4b1 1b2 2b2 3b2 4b2 1b3 2b3 3b3 4b3

    Each name is of the form: digit + "b" + block number. There are sixteen combinations, 4 * 4, or 4-squared. In a 9x9 Sudoku puzzle, there will be 81 combinations.

  2. There are 4 columns, again numbered 0, 1, 2, & 3. Each column must contain each digit exactly once. Again, we combine the digit values and column numbers to name exact cover matrix columns:

    1c0 2c0 3c0 4c0 1c1 2c1 3c1 4c1 1c2 2c2 3c2 4c2 1c3 2c3 3c3 4c3

    Each name is of the form: digit + "c" + column number. There are 16 combinations, (4 * 4, or 4-squared). In a 9x9 Sudoku puzzle, there will be 81 combinations.

  3. Similarly for the 4 rows:

    1r0 2r0 3r0 4r0 1r1 2r1 3r1 4r1 1r2 2r2 3r2 4r2 1r3 2r3 3r3 4r3

  4. We must also make sure that no digit is placed in the same location more than once. So we have constraints on all coordinate pairs, all combinations of rows & columns:

    0,0 1,0 2,0 3,0 0,1 1,1 2,1 3,1 0,2 1,2 2,2 3,2 0,3 1,3 2,3 3,3

Altogether there are 4 sets of constraints, each with 16 (4 * 4) elements, for a total of 64 columns in the exact cover matrix. For a 9x9 puzzle, we will have 4 times (9 squared) = 324 columns.

A Sudoku puzzle has a starting position, a set of given digits in a sparse grid. The program creates one exact cover matrix row for each of these digits. Each row will have exactly four "1" values, one each for the block, the column, and the row (each paired with the digit value), and one for the column & row coordinate pair. The program will then generate one candidate row for each digit in each empty square in the starting position.

The resulting matrix is then fed into algorithm X, which produces the result: a set of rows that satisfies all constraints. If the puzzle is ambiguous (and therefore not well-formed), more than one result may be produced. If an entirely empty starting position is used, the algorithm will eventually produce every possible Sudoku solution (all 6,670,903,752,021,072,936,960 of them), if you give it enough time.

5   Usage

5.2   How can I add my own puzzle?

That's a big question. The beginning of an answer is in How to Extend Polyform Puzzler. If you have questions that aren't answered there, please ask on the puzzler-users@lists.sourceforge.net mailing list (subscribe here).

5.3   How were the graphics created?

The solution images were all generated by Polyform Puzzler itself, via the -s/--svg option, and the SVG vector image files were converted to PNG raster images using Inkscape from the command line (batch mode). For example:

inkscape -D -e docs/images/ominoes/pentominoes-6x10.png -d 180 \
    docs/images/ominoes/pentominoes-6x10.svg

This exports just the drawing (not the page, no margin; -D option) to a PNG file (-e option) at 180 DPI (-d option), based on the SVG file. We use 180 DPI output for polyominoes, polyiamonds, polyhexes, and polytwigs (90 DPI for thumbnails, except for polytwigs which use 120 DPI); 240 DPI for polysticks (120 DPI for thumbnails); and 300 DPI for polytrigs (180 DPI for thumbnails).

SVG image files can be created from existing solution files using the -r/--read-solution option or by solving the puzzle anew. Using -r, you can also choose which solution to render graphically with the -n/--stop-after option.

The X3D models were created via the -x/--x3d option and can be viewed with Xj3D (multiplatform), FreeWrl (Mac & GNU/Linux), Flux Player (Windows), and other 3-D viewing software.

View document source. Generated on: 2016-11-30 05:37 UTC. Generated by Docutils from reStructuredText source.