The New Sudoku Players' Forum

[joschka]

I am both very pleased and rather surprised at the amount of discussion in this otherwise humble topic. For me, at least, the implications of what I'm learning are applicable to much more than Sudoku.

What I've done with my C# program that uses arrays is to solve any Sudoku puzzle I throw at it in a reasonable amount of time. And, even though I cannot define 'reasonable,' I go with former Supreme Court Justice Potter Stewart: "I know it when I see it."

Here is how I got to where I am right now:

Given the usually published rules for solving a Sudoku puzzle, I decided to see if I could write a program that would apply those rules and produce a solution. To review, (I will be brief:) there are rows, columns and regions (RCR) and each RCR must contain one and only one of the digits from 1-9. Typically, nothing is told to the player about there being only one solution.

So I began. My first version examined every square sequentially, when I found a square with only one candidate, I filled that square and removed that candidate everywhere else in the same RCR. After every full scan of the board, I looked to see if I had found any more squares to fill, if not, I scanned again.

In the vast majority of cases, that was enough to solve the puzzle. But occasionally it wasn't enough.

So I set it all aside and thought about it for a long time. My next realization was that I needed to look at the puzzle in a way that was not contained directly in the rules for solving.

For my second version, after using the method above and finding no more squares I could fill, I began scanning the squares again, but this time I looked from the candidate side and checked to see if there was a candidate that was available for only ONE square in the RCR I was examining. If there was, I solved that square and removed that candidate from everywhere else in the RCR.

This version solved just about every puzzle I was trying. My almost exclusive source was the Janric puzzles in the China Post. But finally I hit a puzzle I could not solve this way.

So I took the 'big jump' to using recursion to copy the board and sequentially try all the candidates in all the open squares one at a time. For each copied board, I used all of the methods of the previous version. At that time I had no idea how deeply I might need to go with recursion. So I coded in a user setting of 'depth' with a default of one.

I began finding much harder puzzles and began tinkering with the depth setting. Too large a setting made the program run slower but did not improve the results.

One morning, as I was waking up, I realized I had an important flaw: I was not checking for the situation where I had removed all of the candidates for a square and I was continuing to process that until I later found that square. So I updated my program to check for 'no more candidates' right after I had filled a square and was removing that candidate from the RCR. That made a HUGE improvement in speed. Easter-Monster, which I had let run for about 18 hours without a solution, then solved in about 20 minutes. Is 20 minutes 'reasonable?' For me, it is, though just barely.

About that time, I became interested in how to create puzzles, having more or less satisfied my thirst for solving them. While I was researching that question, I discovered this forum where I have learned a lot about speed.

Conceptually, I know that arrays are very slow and bit-strings are very fast. But a program written with arrays is relatively easy to understand while the bit-string versions are not. (An understatement if you try to figure out how Zsolve works.) My view is that one should first solve the problem with a conceptually understandable solution and only then do you reimplement functions with faster methods. I will assume that is pretty much what has happened and I'm only coming in at the tail end.

Certainly, I have satisfied my goals. For my purposes, solving the same puzzle 100,000 times is milliseconds is worth no more than solving it once in a few seconds. In fact, I don't really care if there are multiple solutions-that wasn't even mentioned in the instructions to players. Only the puzzle creators seemed to know about that.

But lots of people have different goals from mine and for them, solving the same puzzle 100,000 times is very useful because the computer clocks cannot give meaningful estimates of solve times if you run a very fast program and solve only once. Yes, it's lots of fun to see just how fast a program can be devised to work. But I must warn you, if you haven't figured this out already, the coming of quantum computing will make all of the current programs completely obsolete.

Quantum computers will be able to quickly solve EVERY POSSIBLE Sudoku puzzle with every possible number of clues INCLUDING all the puzzles with just one clue. It will happen with such massively parallel processing that everything that can possibly be known about Sudoku, will be known. Nothing will be left to discover.

Backing up a little bit; I managed to get, what to me is a reasonably fast, solution using ONLY the three rules usually given to players and just two more rules: one about looking for a candidate that applies to just one square in an RCR and a second rule about discarding a board if any square comes to have no candidates. The most 'difficult' puzzle I have seen so far, solves in about 20 minutes.

