Sudoku trivia.. what’s the least numbers for a solvable grid without guesses?
So anyway, this morning’s Guardian sudoku has 20 numbers filled in out of the potential 49. That seemed low - 24 or so is more common, I think.
But it wasn’t impossible, and I didn’t have to resort to guessing at any point to finish it. Which brings me back to the question I ask myself from time to time, but can’t think of a way to figure out a priori: what is the smallest number of numbers that one needs filled in on a sudoku grid to make it solvable without guessing?
thelondonpaper’s “difficult” sudoku frequently beats me where the Gdn one rarely does, so clearly there are levels of difficulty even with roughly the same number of already-given squares. But how low can you go?
Anyone know?
- These posts might be related (the database thinks..):
- Sudding Sudoku! How long can it go on? (answer: a few billion years more) (14 May 2005; score: 154.4%)
- So how exactly do you tell the difference between "human" and "artificial" sudoku? (11 May 2005; score: 98.4%)
- Meet the naked triplet and fishy cycles: sadly, they're for solving sudokus (12 December 2007; score: 69.63%)
![[Valid RSS]](wp-includes/images/valid-rss.png "Validate my RSS feed"){kind=small}
May 17th, 2007 at 4:16 pm
Well this person collects them, and suggests that 17 is the lowest unique-answer grid currently known.
“Currently I have a collection of 39681 distinct Sudoku configurations with 17 entries.”
And you can download them all. Should keep you busy…
May 17th, 2007 at 4:51 pm
It depends on your definition of solvable! The empty grid is the easiest to solve of all. If you mean what it is the least number that leads to a unique solution that’s a different question!
May 17th, 2007 at 5:20 pm
@L: you typically precise bugger. Yes, I mean what’s the least number leading to a unique solution.
@Adam: interesting.. but he isn’t trying to find out why 17 appears to be the least number.
Presumably you can set a computer on them. In which the question becomes: what defines a solveable grid? Some 17-clue ones seem to be not solveable. Those become the more interesting ones.
We shall return..
June 15th, 2007 at 7:46 am
Is there a formal set of names for the logical solving techniques used in sudoku?
or is it more of a free for all?
Also … I wonder what the highest unsolvable grid is? … and as L. says what defines an unsolvable grid. I mean there has to be some groups out there doing analyses of logic structures behind solving sudoku grids. I going to go look right now.
C-ya
June 15th, 2007 at 11:13 am
I’d think that a potentially unsolvable grid must be one with 7 rows filled in and the bottom (or top, or side) two rows empty.
Where “unsolvable” means “not soluble without guessing”, in which I think that quite a few of the ones in thelondonpaper count as “unsolvable”. Some of the 17-number grids are actually pretty easy because to be soluble (without guessing) they contain very little ambiguity.
In my own mind I think of it as degrees of freedom - how many DOF does a square have depending on the number of a “connected” square. Connection of course being a loose idea - two squares on opposite sides of the grid can be connected, where filling one will fill the other, given the right conditions.