Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

would you spot an XY wing before naked/hidden N-tuples

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Sat Dec 31, 2005 2:35 am    Post subject: would you spot an XY wing before naked/hidden N-tuples Reply with quote

Hello everyone,
This is my first post on this forum.
I started writing a basic Sudoku Human-style solver in JavaScript about 2 months ago, since then things went out of proportion.

I'm not an expert & programming is a hobby of mine. The simple program is now a chunky solver/generator which TAKES ITS TIME when solving very hard 3x3 grids. (But it does solves any grid at the end)

I have implemented most of the known techniques in it (Except colouring).

I adopt a nesting technique in solving , which means That I start from simple to more complex techniques, returning to the start when any elimination happens on the way.

Now obviously Forcing Chains, Nishio & Guessing (Deeppest T&E) have to be at the end (most outer techniques).

But on the other hand does XY wing for example have to be considered as very difficult technique or would Hidden Quads be more difficult ?

I'm trying to make my generator/solver more EFFECIENT and stop taking so much time in solving the most difficult grids.

By the way, this forum is fantastic & has helped me so much with my program
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sat Dec 31, 2005 3:19 am    Post subject: Reply with quote

Hi Tarek,

welcome to this forum.

There is no simple answer about the relative difficulty of techniques. It depends on too many variables: are you using a helper program, are you writing pencilmarks, etc.

There is, however, a difference between finding techniques vs. rating a puzzle by the required techniques. To find a technique, you want to be as efficient as possible, so search for pairs and triples, then find XY-Wings, and then return to find quads is wasting a lot of solver time.

I'd suggest you use configuration settings to assign priorities, like the Sudoku Susser does.

Happy Hollidays,

Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Sat Dec 31, 2005 10:48 am    Post subject: Reply with quote

Ruud wrote:
I'd suggest you use configuration settings to assign priorities


Thanx Ruud. When assigning priorities, do you actually solve the grid more than once & then select the method which requires the least steps ?

I've read elsewhere, that one way of doing that is by trying all techniques, changing the order in which they are used after having a solution (1234567 then 2345671, ......) & then choosing the most effecient answer.

Now that would mean putting the solver into serious excercise mode especially if we are talking about more than 9-10 techniques.
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sat Dec 31, 2005 1:05 pm    Post subject: Reply with quote

I know people have done tests like that. Not me.

The priorities in Sudo Cue are fixed. I use the order in which the techniques are described in most solving guides. The more difficult the technique, the further back it appears in most manuals (if any).

There is a topic on the Optimal Solving Path that I started on the players forum. You can find it here. A number of developers have given their view on the fastest way to solve a Sudoku. Unfortunately, the topic died.

For pure scientific reasons, you could have a solver try to pick apart a sudodu in as many ways as possible, then assess the shortest solving path. In most cases, you will end up using "Magic Cells" or "Backdoors". Every Sudoku, even the most difficult one, seems to have a few of them.

For a Sudoku helper program, the solver must always choose the simplest technique at each stage and not aim at solving speed.

Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Sat Dec 31, 2005 4:35 pm    Post subject: Reply with quote

I see it more clearly now, Thanx Ruud.

I tried searching for that thread on the Players forum without success. but anyway, I think I'm on the right track.
Back to top
View user's profile Send private message
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Wed Jan 04, 2006 1:42 pm    Post subject: Reply with quote

I finally found the thread (Well... I finally followed the link in your reply!!).
Now I'm pretty sure that my solver would spot things if they're there.
Here are my results:
65 Naked Singles
9 Hidden Singles
1 Line Box interaction (5 eliminations)
0 Doubles (Hidden or Naked)
0 Triples (Hidden or Naked)
0 X-Wing
1 Forcing Chain
5 Nishio
2 Guesses

1 solution

I follow this path:
Naked singles
Hidden singles
Line box elimination
Doubles (Naked & Hidden)
Triples (Naked & Hidden)
Quads,Quintuples, Sextuples (That's why it takes forever)
X-wing,Swordfish,.... (Again the same)
XY wing
Forcing chains
Nishio
Deep T&E (Guessing)

Now, my solver didn't spot any doubles triples X-wing

wa that because I missed them on the way, or was it because of different techniques or techniches not used (colouring, Tabling) ???
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron