Contest proposal

For fans of Killer Sudoku, Samurai Sudoku and other variants

Postby Scott H » Tue Mar 06, 2007 8:04 am

You can get a lot of unfillable cells without much effort. This grid has 28 unfillable cells:
Code: Select all
 *-----------*
 |154|3..|9..|
 |63.|5.1|84.|
 |...|489|267|
 |---+---+---|
 |.73|926|...|
 |84.|.7.|156|
 |915|.3.|824|
 |---+---+---|
 |4.7|.18|5.9|
 |569|..2|471|
 |..2|.67|.83|
 *-----------*

This could start from many possible initial clue sets, including the empty set. I expect anything between the min and max is achievable. So I don't think it's very interesting what potential range of unfillable cells a given set of clues has.

There are starting grids where the solution with the minimum number of unfilled cells is unique (the variant I proposed earlier in this thread). Such puzzles are very sudoku-like, and I'd love to see some. Unfortunately my current sudoku variant generator is not yet up to creating them.
Scott H
 
Posts: 73
Joined: 28 July 2005

Postby Smythe Dakota » Thu Mar 08, 2007 6:07 pm

OK, so define the Impossible Number of a grid as 81 minus the largest possible number of filled-in cells. (We can assume that the grid is "legal so far", i.e. there are no duplicate digits in any row, column, or box.) Then:

1. The Impossible Number of a valid puzzle (one or more solutions) is 0.

2. We have seen that the Impossible Number can never be 1.

3. What restrictions exist for the Impossible Number? Even? Non-prime? Less than 30?

4. What is the largest possible Impossible Number?

Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006

Postby Scott H » Fri Mar 09, 2007 12:39 pm

Smythe Dakota wrote:OK, so define the Impossible Number of a grid as 81 minus the largest possible number of filled-in cells. (We can assume that the grid is "legal so far", i.e. there are no duplicate digits in any row, column, or box.) Then:

1. The Impossible Number of a valid puzzle (one or more solutions) is 0.

2. We have seen that the Impossible Number can never be 1.

3. What restrictions exist for the Impossible Number? Even? Non-prime? Less than 30?

4. What is the largest possible Impossible Number?

Bill Smythe

2, 3, 4, 5, 6, 7, ... is almost trivial to achieve. Try it.

I posted a 28 example above. With more effort I got 35 (I'll look it up and post later). I expect my 35 effort could extend to 36, but 37 or more would need a new idea.

Each placement uses itself and excludes 28 other candidates. Since there are 729 total candidates, at least 26 placements must be made and impossible number cannot be 56. More than 9 placements necessarily duplicates exclusions and becomes less efficient at eliminating candidates, so tightening this argument can lower the provable upper bound a bit. The actual upper bound is probably in 35-45.
Scott H
 
Posts: 73
Joined: 28 July 2005

Postby Scott H » Sat Mar 10, 2007 3:01 am

Here's the 35 unfillable cell example I promised:
Code: Select all
 *-----------*
 |6.7|...|859|
 |..4|321|...|
 |9.8|.54|716|
 |---+---+---|
 |.23|.75|.4.|
 |51.|6.8|.3.|
 |.4.|.9.|12.|
 |---+---+---|
 |736|2..|9.8|
 |...|143|2.5|
 |859|...|6.7|
 *-----------*
Scott H
 
Posts: 73
Joined: 28 July 2005

Previous

Return to Sudoku variants