My previous post took a while to appear (I'm a new poster and it had to be moderated), but it describes a clear way in which a standard DLX solver (with support for optionally covered columns) can handle inequality constraints.
I just realized that in that post strictly speaking I described "less than or equal" constraints, and that the not-equal part would follow only from the standard sudoku column/row constraints.
With a small adjustment, strict inequality can be enforced:
For a puzzle where the cells can have n distinct values, a strict inequality constraint can be encoded for a DLX solver by n matrix columns. These columns must be optionally covered, i.e. in a solution the chosen matrix rows should have at most one 1 in this such a column (they are allowed to have only zeroes). The first column represents the fact that 1 does not lie between the two values of the inequality, the second column that 2 does not lie between the two values of the inequality, etc.
For example, the placing of 3 on the small side of an inequality (3<?) is represented by a matrix row that has ones in 1, 2, and 3 columns, because after placing the 3 it is no longer the case that 1, 2 or 3 lies between the two values of the inequality, regardless of the right hand side.
Similarly, the placing of 3 on the large side of an inequality (?<3) is represented by a matrix row that has ones in the 3, 4, 5, ... columns, because after placing the 3 it is no longer the case that 3 or larger lies between the two values of the inequality, regardless of the left hand side.
Clearly placing both (3<3) would cover the 3-column twice, which the DLX solver will not allow. Any pair of values violating the inequality would cause a column to be covered twice. A pair of values such as 2<4 is allowed - the 3-column is not covered in this case but that is fine since these are optionally covered columns.
What happens with chains of inequalities?
The above matrix encoding of the rules does not take inequality chains into account. This means that the solver may well try placing values that are obviously impossible, e.g. try place a 3 at the high end of a chain of three, like this ?<?<?<3. The solver won't find out this is impossible until the rest of the chain gets filled in, and there are no candidates left for the lowest cell. If the puzzle is small and the solver is fast enough, then this is not a problem. It is no different to how a DLX Sudoku solver does not know about naked triples, and only sees a problem arising a few moves after a wrong guess.
Inequality chains can however be taken care of when setting up the DLX matrix. A matrix row that represents filling a cell should have ones in the columns of the inequalities it directly takes part in in the manner explained above, but you could also put ones in the appropriate columns of the inequalities in the chain that it affects only indirectly. For example, the row representing placing the 3 in 3<?<? should not only have ones in columns 1,2,3 of the first inequality, but also in columns 1,2,3,4 of the second inequality. Any move that makes a chain impossible (e.g. ?<?<?<3) should not be represented in the DLX matrix in the first place.