I have also discovered there are a LARGE number of other rules, extremely useful to people who choose to solve these puzzles without computer assistance and I have only touched the surface of understanding a few of them. I deeply respect the people who have discovered these many rules. By myself, I only discovered the one about a candidate appearing only once in any part of an RCR. (The one about a square with no more candidates isn't really a rule, in this sense.)

I'm seeing a relationship between my own experience here and the American experience in Iraq. Its called 'Mission Creep.' The U.S. went into Iraq without a clear understanding of what 'winning' would look like and then kept adding objectives and adding more objectives.

OK, now I have a couple of ultra-fast programs and I have a copy of "Sudoku Explainer" which is pretty slow, but creates a really nice board with all the candidates showing. That can be printed off and used for manual playing to great advantage!

I have also learned that a recursive depth of 3 is as deep as I'll ever need to go and THAT makes using my primitive program much faster.

If I want to really torture myself, I might try to figure out how Zsolver really works. But to do that I'm going to have to study up on all the known rules so I can hope to identify which rule is being used at any given point in the program. That's all 'hidden' in the bit-strings and mentally converting from an array model to a bit-string model is tricky and error-prone at best.

I expect to hang around here much longer than was initially predicted by our host. And I thank everyone who has been posting here for being remarkably tolerant of my still very primitive understanding of what you all have become so fluent with.

Computers can be fun-even though I so often announce to my wife that 'I hate computers!' She is completely baffled by that, given that I spend so much time using my computers. I cannot explain that to her and to you people, I don't need to.

Happy computing!

Jim

[JasonLion]

You are off by several orders of magnitude on instructions to solve a puzzle. A modern Intel processor is on the order of 100,000 MIPS, so 100 microseconds is roughly 10 million instructions (give or take an order of magnitude) to solve a complex puzzle.

[joschka]

You are off by several orders of magnitude. A modern Intel processor is on the order of 100,000 MIPS, so 100 microseconds is roughly 10 million instructions (give or take an order of magnitude) to solve a complex puzzle.

GHz is clock frequency, not MIPS.

Nobody I'm aware of uses MIPS anymore. Do you have a better understanding of why not than I do? Please share it.

Thanks,

Jim

[m_b_metcalf]

Quantum computers will be able to quickly solve EVERY POSSIBLE Sudoku puzzle with every possible number of clues INCLUDING all the puzzles with just one clue. It will happen with such massively parallel processing that everything that can possibly be known about Sudoku, will be known. Nothing will be left to discover.

Jim, just to reiterate, a Sudoku puzzle has one and only one solution. Further, every possible solution grid has already been generated, by gsf, and is (or was) available on a set of CDs.

OK, now I have a couple of ultra-fast programs and I have a copy of "Sudoku Explainer" which is pretty slow, but creates a really nice board with all the candidates showing. That can be printed off and used for manual playing to great advantage!

SE is written in Java and doesn't pretend to be fast. Further, it solves every puzzle using sometimes incredibly complex logic, and that takes time.

You are off by several orders of magnitude on instructions to solve a puzzle. A modern Intel processor is on the order of 100,000 MIPS, so 100 microseconds is roughly 10 million instructions (give or take an order of magnitude) to solve a complex puzzle.

Jason, champagne mentioned that easy puzzles can be solved in 100 nanoseconds, which on a 2GHz processor is only 200 clock cycles (although I have no idea how many instructions that corresponds to).

As shown by mladen dobrichev, fss2 solves the hardest puzzles in about 100 microseconds, and the easy ones about 1000 times faster.

champagne, would it be possible for you (or mladen) to post such an ultra-easy puzzle?

Thanks,

Mike

[joschka]

Quantum computers will be able to quickly solve EVERY POSSIBLE Sudoku puzzle with every possible number of clues INCLUDING all the puzzles with just one clue. It will happen with such massively parallel processing that everything that can possibly be known about Sudoku, will be known. Nothing will be left to discover.

Jim, just to reiterate, a Sudoku puzzle has one and only one solution. Further, every possible solution grid has already been generated, by gsf, and is (or was) available on a set of CDs.

But not every possible puzzle grid. What I'm saying is that it will become simple to create every possible puzzle grid.

While it seem commonly accepted that a good puzzle must have only one solution, There are too many puzzles around that don't follow this restriction and not every book on Sudoku makes this claim.

There is, for example, the Finnish guy who did a 2012 version and that one has two solutions. The one I found is different from the one he published and someone here assured me that there are exactly two. Also Solution Explainer said there are two solutions. I haven't seen anyone criticize that fact. But other criticisms certainly have been leveled.

OK, now I have a couple of ultra-fast programs and I have a copy of "Sudoku Explainer" which is pretty slow, but creates a really nice board with all the candidates showing. That can be printed off and used for manual playing to great advantage!

SE is written in Java and doesn't pretend to be fast. Further, it solves every puzzle using sometimes incredibly complex logic, and that takes time.

You are off by several orders of magnitude on instructions to solve a puzzle. A modern Intel processor is on the order of 100,000 MIPS, so 100 microseconds is roughly 10 million instructions (give or take an order of magnitude) to solve a complex puzzle.

Jason, champagne mentioned that easy puzzles can be solved in 100 nanoseconds, which on a 2GHz processor is only 200 clock cycles (although I have no idea how many instructions that corresponds to).

As shown by mladen dobrichev, fss2 solves the hardest puzzles in about 100 microseconds, and the easy ones about 1000 times faster.

champagne, would it be possible for you (or mladen) to post such an ultra-easy puzzle?

Thanks,

Mike

[champagne]

Jason, champagne mentioned that easy puzzles can be solved in 100 nanoseconds, which on a 2GHz processor is only 200 clock cycles (although I have no idea how many instructions that corresponds to).

As shown by mladen dobrichev, fss2 solves the hardest puzzles in about 100 microseconds, and the easy ones about 1000 times faster.

champagne, would it be possible for you (or mladen) to post such an ultra-easy puzzle?

Thanks,

Mike

Hi Mike,

a) I use a 3.6Ghz computer as working station.

