Algorithm to generate sure candidates for complete row / col

Str8ts discussion with Jeff Widderich and Andrew Stuart.
Stellen Sie hier Fragen an Str8ts-Erfinder Jeff Widderich und Andrew Stuart.

Moderatoren: Syndicate, Andrew

Algorithm to generate sure candidates for complete row / col

Beitragvon jamesaustin » Freitag 3. Januar 2014, 15:03

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!
jamesaustin
 
Beiträge: 2
Registriert: Freitag 3. Januar 2014, 14:52

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

Beitragvon apo » Dienstag 7. Januar 2014, 20:49

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
apo
 
Beiträge: 45
Registriert: Freitag 1. März 2013, 15:49
Wohnort: Schweiz

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

Beitragvon apo » Dienstag 7. Januar 2014, 21:30

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
apo
 
Beiträge: 45
Registriert: Freitag 1. März 2013, 15:49
Wohnort: Schweiz


Zurück zu English Str8ts forum

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast