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   

Bifurcation vs. Forcing Chain

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

Joined: 05 Mar 2008
Posts: 32
:
Location: Cambodia

Items
PostPosted: Mon Mar 10, 2008 12:28 pm    Post subject: Bifurcation vs. Forcing Chain Reply with quote

Hi,

My first attempt at solving forcing chains (or forced chains?) in a solver I am working on included branching to quickly find if the chain lead to a contradiction. My understanding of chains came from observation and some tutorials I had read, and they had not specifically mentioned how branching was handled.

From the links on this site I found the sudopedia which gives a more precise definition of a forcing chain clearly states that they must not include branching, so today I modified my code and found it made no practical difference, it just identified a different starting point for the chain, and it is significantly slower, because more options are tested before a contradiction is found.

After further reading I found bifurcation which seams to describe more closely my original code. Only cells with two candidates are considered, but branches are followed.

From my understanding of what I am reading, if a puzzle leads to a contradiction by bifurcation then it must by definition contain a forcing chain, otherwise there would be no contradiction. The two techniques are interchangeable.

Is my understanding correct, and how have others handled forcing chains in their code?

Thanks

Garvan
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Adak

Joined: 27 Feb 2008
Posts: 87
:

Items
PostPosted: Thu Mar 13, 2008 1:51 pm    Post subject: Reply with quote

My code hasn't got that far, yet. Just finished locked candidates #1, and the outside rule of pairs.

How far down the list of solving techniques do you plan to go with your program, Garvan?

The list of solving techniques seems very long indeed!

Hopefully, one of the more advanced program coders will give you a better answer.


Last edited by Adak on Fri Mar 28, 2008 8:02 am; edited 1 time in total
Back to top
View user's profile Send private message
Sisophon2001

Joined: 05 Mar 2008
Posts: 32
:
Location: Cambodia

Items
PostPosted: Sat Mar 15, 2008 2:24 am    Post subject: Reply with quote

I will keep at it as long as I enjoy learning about and adding new solving methods, and for as long as I can manage the speed aspects. Each new solving method slows things down, but I never feel I understand a solving method until I write it down in code.

I profiled my code and found that 60% of processing time is taken up looking for fish. I think I need to speed this up first before worrying about chains which is only 1% of processing time. Perhaps I can add more fish types while I am at it.

Garvan
Back to top
View user's profile Send private message Send e-mail Visit poster's website
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