Baumstrukturmodus | Linearer Modus

surbier · (Dieser Beitrag wurde zuletzt bearbeitet: 01.03.2010 20:29 von surbier.)

Hallo

Zuletzt habe ich ein Sudoku aus der Zeitung geloest. Ich musste ein
paar Kandidaten eintragen, habe allerdings hinterher gesehen, dass das
Raetsel nur aus versteckten Einsern (Methode = Scannen, cross hatching)
bestand, von denen ich einige nicht fand. Dabei ueberlegte ich mir nach
welchen Gesichtpunkten man die Sudokus nach Schwierigkeit ordnen kann,
die nur aus versteckten Einsern bestehen.

Ich habe dazu vor einem Jahr schonmal was im Player's Forum ohne grosse
Resonanz gepostet. Dort wurde das Thema bereits frueher fuer Sudokus
mit versteckten UND nackten Einsern diskutiert.

Also als erstes Kriterium habe ich mir ueberlegt, dass man zu jedem
Spielstand die Anzahl der moeglichen versteckten Einser ermitteln koennte.
Ein Raetsel, das nach jedem Zifferneintrag mindestens 12 moegliche
versteckte Einser (hiernach HS fuer hidden singles) vorweist ist doch
bestimmt leichter zu loesen als ein Sudoku, das an einigen Stellen nur
noch 3 moegliche HS zeigt.

Ich zaehle hierbei nicht genau die verschiedenen Kandidaten, sondern die
unterschiedlichen logischen Schritte. Ich meine damit, dass wenn man die
3 in Z5S7 setzten kann, dass man damit bis zu drei unterschiedliche HS
singles hat, je nachdem ob der Kandidat 3 der einzige 3-er Kandidat in
Zeile 5 ist oder zusatzlich der einzige 3-er Kandidat in Spalte 7 oder
zusaetzlich auch der einzige 3-er Kandidat in Block 3 ist.

Das geringste Anzahl der HS (GAHS) waere ein Mass fuer die Schwierigkeit
eines (ich nenne es mal) HS Sudokus. Da man beim Eintragen der letzten
Ziffer immer auf GAHS=3 kommt (die letzte Ziffer ist ja immer ein HS in
Zeile, Spalte und Block), muesste man die Anzahl der HS gegen Ende des
Spielverlaufs ignorieren. Hat man z.B ein Sudoku mit 31 voreingetragen
Ziffern, das man in (81-31) = 50 Schritten loest, koennte man z.B. die
letzten zehn Schritte weglassen.

Das waere der erste Schritt einer Schwierigkeitsbewertung von HS Sudokus.

Die Schwierigsten HS Sudokus waeren solche, bei denen GAHS auf 1
sinkt, bei denen es also im Spielverlauf nur einen einzigen HS gibt;
ein Nadeloer.

Man kann sich nun leicht vorstellen, dass es auch HS Sudokus gibt,
bei denen es mehrere Stationen im Spielverlauf gibt, an denen GAHS auf
1 sinkt, die also mehrere (auch direkt aufeinanderfolgende) Spielzuege
aufweisen, bei den es keine Alternative gibt, nur ein einziges HS.

Fuer Sudokus dieser Schweirigkeitsstufe waere die Anzahl dieser Nadeloere
(die Anzahl der Spielschritte bei denen es keine Alternative gibt)
eine weitere Schwierigkeitsbewertung. Allerdings gibt es sehr wenige
HS Sudokus, bei denen die GAHS mehrmals auf Eins sinkt.

Die erste Bewertung (GAHS) habe ich mal spasseshalber programmiert,
womit die meiner generierten Sudokus, die nur aus HS bestehen, zuaetzlich
die GAHS Zahl als Schwierigkeitsbewertung mitbekommen.

