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.
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 113 |
Nodes: | 8 (1 / 7) |
Uptime: | 121:33:27 |
Calls: | 2,501 |
Files: | 8,692 |
Messages: | 1,923,784 |