Schwierigkeitsbewertung leichter Sudokus - Druckversion +- Logic Masters Forum (http://forum.logic-masters.de) +-- Forum: Allgemeines (http://forum.logic-masters.de/forumdisplay.php?fid=3) +--- Forum: Rätseldiskussionen (http://forum.logic-masters.de/forumdisplay.php?fid=13) +--- Thema: Schwierigkeitsbewertung leichter Sudokus (/showthread.php?tid=574) |
Schwierigkeitsbewertung leichter Sudokus - surbier - 28.02.2010 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] RE: Schwierigkeitsbewertung leichter Sudokus - surbier - 01.03.2010 z.B. dieses Sudoku, das mit versteckten Einsern (= hidden singles = HS) geloest werden kann: Code: . . . . . . . . . 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. RE: Schwierigkeitsbewertung leichter Sudokus - StefanSch - 29.06.2010 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 RE: Schwierigkeitsbewertung leichter Sudokus - surbier - 14.07.2010 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, ... 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. RE: Schwierigkeitsbewertung leichter Sudokus - Pyrrhon - 18.07.2010 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. RE: Schwierigkeitsbewertung leichter Sudokus - surbier - 22.10.2010 Hi, StefanSch A) Ich habe den Aufwand pro Spielzug und den mittleren Aufwand fuer alle Spielzuege wie oben beschrieben codiert und ueber das Raetsel laufen lassen. Dabei bekomme ich einen mittleren Aufwand von 17.8 Kandidaten/(moegliche HS Spielzuege). In der ersten Tabelle sind die Werte fur den Spielverlauf angegeben. Beim 20sten Spielzug gibt es nur einen HS, somit einen hohen Aufwandswert fuer den aktuellen HS und der Aufwandsmittelwert steigt ebenfalls ein wenig. Ich habe das nun fuer mehrere HS-Sudokus mit unterschiedlicher Anzahl der Ausgangsziffern ausprobiert und bekomme Werte zwischen 0.33 und ~30. Sieht auch vielversprechend aus. B) Dann habe ich die Reihenfolge der HS (der Spielzuege) variiert; einfach die Kandidaten Schleife 'for (k=1; k<=9; k++)' in absteigender Reihenfolge als 'for (k=9; k>=1; k--)' laufen lassen. Das obige Beispiel ist bei diesem zweiten Spielverlauf kein GAHS=1 Sudoku mehr. Das heisst der aktuelle Aufwand und der mittlere Aufwand fuer das ganze Raetsel ist abhhaengig vom Loesungsweg (von der Reihenfolge der HS), denn jedes HS reduziert eine unterschiedliche Anzahl von Kandidaten. Man sieht, dass Spielzug #13 und #14 in beiden Spielverlaeufen (siehe zweite Tabelle) identisch sind, und dass alle Spielzuege #1 bis #12 in beiden Spielverlaufen bis auf die Reihenfolge ebenfalls gleich sind. Mit Spielzug #15 divergieren die Spielverlaefe: Code: Spielstand nach 14 Spielzuegen Beim ersten Spielverlauf, loest 5[99] das Nadeloer erst in Spielzug #20 und ist dort das einzige HS. Im zweiten Spielverlauf, wird 5[99] schon im Spielzug #15 gespielt und oeffnet frueher neue HS, die im ersten Spielverlauf erst ab #20 freigegeben werden. Wenn man 5[99] als ersten Spielschritt - Es ist wohl nicht moeglich, eine eindeutige Schwierigkeitsbewertung nur an Hand der HS, der GAHS oder des mittleren Aufwands zu bestimmen. - Die ersten 17 Spielzuege sind unabhaenging voneinader, und das scheint auch wohl der Grund gewesen zu sein, warum man im Beitrag im Players Forum jede Gruppe von unabhaengigen HS und naked singels als einen Schritt gezaehlt hat. - Ich kenne mich in der Theorie der Entscheidungsbaeume und der Graphentheorie nicht aus; das Problem ist dort sicherlich namentlich bekannt und vielleicht gibt es auch Verfaheen um die Mannigfaltigkeit und Tiefe zu messen. Haette mir eigentlich schon frueher einfallen koennen. Gruss surbier Tabelle: Spielverlauf mit aufsteigender Auswahl der Kandidaten. invest=(176/ 17) : 176 Kandidaten (pencil marks) bei 17 moeglichen hidden singles avg=10.353 : Mittelwert bei diesem Spielstand HS col 1 2[61] : hidden single in Spalte 1 eliminiert die 2 in Reihe 6 Spalte 1 FH = full house (ist auch nackter Einser da letzter Kandidat in einer Einheit/house). Code: 1 invest=(176/ 17)=10.353 avg=10.353 HS col 1 2[61] Tabelle 2: Spielverlauf mit absteigender Kandidatenfolge Code: 1 invest=(176/ 17)=10.353 avg=10.353 HS col 5 6[15] |