ThemePark wrote:I've been pondering this for a while, but have been unable to come to any solid conclusion for or against. Is it possible to use DLX to solve a Greater Than Sudoku? The problem is in how to add the constraint of two neighbouring cells being greater/less than each other, and I'm not sure whether or not it's possible, and if it is, how to implement it.

If you have a standard DLX solver that allows for optionally covered columns (i.e. columns that do not need to be covered - the chosen matrix rows may have values in that column that sum to 1 or 0), then you can encode Futoshiki problems for it.

For each inequality on an nxn puzzle, you make n-1 optionally covered columns. One column signifies that 1.5 does not lie between the values on either side of the inequality, one column for 2.5 not lying between the values, etc., all the way up to value n-0.5.

If you were to violate an inequality, one of those columns would be covered twice, which is not allowed.

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.5 and 2.5 columns, because after placing the 3 it is no longer the case that 1.5 or 2.5 lies between the two values of the inequality, regardless of the right hand side.

Similarly, the placing of 2 on the large side of an inequality (?<2) is represented by a matrix row that has ones in the 2.5, 3.5, 4.5, ... columns, because after placing the 2 it is no longer the case that 2.5 or larger lies between the two values of the inequality, regardless of the left hand side.

Clearly placing both (3<2) would cover the 2.5 column twice, which the DLX solver will not allow.