## T&E considered to be an abomination?

Everything about Sudoku that doesn't fit in one of the other sections

### Re: T&E considered to be an abomination?

FWIW ...
coloin wrote: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.
JC Van Hay

Posts: 719
Joined: 22 May 2010

### Re: T&E considered to be an abomination?

joschka wrote: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

m_b_metcalf
2017 Supporter

Posts: 9284
Joined: 15 May 2006
Location: Berlin

### Re: T&E considered to be an abomination?

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.

joschka wrote: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.
dobrichev
2016 Supporter

Posts: 1621
Joined: 24 May 2010

### Re: T&E considered to be an abomination?

joschka wrote: 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

m_b_metcalf
2017 Supporter

Posts: 9284
Joined: 15 May 2006
Location: Berlin

### Re: T&E considered to be an abomination?

m_b_metcalf wrote:
joschka wrote: 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
champagne
2017 Supporter

Posts: 6609
Joined: 02 August 2007
Location: France Brittany

### Re: T&E considered to be an abomination?

dobrichev wrote: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.

joschka wrote: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

Posts: 16
Joined: 07 September 2015

### Re: T&E considered to be an abomination?

m_b_metcalf wrote:
joschka wrote: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

Posts: 16
Joined: 07 September 2015

### Re: T&E considered to be an abomination?

joschka wrote:
dobrichev wrote: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.

joschka wrote: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
joschka

Posts: 16
Joined: 07 September 2015

### Re: T&E considered to be an abomination?

champagne wrote: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

m_b_metcalf
2017 Supporter

Posts: 9284
Joined: 15 May 2006
Location: Berlin

### Re: T&E considered to be an abomination?

m_b_metcalf wrote:
champagne wrote: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

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
champagne
2017 Supporter

Posts: 6609
Joined: 02 August 2007
Location: France Brittany

### Re: T&E considered to be an abomination?

m_b_metcalf wrote:
champagne wrote: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.
joschka

Posts: 16
Joined: 07 September 2015

### Re: T&E considered to be an abomination?

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

ZSolver is faster, but almost completely unreadable.

JasonLion
2017 Supporter

Posts: 640
Joined: 25 October 2007
Location: Silver Spring, MD, USA

### Re: T&E considered to be an abomination?

JasonLion wrote: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.)
joschka

Posts: 16
Joined: 07 September 2015

### Re: T&E considered to be an abomination?

joschka wrote: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
coloin

Posts: 1737
Joined: 05 May 2005

### Re: T&E considered to be an abomination?

champagne wrote:
m_b_metcalf wrote:
champagne wrote: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

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?
Steve

SteveG48
2018 Supporter

Posts: 2375
Joined: 08 November 2013
Location: Orlando, Florida

PreviousNext