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?