Portable Puzzle Collection

bbc micro/electron/atom/risc os coding queries and routines
Post Reply
User avatar
SimonSideburns
Posts: 564
Joined: Mon Aug 26, 2013 9:09 pm
Location: Purbrook, Hampshire
Contact:

Portable Puzzle Collection

Post by SimonSideburns » Sat Jan 11, 2020 3:06 pm

I've always enjoyed playing puzzle games.

On my phone (running Android) and my Windows laptop I have installed a set of puzzles called Simon Tatham's Portable Puzzle Collection (hereafter referred to as STPPC). One of those puzzles, Keen is the same as a Japanese puzzle called KenKen. You get a grid, say 5x5 in size. Every digit from 1 to 5 must be in every row and every column (in essence a magic square). Regions consisting of one or more squares are defined and can be of irregular shapes and sizes).

Some time later, I was given a book containing a bunch of KenKen puzzles, and rather than try to solve them in the book (e.g. having to use pencil and possibly using an eraser when making mistakes), I'd prefer to solve them in STPPC.

Within STPPC you can enter a game ID which is a way to encode the starting grid of a puzzle. I've worked out how the first part of the encoding works (which describes the lines defining regions of the grid), but in the second part it provides a value and an arithmetic sign (plus, minus, times or divide) which provides you with the answer and the sign used to determine the sum used, which should help you to work out the values in each separate square of the region.

For example, a puzzle could be a 5x5 grid, one of the regions could be two squares in size and have an answer of 12x, indicating the digits could be a 3 and a 4 only (since you can only have the digits 1-5 in a row or column).

Here's the layout of the first puzzle of my book. I hope the ASCII art works:

Code: Select all

Puzzle 1
+=====+=====+=====+=====+=====+=====+
|30X  |1-   '     |1-   '     |3-   |
|     |     '     |     '     |     |
+ - - +=====+=====+=====+=====+ - - +
|     '     |14+  '     |4    |     |
|     '     |     '     |     |     |
+=====+=====+=====+ - - +=====+=====+
|5+   '     |3-   |     |3/   |5-   |
|     '     |     |     |     |     |
+=====+=====+ - - +=====+ - - + - - +
|1-   |3/   |     |48X  |     |     |
|     |     |     |     |     |     |
+ - - + - - +=====+ - - +=====+=====+
|     |     |     '     |15X  |9+   |
|     |     |     '     |     |     |
+=====+=====+=====+=====+ - - + - - +
|2    |2/   '     |     '     |     |
|     |     '     |     '     |     |
+=====+=====+=====+=====+=====+=====+

My problem occurs with regions consisting of single grid squares with no mathematical sign and how to encode them into a Game ID.

The source code of STPPC is available and I've been through it a few times. Here's the code for this particular puzzle.

If you search within the code for the word inelegant, it should return two results. The second one seems to hold a clue. Maybe it has to be a + or -, or am I barking up the wrong tree?

If anyone gets the chance to try encoding the puzzle supplied into the format required by the Game ID to get the grid into the puzzle, that would be great. It would at least tell me if I am right so far with my understanding of the encoding used.

One last thing. I like these puzzles so much I am now wondering if there's any way to get them up and running on a Beeb, but I don't even really know the ins and outs of C enough to know if that's doable or not.
Just remember kids, Beeb spelled backwards is Beeb!

User avatar
BigEd
Posts: 3436
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Portable Puzzle Collection

Post by BigEd » Sat Jan 11, 2020 5:21 pm

Possible hints in comments in keen.c:

Code: Select all

     * Encode the block structure. We do this by encoding the
     * pattern of dividing lines: first we iterate over the w*(w-1)
     * internal vertical grid lines in ordinary reading order, then
     * over the w*(w-1) internal horizontal ones in transposed
     * reading order.
     *
     * We encode the number of non-lines between the lines; _ means
     * zero (two adjacent divisions), a means 1, ..., y means 25,
     * and z means 25 non-lines _and no following line_ (so that za
     * means 26, zb 27 etc).

     * Now go through and compress the string by replacing runs of
     * the same letter with a single copy of that letter followed by
     * a repeat count, where that makes it shorter. (This puzzle
     * seems to generate enough long strings of _ to make this a
     * worthwhile step.)
