Sandwich Sudoku

[nic...@gmail.com]

The Sandwich Sudoku also called Between 1 and 9 Sudoku follows the same rules of
classic sudoku but has extra clues outside the grid. The clues are the sum of
the digits between 1 and 9 in that row or column. When you have eg. 0, then
there are NO cells between 1 and 9.

Constraints for a standard Sudoku are well known. However, I can't find anything
for a sandwich sudoku, and I'm having trouble formulating contraints.

The usual formulation is Vxyd where x and y are the rows and columns, d is the
digit in that cell and takes a (0,1) value.

I can create a new variable that is (0,1) if the cell is in the sandwich

Consider a row

3 4 2 1 5 6 9 7 8

We have the 1 and 9 values as

Value 1 - 0 0 0 1 0 0 0 0 0
Value 9 - 0 0 0 0 0 0 1 0 0

You can now easily create effectively 4 new rows

There are two cases to consider. 1 comes before 9. The second is 9 comes before 1
It's easy to create an After 1, After and including 9, Before and including 1 and Before 9

Te first case constraint a binary variable where its 1 if comes after the 1, else is zero
Create a second variable where its 1 if it comes after and including the 9

After 1 - 0 0 0 0 1 1 1 1 1
After including 9 - 0 0 0 0 0 0 1 1 1

We then take the difference and we have

Difference - 0 0 0 0 1 1 0 0 0

This shows the cells that are in the sandwich


Two problems.

It doesn't work the other way where 9 comes before 1. You can create a rule similar to the above, but I can't get a combination working

Secondly I need the sum of the values where its true and this isn't linear
It's a product of the value in the cell, which is a variable, and another variable.

Any ideas?

It feels like their should be an expression that is linear.

[gamo]

El 22/5/20 a las 17:44, nic...@gmail.com escribió:

Really, I can't understand you.
A simple sudoku it's only a big binary linear program - glpk is ok.
So, want to add more restrictions???
You can.

Best regards.


--
http://gamo.sdf-eu.org/
“Aoccdrnig to a rscheearch at Cmabrigde Uinervtisy, it deosn't mttaer
in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is
taht the frist and lsat ltteer be at the rghit pclae. The rset can be
a toatl mses and you can sitll raed it wouthit porbelm. Tihs is bcuseae
the huamn mnid deos not raed ervey lteter by istlef, but the wrod as
a wlohe.”