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?

Postby JC Van Hay » Wed Sep 09, 2015 6:03 am

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: 648
Joined: 22 May 2010

Re: T&E considered to be an abomination?

Postby m_b_metcalf » Wed Sep 09, 2015 6:19 am

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8095
Joined: 15 May 2006
Location: Berlin

Re: T&E considered to be an abomination?

Postby dobrichev » Wed Sep 09, 2015 6:49 am

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: 1302
Joined: 24 May 2010

Re: T&E considered to be an abomination?

Postby m_b_metcalf » Wed Sep 09, 2015 7:29 am

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8095
Joined: 15 May 2006
Location: Berlin

Re: T&E considered to be an abomination?

Postby champagne » Wed Sep 09, 2015 7:43 am

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: 5575
Joined: 02 August 2007
Location: France Brittany

Re: T&E considered to be an abomination?

Postby joschka » Wed Sep 09, 2015 9:09 am

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?

Postby joschka » Wed Sep 09, 2015 9:10 am

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?

Postby joschka » Wed Sep 09, 2015 9:54 am

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?

Postby m_b_metcalf » Wed Sep 09, 2015 10:03 am

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8095
Joined: 15 May 2006
Location: Berlin

Re: T&E considered to be an abomination?

Postby champagne » Wed Sep 09, 2015 10:15 am

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

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
champagne
2017 Supporter
 
Posts: 5575
Joined: 02 August 2007
Location: France Brittany

Re: T&E considered to be an abomination?

Postby joschka » Wed Sep 09, 2015 10:51 am

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?

Postby JasonLion » Wed Sep 09, 2015 11:50 am

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

ZSolver is faster, but almost completely unreadable.
User avatar
JasonLion
2017 Supporter
 
Posts: 620
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: T&E considered to be an abomination?

Postby joschka » Wed Sep 09, 2015 1:13 pm

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?

Postby coloin » Wed Sep 09, 2015 5:18 pm

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: 1576
Joined: 05 May 2005

Re: T&E considered to be an abomination?

Postby SteveG48 » Wed Sep 09, 2015 11:09 pm

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

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?
Steve
User avatar
SteveG48
2017 Supporter
 
Posts: 1879
Joined: 08 November 2013
Location: Orlando, Florida

PreviousNext

Return to General