Knuth's Algorithm X for edge matching puzzles matrix definition

Question

I'm learning a great new stuff and one of the things is Knuth's Algorithm X, which is super simple but an interesting different viewpoint at the problem. Of course this is a great application for Dancing Links, but I'm rather struggling in defining the constraints matrix correctly.

The goal is to solve an NxM edge matching puzzle. The rules are as follows:

• there are NxM tiles
• every tile has 4 edges
• the tiles need to be layed out in an NxM rectangle
• every edge can have one of C different colors.
• every tile can have up to 3x the same color (so no tile with all 4 the same)
• the puzzle is surrounded by a specific border color
• every edge color of a tile needs to match the adjacent tile's edge color
• every position needs to have exactly 1 tile
• as tiles are square, they can be placed in any rotations (0, 90, 180, 270)

The rows are easy to define (In my understanding they represent the choices): Tiles * positions * rotations -> N^(2)*M^(2)*(4)

The columns (In my understanding they represent the constraints) are a little bit problematic. Some are obvious:

• 1 column per position: N*M
• 1 column per tile: N*M (rotations are covered in the choice)

Some might not be needed but are helpful:

• 2*(N+M-4) Border Tiles, which have the border color exactly once
• 4 Corner Tiles

If my understanding is correct we now need horizontal and vertical edge constraints. These can be simply representing the edge

• (N-1)*M horizontal constraints
• N*(M-1) vertical constraints and in this case I would have to check every solution in the end, whether the colors are correct. which would create waaaaaay to many solutions to really be happy.

So I would like to encode the color matching part instead of just horizontal and vertical constraints, and this is where I struggle. Let's just look at horizontal color match constraints for now:

My current thoughts are around creating constraints for every choice's t(x,y,r) right side whether a piece t2(x+1,y,R) matches. That would add NMNM4 further columns (which in itself is not a problem). But it seems like, there is something flawed in this logic, as when I apply Algorithm X it results in empty columns even though the board is still solvable.

Any idea where my logic is flawed?

Answer 1

I found the answer: It's simply impossible in the original version.

But: In The Art of Computer Programming 4B Knuth introduces an Algorithm C, which is an extension to Algorithm X. It adds secondary constraints which add color constraints.

So the type of constraints are:

• every primary item needs to occur once
• every secondary item has been assigned at most one color

There are some more changes to the algorithm, e.g. a purify function is introduced, cover is changed slightly as well as hide. Details can be found in the book.