Das ganze klingt zwar alles etwas akademisch, aber man natuerlich noch
eins draufsetzten: Jeder, der schonmal Sudokus geloest hat, hat die
Erfahrung gemacht dass wenn man z.B. eine 7 gesetzt hat, dass es dann
leichter ist weitere 7er zu setzten (vorausgesetzt es sind welche im Topf
der angebotenen HS) als dass man auf eine andere Ziffer wechseln muss.
Oft kommt es doch vor, dass man eine Ziffer mehrmals hintereinander
eintragen kann bevor man notgedrungen auf eine andere Ziffer wechseln
muss. Deshalb wuerde ich HS Sudokus, die mit aufeinanderfolgenden
Spielzuegen der gleichen Ziffer zu loesen sind leichter bewerten als
solche bei denen nach jedem HS auf einen anderen Kandidaten wechseln muss.

Das habe ich auch mal versucht zu programmieren, also alle moeglichen
Kombinationen von HS Spielzeugen auszuprobieren, um herauszubekommen,
ob es laengere Spielzugsequenzen mit dem selben Kandidaten gibt. Hat man
z.B. am Anfang 10 moegliche HS, sind vielleicht drei davon fuer die Ziffer
6. Die kann man loesen und danach pruefen, ob es nun neue HS fuer die
6 gibt. Wenn man das konsequent durchprobiert ( man muss ja nach jedem
Spielzug alle neuen HS suchen und nach Ziffern gruppieren) ergibt sich ein
langwieriges Unterfangen, das die Rechenzeit vielleicht nicht wert ist.

Hat sich da jemand schonmal Gedanken gemacht ? Ich denke mir die
profesionellen Raetselautoren muessen doch den Schwierigkeitsgrad ihrer
taeglich in Zeitungen veroeffentlichten HS Sudokus absolut unter Kontrolle
halten und muessen vielleicht die Rechenzeit doch in Kauf nehmen ?
Eine andere Situation sind vielleicht Wettbewerbe, wo man
extrem schwierige HS Sudokus anbieten will.

surbier

[an den Moderator: wenn das Thema besser in eine andere Rubrik passt, bitte veschieben]

surbier · 01.03.2010, 18:53

z.B. dieses Sudoku, das mit versteckten Einsern (= hidden singles =
HS) geloest werden kann:

Code:

. . . . . . . . .

1 6 . 3 . . . . 2

. 2 5 . . . 3 6 4

3 5 . 6 . 9 4 . .

8 . . . 2 3 . . .

. . 6 4 . 8 . . 7

. . . 5 3 6 2 1 .

. . 1 . . . . . .

6 3 2 . . 4 . . .

00000000016030000202500036435060940080002300000640800700053621000100000063200400​0

4 7 3 9 6 2 5 8 1

1 6 8 3 4 5 7 9 2

9 2 5 8 7 1 3 6 4

3 5 7 6 1 9 4 2 8

8 4 9 7 2 3 1 5 6

2 1 6 4 5 8 9 3 7

7 8 4 5 3 6 2 1 9

5 9 1 2 8 7 6 4 3

6 3 2 1 9 4 8 7 5

47396258116834579292587136435761942884972315621645893778453621959128764363219487​5

+-----------------------+--------------------------+-----------------------+

| 479    4789   34789   | 12789  1456789   1257    | 15789  5789   1589    |

|  >1<    >6<   4789    |  >3<   45789     57      | 5789   5789    >2<    |

| 79      >2<    >5<    | 1789   1789      17      |  >3<    >6<    >4<    |

+-----------------------+--------------------------+-----------------------+

|  >3<    >5<   7       |  >6<   17         >9<    |  >4<   28     18      |

|  >8<   1479   479     | 17      >2<       >3<    | 1569   59     1569    |

| 29     19      >6<    |  >4<   15         >8<    | 159    2359    >7<    |

+-----------------------+--------------------------+-----------------------+

| 479    4789   4789    |  >5<    >3<       >6<    |  >2<    >1<   89      |

| 4579   4789    >1<    | 2789   789       27      | 56789  345789 35689   |

