Page 1 of 1

Algorithm to generate sure candidates for complete row / col

Posted: Friday 3. January 2014, 15:03
by jamesaustin
I've been writing a solver in Python for the past few days - simply for the pleasure of it.

Could some one give me some tips about creating an algorithm for generating the sure candidates for a complete row / col?

I have already created an algorithm to generate the sure candidates by compartment, but I'm not sure how to adapt or leverage this to generate the sure candidates for the complete row / col.

Any tips or suggestions would be really appreciated.

Happy to share the solver if anyone is interested in collaborating.

Thanks!

Re: Algorithm to generate sure candidates for complete row / col

Posted: Tuesday 7. January 2014, 20:49
by apo
Hi James

It probably depends a little bit on what you are willing to accept as an algorithm: the best way is to go through all the numbers 1-9 for each row/column and simulate if there is still a solution possible when you would skip the number. So: assume you would skip number 1 in row 1 -> will you then still be able to fill the compartments in row 1 without violating the rule that numbers are consecutive and only occur once? To determine this you could either simply check the basics (consecutive and unique) or you could simulate all other rules that you have (like stranded digit, high low, stranded sequence etc). This is I think also what we do when we try to resolve it with our brain (limited to a small number of moves we can anticipate). Whenever you reach a situation where you run into a contradiction you obviously hit a sure candidate.
The problem is (I think) that you want a solver not to be too clever - otherwise you could simply write an algorithm trying each and every combination until you hit the solution. So you have to answer to yourself how far you want to go with your algorithm for this check.
Maybe you start with a limited check (like only the sum of all sure candidates from all compartments of a row /column) and see how far you get with this? I assume you need to determine the SC for a check of Setti's rule?
At least some results you should get this way.

Cheers
apo

Re: Algorithm to generate sure candidates for complete row / col

Posted: Tuesday 7. January 2014, 21:30
by apo
Maybe I should add: you could also check for some patterns. E.g. We all know that if there are 2 compartments , each with 4 digits, in a row then 234678 are sure candidates. But this is not really an algorithm.

Apo