Greater Than Sudoku and DLX

Post the puzzle or solving technique that's causing you trouble and someone will help

Re: Greater Than Sudoku and DLX

Postby Mathimagics » Fri Jan 18, 2019 10:14 pm

.
Succinct, tarek, but alas, inscrutable! 8-)

Of course, my failure to scrute could be a generic problem ... :(

Either way, you'll have to give me the "for dummies" version …


eleven: because the OP asked the question about DLX then got on a bus to parts unknown, then all these guys turned up and started talking about SAT solutions.

Personally, I'd go for knocking up another fsss2 clone to solve these - context constraints seem eminently doable, as per the SudokuFP case.

PS: the SAT just splat on my FAT! :(
User avatar
Mathimagics
2017 Supporter
 
Posts: 1284
Joined: 27 May 2015
Location: Canberra

Re: Greater Than Sudoku and DLX

Postby jaap » Sun Jan 20, 2019 12:26 pm

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.
jaap
 
Posts: 2
Joined: 18 January 2019

Re: Greater Than Sudoku and DLX

Postby Mathimagics » Tue Jan 22, 2019 12:46 am

.
Hi jaap.

A useful contribution! I never implemented optional constraints in my various DLX solvers, as I never could see a use for them. I do remember from DK's paper that the implementation is fairly simple.

I did build a Futoshiki/Sudoku Inequality solver, back in the day. But I can't recall whether I had actually read DK's paper before this, or afterwards. Either way I missed the connection ...

The chains can be identified at the matrix setup stage, as you say. That's just sensible candidate elimination.

I don't think it really matters that you can't make additional eliminations on the fly as chain members are filled in, no big deal, not in the 9x9 case anyway. For larger grid sizes I suppose it could become more of an issue.

Alas, too many pet projects already for me, but I'd be interested to see how DLX fares if somebody cares to implement this model! 8-)

Cheers

BTW: I just remembered how deeply I got into Futoshiki theory at one point. You can see evidence of this in this question that I asked over at StackExchange a few years back. I notice that it has attracted no response, not even a flicker of interest, in all that time! :?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1284
Joined: 27 May 2015
Location: Canberra

Previous

Return to Help with puzzles and solving techniques

cron