Using global inside/outside constraints

The global one-loop constraint is equivalent to two global constraints:

- a one-connected-inside constraint

- a one-connected-outside constraint (outside including the non-displayed space around the grid)

and none of the two can be reduced to the other, as illustrated by the following examples.Having the inside/outside position of all the cells is obviously equivalent to having all the borders.

As a result, it is convenient to print the solution in inside/outside form ("O" for outside the curve, "X" for inside, "—" for undecided in case only a partial solution is obtained).

Here are three examples from the Krazydad Easy book b001, where I need no global constraint to reach a partial solution. (Recall that, in my approach, a partial solution can only have properties common to all the solutions.)

I'll also show how the puzzle can then easily be finished by using the inside or outside global constraints.

Example 1: puzzle #7:

- Code: Select all
`. 0 2 3 3 3 2 `

0 . . . . . 3

2 . 2 . . . 1

. . . . . . 2

. . . . . . 3

3 1 3 1 1 2 3

. . . . 2 . .

partial solution:

OOOXOXO

OOXXXXX

OXXO-OO

XXOO-XO

OXXOOXX

XXOOOXO

OXXXOXX

Notice that all the Os are connected and the one-connected-outside constraint is thus already satisfied.

Let's now use the global one-connected-inside constraint : by colouring in green or red the connected parts inside the loop (the Xs), it is obvious that the only means of satisfying the global one-loop (or global one-connected-inside) constraint is to have r3c5 and r4c5 inside.

This shows that the one-connected-inside constraint is not reducible to the one-connected-outside constraint when they are taken to replace the one-loop constraint (this is obvious as a connected outside might not be singly connected if there are two closed curves).

OOO

XO

XO

OO

XXXXXO

XXO—OO

XXOO—

XO

O

XXOO

XXXXOOO

XO

O

XXXO

XXExample 2, puzzle #2:

- Code: Select all
`. . . 1 . 2 . `

3 2 3 . . 2 .

2 1 3 0 3 . .

. 1 . . . 2 .

. . 2 0 2 2 1

. 1 . . 3 2 2

. 2 . 2 . . .

partial solution:

XXXXXXX

XOOXOOX

OOXXXO—

XOOXOOX

XOXXXXX

XXXXOOX

XXOXXOX

Here, all the X's are already connected, and the one-connected-inside constraint is thus already satisfied

But the only means of connecting the Os is to have r3c7 outside the loop.

This shows that the one-connected-outside constraint is not reducible to the one-connected-inside constraint when they are taken to replace the one-loop constraint (this is obvious as a connected inside might not be singly connected if there are two closed curves).

Example 3 (an example of the same kind as above), puzzle #4:

- Code: Select all
`. 2 . 2 . . . `

2 2 . . . 2 2

2 3 1 2 2 . 2

2 . 3 . 2 . 3

3 . 2 1 3 2 1

2 1 . . . 0 2

. . . 3 . 3 .

partial solution:

OXX—XOX

XXOOXXX

XOOXXOO

XXOXOOX

OXXXOXX

XXOXXXX

XXOXOXO

Again, all the X's are already connected, and the one-connected-inside constraint is thus already satisfied.

But the only means of connecting the Os is to have r1c4 outside the loop.

Exercise, # 6 of the same Karzydad "book":

- Code: Select all
`. 1 . 2 2 2 . `

. 3 3 . 2 . .

. 2 0 2 1 . .

. . 2 . 2 . .

. . 1 1 3 2 .

. . 3 . 3 2 .

. 2 2 1 . 2 .

Using only local constraints, show that one can obtain the following situation:

- Code: Select all
`XXXXO—X`

OXOX———

OOOOO——

XXOXOO—

—OOXXOX

—XOXOOX

OXXXXXX

Now using the only-one-inside constraint, show that one must have:

- Code: Select all
`XXXXO-X`

OXOXXX-

OOOOO-X

XXOXOOX

XOOXXOX

XXOXOOX

OXXXXXX

The final three cells are easily dealt with using the givens and the global constraints:

r3c5 = 1 => r3c6 can only be O

r1c5 = 2 => r1c6 can only be O

Finally, connexity of the Xs requires r2c7 = X