Search code examples
prologsudokuclpfdeclipse-clp

An alldifferent for tuples

I'm trying to solve a sudoku with the viewpoint that every number has 9 positions. This is the representation for my sudoku:

sudoku

From the table you can read that number 5 has following positions (Row,Col) in the sudoku: (2,8),(4,2),(6,5).

When I mention a row in my explanation, I mean a row like this: row

For example, the above row is row 1.

What I have done is the following:

  • For every row check if all ROW-Values in that row are different using alldifferent from ic_global.
  • Do the same as above but then for the COLUMN-Values.
  • For every row, check if the square numbers are different (calculated using a row and col value each time), using alldifferent again.

The above things work fine and I get a solution for the sudoku but not the correct one. This is because I have to check one more thing: every position must be different. With the current state of my solver I could get a solution that has multiple numbers on the same position, f.e.: 2 and 3 could both be at position (5,7) because I don't check if all positions are different.

How would I tackle this problem? I tried to get ALL the positions in one list in tuple form and then check if all tuples are different but I have been struggling for hours and I'm getting really desperate. I hope I can find a solution here.

EDIT: Added code

code

Solution

  • As you already know, all_different/1 and related constraints work on integers. Also, in your case, you are actually interested in a special case of tuples, namely pairs consisting of rows and columns.

    So, your question can actually be reduced to:

    How can I injectively map pairs of integers to integers?

    Suppose you have pairs of the form A-B, where both A and B are constrained to 1..9.

    I can put such pairs in a one-to-one correspondence to integers in several ways. A very easy function that does this is: 9×A + B. Think about it!

    Thus, I recommend you map such positions to integers in this way or a similar one, and then post all_different/1 on these integers.

    Exercise: Think about other possible mappings and their properites. Then generalize them to work on tuples.