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   

Simple Sudoku Solving Techniques and Order
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Fri Mar 31, 2006 5:23 pm    Post subject: Simple Sudoku Solving Techniques and Order Reply with quote

I have Simple Sudoku and enjoy playing it at my limited skill level. However, I will never forgive angusj for removing bold highlighting from naked_single cells in version 4.1z. Very Happy

Anyway, I recently was stumped on a puzzle and the F7 hint said that eliminations could be performed based on a naked_quad. However, when I ran the same puzzle through QQwing, it reported a hidden_pair at the same step.

Obviously, the two programs apply solution techniques in a different order. That's okay, but now I'm curious as to the order SS applies its solution techniques. angusj?
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Fri Mar 31, 2006 10:20 pm    Post subject: Re: Simple Sudoku Solving Techniques and Order Reply with quote

daj95376 wrote:
That's okay, but now I'm curious as to the order SS applies its solution techniques. angusj?


Naked Singles
Hidden Singles
Naked Pairs
Locked Candidates
Naked Triples
Naked Quads
Hidden Pairs
XWing
Swordfish
Colors
MultiColors
Hidden Triples
XYWing
Hidden Quads

Smile
Back to top
View user's profile Send private message Visit poster's website
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Fri Mar 31, 2006 10:59 pm    Post subject: Reply with quote

Thank you for Simple Sudoku ... and your reply.
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Sat Apr 01, 2006 12:37 am    Post subject: Reply with quote

daj95376 wrote:
Thank you for Simple Sudoku ... and your reply.

It's a pleasure. Thanks for your thanks too Smile.
Back to top
View user's profile Send private message Visit poster's website
gypsy fly

Joined: 06 Mar 2006
Posts: 18
:
Location: Portland OR USA

Items
PostPosted: Mon Apr 03, 2006 5:12 am    Post subject: Reply with quote

Does SS scan left to right, top to bottom?
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Mon Apr 03, 2006 5:50 am    Post subject: Reply with quote

gypsy fly wrote:
Does SS scan left to right, top to bottom?

Yes.
Back to top
View user's profile Send private message Visit poster's website
evert

Joined: 30 Aug 2005
Posts: 68
:
Location: Amsterdam

Items
PostPosted: Mon Apr 03, 2006 12:16 pm    Post subject: Reply with quote

In some cases it's a pity that Simple Sudoku doesn't look at the number of elimination steps.
See the following puzzle:
Code:

 *-----------*
 |..1|4..|9.7|
 |..2|..6|.58|
 |.7.|...|...|
 |---+---+---|
 |.5.|.24|1..|
 |...|...|.3.|
 |7.9|5..|..4|
 |---+---+---|
 |29.|8..|..3|
 |...|..1|...|
 |.45|...|...|
 *-----------*

 *-----------*
 |..1|43.|9.7|
 |932|..6|458|
 |.7.|...|3.1|
 |---+---+---|
 |.5.|.24|1..|
 |...|...|.3.|
 |7.9|5.3|.84|
 |---+---+---|
 |29.|84.|.13|
 |...|..1|.4.|
 |145|3..|8..|
 *-----------*
 
 *-----------------------------------------------------------*
 | 568   68    1     | 4     3     258   | 9     26    7     |
 | 9     3     2     | 17    17    6     | 4     5     8     |
 | 4568  7     468   | 29    589   2589  | 3     26    1     |
 |-------------------+-------------------+-------------------|
 | 38    5     38    | 679   2     4     | 1     79    69    |
 | 46    12    46    | 179   1789  789   | 257   3     259   |
 | 7     12    9     | 5     16    3     | 26    8     4     |
 |-------------------+-------------------+-------------------|
 | 2     9     67    | 8     4     57    | 567   1     3     |
 | 368   68    3678  | 2679  5679  1     | 2567  4     2569  |
 | 1     4     5     | 3     679   279   | 8     79    269   |
 *-----------------------------------------------------------*

From this stadium Simple Sudoku applies 4 color steps.
However one multiple color step also solves it - see 6 R9C59 and 6 R6C57R4C9.
It was also easier for me to spot it. Smile
Regards
Evert
Back to top
View user's profile Send private message Send e-mail
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Mon Apr 03, 2006 1:08 pm    Post subject: Reply with quote

