Anonymous asked in Science & MathematicsMathematics · 6 years ago

Integer Programming Formula?

In the game of Shidoku (a smaller version of Sudoku), you flll in a 4 x 4 grid so that every row, every column, and every one of the four 2 x 2 box contains the digits 1 through 4. The figure below is an example. Set up an IP(Integer Programming) to solve this game. (The IP formula does not need to be solved, only needs to be set up)

I have attached a photo of the 4 x 4 grid

Attachment image

1 Answer

  • 6 years ago
    Favorite Answer

    A pretty obvious choice is a_ij = the number in cell (i, j). And it's pretty obvious that those variables take the values {1, 2, 3, 4}.

    Now write down the constraints in terms of i and j. For instance a_ij not equal to a_ik if j not equal to k. That says you don't get the same number twice in one row. Now capture the other inequality constraints.


    A less obvious choice which leads to a much larger problem but it's easier to write the constraints is to define a_ijk = 1 if the number k is chosen for the (i,j)-th cell. So if you choose to write 3 in cell (i,j), that is represented as a_ij1 = 0, a_ij2 = 0, a_ij3 = 1, a_ij4 = 0. The constraint that you can only choose one value for each cell is sum(k=1,4) a_ijk = 1. The constraint that you can only choose any given number once in each row is sum(i=1,4) a_ijk = 1.

    The a_ijk's can only be {0, 1}. This is the way the problem would probably actually be solved by a mathematician, since making it a binary problem simplifies the search algorithm.

Still have questions? Get your answers by asking now.