|
View previous topic :: View next topic |
Author |
Message |
| tarek
| Joined: 31 Dec 2005 | Posts: 153 | : | Location: London, UK | Items |
|
Posted: Sat Dec 31, 2005 2:35 am Post subject: would you spot an XY wing before naked/hidden N-tuples |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Sat Dec 31, 2005 3:19 am Post subject: |
|
|
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 |
|
|
| tarek
| Joined: 31 Dec 2005 | Posts: 153 | : | Location: London, UK | Items |
|
Posted: Sat Dec 31, 2005 10:48 am Post subject: |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Sat Dec 31, 2005 1:05 pm Post subject: |
|
|
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 |
|
|
| tarek
| Joined: 31 Dec 2005 | Posts: 153 | : | Location: London, UK | Items |
|
Posted: Sat Dec 31, 2005 4:35 pm Post subject: |
|
|
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 |
|
|
| tarek
| Joined: 31 Dec 2005 | Posts: 153 | : | Location: London, UK | Items |
|
Posted: Wed Jan 04, 2006 1:42 pm Post subject: |
|
|
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 |
|
|
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|