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 m_b_metcalf » Sun Sep 13, 2015 9:35 am

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

[snip]
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.


Gérard,
Thanks for the new information, but the EDIT leaves me slightly confused. Do you mean this puzzle:
Code: Select all
.1.....2.23.....45...2.5.....67324.....8.6.....79546.....3.8...85.....36.4.....9.;1.20;1.00;1.00

because it is very easy, has one solution and is minimal? So in what way is it "non valid"? Or did you mean a different one?

Anyway, I understand that the new timing, at 3.6 GHz, becomes roughly 1 microsecond per call for the easy puzzle, and an average of roughly 100 microseconds for each of the eight very hard ones (could you please post them here?).

Bon dimanche

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 7938
Joined: 15 May 2006
Location: Berlin

Re: T&E considered to be an abomination?

Postby champagne » Sun Sep 13, 2015 12:12 pm

Hi Mike,

Here after the full results for my tiny sample file.

In the first tests for the brute force I work with the following file

Code: Select all
...12........35......96....2.48.6.9....7.3....1.4.26.8....41......57........89...test t=0 1
...12........35......96....2.48.6.5....7.3....5.4.26.8....41......57........89...test t=59 2
...12........35......96....2.48.6.1....7.3....9.4.26.8....41......57........89...test t=47 3
...12........35......96....3.74.2.9....7.3....1.8.63.7....41......57........89...test t=55 4

.1.....2.23.....45...2.5.....67324.....8.6.....79546.....3.8...85.....36.4.....9.;1.20;1.00;1.00 5   
.1.....2.23.....45...2.5.....67324.....8.6.....79546.....3.8...85.....36.4.....9.;1.20;1.00;1.00 6
6....87......4..5....5....6....1..6...34.78...1..2....7....1....2..6......83....5;1.50;1.50;1.50 7

..9.8.7...6...5.4.3.....6.2.......3.5...7.1...2.......4.7.2...1.3.8...7...1...9..;6.70;6.70;6.70  8

98.7.....7.....6....6.5.....4...5.3...79..5......2...1..85..9......1...4.....3.2.;11.90;11.90;11.80;GP;champagne dry;1;22; 9
98.7.....6.....87...7.....5.4..3.5....65...9......2..1..86...5.....1.3.......4..2;11.90;11.90;11.60;GP;kz0;11523;23;10
12..3....4....1.2...52..1..5..4..2......6..7......3..8.5....9....9.7..3......8..6;11.90;11.90;11.30;elev;second flush;2;23;11
.......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....;11.90;11.90;11.30;tax;Golden-Nugget;3;21;12
.2.4...8.....8...68....71..2..5...9..95.......4..3.........1..7..28...4.....6.3..;11.90;11.90;9.90;elev;3;4;22;13
........1....23.45..51..2....25...1..6...27..8...9......42....7.3...6...9...8....;11.90;11.90;9.90;dob;12_12_03;248078;23;14
12.3.....4.5...6...7.....2.6..1..3....453.........8..9...45.1.........8......2..7;11.90;11.90;2.60;elev;1;5;22;15
..3..6.8....1..2......7...4..9..8.6..3..4...1.7.2.....3....5.....5...6..98.....5.;11.90;1.20;1.20;elev;2;6;22;16



4 "not valid" puzzles that the first version of the "zhou" process had difficulties to reject
3 easy puzzles and one "medium rating" ,puzzle out of the pattern game
8 puzzles from the data base of potential hardest (top of the list when I picked them).

The fss2 clock in milliseconds for 100 000 calls for that file is about (small variations from one run to another one)

Code: Select all
17 17 17 17 for the "non valid"
82 82 130 for the "easy"
155 for the "medium rating"
11208 7079 9607 9703 12140 5868 5557 12194


I delivered a wrong information when I used the results of the first puzzle in my file (1 millisecond for 10 000 calls) as a result for the first "easy".

I hope that all is now clear.

Best regards

champagne
champagne
2017 Supporter
 
Posts: 5445
Joined: 02 August 2007
Location: France Brittany

Re: T&E considered to be an abomination?

Postby m_b_metcalf » Mon Sep 14, 2015 7:17 am

champagne wrote:I hope that all is now clear.

Crystal clear. Thanks.

Mike
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 7938
Joined: 15 May 2006
Location: Berlin

re: number of answers

Postby Pat » Wed Sep 16, 2015 9:20 am

joschka wrote:
m_b_metcalf wrote:Any puzzle published with multiple solutions is simply a mistake.

Other than here, I simply haven't seen mention of this restriction to one solution.

    A. in my own view, a valid SuDoku can indeed have any number of answers.
    (classified as: 0ans, 1ans, 2+ans.)

    B. others reject 0ans,
    and call it "valid" only with 1-answer-or-more.

    C. and some call it "valid" only with exactly-1-answer.
    (perhaps the majority on this forum.)

    D. there's even one who restricts "valid" even more,
    requiring exactly-1-answer and not-too-tough.
    (using his own definition of too-tough.)
User avatar
Pat
 
Posts: 3250
Joined: 18 July 2005

Re: re: number of answers

Postby champagne » Wed Sep 16, 2015 12:02 pm

Pat wrote:[list]A. in my own view, a valid SuDoku can indeed have any number of answers.
(classified as: 0ans, 1ans, 2+ans.)



interesting,

so

... ... ...
... ... ...
... ... ...

... ... ...
... ... ..
... ... ...

... ... ...
... ... ...
... ... ...

is a valid sudoku :D
champagne
2017 Supporter
 
Posts: 5445
Joined: 02 August 2007
Location: France Brittany

Re: T&E considered to be an abomination?

Postby JasonLion » Wed Sep 16, 2015 12:40 pm

The earliest definitions of Sudoku from Number Place and Nikoli never explicitly say that the puzzle will have exactly one solution. On the other hand, every puzzle ever published by those two sources does have exactly one solution. So while the single solution rule is never mentioned by the most authoritative sources, it is strongly implied. In practice, while there is some debate about wording, nearly everyone agrees that a properly formed puzzle, or valid puzzle, or whatever you want to call it, must have exactly one solution.

The presumption here on the forum is that puzzles are presumed to have exactly one solution unless stated otherwise. Discussions of puzzles with other numbers of solutions comes up often enough. Whatever you call those puzzles, they are of some interest.
User avatar
JasonLion
2017 Supporter
 
Posts: 600
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: re: number of answers

Postby coloin » Wed Sep 16, 2015 2:00 pm

champagne wrote:interesting,

so
... ... ...
... ... ...
... ... ...

... ... ...
... ... ..
... ... ...

... ... ...
... ... ...
... ... ...
is a valid sudoku :D


no it is 6670903752021072936960 valid sudoku - as first found by dukuso

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

well the number of solution grids can be calculated in less than ? 0.1 sec here
but i doubt we can know everything .....
coloin
 
Posts: 1539
Joined: 05 May 2005

Re: T&E considered to be an abomination?

Postby eleven » Mon Sep 21, 2015 10:52 am

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

I must warn you not to be too optimistic about the possibilities of quantum computers, see e-g- https://en.wikipedia.org/wiki/Quantum_computing#Relation_to_computational_complexity_theory:
"There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false."
eleven
 
Posts: 1386
Joined: 10 February 2008

Previous

Return to General

cron