The New Sudoku Players' Forum

[joschka]

With all due respect to why everyone considers T&E to be an abomination (see for example this topic), I humbly report the following:

Two or three years ago, I wrote a C# program to solve Sudoku games by (dare I say it) T&E. I thought it was working rather well until I stumbled across this forum. I decided to 'go for broke' and attempted Easter-Monster which was still running after about 18 hours.

But then I dreamed up an additional optimization I could add to my program. After which, Easter-Monster solved in roughly 9 seconds (estimated.)

This is what I got:
174385962293467158586192734451923876928674315367851249719548623635219487842736591

I readily acknowledge that using a computer program to solve the puzzle is something less than an intellectual feat, but writing the program that did this seems worthy of some satisfaction. I also acknowledge that the computer can use housekeeping approaches that would be mindbogglingly tedious for a person. No sane person would attempt a solution using the same approach.

There may well be other solutions to Easter-Monster, but I have made no attempt to look for more than one.

So, if a program can solve the puzzle in less than 10 seconds, then, I suspect T&E may really be good enough.

I tend to think that writing a program that solves 'any' Sudoku is akin to solving them all.

I would be interested in responses.

[David P Bird]

Joshka, Welcome to the forum however short your stay will probably be!

Sudoku puzzles set a challenge and how you respond to that challenge is up to you. Now that you have finished your program your challenge is over and you should either move on or try a completely different approach.

How would you get to the top of a mountain? The options are by helicopter, errecting scaffolding, using artificial climbing aids, or free climbing with no aids. Whichever one you choose, all the others options will appear inferior, but which one will give you the most satisfaction as you ascend in stages and finally when you reach the summit?

For me trial and error techniques are equivalent to using scaffolding. The only skill involved is in deciding where the most promising approach lies and after that it's sheer tedium. My personal challenge is to steadily be able to solve harder and harder problems using the minimum of artificial aids, and that's how I've maintained my interest in Sudoku going for so long.

DPB

[joschka]

Hello DBP,

Thank you for accepting my posting. I can only hope that you and other people will find some unexpected interest in this thread.

From you reply, infer that you have rejected T&E out of hand. And, in consequence, you would not have encountered the questions I've developed over the few years I've been playing with my program. One obvious reason for continuing to play with it is the hope that a puzzle will come along that either breaks it or overwhelms it. The Finnish guy's supposedly hardest puzzle did not directly do that, but my tinkering with his puzzle did overwhelm my program and that lead to an additional optimization process.

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.

But I digress.

All analogies break down, this I understand. But I think your mountain climbing analogy breaks down too quickly to be useful. From a traditional mountain climber's POV, every climb is different. There is the matter of the climber's physical condition and the weather conditions. Either of these will be different on each climb. The snow and ice on the mountain will be different on every climb and the possibilities for physical and equipment failures is also unpredictable.

Even scaffolding would have to be adjusted somewhat to each mountain. In compensation, the mountain or the scaffolding climber would be rewarded with a somewhat different view of things on the way up and at the top.

With my T&E program, the mountain (the basic puzzle) is almost irrelevant; the scaffolding (my program) is exactly the same every time AND reaching the top (the solution) is also of essentially no interest. There is nothing to see other than confirming that the top (the solution) can be reached. Or, in my case, that there is at least ONE solution.

So why or how have I managed to maintain my interest for four or five years?

The first mystery I encountered came about because the local English Language newspaper, to which I subscribe, publishes a Sudoku puzzle every day. The puzzles are purchased from a company named Janric and are rated as Bronze, Silver, or Gold depending on Janric's opinion about the difficulty. Using my program, I found the three levels to be utterly indistinguishable. So I posted a question to Janric about their method of determining difficulty but they did not reply.

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.

Having discovered some respectable opinions denying that the Finn's puzzle is 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.

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?

Then, of course, there is the fact that my program uses a fixed sequence of traversing the game board. "Rotating" the board would, logically, produce four different results for my program and with mirror images, eight different results. Would they be the same or even similar? I don't know because I haven't tried this yet. I suspect they would be the same using Denis Berthier's measures, they would all be 'the same' puzzle. But, would a human solver find them to be the same? That is not clear as human perception is well known to be highly dependent on POV. Just try to recognize the person in a photograph when it is held upside down.

I downloaded HardestDatabase110626 and extracted HardestSudokusThread-02095. An 11.9 difficulty. It took a bit over 20 minutes. (An additional enhancement to my program witch now displays the time difference between start and finish.) That, I feel, isn't really all that difficult. But 'difficulty' itself seems to be a slippery concept.

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.

At this point, one could argue that the puzzles and their solutions are of almost no real interest at all. The only thing that remains a real intellectual challenge is CREATING NEW PUZZLES! And, given the large numbers of supposedly 'very difficult' puzzles floating around, there isn't any really good theoretical work out there on the creation process. (Please let me know if this is nothing more than an ignorant conclusion.)

