Entwickler-Ecke :: Thema anzeigen

Fiete - Mo 31.07.17 18:03
Titel: Bidoku-Generator

Moin,
ein Bidoku ist ein vom bekannten Sudoku inspiriertes Denkspiel für
Informatiker. In einem 16x16-Raster sollen Nullen und Einsen verteilt
werden. Dabei ist das Raster in 16 Zeilen, 16 Spalten und 16
4x4-Unterquadrate unterteilt.
BidokuScreen1

Das Bidoku ist gelöst, wenn in jeder der Spalten und Zeilen und in jedem der
Quadrate genau 8 Einsen und genau 8 Nullen stehen.
BidokuScreen2

Bidokus scheinen stark mit Sudokus zusammenzuhängen.
Bei den Lösungsstrategien gibt es allerdings deutliche Unterschiede.
Übliche Sudoku-Techniken wie das Führen von Kandidatenlisten oder das
Erarbeiten von Teillösungen sind im binären Fall nicht anwendbar.

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

                                                   NE
                1 1 1 - - 1 0 1 - 0 1 0 0 0 - 0    66
                0 - 1 1 - 0 1 1 1 1 - 1 0 0 0 -    57
                1 1 0 0 0 0 0 1 0 0 - 1 1 1 1 1    78
                0 0 - 0 1 0 0 - 0 0 1 1 - 1 1 1    76
                1 0 1 0 1 1 - - 1 0 0 - 1 0 - 0    66
                1 - 1 0 1 0 0 0 0 - 0 0 1 1 1 -    76
                0 1 - 0 1 1 1 0 0 1 1 1 0 - 0 0    77
                1 - 0 0 0 1 - 0 1 1 - 1 0 1 1 0    67
                - 0 1 0 1 1 1 - 1 0 1 0 - 0 0 -    66
                1 0 1 - 1 - 1 1 - 1 0 0 0 0 - 0    66
                1 0 - 1 0 0 0 1 0 1 0 - 1 1 1 1    68
                0 0 1 0 - 0 0 0 1 - 1 1 1 0 1 1    77
                - 1 0 1 1 0 0 - 0 1 - 0 - 1 0 -    65
                0 1 0 - 0 1 - 0 - 1 0 0 0 1 0 1    85
                0 1 0 1 0 1 1 0 1 0 0 1 1 - 0 0    87
                0 - 0 1 0 - 1 0 1 0 - 1 1 0 0 1    76

                7 6 6 8 6 7 7 7 6 7 6 6 6 7 7 6  Nullen
                7 6 7 5 7 7 6 5 7 7 5 8 7 7 6 6  Einsen

Ein ganz einfaches Bidoku mit 48 freien Feldern.
Quelle: BWInf 25(2008) Runde2 Aufgabe2

Ein Bidoku wird generiert indem im ersten Schritt ein vollständig
gelöstes erzeugt wird. Im nächstenSchritt werden Zahlen gelöscht.
Zur Wahl steht unter Options eindeutige Lösung oder mehrdeutige.
Die in der Prozedur BidokuErstellen angegebenen Löschzahlen werden in der
eindeutigen Suche nicht immer erreicht, zu berücksichtigen ist auch
die Wahl der Muster(6 sind vorgegeben).

Zum Lösen eines Bidokus kann wie folgt vorgegangen werden:
wenn man eine Zeile, Spalte oder ein Quadrat findet, in dem bereits
acht Nullen oder acht Einsen stehen kann man die leeren Felder mit
der jeweils anderen Zahl füllen. Die einfachste Strategie ist es also,
immer die Anzahlen der Zahlen in jeder Zeile, Spalte und in jedem
Quadrat zu prüfen.
Wenn man mit dieser einfachen Regel keine Zahlen mehr eintragen kann,
muß man die Spalten(Zeilen) mit den Quadraten kombinieren.
Es ergibt sich folgender Sachverhalt(in der PDF-Datei, Seite 16)

gilt 16 - Einsen(Quadrat q) - Nullen(Spalte s)<= Frei(Spalte s, Quadrat q)

dann kann man das entsprechende Quadrat außerhalb des Schnitts mit Nullen und die
entsprechende Spalte außerhalb des Schnittes mit Einsen auffüllen.
Glücklicherweise funktioniert dieser Trick nicht nur für jede Kombination
von Spalten mit Quadraten, sondern auch für jede Kombination von Zeilen mit
Quadraten. Außerdem können sich die Rollen von Einsen und Nullen vertauschen.

Wer ein Bidoku selbst lösen möchte hat als Hilfe die Zeilen-, Spalten- und
Quadratzählung. Falls ein Eintrag falsch sein sollte kann über Bearbeiten
eine Korrektur vorgenommen werden. Zum Üben ist Einfach001.bid günstig!
Eigene Muster können über Datei - Neu oder über Muster selbst kreiert werden,
zum Löschen einzelner Werte kann die Leer- oder Minustaste benutzt werden.
Nach dem Speichern kann über Felder sperren eine Lösung angezeigt werden.
Bidokus können gedruckt bzw. als bmp-Datei gespeichert werden.
Viel Spaß beim Testen!
Gruß Fiete

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!