Viewpoints Sudoku

Question

I'm looking for alternative viewpoints to solve sudoku problems using constraint programming.

The classical viewpoint is to use a finite domain (row, column) variables who can take values from 1 to 9. This is a good viewpoint and it's easy to define constraints for it. For example: (1,2) variable with as value 4 means 4 is in row 1 in column 2.

But it's hard to come up with other viewpoints. I tried and came up with the viewpoint of a 3-dimensional matrix that takes binary values. For example variable (1,2,7) with 1 as value means there is a 7 in row 1 in column 2. But using binary values should be your go to if all other viewpoints fail to deliver good constraints.

Are there any other good viewpoints out there?

EDIT: A good viewpoint should allow the constraints to be concisely expressed. I prefer viewpoints that allow the problem to be described using as few constraints as possible, as long as those constraints have efficient algorithms.

Definition viewpoint: A viewpoint is a pair X,D, where X = {x1, . . . , xn} is a set of variables, and D is a set of domains; for each xi ∈ X, the associated domain Di is the set of possible values for x. It must be possible to ascribe a meaning to the variables and values of the CSP in terms of the problem P, and so to say what an assignment in the viewpoint X,D is intended to represent in terms of P.

Answer 1

The viewpoints you gave are a homomorphical mapping of the positional encoding of the relation a sudoku is build from (row,column, digit).

Another approach would be encoding the restriction sets (rows[1-9], columns[1-9], squares[ul,um,ur,ml,mm,mr,ll,lm,lr], or whatever restrictions apply) and whether a certain digit is placed in it. This likely will be horrible with respect to defining constraints. (So I'd guess it is to be considered as not good). It requires encoding the relation among the restriction sets to be "known" separately.

E.g. a (2,5,7) in classical viewpoint would imply (row2,7),(col5,7) and (um,7) in this alternative.

As you can see, the problem is with the encoding of the relation between a logical position and the various constraints. The classical vieport is building upon encoding the positional data and applies constraints on possible placings. (The way a sudoko is explained and approached for solving.) The alternative is using the constraint sets as viewpoints and needs to address the positioning as constraints.

Normal people might get a knot into their brains from such representation, though. (And I'd not volunteer for figuring out the constraints...)