SE 6.7 takes an enormous amount of time to evaluate

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

SE 6.7 takes an enormous amount of time to evaluate

Postby Laitinen » Thu May 08, 2008 8:40 pm

Hi!

I have been trying to create very difficult sudokus with a couple of my friends. We created a computer program that generates sudokus, and we've had some moderate successes with it, though the hardest one being only SE 9.2.

Anyway, today I encountered a very weird thing while I was checking the difficulties of a bunch of our sudokus. For some reason onw of our sudokus took over one hour with the command-line check, and with another instance of SE about 20 minutes too. The sudoku is here:

000000080000060430030050609500000000206000000010000004000630005060084203008005060

and in more readable format:

000 000 080
000 060 430
030 050 609
500 000 000
206 000 000
010 000 004
000 630 005
060 084 203
008 005 060.

Other solvers solve this rather painlessly. Does anyone have any idea why is this being such a tough nut for SE?
Laitinen
 
Posts: 4
Joined: 08 May 2008

Re: SE 6.7 takes an enormous amount of time to evaluate

Postby ronk » Thu May 08, 2008 8:54 pm

Laitinen wrote:For some reason onw of our sudokus took over one hour with the command-line check, and with another instance of SE about 20 minutes too.

Was this the SE=9.2?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: SE 6.7 takes an enormous amount of time to evaluate

Postby gsf » Thu May 08, 2008 10:38 pm

Laitinen wrote:Anyway, today I encountered a very weird thing while I was checking the difficulties of a bunch of our sudokus. For some reason onw of our sudokus took over one hour with the command-line check, and with another instance of SE about 20 minutes too. The sudoku is here:

000000080000060430030050609500000000206000000010000004000630005060084203008005060

I got this on a 2Ghz pentium
Code: Select all
6.7/1.2/1.2 4m55s 000000080000060430030050609500000000206000000010000004000630005060084203008005060
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Laitinen » Fri May 09, 2008 12:02 am

No, as I mentioned in the topic, it was SE 6.7. Though it might have been a bit unclear due to my typing errors in the main text:) .
Laitinen
 
Posts: 4
Joined: 08 May 2008

Postby ronk » Fri May 09, 2008 1:16 am

Laitinen wrote:No, as I mentioned in the topic, it was SE 6.7

Sorry, I have a bad habit of not reading topic titles. I thought you might a rating upwards of 10.6 which takes foreeeeveeeer on my 450 MHz machine ... so I didn't even try it. But I see gsf has already replied with a time.

[edit: added the following]

Laitinen wrote:Does anyone have any idea why is this being such a tough nut for SE?

Since you got (approx) 1 hour and 20 minutes on two different runs for the same puzzle, I suspect some other process(es) was/were competing for CPU time. Sudoku Explainer uses the Java runtime environment, and Java apps seem to have the lowest process priority on Windows.

Assuming you're actually using Windows, you can get some idea of what's going on in the Processes tab of Windows Task Manager. Place the processes using the most CPU time at the top of the list by double-clicking on the "CPU" column header.
Last edited by ronk on Thu May 08, 2008 9:37 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: SE 6.7 takes an enormous amount of time to evaluate

Postby daj95376 » Fri May 09, 2008 1:23 am

Laitinen wrote:Other solvers solve this rather painlessly. Does anyone have any idea why is this being such a tough nut for SE?

I don't know SE, but since no one has answered yet, I'll venture a guess that it can't handle Jellyfish or else it can't handle multiple colors (UR/turbot fish).
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Laitinen » Fri May 09, 2008 7:51 am

Actually it can, and it states that it has Jellyfish. The weird case is that we have loads of sudokus like this, the same rating and the same statistics, and usually it takes under 200 ms with our core quad running on linux - this time it took one hour. I was just thinking whether this particular sudoku was some kind of a worst case for SE.
Laitinen
 
Posts: 4
Joined: 08 May 2008

Postby Jean-Christophe » Fri May 09, 2008 8:10 am

SE takes abnormaly long time to solve this 6.7.

I believe SE has a bug in its Unique Rectangle/Loop technique. When I turn it off, it solves with normal times. When it's on, it takes ages to solve.

FWIW, the same puzzle with all singles already solved
600403582850062430432058609584300026206540308013826054020630845065084203348205060
Jean-Christophe
 
Posts: 149
Joined: 22 January 2006

Postby gsf » Fri May 09, 2008 2:20 pm

4m55s was on linux 2Ghz pentium, with other stuff running
20m (or greater) sounds fishy -- 200ms for SE on any puzzle sounds even fishier
if there is a lot of contention then time(1) will show a disparity between real vs (usr+sys) times
its ok to use usr+sys to measure performance

post a few dozen puzzles with the similar ratings so others can reproduce your results
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA


Return to General

cron