Wednesday, March 4, 2009

Questions on project 2

I have a question about the meaning of the "main diagonal constraint" on project 2.

1. What's the precise meaning of main diagonal? For example, for a 4x4 board:

1 2 3 4
5 6 7 8
4 5 6 7
2 3 4 5

is the main diagonal 1 6 6 5 ?

2. Does this apply to each block or to the entire board?

6 comments:

  1. I could be wrong but this is how I understood it from reading the project description:

    I think you're correct with main diagonal being 1 6 6 5 in your example. Also, 2 5 7 4 would be another main diagonal.

    As for your other question, I think it would apply to the entire board. All 9 squares of each 3x3 block are already guaranteed to have different values as part of the normal rules of sudoku, so introducing another constraint that local diagonals can't have two of the same value wouldn't really change the problem

    ReplyDelete
  2. Thanks for the discussion. Yes, your second point makes perfect sense. For the first point, we need to double check with Prof. Rao.

    ReplyDelete
  3. Shuiwang

    Re: your question, for

    1 2 3 4
    5 6 7 8
    4 5 6 7
    2 3 4 5

    1,6,6,5 is indeed the main-diagonal
    the constraint is that all the main-diagonal numbers be different.
    (So in this case, the constrain is violated).

    There is only one *main* diagonal for the entire board (the all-different constraint for the diagonals is trivially satisfied for each of the blocks anyway--since each block has each of 1--9 exactly once). The only non-trivial constraint left is that all blocks together should still cooperate to ensure the main diagonal constraint--
    which crosses (and joins the diagonals of) the upper left, middle and lower-right blocks.

    Does this help?

    rao

    ReplyDelete
  4. Just to clarify, you're saying there's only one main diagonal for the entire board from top left to bottom right and we should ignore the other possible candidate for main diagonal from top right to bottom left?

    ReplyDelete
  5. adam
    Re: your question below, the answer is yes.

    rao

    -----
    Just to clarify, you're saying there's only one main diagonal for the entire board from top left to bottom right and we should ignore the other possible candidate for main diagonal from top right to bottom left?
    -------

    ReplyDelete
  6. Prof. Rao,

    Thanks for the clarification. Now this point is quite clear.

    Shuiwang

    ReplyDelete

Note: Only a member of this blog may post a comment.