joschka wrote:I'll insert a quick note on Sudoku Samurai: I expanded my approach and found, to my surprise,
that the Samurai puzzles I was able to find were much easier than simple Sudoku.
It does not seem immediately obvious that this should be so and I attribute the result to what
I suspect is the much greater difficulty of creating Samurai puzzles rather than the difficulty of the puzzles themselves.
Your post contains many misconceptions, to start with on samurais.
Indeed, it is not obvious that they are simpler
because it is not true. Consider, for instance this puzzle posted many years ago by ruud
- Code: Select all
009070080000600020605040000060503000801000007000800904000004000950000000000065000 top left
809000010000040008001062000020500430370080000000006000000000305000603000000070800 top right
600040000000570000207000000000800040073090002006005090000300509100600000080000200 bottom left
000700040000002090000500003702060000000370000090000350000004006280003000001000500 bottom right
An American I met here in Taiwan told me about the Finnish guy and his program. But my T&E program solved that in a shade under nine seconds.
That American stopped talking to me! A little more searching on the Internet and I discovered this forum and read about an entirely different
method of determining difficulty. More on that later.
On this Forum, the commonly accepted definition of difficulty is that provided by Sudoku Explainer (http://diuf.unifr.ch/pai/people/juillera/Sudoku/Sudoku.html
even if it has imperfections it is universally available. As already noted, any respectable brute-force program can solve any valid puzzle is less
than a millisecond.
Having discovered some respectable opinions denying that the Finn's puzzle is [not] all the hard, I did some tinkering with it. I sequentially removed
just one of the original numbers in the 2012 puzzle and the used T&E to find a solution. Defining a 'fork' as a situation where my program has to
choose one of two or more alternatives for a square, and proceed with a copy of the board, I discovered the number of forks varied from a
low of 11 to a high of 29,067. That larges value was an outlier in that the second highest value was 820.
It would seem, then, that by deleting the '6' in r6c7 of the Finn's puzzle, I had made a MUCH harder puzzle. If nothing else, this raises
some questions about the Finn's methods of puzzle generation. OTOH, while I found the 'new' puzzle to be much harder for my program,
I have no clear idea if a human solver would find it much harder.
If a puzzle is 'minimal' (has no redundant clue), then removing any clue results in a pseudo-puzzle with multiple solutions. These are
of no interest. In particular, they have no definable level of difficulty.
That's another mystery: how does 'difficulty' as viewed by a human solver compare to 'difficulty' as seen by a computer program since
the approaches are dramatically different?
It depends on whether the 'computer program' is using logic, as Sudoku Explainer does, or whether it just uses brute force.
Somewhere along the way, I recently read a brief description of how to create a Sudoku puzzle. The description was simple enough, basically,
you use a random number generator to fill a puzzle square, keeping in mind that you must provide a minimum of (I think it was) 16 clues.
It doesn't take a lot of thought to realize that this approach is woefully inadequate. First, because it is so easy to create a puzzle with
no solutions at all and it can take a very long time to be sure your puzzle does have a solution. Second, about that minimum of 16, a little more thought
(and another look at how I made the Finnish puzzle much harder) and you realize that every time my program makes a 'guess' and puts that into a square,
I have a 'new' puzzle with one more clue than the original. So, in theory, I could start with a puzzle square with just one clue and solve that one.
Or, a completely blank puzzle square and even, in principle, solve that one.
It has been shown that the minimum number of clues for a valid sudoku puzzle, with one and only one solution, is 17. Such puzzles are very hard to
produce. One standard approach to producing a valid puzzle is to create a full grid and then to successively remove clues until minimality is
reached. This requires a solver which can be stopped if it finds that a candidate puzzle has at least two solutions. Using this top-down approach, zero
solutions is not possible (unlike building a puzzle bottom-up, where that can happen unless the clues are selected from a solved grid).
To get puzzles with fewer than about 30 clues usually requires a more sophisticated multi-level approach.
I hope this helps, and look forward to your further contributions.