|  >6<    >3<    >2<    | 1789   1789       >4<    | 5789   5789   589     |

+-----------------------+--------------------------+-----------------------+

Zu Spielanfang hat man 9 verschiedene Zahlen die man mittels HS eintragen
kann. Mehrmals spaeter im Spielverlauf hat man keine Alternative; es gibt
nur eine moeglichen Zahl, die man als HS eintragen kann, und gegen Ende,
wenn es weniger als 10-7 Ziffern einzutragen gilt, sinkt die Anzahl der
moeglichen Ziffern gegen 1.

Code:

9, 8, 8, 7, 8, 7, 6, 5, 4, 4, 3, 2, 1, 2, 3, 2, 4, 3, 3, 2, 1, 2, 1, 2, 3, 3, 2, 1, 3, 5, 5, 4, 3, 4, 4, 3, 5, 6, 7, 6, 5, 6, 5, 6, 5, 4, 4, 3, 2, 1

Zaehlt man, anders, naemlich die Anzahl der logischen Moeglichkeiten,
findet man zu Spielanfang 17 verschiedene logische Hebel um die 9
verschiedenen Zahlen zu setzen, da z.B. die 2 in [61] sowohl HS in Spalte
1 als auch HS in Block 4 ist; man kann sie auf zwei verschiedene Weisen
eintragen/setzen. Nachdem man die 20ste Zahl eingetragen hat, egal in
welcher Reihenfolge, gibt es nur eine einzige logische Alternative,
nur eine Ziffer mit nur einem (von drei moeglichen) HS. Die letzte
einzutragende Zahl ist als 'full house' noch trivialer als ein HS,
erscheint jedoch in dieser Zaehlung als ein HS bezueglich der Zeile,
der Spalte und des Blocks, deshalb 3.

Code:

17,17,16,13,16,13,11, 9, 8, 7, 5, 5, 2, 2, 3, 2, 6, 3, 3, 3, 1, 2, 2, 2, 5, 7, 4, 2, 4, 7, 9, 6, 6, 6, 7, 4, 8, 8,11,10,10, 9, 6, 9, 9, 6, 9, 9, 6, 3

Fuer dieses Sudoku, das nur aus HS besteht, ist nach letzterer Zaehlweise
GAHS=1, es also unter der Klasse der HS Raetsel schon etwas schwieriger.

StefanSch · 29.06.2010, 01:13

Ich weiß nicht, ob es Dich noch interessiert, aber wie wäre es mit folgenden Ansätzen zur Schwierigkeitsbewertung.

1) Nur das Minimum der HS zu betrachten, oder ggf. noch zu zählen, wie oft es vorkommt, blendet viele Informationen aus. Ein Rätsel bei dem ich lange Zeit nur wenige Möglichkeiten (z.B. 2 oder 3) habe, ist schwerer als eines, bei dem ich lange Zeit in Möglichkeiten schwimme und nur irgendwann einmal kurz intensiv suchen muss.
Da bietet sich folgender Ansatz an: Wenn noch n Kandidaten (damit meine ich eine Kombination aus Zahl + Zeile/Spalte oder Block) offen sind und es darunter k HS gibt, dann probiere ich einfach alle Kandidaten in einer zufälligen Reihenfolge durch, bis ich den ersten finde. Mit etwas Wahrscheinlichkeitstheorie kann man nachrechnen, dass ich im Mittel (n+1)/(k+1) Felder anschauen muss, bis ich fündig werde.
Diesen mittleren Aufwand addiert man einfach auf und weiß, wie lange man für das ganze Rätsel im Mittel suchen muss.

