1
$\begingroup$

I am trying to solve a problem which is smilar to sudoku. I have a specific device location on map I need to gave them a unique integer numbers. However, as in the sudoku I can assign up to 9 and adjacent points cannot has the same number. (for instance inside the 20m circle.) Obviously, I don't have objective function. When it comes to constraint I'm stuck on providing adjacent point unique number issue.

I search couple of article here is the one of them:

https://towardsdatascience.com/using-integer-linear-programming-to-solve-sudoku-puzzles-15e9d2a70baa

Could you help me to write constraint that I mentioned?

$\endgroup$
2
  • 2
    $\begingroup$ Can you please provide more context? What do you mean 20m circle? Why doesn't Sudoku work here? $\endgroup$ Commented Jul 2 at 14:42
  • $\begingroup$ For each row and coloumn we can use the number only one time. However in my case I can write as many as I can except the point coverage area is not intersecting. You can think that it is a kind of circle and if circles has intersection area unique numbers cannot be same. $\endgroup$
    – Serkan
    Commented Jul 3 at 7:19

1 Answer 1

1
$\begingroup$

For each point $i$ and each value $k\in\{1,\dots,9\}$, let binary decision variable $x_{ik}$ indicate whether point $i$ is assigned value $k$. If you want to prevent points $i$ and $j$ from being assigned the same value, impose "conflict" constraints $$x_{ik} + x_{jk} \le 1 \quad \text{for all $k$}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.