• Suguru

    From Richard Tobin@21:1/5 to All on Thu Jan 23 11:17:43 2020
    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)
  • From Richard Heathfield@21:1/5 to Richard Tobin on Thu Jan 23 15:33:11 2020
    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)
  • From Richard Tobin@21:1/5 to rjh@cpax.org.uk on Thu Jan 23 16:25:14 2020
    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)
  • From Richard Heathfield@21:1/5 to Richard Tobin on Thu Jan 23 17:31:08 2020
    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)
  • From Jonathan Dushoff@21:1/5 to Richard Tobin on Thu Jan 23 11:25:33 2020
    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)
  • From Richard Tobin@21:1/5 to Richard Tobin on Thu Jan 23 21:03:13 2020
    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)
  • From Richard Tobin@21:1/5 to jdushoff@gmail.com on Thu Jan 23 20:49:02 2020
    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)
  • From Richard Tobin@21:1/5 to rjh@cpax.org.uk on Thu Jan 23 21:10:04 2020
    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)
  • From Richard Heathfield@21:1/5 to Richard Tobin on Thu Jan 23 21:42:07 2020
    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)
  • From Richard Tobin@21:1/5 to rjh@cpax.org.uk on Fri Jan 24 00:48:25 2020
    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)
  • From Richard Tobin@21:1/5 to All on Sat Jan 25 18:16:04 2020
    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)
  • From Richard Heathfield@21:1/5 to Richard Tobin on Sat Jan 25 19:35:55 2020
    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)
  • From Richard Tobin@21:1/5 to rjh@cpax.org.uk on Sat Jan 25 19:48:12 2020
    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)
  • From Richard Tobin@21:1/5 to All on Fri Feb 7 21:16:21 2020
    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)