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

000000000000010000000060000000000501062005000000090032000400000000001000000302000 middle

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.

Regards,

Mike Metcalf