How can we formulate an anti-knight Sudoku as an exact cover problem?

Question

Formulating standard Sudoku as an exact cover problem is easy and well documented. All of the constrained groups contain every digit which makes it natural to express the problem this way. Wikipedia claims without citation that:

Although other Sudoku variations have different numbers of rows, columns, numbers and/or different kinds of constraints, they all involve possibilities and constraint sets, and thus can be seen as exact hitting set problems.

How would one formulate other variants as exact cover problems with an incidence matrix? I'm focusing on the anti-knight variant, but with the goal of learning about expressing arbitrary variants.

The anti-knight Sudoku variant includes all of the standard rules, and additionally requires that no two squares which are a knight's move (in chess) apart may contain the same digit. I don't know how to approach this because a constraint between two squares cannot be expressed as requiring all digits to be present in some permutation. I can imagine a version of Algorithm X that solves this by removing additional rows by manual application of the anti-knight rule, but I believe Wikipedia is claiming this constraint should be expressible in the matrix alone without modifying the algorithm.

Is Wikipedia's claim that all variants can be expressed this way correct, and how would one approach the anti-knight example?

Answer 1

We start with the regular sudoku exact cover problem:

Sudoku Set Cover

• 729 sets, each (row, col, num) triple.
  • Each set contains 4 elements: (row, col), (row, num), (col, num), (box, num) -- corresponding to the below.
• 324 elements:
  • 81 elements, each (row, col) pair.
  • 81 elements, each (row, num) pair.
  • 81 elements, each (col, num) pair.
  • 81 elements, each (box, num) pair.

This creates a 729 x 324 matrix with 2916 ones.

Anti-Knight Constraints

There are 152 non-redundant anti-knight moves (24 in 4 corner boxes, 38 in 4 edge boxes, and 56 in the middle box, all divided by 2 to avoid double-counting).

The anti-knight moves are like boxes that only contain two cells. However we only want to avoid an intersection, we don't care about covering all 1-9 nums. To allow this we add dummy sets which each contain a single element corresponding to a knight constraint. (This is the extension described in the comments).

• 1368 (9 * 152) new sets, each (knight-move, num) pair, each containing the 1 corresponding element.
• 1368 new elements, each (knight-move, num) pair.
• Each existing set (row, col, num) gets up to 8 more elements added which are the knight jumps with number num either starting or ending at that cell. Total is 2736 additional set members.

The final result is a 2097 x 1692 matrix with 7020 ones.