Is there a 6x6 suguru puzzle with no initial digits given that
has a unique solution?

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 23/01/2020 11:17, Richard Tobin wrote:

Is there a 6x6 suguru puzzle with no initial digits given that
has a unique solution?

I am unfamiliar with suguru, and I have a question about it.

I have managed to discover that:

* there is a square array of cells, side N;
* the array is divided into discrete zones of arbitrary shape that are contiguous (that is, they are connected either horizontally, vertically,
or both, a la Fillomino);
* the zones must be populated with the integers 1 to m, where m is the
number of cells in the zone;
* when the array is filled, the integer i will not occur in both of two
cells that are adjacent either horizontally, vertically, or diagonally.

So far, so good.

What I have not been able to discover is whether there is an upper limit
on the size of a zone. Is m > N allowed? That is, can a 6x6 puzzle
contain a zone of, say, 7 cells?

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <r0cebo$4sj$1@dont-email.me>,
Richard Heathfield <rjh@cpax.org.uk> wrote:

I am unfamiliar with suguru [...]

The Guardian publishes one each day, Monday-Friday.

What I have not been able to discover is whether there is an upper limit
on the size of a zone. Is m > N allowed? That is, can a 6x6 puzzle
contain a zone of, say, 7 cells?

I hadn't considered that a rule of the puzzle, just a choice made by
the setter. The Guardian ones I've seen are always 6x6 with a maximum
group size of 5.

Here is a 5x5 puzzle which needs no initial digits:

+---+---+---+---+---+
| | | |
|---+---+---+ + |
| | | |
| +---+ +---+---|
| | |
| + +---+---+---|
| | |
|---+---+---+---+---|
| | |
+---+---+---+---+---+

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 23/01/2020 16:25, Richard Tobin wrote:

In article <r0cebo$4sj$1@dont-email.me>,
Richard Heathfield <rjh@cpax.org.uk> wrote:

What I have not been able to discover is whether there is an upper limit
on the size of a zone. Is m > N allowed? That is, can a 6x6 puzzle
contain a zone of, say, 7 cells?

I hadn't considered that a rule of the puzzle, just a choice made by
the setter.

In that case:

For an NxN board there are potentially N-1 internal boundaries in a row,
and N rows, giving N(N-1), and we double it because columns, giving
N(N-1)*2.

So we can model the board as an array of N(N-1)*2 bits, where each bit represents either the absence or the presence of an internal boundary.

For N=6, N(N-1)*2 = 60.

On the face of it, this therefore becomes a trivial exercise in brute
force. 2^60 is 1152921504606846976. If my calculations are correct
(which is not a given), at a million trials a second this will take a
mere 36,533 million years - a very Saganesque period indeed.

Clearly this requires a little more analysis, to say the least.

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Thursday, January 23, 2020 at 11:30:02 AM UTC-5, Richard Tobin wrote:

Here is a 5x5 puzzle which needs no initial digits:

+---+---+---+---+---+
| | | |
|---+---+---+ + |
| | | |
| +---+ +---+---|
| | |
| + +---+---+---|
| | |
|---+---+---+---+---|
| | |
+---+---+---+---+---+

Nice.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <r0chda$ar9$1@macpro.inf.ed.ac.uk>,
Richard Tobin <richard@cogsci.ed.ac.uk> wrote:

Here is a 5x5 puzzle which needs no initial digits:

And here is a 7x7:

+---+---+---+---+---+---+---+
| | | | | |
|---+ + + +---+---+---|
| | | | |
| +---+---+---+ +---+ |
| | | | | | |
|---+ + + + + + |
| | | | | |
|---+ +---+ +---+ +---|
| | | | | |
| +---+ +---+---+---+---|
| | | |
| +---+---+---+---+---+ |
| | | |
+---+---+---+---+---+---+---+

