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?

## Wednesday, March 4, 2009

Subscribe to:
Post Comments (Atom)

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

ReplyDeleteI 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

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

ReplyDeleteShuiwang

ReplyDeleteRe: 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

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?

ReplyDeleteadam

ReplyDeleteRe: 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?

-------

Prof. Rao,

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

Shuiwang