The New Sudoku Players' Forum

[Smythe Dakota]

Here's an idea for a parlor game, or contest:

The dealer (or some genius on this forum) produces an illegal puzzle, i.e. a puzzle with no solution. All givens, however, follow the rules (no two of the same digit in the same row, column, or box).

The idea is to fill in as many cells as possible, legally (i.e. without putting two of the same digit in the same row, column, or box). The player who can fill in the most cells is the winner.

For example, one player might be able to fill in 73 of the 81 cells before reaching a position where no additional cells can be filled legally. Another player, using a completely different solution, might be able to fill in 77 of the 81. The latter player is then the winner.

Another part of the contest could be to establish, somehow, the maximum and minimum number of cells that can be filled in, in the given puzzle. In the above example, 73 might be the minimum, and 77 the maximum.

Any takers?

[Scott H]

Richard's free PBeM server does this as a 2 player game. No givens, alternate turns placing one symbol, last person to move wins. That makes Richard's game a funky variant of Nim, for people who know about such things.

[Scott H]

Another twist on this idea as a sudoku variant: Puzzle designer supplies some givens so that a solution which maximizes the final number of givens is unique. Optionally, the maximum number of givens could be provided as part of the puzzle.

[r.e.s.]

Here's an idea for a parlor game, or contest:

The dealer (or some genius on this forum) produces an illegal puzzle, i.e. a puzzle with no solution. All givens, however, follow the rules (no two of the same digit in the same row, column, or box).

The idea is to fill in as many cells as possible, legally (i.e. without putting two of the same digit in the same row, column, or box). The player who can fill in the most cells is the winner.

Interesting. We can define "solution" for this game (or the one Scott H mentions) to be any candidate grid in which every cell contains exactly 0 or 1 candidates by the usual rules. It's easy to play around with the idea in solvers like Susser, etc.; might be challenging to determine, for a given puzzle, what is the least possible number of empty cells.

For example, what is the least possible number of empty cells in a "solution" to the following puzzle?

Code: Select all

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


The best I've managed is FIVE. <-- highlight to read

[r.e.s.]

Richard's free PBeM server does this as a 2 player game. No givens, alternate turns placing one symbol, last person to move wins. That makes Richard's game a funky variant of Nim, for people who know about such things.

If a "solution" for this game (or Smythe Dakota's) is any candidate grid in which every cell contains exactly 0 or 1 candidates by the usual rules, it would be interesting to know (however roughly) how many "solutions" there are altogether. It's obviously vastly more than the number of standard sudoku solutions, as these are just the completely-filled "solutions". But I wonder how it compares to the number of standard sudoku puzzles. (Something tells me we may never know either number.)

[HATMAN]

r.e.s.

On number of puzzles, given human ingenuity, you can only hope to have a finite number if you limit it strictly to plain vanilla Sudoku. In the case of any precisely defined puzzle type such as plain vanilla or plain killer an upper bound on the number of puzzles should be deducible.

HATMAN

[r.e.s.]

HATMAN,

The number in question is the number of candidate grids with the property that every cell contains at most one candidate (i.e., either none or one) by the usual rules -- no candidate digit occurs more than once in any row, column, or box.

This number is of course just some integer, though much larger than the number of standard solutions. (The standard solutions comprise a subset of these "solution" grids). By "knowing" this number or the number of standard puzzles, I was referring to knowing the number explicitly and precisely -- e.g., displaying its exact decimal representation.

[HATMAN]

r.e.s.

I do understand that. It is just that as the comment was posted in this "other" forum I started thinking about all possible Sudoku variants.

However given your exact definition, we can look at the number in terms of upper bounds on its value. Sometimes this approach is helpful - but I am not sure it would be in this case.

HATMAN

[HATMAN]

r.e.s.

In your definition of puzzle it might be more interesting to reduce it to the minimal ones - i.e. no value can be removed without giving multiple solutions. (You were probably implying this.)

HATMAN

[Scott H]

Here's an idea for a parlor game, or contest:

The dealer (or some genius on this forum) produces an illegal puzzle, i.e. a puzzle with no solution. All givens, however, follow the rules (no two of the same digit in the same row, column, or box).

The idea is to fill in as many cells as possible, legally (i.e. without putting two of the same digit in the same row, column, or box). The player who can fill in the most cells is the winner.

Interesting. We can define "solution" for this game (or the one Scott H mentions) to be any candidate grid in which every cell contains exactly 0 or 1 candidates by the usual rules. It's easy to play around with the idea in solvers like Susser, etc.; might be challenging to determine, for a given puzzle, what is the least possible number of empty cells.

For example, what is the least possible number of empty cells in a "solution" to the following puzzle?

Code: Select all

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


The best I've managed is ###

I can name that tune (err, solve that puzzle) with just ( TWO <-- highlight to read) empty cells.

[r.e.s.]

True or false? .... Given any invalid sudoku having no solution, it can be played (by the standard rules) until only two cells remain unsolved -- but it cannot be played until only one cell remains unsolved.

[Smythe Dakota]

True or false? .... Given any invalid sudoku having no solution, it can be played (by the standard rules) until only two cells remain unsolved -- but it cannot be played until only one cell remains unsolved.

Correct on the second, I would think. Once 80 dells have been filled, just fill in the 81st with whichever digit has been used only 8 times so far.

The first seems wrong:

Code: Select all

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


This seems to leave at 3 boxes unfillable - no 4 in the upper left box, no 7 in the upper center, and no 1 in the upper right.

Bill Smythe

[r.e.s.]

Nice counterexample!

[Scott H]

True or false? .... Given any invalid sudoku having no solution, it can be played (by the standard rules) until only two cells remain unsolved -- but it cannot be played until only one cell remains unsolved.

Many cells can be unfillable. No sudoku-constrained puzzle can have exactly one unfillable cell (since the rest of the puzzle would force its value).

If a sudoku-constrained puzzle has exactly two unfillable cells there are constraints on what the relative locations of the two cells are. They can't be in the same row, the same column, or different (vertical or horizontal) stacks.

[Smythe Dakota]

Next question: For which values of N do there exist impossible puzzles with exactly N unsolvable cells?

Also: If the same impossible puzzle has both N and M unsolvable cells, depending on which partial solution is presented, are both N and M considered legitimate "impossible numbers" for the puzzle, or only the smaller?

Bill Smythe