So a puzzle encoded with
https://www.chiark.greenend.org.uk/~sgt ... s3m4d2s1d2
falls into two parts:
  • b_10a_a3_3a_3aa__a_3a_b__b__baa
    m360a8a5d2s3a7m4a7m12s4d3d3s3m4d2s1d2
where the second part is the annotations, in reading order, with m360 meaning 'multiply by 360'
and the first part is describing the interior lines, which are either missing or present, encoded as the gap length, and then run-length encoded because runs of no gaps are common:
  • b
    _10
    a
    _
    a3
    _
and so on, meaning
  • 2
    0 0 0 0 0 0 0 0 0 0
    1
    0
    1 1 1
    0
and so on, meaning
  • gap of 2 lines, which is to say it's a run of three blocks
    gap of 0 lines, which is to say it's a run of one block
    repeated 10 times
    gap of 1 line, which is to say it's a run of two blocks
So this

Code: Select all

Puzzle 1
+=====+=====+=====+=====+=====+=====+
|30X  |1-   '     |1-   '     |3-   |
|     |     '     |     '     |     |
+ - - +=====+=====+=====+=====+ - - +
|     '     |14+  '     |4    |     |
|     '     |     '     |     |     |
+=====+=====+=====+ - - +=====+=====+
|5+   '     |3-   |     |3/   |5-   |
|     '     |     |     |     |     |
+=====+=====+ - - +=====+ - - + - - +
|1-   |3/   |     |48X  |     |     |
|     |     |     |     |     |     |
+ - - + - - +=====+ - - +=====+=====+
|     |     |     '     |15X  |9+   |
|     |     |     '     |     |     |
+=====+=====+=====+=====+ - - + - - +
|2    |2/   '     |     '     |     |
|     |     '     |     '     |     |
+=====+=====+=====+=====+=====+=====+
should be encoded as
https://www.chiark.greenend.org.uk/~sgt ... 8m15a9a2d2

Edit: unfortunately the page says there's no solution!

User avatar
SimonSideburns
Posts: 564
Joined: Mon Aug 26, 2013 9:09 pm
Location: Purbrook, Hampshire
Contact:

Re: Portable Puzzle Collection

Post by SimonSideburns » Sat Jan 11, 2020 7:57 pm

Thanks for taking a look at this for me. I was getting to the point where I couldn't figure it out for looking.
BigEd wrote:
Sat Jan 11, 2020 5:21 pm
So this

Code: Select all

Puzzle 1
+=====+=====+=====+=====+=====+=====+
|30X  |1-   '     |1-   '     |3-   |
|     |     '     |     '     |     |
+ - - +=====+=====+=====+=====+ - - +
|     '     |14+  '     |4    |     |
|     '     |     '     |     |     |
+=====+=====+=====+ - - +=====+=====+
|5+   '     |3-   |     |3/   |5-   |
|     '     |     |     |     |     |
+=====+=====+ - - +=====+ - - + - - +
|1-   |3/   |     |48X  |     |     |
|     |     |     |     |     |     |
+ - - + - - +=====+ - - +=====+=====+
|     |     |     '     |15X  |9+   |
|     |     |     '     |     |     |
+=====+=====+=====+=====+ - - + - - +
|2    |2/   '     |     '     |     |
|     |     '     |     '     |     |
+=====+=====+=====+=====+=====+=====+
should be encoded as
https://www.chiark.greenend.org.uk/~sgt ... 8m15a9a2d2

Edit: unfortunately the page says there's no solution!
Oops. In my haste to get my topic in I made an error. Does this work out any better?

https://www.chiark.greenend.org.uk/~sgt ... 8m15a9a2d2

Code: Select all

Puzzle 1
+=====+=====+=====+=====+=====+=====+
|30X  |1-   '     |1-   '     |1-   |
|     |     '     |     '     |     |
+ - - +=====+=====+=====+=====+ - - +
|     '     |14+  '     |4    |     |
|     '     |     '     |     |     |
+=====+=====+=====+ - - +=====+=====+
|5+   '     |3-   |     |3/   |5-   |
|     '     |     |     |     |     |
+=====+=====+ - - +=====+ - - + - - +
|1-   |3/   |     |48X  |     |     |
|     |     |     |     |     |     |
+ - - + - - +=====+ - - +=====+=====+
|     |     |     '     |15X  |9+   |
|     |     |     '     |     |     |
+=====+=====+=====+=====+ - - + - - +
|2    |2/   '     |     '     |     |
|     |     '     |     '     |     |
+=====+=====+=====+=====+=====+=====+
At least it confirms my suspicion that single cells can use either addition or subtraction since it shouldn't matter.
Just remember kids, Beeb spelled backwards is Beeb!

