Jigsaw Layouts with Variable-sized Regions

One of the good things about using the value zero in number-place (Latin Square) puzzles is that we can then construct puzzles on a 10x10 grid and yet still require only one digit to be placed in each cell. But a 10x10 grid requires Sudoku(Jigsaw)-style regions to be defined, otherwise you need to have a very large number of "givens".

The only "regular tiling" (by which I mean a division into regions that are like floor tiles, each being the same size and shape) for a 10x10 grid is that of rectangular 2x5 blocks. This is also true of the 8x8 grid, which only tiles with 2x4 blocks. The elegance of the standard Sudoku puzzle is, of course, largely due to the simple fact that 9 = 3x3.

I've been working on my puzzle-production software, making it capable of producing SSZ puzzles on a 10x10 grid with jigsaw regions, and a rather novel idea occurred to me - why not allow regions that are not only different in shape, but different in size? All numbers in any region have to be different, of course, but a region does not have to contain a complete set!

For want of a better name, I've called this VSR (Variable-sized Regions). The standard placement rule for any puzzle with this layout is:

Quote

Place 1 to N in each row and column. No value can be repeated within any bold-lined area.

A simple variation, but the effect is quite profound, and is best illustrated by example! The attached file is a Skyscraper Zero puzzle with VSR on a 10x10 grid.


PS: I should of course note that, like SSZ, while the idea seemed novel to me at the time, this does not mean it's really a novel idea.

That's a great puzzle and I think constraints like this are good fun. There have been several Sudoku variants that include regions like this (the simplest perhaps is where this constraint [that numbers can't repeat] is used on all diagonals, including those shorter than 9 long; see also 'isosudoku'), but I don't recall ever seeing it combined with a skyscraper variant before.



Edited 1 time(s). Last edit at 04/26/2011 04:08PM by gareth.

Another fun variant along similar lines is when you allow numbers to repeat in a region based on certain rules, the simplest of which is that there must be precisely one number that occurs twice in each bold-lined region (and each other number occurs once). This is sometimes called 'surplus sudoku'. Often to make this work you'll need to have one 'special' region, for example in a 9x9 puzzle you'd have a 1-region cage left over and whatever went in here would be the one number that didn't ever occur twice in a region (and each other number would only be able to repeat the one time). At least I think that's how it all works out.

Thanks for pointing me to that, I hadn't considered the possibility of regions with more than N cells (N being the grid size).

I looked at the link you provided and I can see that "Surplus Sodoku" as defined must always involve a one-cell region on any size grid, since by that definition, you have N-1 regions of size N+1, which covers N²-1 cells which leaves one remaining.

As you said, the isolated cell's value can't be a repeater in any of the larger regions, otherwise it would have to occur more than N times all up.

I happen to dislike single-cell regions, so it would be nice to have repeating values without them.

Is this possible? Yes, but not if we want cages to all be the same size, K. This requires that N² is divisible by K, and we want K>N, so it doesn't work at all for N = 5, 7 or 9, and for N = 6, 8, 10 it only works with K = 2N, which is not particularly interesting. The only other case that works is N=6, K=9.

So, if we want any regions to have more than N cells, then we will generally need some regions with less than N cells.

In other words, we need VSR

We just need to extend that rule I gave above like this:

• if a region has N or less cells no digit can be repeated

• if a region has more than N cells then every digit must appear at least once

This rule allows for oversized regions of any size in any of the regular puzzle formats, and greatly extends the range of possible region design patterns. I will modify my software to implement this and I hope to create some interesting examples. Oversize regions should, theoretically, tend to increase puzzle complexity.

OK, I've got the generalised VSR system working, and have attached two samples, with grid size N = 7 and 8.

Both have nice symmeteric layouts using 3x3 regions, and this definitely adds an interesting twist to the solving process.

With N=7 a region with 9 cells has two values occurring twice, or one value occurring 3 times. For N=8 a 9-cell region has just the one value occurring twice.

The most significant effect is that you have to be very careful about using known values in a region to eliminate candidate cells in intersecting rows or columns - this can only be done safely when you know what the repeating values are.

The examples will show you just what I mean - I completely stuffed up my first attempt at solving the second puzzle by forgetting this important principle!

Enjoy!

Hi Mathimagics!

I can't comment on the mechanics of these puzzles but just wanted to say I have downloaded the three puzzles you attached above and have had a very enjoyable afternoon solving them. It took me more than one attempt on each one ( I occasionally forgot to take the '0' into account, but I guess that will resolve itself with practise - was also watching the World Snooker semi-finals at the same time!) but I finally solved each one, and a great sense of satisfaction that gave me! I'd love to see some more of these variants in Xtra. The difficulty level was just about right for me - any harder and I think I'd be struggling.

Now for a go at the Killer version!

As regards the Cryptic ones, I'm not really sure how to start with these, but then I was stuck with the Krypto Kakuros that inspired you until you were kind enough to give me a few hints and now they have become one of my firm favourites. It you get the time, it would be great to have a bit of a 'walk through' of one of the examples, but no problem if not.

I'm very happy to hear you like these puzzles. I enjoyed solving them myself so I am not surprised you liked them.

Some clues for the cryptics:

Draw up a yes/no grid like those used in Logic Puzzles, with the letters along the top and numbers 0 to N-1 down the side. This will help you eliminate potential letter/value combinations - crossing out those combinations you know can't work. The number of letters given might be less than N, in which case this grid won't be square.

Start with which letter must be 1. That letter must appear on every side of the grid as a VC (visibility-count) clue. It might occur twice on some sides (this being SSZ), but no more than twice. This should enable you to quickly determine which letter is 1.

Zero can't occur as a visibility count clue (VC), so a letter could only be zero if it only occurs inside the grid, ie: as a given. A letter that occurs only inside the is not necessarily 0, but if we do have a full set of N letters then it must be.

Once you have found 1, then you can fill in some of the cells with the max value, and can start to cross out cells in the yes/no grid.

For example, say the grid size is 7, and we have value 6 placed into column 3 of the top row, ie xx6xxxx. If the VC on the left is B, then B must be 2 or 3, so in our yes/no grid we can cross out B4, B5 and B6.

It should then be possible to at the very least to decide which letters can have low values (eg 2,3) and by elimination which can be higher.

That should get you started!

Thanks for taking the trouble to write out those tips - much appreciated. I've had a busy week this week so not had time to give it a go yet, but I'll get around to it eventually and give you some feedback!