3

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

mat
  • 40,498
  • 3
  • 51
  • 78
Stanko
  • 4,275
  • 3
  • 23
  • 51

1 Answers1

4

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.

mat
  • 40,498
  • 3
  • 51
  • 78
  • 2
    Thank you mat, I'll try that. I thought of the idea of mapping them but didn't think of that function and wasn't sure if it was the best way to solve my problem, I tried Row x Col x SquareNumber but that didn't work out. I'll let you know how it goes. – Stanko May 18 '16 at 09:01
  • 1
    Your mapping probably was not injective. – mat May 18 '16 at 09:04