evert wrote:
In some cases it's a pity that Simple Sudoku doesn't look at the number of elimination steps.

Yes, it is a pity. However, it'd take about 10 times as long to write (and debug) such a programme and consequently would probably never see the light of day Smile.
Back to top
View user's profile Send private message Visit poster's website
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Mon Apr 03, 2006 2:49 pm    Post subject: Reply with quote

evert wrote:
From this stadium Simple Sudoku applies 4 color steps.
However one multiple color step also solves it - see 6 R9C59 and 6 R6C57R4C9.
It was also easier for me to spot it.

I don't see that "one color step" at all. Would you please clarify?

TIA, Ron
Back to top
View user's profile Send private message
evert

Joined: 30 Aug 2005
Posts: 68
:
Location: Amsterdam

Items
PostPosted: Mon Apr 03, 2006 3:25 pm    Post subject: Reply with quote

Very helpful explanation of multiple colors:
http://www.setbb.com/sudoku/viewtopic.php?p=2575&mforum=sudoku#2575

There is a very short conjugate chain of 6s R9C5-R9C9 - let's lable them a and A.
There is also a conjugate chain R6C5-R6C7-R4C9 - let's lable them b and B and b.

R6C5 looks at R9C5 therefore b looks at a.
R4C9 looks at R9C9 therefore b looks at A.

If b looks at both a and A then b is false and therefore B is true.

--> R6C7 = 6.
Back to top
View user's profile Send private message Send e-mail
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Mon Apr 03, 2006 5:22 pm    Post subject: Reply with quote

evert wrote:
If b looks at both a and A then b is false and therefore B is true.

Of course, but the design philosophy of Simple Sudoku is to emulate a human solver. Therefore, it will find all simple coloring deductions -- those based on a single chain of conjugate links -- before it makes any multi-color deductions with two chains.
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Mon Apr 03, 2006 6:14 pm    Post subject: Reply with quote

rkral wrote:
the design philosophy of Simple Sudoku is to emulate a human solver. Therefore, it will find all simple coloring deductions before it makes any multi-color deductions with two chains.

It is my experience - having published over a 100 nightmares - that human solvers shoot first and ask questions later. Many of the nightmares were immediately attacked with forcing chains after basic eliminations, despite my effort to select sudokus that do not require forcing chains.

The human solver is too diverse to be emulated by a single program.

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

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Mon Apr 03, 2006 7:57 pm    Post subject: Reply with quote

Ruud wrote:
The human solver is too diverse to be emulated by a single program.

You are taking my statement too literally, I think.

If for any given puzzle, 51% or more of human solvers find a single chain of conjugates before they find two chains of conjugates, then I'd say a solver designed to make single chain deductions before multi-chain deductions is emulating a human solver.

Hmmm. Doesn't one *always* need to spot a 1st chain before one can spot a 2nd chain? Smile
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Mon Apr 03, 2006 8:57 pm    Post subject: Reply with quote

rkral wrote:
Hmmm. Doesn't one *always* need to spot a 1st chain before one can spot a 2nd chain?

Not necessarily. I can spot a "skyscraper" or a "2-string-kite" as a single pattern, although I know there are multiple chains involved.

The human solver, unlike a computer program, will look at the complete picture and spot *anything* recognizable. How often will you not handle a set of locked candidates as a naked triple, rather than using the *easier* line-box interactions?

Are you really looking for singles first, then line-box, then naked pairs, then naked triples, then.... when an X-Wing is drawing your attention?

The use of programs like SudoCue and Simple Sudoku make it easier for a player to spot patterns than ever before. I can spot a finned fish even before I smell it. Yet many solvers prefer to apply coloring before any finned fish is reeled in.

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

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Mon Apr 03, 2006 9:19 pm    Post subject: Reply with quote

Ruud wrote:
Are you really looking for singles first, then line-box, then naked pairs, then naked triples, then.... when an X-Wing is drawing your attention?

You use whatever "pops out" at you, of course ... so I think that's a silly question. I'm referring to a regimen one must fall back upon when nothing ... absolutely nothing ... pops out.

Anyway, I'm done with this topic. The relative priority of techniques is often a matter of personal preference and opinion, and I'm sure you know what people say about opinions. Besides, it's not even my solver. Smile
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
Goto page 1, 2  Next
Page 1 of 2

 
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