Remember, ANY PUZZLE can be made 'more difficult' simply by deleting one of the authors supplied clues. If deleting one clue is good, why not two? Does a meaningful puzzle have to guarantee there is only ONE solution? The Finn's puzzle has at least two (the one he supplied and the one I found.) If multiple solutions is OK, why not delete ALL of the original clues? If that's a ridiculous extreme, where to stop? And why must one stop THERE?

I looked up Berthier's latest book, but Amazon doesn't have it in ebook format and, living in Taiwan, it's slow and expensive to get printed books delivered from the US. I may eventually resort to that approach because I tried to understand his descriptions and got absolutely nowhere. I suppose I need the book.

Unless it's true that only puzzle creation is really interesting. I started to create a puzzle generation program based on my puzzle solving program and quickly realized I have no idea, as yet, on how to proceed.

In any case, DBP, I hope I have at least persuaded you that having used T&E, I have developed an interesting view of Sudoku, unlike the others I've seen so far.

Jim (Joschka)

PS: If anyone should want a copy of my program, I can post the whole package (Microsoft Visual Studio 2015 C#) for download. Just ask.

[pjb]

Joshka

Two comments: firstly your solution is correct, and secondly, well made puzzles such as this one have one solution only, since uniqueness is a requirement in designing them.
Like David, my challenge is to solve by logic (with or without computer assistance), not by a brute-force method.

Phil

[joschka]

I would love to know how one can 'prove' there is only one solution?

Presumably not with brute force!

Jim

[champagne]

Hi Joska,

Just another view point on the T&E.

This is by far the main process used, but to check the properties of a a puzzle

does it have a solution
Is it unique
do you have redundant given ...

but then, you have millions, billions of puzzles to check.

so the challenge is to have a very efficient process solving thousands (at minimum) of puzzles per second.

The last discussions on that topic took place int hat thread 3-77us-solver-2-8g-cpu-testcase-17sodoku-t30470-165.html

When you have a puzzle known as being a valid sudoku, the challenge is to solve it using pure logic, without any guess.

[Sudtyro2]

But then I dreamed up an additional optimization I could add to my program. After which, Easter-Monster solved in roughly 9 seconds (estimated.)

9 seconds is pretty slow. Andrew Stuart's online solver uses a recursive 712252-pass, brute-force algorithm to solve Easter-Monster literally in the blink of an eye.

SteveC

[JasonLion]

I would love to know how one can 'prove' there is only one solution?

There are two ways. A properly documented logical solution normally constitutes a proof. You can also use trial and error on a computer to try every possible solution. Both approaches are in common use.

Remember, ANY PUZZLE can be made 'more difficult' simply by deleting one of the authors supplied clues.

This is not true in general. First you need to be careful about defining what you mean by "difficult". There are many definitions and hardly any agreement about which one to use. Then, once you have picked a definition, you will find that puzzles occasionally get easier when removing a clue. You also need to consider the question of validity. Removing a clue from a minimal puzzle makes the puzzle invalid, at which point most people would say that it doesn't have a "difficulty".

Puzzle creation is interesting for several reasons. The aspect I find most intriguing involves trying to develop a measure of difficulty based on human solving time without T&E .

Since you have defined difficulty in a very narrow way, the possible conclusions you can come to are very limited. If you define difficulty in other ways Sudoku becomes a much more interesting puzzle.

[m_b_metcalf]

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

[David P Bird]

Joschka, you're right, analogies can always be taken too far, but before I come off the mountain one, I would rate your challenge as being to design a helicopter!

So why or how have I managed to maintain my interest for four or five years?

I would hazard that's because you're more interested in the nuts and bolts of program building than you are in solving what should be a logical puzzle. You aren't alone in that and there are plenty of very absorbing sub-topics there which have been discussed on this forum and elsewhere:
• Program design and optimising issues
• Composing puzzles with the minimum number of clues to ensure they only have one solution
• Rating difficulty

After you've spent a few years on those you might turn to aspects that I would find interesting:
• A computer solver that can show a human solver the shortest logical path to reach the solution (a point I put to Denis Berthier, and you can see his response <here>).
• The use of artificial intelligence to scan a puzzle at the start and decide the where the promising openings are as a human solver would.

But you've got me right, I'm primarily a solver who rejects T&E out of hand, not a programmer or puzzle designer, so I'll leave you to their tender mercies.

DPB
.

[m_b_metcalf]

I would love to know how one can 'prove' there is only one solution?

Presumably not with brute force!

Yes, with brute force you can simply count them:

Code: Select all

 1 2 0 3 0 0 4 0 0
 5 0 0 0 6 0 0 0 0
 0 0 7 0 0 8 0 0 0
 6 0 0 0 0 0 0 2 0
 0 4 0 0 8 0 3 0 0
 0 0 2 0 0 7 0 0 5
 3 0 0 0 1 0 9 0 0
 0 0 0 9 0 0 0 0 8
 0 0 0 0 0 4 0 7 0
No. of givens =  23

brute found 1 solution(s) in    0.00 seconds.

Remove a clue, at r8c9, and we get

Code: Select all

 1 2 0 3 0 0 4 0 0
 5 0 0 0 6 0 0 0 0
 0 0 7 0 0 8 0 0 0
 6 0 0 0 0 0 0 2 0
 0 4 0 0 8 0 3 0 0
 0 0 2 0 0 7 0 0 5
 3 0 0 0 1 0 9 0 0
 0 0 0 9 0 0 0 0 0
 0 0 0 0 0 4 0 7 0
No. of givens =  22

brute found 39 solution(s) in    0.00 seconds. Last was:
  1  2  6  3  9  5  4  8  7
  5  8  4  7  6  1  2  3  9
  9  3  7  4  2  8  5  6  1
  6  5  3  1  4  9  7  2  8
  7  4  1  5  8  2  3  9  6
  8  9  2  6  3  7  1  4  5
  3  7  8  2  1  6  9  5  4
  4  6  5  9  7  3  8  1  2
  2  1  9  8  5  4  6  7  3

Common clues (22):
  1  2  0  3  0  0  4  0  0
  5  0  0  0  6  0  0  0  0
  0  0  7  0  0  8  0  0  0
  6  0  0  0  0  0  0  2  0
  0  4  0  0  8  0  3  0  0
  0  0  2  0  0  7  0  0  5
  3  0  0  0  1  0  9  0  0
  0  0  0  9  0  0  0  0  0
  0  0  0  0  0  4  0  7  0

Regards,

Mike Metcalf

[coloin]

Hi joschka
Well in my opinion... T&E is logical - so I wouldn't be so keen to call it an "abomination"
However....I would be interested to see how long your program takes with this one !!!!

Code: Select all

..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5..#Suexrat9-10364

C

[joschka]

Hi Coloin,

I got this result:
123456789457189236968327154249561873576938412831742695314275968695814327782693541

It took 24 min 38.65 seconds
There were 184,166 'forks'

I'd love to know how that compares with your expectations.

Note: for each fork, there was a recursive reentry into the solve procedure. There is, of course some significant overhead for each of those. The user who claims any good brute force program should be able to solve any Sudoku game in a microsecond either knows vastly more than I do about computers, or vastly less.

I would love to get the source of such a solution program!

My source (the complete folder used by Visual Studio) is now available for download at:
http://d25eh1ita52200.cloudfront.net/fi ... %20Kay.zip Packed by WinZip V19.5 Pro (11475) 64-bit

The entire file is available under the Creative Commons license. Any use must be for free and include my copyright statement or a suitable statement crediting my work. Any derived work must also be distributed for free under the same Creative Commons license and include an attribution to my work.

PS: I picked up the word 'abomination' in this forum. I isn't my view either.

[joschka]

I would love to know how one can 'prove' there is only one solution?

Presumably not with brute force!

Yes, with brute force you can simply count them:

Code: Select all

 1 2 0 3 0 0 4 0 0
 5 0 0 0 6 0 0 0 0
 0 0 7 0 0 8 0 0 0
 6 0 0 0 0 0 0 2 0
 0 4 0 0 8 0 3 0 0
 0 0 2 0 0 7 0 0 5
 3 0 0 0 1 0 9 0 0
 0 0 0 9 0 0 0 0 8
 0 0 0 0 0 4 0 7 0
No. of givens =  23

brute found 1 solution(s) in    0.00 seconds.

Remove a clue, at r8c9, and we get

Code: Select all

 1 2 0 3 0 0 4 0 0
 5 0 0 0 6 0 0 0 0
 0 0 7 0 0 8 0 0 0
 6 0 0 0 0 0 0 2 0
 0 4 0 0 8 0 3 0 0
 0 0 2 0 0 7 0 0 5
 3 0 0 0 1 0 9 0 0
 0 0 0 9 0 0 0 0 0
 0 0 0 0 0 4 0 7 0
No. of givens =  22

brute found 39 solution(s) in    0.00 seconds. Last was:
  1  2  6  3  9  5  4  8  7
  5  8  4  7  6  1  2  3  9
  9  3  7  4  2  8  5  6  1
  6  5  3  1  4  9  7  2  8
  7  4  1  5  8  2  3  9  6
  8  9  2  6  3  7  1  4  5
  3  7  8  2  1  6  9  5  4
  4  6  5  9  7  3  8  1  2
  2  1  9  8  5  4  6  7  3

Common clues (22):
  1  2  0  3  0  0  4  0  0
  5  0  0  0  6  0  0  0  0
  0  0  7  0  0  8  0  0  0
  6  0  0  0  0  0  0  2  0
  0  4  0  0  8  0  3  0  0
  0  0  2  0  0  7  0  0  5
  3  0  0  0  1  0  9  0  0
  0  0  0  9  0  0  0  0  0
  0  0  0  0  0  4  0  7  0

Regards,

Mike Metcalf

As currently designed, my program terminates after finding the first solution. Looking for them all would potentially take much much more time and would require a bit of reworking the code.

[joschka]

Hello Mike Metcalf,

Would you be so kind as to repost the link to Sudoku Explainer? The link above does not work.

Thanks,
Jim