User avatar
BigEd
Posts: 3436
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Portable Puzzle Collection

Post by BigEd » Sat Jan 11, 2020 8:35 pm

The code comments say addition or multiplication, I think.

Edit: yes, your revised puzzle has a solution!

User avatar
SimonSideburns
Posts: 564
Joined: Mon Aug 26, 2013 9:09 pm
Location: Purbrook, Hampshire
Contact:

Re: Portable Puzzle Collection

Post by SimonSideburns » Sat Jan 11, 2020 9:08 pm

Brilliant.

I had everything correct but the only thing I wasn't sure of was what to do with single cells (I should have known however which has annoyed me!).

Now I know, I can start to work out the Game IDs for all 100 puzzles in the book.

Might take me some time, but I do like giving myself these challenges.

You're right about the comments stating that it can be add or mul, but personally I don't see how multiply works with one single digit so I'll stick with add in this case.
Just remember kids, Beeb spelled backwards is Beeb!

User avatar
BigEd
Posts: 3436
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Portable Puzzle Collection

Post by BigEd » Sat Jan 11, 2020 9:55 pm

SimonSideburns wrote:
Sat Jan 11, 2020 3:06 pm
The source code of STPPC is available and I've been through it a few times. Here's the code for this particular puzzle.
...
One last thing. I like these puzzles so much I am now wondering if there's any way to get them up and running on a Beeb, but I don't even really know the ins and outs of C enough to know if that's doable or not.
I do agree it would be nice to see one or more of the Puzzle Collection implemented on a Beeb. I suspect a reimplementation from scratch might be called for, which is to say I'm pessimistic about porting the C. Unless... unless one used RobC's technique and ran the compiled C on a Native ARM second processor.

But my pessimism isn't necessarily a good judgement. It might well be that these puzzles could be compiled for a 6502 second processor.

User avatar
BigEd
Posts: 3436
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Portable Puzzle Collection

Post by BigEd » Sun May 24, 2020 8:08 am

Just revisiting this idea of getting Portable Puzzles onto the Beeb.

The really clever bit of Portable Puzzles is that there's any number of randomly generated puzzles, and all are valid puzzles with a unique solution, and so evidently there's a solver in there to help with the generation. (Indeed, the user interface offers a 'solve' button.)

But that could all be dropped, at the cost of including some number of curated puzzles - maybe a hundred - with the Beeb version: now all that's needed is a nice user interface and the relatively simple checking code to see if the constraints are met by the user's current effort.

I think that should reduce the difficulty of a port by a great amount, and leaves open the possibility of adding the solver back in at a later point, and then using the solver to offer randomly generated puzzles.

(I've just had a quick play with Tracks, having played Tents previously, and before that Map and Net)

User avatar
SimonSideburns
Posts: 564
Joined: Mon Aug 26, 2013 9:09 pm
Location: Purbrook, Hampshire
Contact:

Re: Portable Puzzle Collection

Post by SimonSideburns » Mon May 25, 2020 9:17 am

The puzzles are a wonderful way to spend time.

I mostly play Pearl, Loopy, Net, Galaxies, Map, Unequal, and Slant, but do dip in and out of others as and when I'm in the mood. Such a variety.
Just remember kids, Beeb spelled backwards is Beeb!

User avatar
BigEd
Posts: 3436
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: Portable Puzzle Collection

Post by BigEd » Sat Jun 06, 2020 6:23 pm

Recently I've got into Tents, Towers, and Tracks - that's in increasing order of 'reward'

User avatar
SimonSideburns
Posts: 564
Joined: Mon Aug 26, 2013 9:09 pm
Location: Purbrook, Hampshire
Contact:

Re: Portable Puzzle Collection

Post by SimonSideburns » Sun Jun 07, 2020 4:05 pm

BigEd wrote:
Sat Jun 06, 2020 6:23 pm
Recently I've got into Tents, Towers, and Tracks - that's in increasing order of 'reward'
Ah, Towers. Some randomly generated grids are fairly easy to solve but now and again there's one that provides extra head scratching for a while.

I have played Tracks too, but not so much Tents.

There are some real gems in there.
Just remember kids, Beeb spelled backwards is Beeb!

Post Reply

Return to “programming”