Contest proposal

For fans of Killer Sudoku, Samurai Sudoku and other variants

Contest proposal

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?
Smythe Dakota

Posts: 564
Joined: 11 February 2006

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

Posts: 73
Joined: 28 July 2005

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.
Scott H

Posts: 73
Joined: 28 July 2005

Re: Contest proposal

Smythe Dakota wrote: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.

Posts: 337
Joined: 31 August 2005

Scott H wrote: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.)
r.e.s.

Posts: 337
Joined: 31 August 2005

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
HATMAN

Posts: 275
Joined: 25 February 2006
Location: Nigeria

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.
r.e.s.

Posts: 337
Joined: 31 August 2005

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
Last edited by HATMAN on Mon Feb 26, 2007 7:04 pm, edited 1 time in total.
HATMAN

Posts: 275
Joined: 25 February 2006
Location: Nigeria

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
HATMAN

Posts: 275
Joined: 25 February 2006
Location: Nigeria

Re: Contest proposal

r.e.s. wrote:
Smythe Dakota wrote: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.
Scott H

Posts: 73
Joined: 28 July 2005

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.
r.e.s.

Posts: 337
Joined: 31 August 2005

r.e.s. wrote: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
Smythe Dakota

Posts: 564
Joined: 11 February 2006

Nice counterexample!
r.e.s.

Posts: 337
Joined: 31 August 2005

r.e.s. wrote: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.
Scott H

Posts: 73
Joined: 28 July 2005

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
Smythe Dakota

Posts: 564
Joined: 11 February 2006

Next