The New Sudoku Players' Forum

[JC Van Hay]

FWIW ...

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

An easy puzzle :

The solutions of the double exocet {(1259)r13c1, (1259)r89c3, (1259)R247} exclude a set of 74 candidates; 37 Singles.
The solutions of the skyscraper {9R38} exclude 9r1c2; singles to the end.

[m_b_metcalf]

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

http://diuf.unifr.ch/pai/people/juillera/Sudoku/Sudoku.html

[dobrichev]

Hi joschka, welcome to the forum.

There is no consensus (and couldn't be) where the pure logic ends and T&E starts.
Obviously, for a human solver, following the steps in your algorithm can't lead to satisfaction.
From the other hand, I don't know how searching for a particular pattern (finding the right pattern supposed to be a shortcut in the solving process due to proven eliminations it does and therefore is considered a "pure logic") can be named rather than T&E.

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.

It took 11.236 seconds to my T&E solver to solve 100 000 copies of this puzzle up to the first solution which is about 112 microseconds per puzzle.

[m_b_metcalf]

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.

Microsecond was corrected to millisecond not long after the original post. Sorry for that.

M

[champagne]

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.

Microsecond was corrected to millisecond not long after the original post. Sorry for that.

M

but in average, knowing that most puzzles are easy ones, it should be some micro seconds.
As shown by mladen dobrichev, fss2 solves the hardest puzzles in about 100 microseconds, and the easy ones about 1000 times faster


EDIT. fss2 is written in C++, but only works on a 64 bit processor.
fss2 uses some "native" code in the critical branches, either using the intrinsic calls provided by the last version of microsoft visual C++ or using short .asm sequences

[joschka]

Hi joschka, welcome to the forum.

There is no consensus (and couldn't be) where the pure logic ends and T&E starts.
Obviously, for a human solver, following the steps in your algorithm can't lead to satisfaction.
From the other hand, I don't know how searching for a particular pattern (finding the right pattern supposed to be a shortcut in the solving process due to proven eliminations it does and therefore is considered a "pure logic") can be named rather than T&E.

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.

It took 11.236 seconds to my T&E solver to solve 100 000 copies of this puzzle up to the first solution which is about 112 microseconds per puzzle.

Hello dobrichev and thank you for the welcome!

Your result is, indeed, quite a memorable welcome. (Its good to be humbled as long as it doesn't happen too often.) At least you have opened up a whole new opportunity to look at how Sudoku works.

I had GIT installed and running on my system but decided I didn't much want to use it, so I uninstalled it all. Now I see your program is in GIT format. I'm going to try to get Visual Studio to get it for me. That is supposed to work!

Cheers,
Jim

[joschka]

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

http://diuf.unifr.ch/pai/people/juillera/Sudoku/Sudoku.html

Thank you, I got it now.

[joschka]

Hi joschka, welcome to the forum.

There is no consensus (and couldn't be) where the pure logic ends and T&E starts.
Obviously, for a human solver, following the steps in your algorithm can't lead to satisfaction.
From the other hand, I don't know how searching for a particular pattern (finding the right pattern supposed to be a shortcut in the solving process due to proven eliminations it does and therefore is considered a "pure logic") can be named rather than T&E.

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.

It took 11.236 seconds to my T&E solver to solve 100 000 copies of this puzzle up to the first solution which is about 112 microseconds per puzzle.

Hello dobrichev and thank you for the welcome!

Your result is, indeed, quite a memorable welcome. (Its good to be humbled as long as it doesn't happen too often.) At least you have opened up a whole new opportunity to look at how Sudoku works.

I had GIT installed and running on my system but decided I didn't much want to use it, so I uninstalled it all. Now I see your program is in GIT format. I'm going to try to get Visual Studio to get it for me. That is supposed to work!

Cheers,
Jim

The good news is that Visual Studio cloned fsss2 from GitHub with a couple of clicks.

The bad news is that turning that into something that Visual Studio can compile is a VERY different thing. Maybe I'd be better of letting you do that.

Jim

[m_b_metcalf]

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

So it reads an easy puzzle, solves it, and writes it to file with just a few hundred machine instructions being executed. Or do I misunderstand?

Regards,

Mike

[champagne]

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

So it reads an easy puzzle, solves it, and writes it to file with just a few hundred machine instructions being executed. Or do I misunderstand?

Regards,

Mike

Hi Mike,

Usually, to have the answer to the question "how long does it take to solve a puzzle", we do the following

read it
solve it "n times"


This is more to see what you can expect in a process where most of the time the puzzle is internally created and most often "not valid" for the goal of the run.

in my case, the clock is started with the first "solve" and closed after the last "solve.

We try in such tests to limit the effect of external reads/writes

[joschka]

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

So it reads an easy puzzle, solves it, and writes it to file with just a few hundred machine instructions being executed. Or do I misunderstand?

Regards,

Mike

Decades ago, computer processors were rated in MIPS (Million Instruction Per Second) but for an assortment of reasons, manufacturers have switched to rating processors in Giga Hertz. As I understand it, there is no simple conversion from GHz to Instructions per second. Different instructions take different numbers of cycles.

To add to the confusion, another method of rating speed uses FLOPS Floating point Operations Per Second. The floating point operations can be the limiting factor in many kinds of computation problems, but they are not the only type of operations that make up a complete program.

In any event, '...just a few hundred machine instructions...' is a far too small number. And because all modern general purpose computer operating systems support both virtual memory and multi-tasking, even running the exact same sequence of source program instructions over and over would not be likely to translate to anything like the same number of machine instructions with an accuracy 'a few hundred instructions.'

As an example, a simple page fault could easily cost a few hundred machine instructions and a single running program does not begin to determine how many of its pages get invalidated. That depends more on what else is happening and how much free memory is installed. There always LOTS of other things happening.

I would think any serious attempt to count instructions would, itself, seriously distort the results. Running something 100,000 times and averaging the results may be as good as can be gotten. It might be interesting to collect those times separately to look at the variance, but even that might be impractical or impossible. Maybe running it 1,000 times for a time count and repeating that 100 times for a sample. Then calculate the variance. I've never tried anything like that.

[JasonLion]

JSolve, while no longer the fastest, is probably the most readable of the really fast solvers.

ZSolver is faster, but almost completely unreadable.

[joschka]

JSolve, while no longer the fastest, is probably the most readable of the really fast solvers.

ZSolver is faster, but almost completely unreadable.

I've now looked at the source!

Zsolver reminds me of a comment I read long ago: APL is a write only programming language.

Zsolver is pretty much 'write only' as well.

Which also reminds me of a long-ago component manufacturer's catalog that included a 'gag item' page the engineers had created for 'write only memory.' (The older I get, the more I think I too am developing a write-only memory.)

[coloin]

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

The puzzle over rated on a similar and fairly recent thread.
here
Im not sure why this puzzle is so difficult to guess by T&E .... but its not a super hard puzzle as shown.
C

[SteveG48]

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

So it reads an easy puzzle, solves it, and writes it to file with just a few hundred machine instructions being executed. Or do I misunderstand?

Regards,

Mike

Hi Mike,

Usually, to have the answer to the question "how long does it take to solve a puzzle", we do the following

read it
solve it "n times"


This is more to see what you can expect in a process where most of the time the puzzle is internally created and most often "not valid" for the goal of the run.

in my case, the clock is started with the first "solve" and closed after the last "solve.

We try in such tests to limit the effect of external reads/writes

Hi, Champagne,

I understand that you're eliminating external operations using this technique, but it still comes down to doing the actual solving of an easy puzzle in about 100 nanoseconds. That can't be more than a few machine cycles. How in the world do you do that?