I am pessimistic about finding a 6x6, at least with a maximum group
size of 5, as one can easily show it must have at least 10 groups, and
every solvable 6x6 grid I have found so far has either 8 or 9 groups.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <9c115106-57c8-4dbc-9bbe-72ee21244ccb@googlegroups.com>,
Jonathan Dushoff <jdushoff@gmail.com> wrote:

Here is a 5x5 puzzle which needs no initial digits:

+---+---+---+---+---+
| | | |
|---+---+---+ + |
| | | |
| +---+ +---+---|
| | |
| + +---+---+---|
| | |
|---+---+---+---+---|
| | |
+---+---+---+---+---+

Nice.

There are 2,531,745 solvable 5x5 grids using groups of up to 5
squares, of which 9,872 have a unique solution without adding any
initial digits.

Here's one that doesn't have any 5-square groups:

+---+---+---+---+---+
| | | |
| +---+---+ +---|
| | | |
| +---+---+---+ |
| | | | |
|---+ +---+---+---|
| | | |
| +---+ + + |
| | | |
+---+---+---+---+---+

The solution is rather regular.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <r0cebo$4sj$1@dont-email.me>,
Richard Heathfield <rjh@cpax.org.uk> wrote:

* there is a square array of cells, side N;

Actually many examples on the web use a non-square rectangular
array.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 23/01/2020 21:10, Richard Tobin wrote:

In article <r0cebo$4sj$1@dont-email.me>,
Richard Heathfield <rjh@cpax.org.uk> wrote:

* there is a square array of cells, side N;

Actually many examples on the web use a non-square rectangular
array.

Bugger. So much for simplicity!

But yes, I suppose that makes sense; there's no particular need to make
it a square (except for your problem, of course, since it's defined to
be 6x6).

I've now worked my way through 1x1, 1x2, 2x2, and 2x3, and I've
satisfied myself that, apart from the trivial 1x1, none of them allow
unique clueless solutions.

3x3 is more of a challenge, and I'm starting to scout around for excuses
not to cut code.

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <r0d3vg$eo0$1@dont-email.me>,
Richard Heathfield <rjh@cpax.org.uk> wrote:

I've now worked my way through 1x1, 1x2, 2x2, and 2x3, and I've
satisfied myself that, apart from the trivial 1x1, none of them allow
unique clueless solutions.

3x3 is more of a challenge, and I'm starting to scout around for excuses
not to cut code.

Va n tevq ng yrnfg 2k2, sbe rirel x-tebhc jvgu x <= 3 gurer vf n
fdhner gung vf nqwnprag gb nyy bs vgf fdhnerf, naq gurersber pna'g
pbagnva nal bs 1 .. x. Fb gb or fbyinoyr gurer zhfg or ng yrnfg n
4-tebhc.

N chmmyr jvgu n havdhr pyhryrff fbyhgvba (tbbq cuenfr!) gung pbagnvaf
na z-tebhc zhfg pbagnva x-tebhcf sbe nyy x <= z orpnhfr vs gurer jnf
ab tebhc sbe fbzr x, gura rkpunatvat x naq x+1 rireljurer jbhyq tvir
nabgure fbyhgvba.

Fb n 3k3 tevq jbhyq unir gb pbagnva tebhcf bs fvmrf 1, 2, 3, naq 4,
juvpu erdhverf zber guna 9 fdhnerf.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <r0d1mh$jsk$1@macpro.inf.ed.ac.uk>, I wrote:

Here is a 5x5 puzzle which needs no initial digits:

And here is a 7x7:

And here is an 8x8:

+---+---+---+---+---+---+---+---+
| | | |
|---+---+---+---+---+ +---+---|
| | | | |
|---+---+ +---+ +---+---+ |
| | | | | | |
| + +---+ + + +---+ |
| | | | | |
|---+ + +---+---+ + +---|
| | | | | | |
| +---+---+ +---+---+---+ |
| | | | |
| +---+ +---+ +---+---+ |
| | | | | | |
|---+---+---+---+ +---+ +---|
| | | |
+---+---+---+---+---+---+---+---+

