Bifurcation vs. Forcing Chain

Sisophon2001 · Posted: Mon Mar 10, 2008 12:28 pm Post subject: Bifurcation vs. Forcing Chain

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

Adak · Posted: Thu Mar 13, 2008 1:51 pm Post subject:

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.

Sisophon2001 · Posted: Sat Mar 15, 2008 2:24 am Post subject:

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