b) here is a very easy puzzle out of the pattern game.

.1.....2.23.....45...2.5.....67324.....8.6.....79546.....3.8...85.....36.4.....9.;1.20;1.00;1.00

In that case (I did not check how fss2 solves it) using the zhou process, the puzzle is solved in one update() call. For such a puzzle, the clock gives me 1 millisecond for 10 000 fss2 calls (the puzzle is previously put is a zero based form).

[m_b_metcalf]

In that case (I did not check how fss2 solves it) using the zhou process, the puzzle is solved in one update() call. For such a puzzle, the clock gives me 1 millisecond for 10 000 fss2 calls (the puzzle is previously put is a zero based form).

Gérard, Many thanks. It's very impressive indeed.

Regards,

Mike

[m_b_metcalf]

But not every possible puzzle grid. What I'm saying is that it will become simple to create every possible puzzle grid.

Simple? Some of the world's finest minds are working on quantum computing, and seemingly getting nowhere fast.

While it seem commonly accepted that a good puzzle must have only one solution, There are too many puzzles around that don't follow this restriction and not every book on Sudoku makes this claim.

There is, for example, the Finnish guy who did a 2012 version and that one has two solutions. The one I found is different from the one he published and someone here assured me that there are exactly two. Also Solution Explainer said there are two solutions. I haven't seen anyone criticize that fact. But other criticisms certainly have been leveled.

Any puzzle published with multiple solutions is simply a mistake. We all make mistakes. Further, the 'Finnish guy', Arto Inkala, is a fraud, well known (and criticized) in these parts.

Regards,

Mike Metcalf

[JasonLion]

You are off by several orders of magnitude. A modern Intel processor is on the order of 100,000 MIPS, so 100 microseconds is roughly 10 million instructions (give or take an order of magnitude) to solve a complex puzzle.

GHz is clock frequency, not MIPS.

These days GHz and IPS are roughly the same thing. See for example the Intel Core i7 entries (towards the bottom) in this chart. Modern processors can process several instructions per clock, which makes up for the pauses when branch prediction guesses wrong or cache filling causes a delay.

