Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Dop­pel­stun­de 11: Su­do­ku – eine An­wen­dung von Sets [nur LF, op­tio­nal]

Die letz­te Dop­pel­stun­de der Ein­heit ist op­tio­nal. Sie stellt eine in­ter­es­san­te An­wen­dung von Sets dar, ist aber ggf. zu kom­plex. Daher kann das Pro­jekt auch zur Dif­fe­ren­zie­rung in an­de­ren Stun­den ver­wen­det wer­den. In­halt­lich könn­te das Pro­jekt be­reits nach Dop­pel­stun­de 3 (ADTs, dar­un­ter Set) ein­ge­fügt wer­den. Al­ler­dings wird auch ein Back­tracking-An­satz ver­wen­det, der erst nach Dop­pel­stun­de 9 sinn­voll wäre. Es wäre sinn­voll (aber nicht un­be­dingt nötig), wenn im Vor­feld be­reits Lamb­da-Aus­drü­cke be­han­delt wor­den sind, da das Pro­gramm sich damit oft ein­fa­cher und ele­gan­ter im­ple­men­tie­ren lässt.

Das Ziel ist die Im­ple­men­tie­rung eines Su­do­ku-Lö­sungs­pro­gramms. Mit dem Auf­ga­ben­blatt 13_­su­do­ku.odt wer­den die Schü­le­rin­nen und Schü­ler durch die Im­ple­men­ta­ti­on einer Lö­sungs­stra­te­gie ge­führt. Pro­ble­ma­tisch könn­te es wer­den, wenn die Schü­le­rin­nen und Schü­ler nicht mit Su­do­ku-Rät­seln ver­traut sind. Daher wird der Al­go­rith­mus zur Be­stim­mung von Kan­di­da­ten­men­gen an einem Bei­spiel aus­führ­lich er­klärt und auf Men­gen­ope­ra­tio­nen zu­rück­ge­führt. Ähn­lich wie bei frü­he­ren Auf­ga­ben­blät­tern wird aus­schließ­lich in einer Mo­dell­klas­se (hier „Su­do­ku­Git­ter“) ge­ar­bei­tet, die GUI-Klas­sen wer­den nicht an­ge­fasst.

Wenn die Stra­te­gie mit nack­ten und ver­steck­ten Ei­nern nicht mehr wei­ter­führt, muss eine Zahl ge­ra­ten wer­den und über­prüft wer­den, ob man damit zu einem Ende kommt. Der hier ei­gent­lich nö­ti­ge Re­kur­si­ons­schritt wird über die GUI-Klas­se Su­do­kuF­rame er­le­digt5 . Damit müs­sen die Schü­le­rin­nen und Schü­ler den Re­kur­si­ons­schritt nicht selbst for­mu­lie­ren. Statt­des­sen kann man sehen, dass sich ein neues Fens­ter über das ak­tu­el­le legt und dort wei­ter­ge­ar­bei­tet wird. Even­tu­ell wer­den von dort aus noch wei­te­re Back­tracking-Schrit­te nötig sein usw.6 Erst wenn alle Mög­lich­kei­ten auf der un­ters­ten Stufe über­prüft wor­den sind (und diese nicht zu einem ge­lös­ten Spiel füh­ren), wird zu­rück­ge­kehrt und es wer­den dort die an­de­ren Mög­lich­kei­ten über­prüft.

Falls ein­zel­ne Schü­le­rin­nen und Schü­ler der Mei­nung sind, dass kom­ple­xe­re Lö­sungs­stra­te­gi­en bes­ser zum Ziel füh­ren als Back­tracking, kön­nen sie diese gerne als Er­wei­te­rung im­ple­men­tie­ren. „Nack­te Zwei­er“ sind noch re­la­tiv leicht im­ple­men­tier­bar, diese müss­ten nach dem Auf­stel­len der Kan­di­da­ten­men­gen ge­sucht wer­den, um die Kan­di­da­ten­men­gen ggf. zu re­du­zie­ren. Eine Über­prü­fung der schwe­ren mit­ge­lie­fer­ten Rät­sel führ­te al­ler­dings zum Er­geb­nis, dass diese nur in sel­te­nen Fäl­len wei­ter­hel­fen. An­de­rer­seits führt das Über­prü­fen sol­cher kom­ple­xer Stra­te­gi­en zu einem zu­sätz­li­chen Re­chen­auf­wand, der den Ef­fi­zi­enz­ge­winn durch die Ein­spa­rung der Re­kur­si­ons­schrit­te schnell zu­nich­te macht.

 

5 Auf­grund der Funk­ti­ons­wei­se der Java-Frames und der asyn­chro­nen Funk­ti­ons­auf­ru­fe muss die Re­kur­si­on in ver­schie­de­ne Me­tho­den der Klas­se Su­do­kuF­rame aus­ge­la­gert wer­den.

6 Beim Tes­ten war die ma­xi­ma­le Re­kur­si­ons­tie­fe, die vor­kam, 6 Stu­fen.

 

Un­ter­richts­ver­lauf: Her­un­ter­la­den [odt][187 KB]

 

Wei­ter zu Hin­ter­grund­in­for­ma­tio­nen