2) Das ist zwar ein netter Ansatz, aber in der Praxis sind nicht alle Kandidaten gleich erfolgversprechend. Wenn ich gerade eine 7 eingetragen habe, lohnt sich als nächstes eine Kombination aus einer weiteren 7 und einer Z/S/B, die durch die vorhergehende 7 auch beeinflusst wird. Werde ich da nicht fündig, dann lohnen sich Kombinationen, die man schon längere Zeit nicht untersucht hat, eher als solche die man gerade eben erst angeschaut hat. Naheliegend wäre hier eine zyklische Suche, die reihum alle Kandidaten nacheinander überprüft. Eventuell erweitert um "Zahlen-Schleifen", die Kandidaten mit der gleichen Zahl so lange bevorzugt untersucht, bis keine HS mehr gefunden werden.
Hier kann der Rechner dann selber zählen, wie of er Kandidaten testen musste.

Viele Grüße,
Stefan

surbier · 14.07.2010, 12:31

Hallo StefanSch

1)

Stimmt,
der mittlere Mehraufwand als Summe aller (n+1)/(k+1) ist besser. Ist wohl
mehr das Integral ueber den ganzen Spielverlauf, als mein vorgeschlagenes
Maximum. Der Vorteil ist auch, dass man die Mehraufwendungen am Spielende
nicht ausblenden muss. Sudokus mit weniger Ausgangsziffern wuerden
im Mittel schwieriger bewertet werden, da mehr Summanden beitragen. Ich wuerde
trotzdem eher n/k anstatt (n+1)/(k+1) aufsummieren (Anzahl der Tests durch
Anzahl der gefunden HS). Ist bei einem Spielstand kein HS vorhanden,
ist die Schwierigkeit sowieso nicht nicht ueber HS definiert.

Code:

n=40 k= 0:  #  nicht definiert, Sudoku ist kein HS Sudoku, vielleicht eins mit X-wing, nice loops, ...

n=40 k=20:  2 (leichter Schritt)

n=40 k= 1: 40 (schwieriger Schritt)

n=6  k= 6:  1 (leichter Schritt bei der zweitletzten einzutragenden Ziffer)

n=6  k= 2:  3 (etwas schwierigerer Schritt bei der zweitletzten einzutragenden Ziffer)

2)
Stimme ich dir ebenfalls zu. Ich hatte urspruenglich einen rekursiven
Loesungsweg programmiert, der alle moegliche Reihenfolgen der HS
ausprobiert, mit einem Vorzug von HS Reihenfolgen mit Kandidaten der
selben Art, um z.B. den Loesungsweg auszugeben mit der geringensten
Anzahl von Kandidatenwechseln. Ein HS-Sudoku, in dem nur noch die
6er fehlen, haette dann null Kandidatenwechsel, Ein HS-Sudoku, in dem
ein 3 und zwei 5er fehlen, koennte theoretisch mit einem oder zwei
Kandidatenwechel geloest werden (3, 5, 5 gegen 5, 3, 5). Wenn die
zuletzt geloeste Ziffer eine 5 war, wurde ein HS in der 5 als naechster
Loesungsschritt forciert. Wegen des dennoch grossen Paramerraums, war
die Rechenzeit extrem gross, sodass ich das Thema irgendwann ad acta
gelegt habe.

Auch die Idee nur die drei Einheiten Z/S/B zu testen in denen die letzte
Ziffer als HS gesetzt wurde bedeutet doch noch etwas Programmieraufwand.

Pyrrhon · 18.07.2010, 21:54

Im sel. Forum von sudoku.com haben sie eine ganze Zeit lang eine Schwierigkeitsschätzung verwendet, die dem Vorschlag sehr ähnlich ist. Auf Hidden Singles angewendet würde es heißen, dass man in jedem Schritt überlegt, welche Hidden Single alle möglich sind und dann alle möglichen Hidden Singles auf einmal ausführt. Danach folgt der nächste Schritt (die nächste Überlegung aller möglichen Hidden Singles). Das Maß ist dann die die Anzahl der Schritte bis zur Lösung.

Ich halte dieses Maß allerdings nicht für besonders gut, da es zumindest mir so geht, dass ich Hidden Singles in 3x3-Gebieten wesentlich leichter sehe als solche in Zeilen oder Spalten.