It can be solved by hand, though it took me a while.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Spoiler alert: solution below (which I >>>think<<< is correct).

On 25/01/2020 18:16, Richard Tobin wrote:

In article <r0d1mh$jsk$1@macpro.inf.ed.ac.uk>, I wrote:

Here is a 5x5 puzzle which needs no initial digits:

And here is a 7x7:

And here is an 8x8:

+---+---+---+---+---+---+---+---+
| | | |
|---+---+---+---+---+ +---+---|
| | | | |
|---+---+ +---+ +---+---+ |
| | | | | | |
| + +---+ + + +---+ |
| | | | | |
|---+ + +---+---+ + +---|
| | | | | | |
| +---+---+ +---+---+---+ |
| | | | |
| +---+ +---+ +---+---+ |
| | | | | | |
|---+---+---+---+ +---+ +---|
| | | |
+---+---+---+---+---+---+---+---+

It can be solved by hand, though it took me a while.

It can. Darn you to heck, Richard, it took me an *hour*!

The biggest problem I have with these is vestigial "Latin square"
thinking, from doing too many Sudoku-style puzzles.

Anyway, I did this one by hand; I believe it's the correct solution.

Anyway, I did this one by hand; I believe it's the correct

Anyway, I did this one by hand; I believe it's the

Anyway, I did this one by hand; I believe it's

Anyway, I did this one by hand; I believe

Anyway, I did this one by hand; I

Anyway, I did this one by hand;

Anyway, I did this one by

Anyway, I did this one

Anyway, I did this

Anyway, I did

Anyway, I

Anyway... here it is.



+-----+-----+-----+-----+-----+-----+-----+-----+
| 1 . 3 . 2 | 4 . 1 . 3 | 1 . 2 | +-----+-----+-----+-----+-----+ +-----+-----+
| 2 . 4 . 1 . 3 | 5 | 2 . 5 | 3 |
+-----+-----+ +-----+ +-----+-----+ +
| 1 | 3 | 5 | 2 . 1 | 3 . 4 | 1 |
+ + +-----+ + + +-----+ +
| 2 | 4 . 1 | 3 . 4 | 5 | 2 . 5 |
+-----+ + +-----+-----+ + +-----+
| 1 | 5 . 2 | 5 | 2 . 1 | 4 | 3 |
+ +-----+-----+ +-----+-----+-----+ +
| 2 | 4 . 3 . 1 | 3 | 5 . 2 . 1 |
+ +-----+ +-----+ +-----+-----+ +
| 3 | 1 | 2 | 4 . 2 | 4 . 3 | 4 |
+-----+-----+-----+-----+ +-----+ +-----+
| 2 . 4 . 3 . 1 | 5 . 1 | 2 . 1 | +-----+-----+-----+-----+-----+-----+-----+-----+

--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <r0i5as$41j$1@dont-email.me>,
Richard Heathfield <rjh@cpax.org.uk> wrote:

Spoiler alert: solution below (which I >>>think<<< is correct).

It is.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

In article <r0d1mh$jsk$1@macpro.inf.ed.ac.uk>,I wrote:

I am pessimistic about finding a 6x6, at least with a maximum group
size of 5, as one can easily show it must have at least 10 groups, and
every solvable 6x6 grid I have found so far has either 8 or 9 groups.

I should have noticed this sooner:

Divide a 6x6 grid into 9 2x2 blocks. Each block can contain at most
one 1, otherwise they would be adjacent. So a solvable 6x6 suguru
cannot contain more than 9 1s, and therefore not more than 9 groups.

So there is no "clueless" 6x6 suguru with maximum group size 5 that
has a unique solution.

It is still possible that there exist ones with maximum group size 6,
7, or 8. One with maximum group size 8 would have to have exactly one
group of each size 1-8.

-- Richard

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)