[joschka]

But not every possible puzzle grid. What I'm saying is that it will become simple to create every possible puzzle grid.

Simple? Some of the world's finest minds are working on quantum computing, and seemingly getting nowhere fast.

I've seen some rather more optimistic reports, mainly about qbits. But those are fundamental to quantum computing.

While it seem commonly accepted that a good puzzle must have only one solution, There are too many puzzles around that don't follow this restriction and not every book on Sudoku makes this claim.

There is, for example, the Finnish guy who did a 2012 version and that one has two solutions. The one I found is different from the one he published and someone here assured me that there are exactly two. Also Solution Explainer said there are two solutions. I haven't seen anyone criticize that fact. But other criticisms certainly have been leveled.

Any puzzle published with multiple solutions is simply a mistake. We all make mistakes. Further, the 'Finnish guy', Arto Inkala, is a fraud, well known (and criticized) in these parts.

Other than here, I simply haven't seen mention of this restriction to one solution. As far as being a mistake, I've come to understand that validating the number of solutions is quite fast and easy. Soduko Explainer, for example, does that very quickly. It's a mistake that need not happen and is thus not forgivable; unless the puzzle authors do not agree that having just one solution is necessary.

Regards,

Mike Metcalf

[Pat]

There is, for example, the Finnish guy who did a 2012 version and that one has two solutions. The one I found is different from the one he published and someone here assured me that there are exactly two. Also Solution Explainer said there are two solutions. I haven't seen anyone criticize that fact.

i don't recall that puzzle,
could you please post it?

[joschka]

There is, for example, the Finnish guy who did a 2012 version and that one has two solutions. The one I found is different from the one he published and someone here assured me that there are exactly two. Also Solution Explainer said there are two solutions. I haven't seen anyone criticize that fact.

i don't recall that puzzle,
could you please post it?

I have this: 800000000003600000070090200050007000000045700000100030000000068008500010090000400

Here I use a csv format that loads like Excel

8,,,,,,,,
,,3,6,,,,,
,7,,,9,,2,,
,5,,,,7,,,
,,,,4,5,7,,
,,,1,,,,3,
,,,,,,,6,8
,,8,5,,,,1,
,9,,,,,4,,

You can double check if you think I transcribed it wrong.

A JPG image is here: http://d25eh1ita52200.cloudfront.net/fi ... st2012.jpg

And a newspaper article is here: http://www.telegraph.co.uk/news/science ... ck-it.html

Jim

[m_b_metcalf]

I have this: 800000000003600000070090200050007000000045700000100030000000068008500010090000400

But I have this:

Code: Select all

005300000800000020070010500400005300010070006003200080060500009004000030000009700   2010  ED=10.6/1.2/1.2
800000000003600000070090200050007000000045700000100030001000068008500010090000400   2012  ED=10.7/10.7/9.7


where there is one more clue in the second one than you show. For all his faults, the two puzzles are hard and minimal, and have each only one solution.

Your version has not 2 solutions, but 1726.

Regards,

Mike Metcalf

[Pat]

thanks !
the 2012 puzzle ( http://www.efamol.com/efamol-news/news-item.php?id=43 )
has a given in r7c3

[champagne]

In that case (I did not check how fss2 solves it) using the zhou process, the puzzle is solved in one update() call. For such a puzzle, the clock gives me 1 millisecond for 10 000 fss2 calls (the puzzle is previously put is a zero based form).

Gérard, Many thanks. It's very impressive indeed.

Regards,

Mike

Hi Mike,

As One millisecond was not very accurate, and as I am working in parallel on a revised version of the "Zhou" process, I pushed the test to 100000 calls.

fss2 solves the easy puzzle 100 000 times in 77 milliseconds
and the current code on which I am working in 102 milliseconds

In both cases, the average clock time for the 8 puzzles at the top of the file of potential hardest is less than 10 seconds

done on an i7 3.6Ghz

Best Regards

champagne

EDIT This also means that I did not pick the right puzzle in the former post. The first puzzle was not the easy one, but a "non valid" puzzle.
Sorry for that