The New Sudoku Players' Forum

[r.e.s.]

Readers of this forum might enjoy the following paper by Tim Chow ...
Why Should Latin Squares Have All the Fun? (pdf file)
and also
"Pseudoku" (thread in the rec.puzzles newsgroup)

Here's his first example of "pseudoku", which seems especially neat. (This one's easy to solve, but I suppose they can get much more interesting.) ...

Code: Select all

. . . 6 . . . 5 . .
. 7 . . . . . . . 2
. . 9 . . . 1 . . .
. . . . . . . .
8 . . . 3 6 . .
. . . . . .
4 . . . .
. . . . 5
. 3 .
. . 1

Each row/column must contain all the numbers from 1 to the length of that particular row/column. (I've put a dot in each unsolved cell.)

I wonder if that can be extended to grids with solutions something like this ...

Code: Select all

  x x x   x x x
x x   x x
x x   x x x x x x x x
  x x x x     x x x
x x x x
  x x x x x x x x x x
  x x x x x
    x x x
    x x x   x x x x x
      x x x x x x 

where rows and columns can have "gaps" in them. I.e., in the picture, row#1 has length 6 (so contains 1-6), and col#1 has length 3 (so contains 1-3, etc.)

[udosuk]

I suspect what you're describing is very similar to the old "kakuro", with each of the sums being n(n+1)/2 where n is the length of the lines.

The differences were, in the 1st version, that cells can have values larger than 9, and in the 2nd version, that broken lines where allowed... (The second version looks exactly like a kakuro grid, except in kakuro sums of each section of the "broken lines" are given...)

[evert]

Code: Select all

. . . 6 . . . 5 . .
. 7 . . . . . . . 2
. . 9 . . . 1 . . .
. . . . . . . .
8 . . . 3 6 . .
. . . . . .
4 . . . .
. . . . 5
. 3 .
. . 1

Each row/column must contain all the numbers from 1 to the length of that particular row/column. (I've put a dot in each unsolved cell.)

I wonder if that can be extended to grids with solutions something like this ...

Code: Select all

  x x x   x x x
x x   x x
x x   x x x x x x x x
  x x x x     x x x
x x x x
  x x x x x x x x x x
  x x x x x
    x x x
    x x x   x x x x x
      x x x x x x 

where rows and columns can have "gaps" in them. I.e., in the picture, row#1 has length 6 (so contains 1-6), and col#1 has length 3 (so contains 1-3, etc.)

Should be possible with boxes also.
I'd like to see a puzzle like this with box constraint added.

[Smythe Dakota]

Code: Select all

. . . 6 . . . 5 . .
. 7 . . . . . . . 2
. . 9 . . . 1 . . .
. . . . . . . .
8 . . . 3 6 . .
. . . . . .
4 . . . .
. . . . 5
. 3 .
. . 1

That's neat! It's interesting that only 13 clues are required, smaller than the currently thought-to-be minimum 17 for regular puzzles. And this despite the lack of additional information usually provided by the smaller 3x3 squares.

Of course, there are only 68 points instead of 81, so that might explain part of the difference. In addition, certain types of reasoning can be used here that don't exist in the regular puzzles, such as "all 9's and 10's must be in the upper left 3x3 area, since otherwise either the row or the column (or both) will contain fewer than 9 points".

I suppose one nice feature is that no one can solve this using a computer, because nobody has bothered to write a program yet. I'm sure this is coming, however.

Bill Smythe

[r.e.s.]

Here's an example of yet another variation (with unique solution) ...

Code: Select all

      3 1   x       x
3     x x           5
x     6     5 x     x
x 8   4 0 x x x x 1 x
      x     x
x       x
4     x 3   x   x
      x   x 8   5   x
x x 5 8

The only rule: Each row and each column contains a set of consecutive numbers (in some order, with no repetitions).
The 'x's are the cells to be solved; e.g., in the top row, two of the four cells need to be solved.

[Smythe Dakota]

.... The only rule: Each row and each column contains a set of consecutive numbers (in some order, with no repetitions). ....

Are you allowed to count 0 as either 0 or 10 (just as an Ace in blackjack counts as 1 or 11)?

Better yet, are you allowed to wrap around, so that for example 8-9-0-1-2 counts as five consecutive numbers?

Bill Smythe

[r.e.s.]

Are you allowed to count 0 as either 0 or 10 (just as an Ace in blackjack counts as 1 or 11)?

Better yet, are you allowed to wrap around, so that for example 8-9-0-1-2 counts as five consecutive numbers?

No, those would be alternative variations (presumably for rows/columns containing no more than ten numbers -- which I wasn't assuming to be the general case). I made the posted example to have a unique solution when "consecutive" is taken literally with its usual meaning.

[r.e.s.]

Code: Select all

  x x x   x x x
x x   x x
x x   x x x x x x x x
  x x x x     x x x
x x x x
  x x x x x x x x x x
  x x x x x
    x x x
    x x x   x x x x x
      x x x x x x 

where rows and columns can have "gaps" in them. I.e., in the picture, row#1 has length 6 (so contains 1-6), and col#1 has length 3 (so contains 1-3, etc.)

Should be possible with boxes also.
I'd like to see a puzzle like this with box constraint added.

Here's a simple way to generate special cases -- which I'll call sub-sudokus -- of this type of puzzle with box constraints, by producing them from a starting sudoku puzzle. I think these always have a unique solution (assuming we start with a unique-solution sudoku). I've verified solution-uniqueness for all three of the following examples ...

Example 1
In three steps ...
(1) Start with an ordinary sudoku puzzle ...

Code: Select all

6 2 . | 3 . . | . . 9
. . 7 | . 6 8 | . . .
. 4 3 | . 9 . | . . .
------+-------+------
2 . . | . 3 6 | . . .
. . 9 | 8 . 5 | 6 . .
. . . | 7 4 . | . . 5
------+-------+------
. . . | . 1 . | 8 4 .
. . . | 6 8 . | 3 . .
1 . . | . . 3 | . 9 6

(2) solve it ...

Code: Select all

6 2 1 | 3 5 4 | 7 8 9
5 9 7 | 2 6 8 | 4 1 3
8 4 3 | 1 9 7 | 5 6 2
------+-------+------
2 5 4 | 9 3 6 | 1 7 8
7 1 9 | 8 2 5 | 6 3 4
3 6 8 | 7 4 1 | 9 2 5
------+-------+------
9 3 6 | 5 1 2 | 8 4 7
4 7 2 | 6 8 9 | 3 5 1
1 8 5 | 4 7 3 | 2 9 6

(3) remove all 7,8,9 digits, then replace with '.' all remaining digits that were not originally clues ...

Code: Select all

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

This is now the first example puzzle, which has only one rule:
Replace each '.' with a digit such that each row, column, and box contains all six digits 1,...,6.

(I've put '.'s instead of 'x's so printing with a large fixed-width font will give a bit more suitable grid for pencil-and-paper solving.)

Example 2
Using the same method, here's the result of reducing a 16-digit sudoku (with 4x4 boxes) to a 9-digit puzzle ...

Code: Select all

    1   | .     . |     . . | 5 2 7 .
. 2 . . |   8     |     .   |   . . .
. . .   | . 7 . 3 |   5   . |       
  .     | .     . | . . . 6 | . .   
--------+---------+---------+--------
9 .   . |   .   . | . .     |   1 . 
  .   . | . .     |   6 7   |   9 3 .
2   4 . |     7 . |   . . 3 |     6 
  .     | .   3 4 | .   1   | 2 .   .
--------+---------+---------+--------
    .   |   . 5 . | 6     . | . 3   .
. . . 4 |   3   2 |       . | 6     8
  .   . | . .     | 4 . . . |   .   
    8 . | .   .   |   .   . |   . 9 2
--------+---------+---------+--------
4     . | .   8   | . 7 .   | .   . 
.   . 5 | . 1 .   | . 9     | 7     
. 8     |   . . . | .       | 4   . .
3   .   |     .   | .   . . | .   5 9

Replace the '.'s to make each row, column, and box contain all nine digits 1,...,9.

Example 3
And finally this one by reducing a 12-digit sudoku (with 3x4 boxes) to a 10-digit puzzle ...

Code: Select all

. . 4   |   1 2 . | 6 3 . .
. . 2 . | 3 . 9 4 |     . .
.   6 . |   . . 5 | 9 4 . .
--------+---------+--------
5 3   . | . . . . | . 2   8
. . . 0 | 4   . 8 | . 9 . 
  . . 4 | .   . . | . . . .
--------+---------+--------
. . 1   | . . 7   | . . 6 .
3 0 . . | 6 . . . |     4 .
. .   . | 2 .   . | . . . 7
--------+---------+--------
1 . . . | . . 6 . | . 7   
    . . | 1 0 4 . | 2 . . .
. 7 5 . | 8 .     | 0 . . .

Replace the '.'s to make each row, column, and box contain all ten digits 1,...,9,0 (abbreviating 10 as 0 for convenience).

The same method can reduce any n-digit sudoku to such an m-digit sub-sudoku (1 < m < n), with the only rule being to replace the '.'s with digits to make each row, column, and box contain all the digits 1,...,m. (I suppose sub-sudokus can be extracted from other types of sudoku variant, e.g. jigsaws, etc., as well as from themselves.)

As expected, it seems that the sub-sudokus of a given n-digit starting sudoku increase in difficulty as m increases from 1 to n. Also, from a given n-digit starting sudoku, various "disjoint sub-sudokus" can be produced in an obvious way by reducing to disjoint sets of digits.

[RW]

I think these always have a unique solution (assuming we start with a unique-solution sudoku).

Yes, you can be 100% sure that they always have a unique solution if you construct them the way you said. In fact you could reduce many candidates and still have a unique solution This can be proved with an basic attribute of all puzzles. As we know, all numbers are solved by naked or hidden singles. Other techniques reduce the possibilities. This means that in the end, the only way numbers a affect other numbers b is by "getting in the way", eliminating a possible placement for that number in the unit.

So when you made your first puzzle, you left blank spots (=not possible cells) where all numbers 7,8 and 9 had been. This gives the solver just as much information as filling those boxes with numbers 7, 8 and 9 would give him. Therefore, when making a puzzle like this, you should leave in all numbers you are about to remove, then reduce as many as possible of the remaining numbers and only then remove the numbers that leave empty cells. Your example could like this be reduced to:

Code: Select all

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


and still have a unique solution.

RW

[r.e.s.]

you should leave in all numbers you are about to remove, then reduce as many as possible of the remaining numbers and only then remove the numbers that leave empty cells.

Let the term "n-digit puzzle" refer to a puzzle whose solution uses n different digits, and let the term "sub-sudoku" refer to a puzzle constructed as I described previously. Then, for each chosen m-digit subset of the given n digits (1 <= m <= n), every valid n-digit sudoku puzzle has exactly one m-digit sub-sudoku using the chosen subset of digits.

Now compare the followng two procedures for reducing the number of clues, supposing that both start with the same valid n-digit sudoku puzzle S, and both use the same m-digit subset:
(1) First find the m-digit sub-sudoku of S (call it M), and then reduce the number of clues in M (if possible) to form a unique-solution "reduced-clues" puzzle.
(2) First reduce the number of clues in S (if possible) to form a unique-solution "reduced-clues" sudoku (call it R), and then find the m-digit sub-sudoku of R.

Can every puzzle obtained by method (1) also be obtained by method (2)? And vice versa?

E.g., isn't your "reduced-clues" puzzle above obtainable by either (1) or (2)?

[RW]

E.g., isn't your "reduced-clues" puzzle above obtainable by either (1) or (2)?

Yes, of course it is. In a way you could say that I used them both, I started with the full puzzle S and filled in all numbers not included in the m-digit subset M. Then I removed as many digits as possible from M, still maintaining a unique solution for S (don't know if it's the most reduced form, just removed them randomly until there was no more removable digits in M).

So in a way I used method
(2) I removed the clues from a full puzzle S
(1) By filling in all numbers not included in M (equivalent to writing in blank cells that cannot hold a number) I first found the sub-sudoku M and reduced the clues in M.

My suggestion of how to make a reduced puzzle was simply based on the fact that most people who make puzzles have a computerprogram that tell them what clues can be removed from a "normal" grid, so I told you how this can be done in such a program. I don't have such a program myself, I used this program. If you wish to make Sub-Sudokus by first writing in blank cells for all cells not included in M and then reduce M, you'll do the same thing I did, but in a harder way. Remember, it doesn't matter if the cells not included in M are just blank, hold numbers not in cluded in M or are filled with bananas, the effect on M is still the same.

Btw. I haven't seen sub-sudokus like this before, but certainly combined sub-sudokus. An odd-even sudoku can be seen as two different sub-sudokus in the same grid and a "147-sudoku" is actually three sub-sudokus in the same grid.

RW

[Smythe Dakota]

.... No .... I made the posted example to have a unique solution when "consecutive" is taken literally with its usual meaning.

But I still need to know, is 0 low or high? i.e. does it precede 1, or is it being used as a symbol for 10? (Of course, in a ten-cell row or column, it makes no difference.)

For example, if I have a three-cell row, and two of the cells are 8 and 9, can I conclude that the remaining cell is 7, or could it possibly be 0?

Bill Smythe

[Smythe Dakota]

.... But I still need to know, is 0 low or high? ....

In this example, I can answer my own question, because the only 0 among the clues appears in a 5-cell column with the digits 1 and 3.

I still think the wrap-around concept is better, though. It provides digit symmetry, in that any "rotation" of the digits, such as:

0 --> 4
1 --> 5
2 --> 6
3 --> 7
4 --> 8
5 --> 9
6 --> 0
7 --> 1
8 --> 2
9 --> 3

-- means that the puzzle is essentially unchanged (isomorphic).

Bill Smythe

[r.e.s.]

But I still need to know, is 0 low or high?

In the example you're referring to, '0' does not mean 'ten', and nine and zero are not consecutive numbers. The only constraint on the rows & columns in this type of puzzle is that each must contain a permutation of some set of consecutive numbers (consistent with the given clue numbers).

Although in the example it turns out that the solution has no number less than 0 nor greater than 9, that's not part of the given information. (In the type of puzzle I had in mind, more than ten numbers may appear in a row or column, in which case some of them will obviously be outside the range 0-9.)

I agree that another appealing variation is to restrict the puzzle to using ten digits in cyclic sequence, when there are no more than ten numbers in each row & column. More generally -- when rows or columns may contain up to n numbers -- a variant could use any specified set of n ordered symbols in cyclic sequence.