The New Sudoku Players' Forum

[Smythe Dakota]

All that discussion of the 6x6 ATK puzzles recently has led me to wonder: Are all the 6x6 ATK puzzles isomorphic to each other? Or at least those that have that same pattern (or a rotation or reflection of it)?

Let us define a potential Kakuro grid as a finite rectangular lattice of white and black cells having the following properties:

• The grid is connected, i.e. every white cell can be reached from any other white cell via a finite sequence of single-cell horizontal and/or vertical moves.
• Every white cell has at least one immediate horizontal neighbor and at least one immediate vertical neighbor (i.e. no 1-digit words are permitted).
• Every row and every column contains at least one (and hence at least two) white cells.
• No word may be longer than 9 cells (or some other number, depending on what number system base is being used).

Let us further define a legitimate Kakuro grid as a potential grid for which there exists a legitimate sum set (i.e. a set of sums, one sum for each word) that makes the grid a legitimate Kakuro puzzle with one and only one solution.

Finally, let us define a uniquely legitimate Kakuro grid as a legitimate grid for which there exists, up to isomorphism, only one legitimate sum set.

Now, I do believe that a 2x2 grid with no black cells is a uniquely legitimate Kakuro grid. Check me out on this, I'm not completely sure.

What other uniquely legitimate Kakuro grids are there? Is that 6x6 ATK grid, with a black cell in two corners and two black cells in the middle. a uniquely legitimate grid?

Gee, we could have our own Patterns Game conversation, just like the one up there in the Sudoku thread.

Bill Smythe

[denis_berthier]

I do believe that a 2x2 grid with no black cells is a uniquely legitimate Kakuro grid. Check me out on this, I'm not completely sure.

It seems to me that the 2x2 puzzles with the following unique solutions are not iso.

Code: Select all

1 2
3 4

Code: Select all

1 2
3 5

Code: Select all

1 2
3 6


Code: Select all

1 2
3 7


...

What other uniquely legitimate Kakuro grids are there? Is that 6x6 ATK grid, with a black cell in two corners and two black cells in the middle. a uniquely legitimate grid?

Your question is interesting. However, you should be more precise about isos. Are you speaking of the isos valid for any puzzle of fixed size (in which case there are only few symmetries) or the isos valid for some given pattern of black cells (in which case there may also be row and/or column permutations)?

In the same vein, one could ask for patterns that have a unique (upto isos) solution with no given at all. This is logically equivalent to your requirement (whichever of the above 2 definitions of an iso one adopts).

[Serg]

Hi, colleagues!
First, we should define - what is isomorphism for kakuro?
To my mind, two puzzles (not only kakuro puzzles) are isomorphic, if they have equivalent (or essentially the same) solution pathes. Solution path is a sequence of steps. Each step for kakuro is applying some solving rule to a word (or entry), which eliminates some cadidates from word's cell. So, if we have 2 different kakuro puzzles such, that each solution path of the first puzzle is equivalent to some solution path of the second puzzle and vice versa, then both puzzles are isomorphic.

Serg

[Smythe Dakota]

I agree that the concept of isomorphism needs to be nailed down a bit more, especially in the context of the current thread.

To begin with, two puzzles must be considered isomorphic in case one can be obtained from the other by:

• a reflection (horizontal, vertical, or diagonal), or
• a rotation (90, 180, or 270 degrees), or
• replacing the value x in each cell by 10-x, and the sum s of each n-cell word by 10*n-s, or
• any combination of two or more of these, or of any further criteria that may be added to the list.

As has been pointed out, other criteria should be admissible, too. For example, any puzzle with

oox
ooox
xxo

in the upper left corner (o and x represent white and black cells, respectively) would have an automorphism obtained by switching cells r1c1-r2c1 with cells r1c2-r2c2.

Once the definition of isomorphism is nailed down completely, it becomes interesting to ask if there is any such thing as a pattern with no sums and no givens at all, and for which there is only one pair of sum sets that yields a pair of puzzles each of which has a unique solution. Sort of a "uniqueness of uniqueness" question. I say "pair" because there will always be the 10-x automorphism.

Bill Smythe

[denis_berthier]

I'm not sure my 2x2 counter-example completely rules out all the possibilities (I have no time to check), but it probably makes them very rare.
A counter-counter-example, i.e. a no-given one-solution (modulo isos) puzzle would therefore be welcome before going further.

[Serg]

Hi, Bill!

... two puzzles must be considered isomorphic in case one can be obtained from the other by:

• a reflection (horizontal, vertical, or diagonal), or
• a rotation (90, 180, or 270 degrees), or
• replacing the value x in each cell by 10-x, and the sum s of each n-cell word by 10*n-s, or
• any combination of two or more of these, or of any further criteria that may be added to the list.

As has been pointed out, other criteria should be admissible, too. For example, any puzzle with

oox
ooox
xxo

in the upper left corner (o and x represent white and black cells, respectively) would have an automorphism obtained by switching cells r1c1-r2c1 with cells r1c2-r2c2.

I am afraid, the "isomorphism" concept for kakuro is not so evident as sudoku isomorphism. For example, let's consider 2 kakuro 2 x 2 puzzles, presented by their solutions:

Code: Select all

K1      K2

1 2     1 3
2 9     3 8

I treat these puzzles as isomorphic, because they have the same solution paths (we should replace "2" candidate in K1 solution path by "3" candidate to get K2 solution path).

... it becomes interesting to ask if there is any such thing as a pattern with no sums and no givens at all, and for which there is only one pair of sum sets that yields a pair of puzzles each of which has a unique solution. Sort of a "uniqueness of uniqueness" question.

Very interesting idea! If we would apply this idea to sudoku, we would be asked for finding sudoku patterns having 1 valid puzzle only. If such sudoku patterns could exist, one could publish such sudoku puzzles without any clues, but marking cells containing clues only ("white cells" and "black cells" for sudoku?). But I've never heard about sudoku patterns having 1 valid puzzle only. Maybe they do exist ...

Serg

[Edited. I corrected typos.]

[dobrichev]

...If we would apply this idea to sudoku, we would be asked for finding sudoku patterns having 1 valid puzzle only. If such sudoku patterns could exist, one could publish such sudoku puzzles without any clues, but marking cells containing clues only ("white cells" and "black cells" for sudoku?). But I've never heard about sudoku patterns having 1 valid puzzle only. Maybe they do exist ...

A good candidate for such sudoku pattern is the 16-given puzzle which determines "sf" grid up to isomorphism.