De Canadees Jeff Widderich ontwierp deze puzzel in 2007. Het doel is om in elke witte cel een cijfer tussen 1 en 9 in te vullen, zodat elk getal in het kruiswoordraadsel een straat vormt — een reeks opeenvolgende cijfers die in willekeurige volgorde mogen staan. Zo mag je op de bovenste rij van deze puzzel bijvoorbeeld de 5 cijfers 96587 invullen, maar niet 91548.
Er is nog een andere beperking: elk cijfer tussen 1 en 9 mag hoogstens één keer voorkomen op elke rij en op elke kolom. Dat betekent bijvoorbeeld dat elk van de twee lange verticale getallen alle negen cijfers zal bevatten. De cijfers in de zwart gekleurde cellen tellen mee voor deze beperking — de 9 in de zwarte cel dicht bij het midden betekent dat er in die rij en kolom geen andere 9 meer mag voorkomen. De unieke oplossing van bovenstaande opgave ziet er dan als volgt uit.
Het rooster van een str8ts puzzel bestaat steeds uit 9 rijen en 9 kolommen. Om de posities van de cellen in het rooster te kunnen aanduiden, worden de rijen (resp. de kolommen) van boven naar onder (resp. van links naar rechts) genummerd vanaf nul.
Opgave
Een cel in het rooster van een str8ts puzzel heeft twee onafhankelijke eigenschappen. De cel is al dan niet zwart gekleurd en de cel bevat al dan niet een cijfer. Om het rooster compact te kunnen voorstellen, wordt de combinatie van deze twee eigenschappen gecodeerd als één enkel karakter volgens dit schema:
| cijfer | geen cijfer | |
|---|---|---|
| niet gekleurd (wit) | een cijfer (1–9) | een punt (.) |
| wel gekleurd (zwart) | een letter (A–I) | een hekje (#) |
Zo wordt een witte cel die het cijfer 3 bevat gecodeerd als 3 en een zwarte cel die het cijfer 3 bevat als C (de derde letter van het alfabet). Een witte cel zonder cijfer wordt voorgesteld door een punt (.) en een zwarte cel zonder cijfer door een hekje (#). Op die manier kan de opgave van de voorbeeldpuzzel als volgt voorgesteld worden in een tekstbestand:
##..5..C# .6..##1.. ...#H.... 9..D...#E #....3..# ##...I.4. 4.3.##.6. ..1##.... ##8....#B
Cel
Definieer een klasse Cel waarmee cellen in het rooster van een str8ts puzzel kunnen voorgesteld worden. Bij het aanmaken van een nieuwe cel (Cel) moet het karakter (str) doorgegeven worden dat de twee eigenschappen van de cel codeert. Als het argument geen karakter is dat de toestand van een cel codeert, dan moet een AssertionError opgeworpen worden met de boodschap ongeldig symbool. Zorg ervoor dat de ingebouwde functie str dit gecodeerde karakter teruggeeft als er een cel (Cel) aan doorgegeven wordt.
Zorg ervoor dat je op een cel $$c$$ (Cel) minstens de volgende methoden kunt aanroepen:
-
Een methode isgekleurd (zonder argumenten) die een Booleaanse waarde (bool) teruggeeft, die aangeeft of cel $$c$$ (zwart) gekleurd is.
-
Een methode cijfer (zonder argumenten) die het cijfer (int) uit cel $$c$$ teruggeeft, of de waarde None als de cel geen cijfer bevat.
isstraat
Definieer een functie isstraat waaraan een getal $$n \in \mathbb{N}$$ (int) moet doorgegeven worden. De functie moet een Booleaanse waarde (bool) teruggeven, die aangeeft of $$n$$ een straat is. Dat is het geval als de cijfers van het getal in een opeenvolgende reeks kunnen gezet worden en als het cijfer nul (0) niet voorkomt in het getal.
Str8ts
Definieer een klasse Str8ts waarmee het rooster van een str8ts puzzel kan voorgesteld en ingevuld worden. Bij het aanmaken van een nieuwe puzzel (Str8ts) moet de locatie (str) doorgegeven worden van een tekstbestand met de opgave van een puzzel. Zorg ervoor dat de ingebouwde functie str een stringvoorstelling van het rooster teruggeeft als de puzzel (Str8ts) er aan doorgegeven wordt. Deze voorstelling heeft dezelfde vorm als in het gegeven bestand, waarbij cellen voorgesteld worden door het karakter dat de combinatie van hun twee eigenschappen voorstelt. Voorts moet de klasse Str8ts minstens de volgende methoden ondersteunen:
-
Een methode horizontaal_getallen waaraan het nummer (int) van een rij in het rooster moet doorgegeven worden. De methode moet een dictionary (dict) teruggeven die het nummer (int) van elke kolom waar het eerste cijfer van een getal moet ingevuld worden (witte cellen) afbeeldt op het patroon (str) dat aangeeft welke cellen van dat getal reeds ingevuld werden: een cijfer voor de ingevulde cellen en een punt voor de cellen die nog niet ingevuld werden.
-
Een methode verticaal_getallen waaraan het nummer (int) van een kolom in het rooster moet doorgegeven worden. De methode moet een dictionary (dict) teruggeven die het nummer (int) van elke rij waar het eerste cijfer van een getal moet ingevuld worden (witte cellen) afbeeldt op het patroon (str) dat aangeeft welke cellen van dat getal reeds ingevuld werden: een cijfer voor de ingevulde cellen en een punt voor de cellen die nog niet ingevuld werden.
-
Een methode horizontaal_cijfers waaraan het nummer (int) van een rij in het rooster moet doorgegeven worden. De methode moet een verzameling (set) teruggeven met alle cijfers (int) die reeds ingevuld werden op de gegeven rij (zowel in de witte als in de zwarte cellen).
-
Een methode verticaal_cijfers waaraan het nummer (int) van een kolom in het rooster moet doorgegeven worden. De methode moet een verzameling (set) teruggeven met alle cijfers (int) die reeds ingevuld werden op de gegeven kolom (zowel in de witte als in de zwarte cellen).
-
Een methode horizontaal_invullen waaraan drie argumenten moeten doorgegeven worden: i) een rijnummer $$r$$ (int), ii) een kolomnummer $$k$$ (int) en iii) een getal $$n$$ (int). De methode moet het getal $$n$$ horizontaal invullen vanaf positie $$(r, k)$$ in het rooster. Dit is enkel mogelijk als de volgende voorwaarden voldaan zijn:
-
$$n$$ is een straat
-
$$(r, k)$$ is de eerste cel van een horizontaal getal
-
$$n$$ heeft evenveel cijfers als het getal dat horizontaal moet ingevuld worden op positie $$(r, k)$$
-
de cijfers die reeds in het rooster ingevuld zijn corresponderen met de overeenkomstige cijfers van $$n$$
-
de cijfers die nieuw in het rooster ingevuld moeten worden, komen in die rij en in die kolom nog niet voor
Als minstens één van deze voorwaarden niet voldaan is, dan moet een AssertionError opgeworpen worden met de boodschap ongeldige vulling. In dat geval mag ook niets ingevuld worden in het rooster.
-
-
Een methode verticaal_invullen waaraan dezelfde argumenten moeten doorgegeven worden als bij de methode horizontaal_invullen. De methode werkt ook analoog aan de methode horizontaal_invullen, maar moet het getal $$n$$ verticaal invullen in het rooster, in plaats van horizontaal.
Voorbeeld
In onderstaande voorbeeldsessie gaan we ervan uit dat het tekstbestand puzzel.txt1 zich in de huidige directory bevindt.
>>> cel = Cel('C')
>>> str(cel)
'C'
>>> cel.isgekleurd()
True
>>> cel.cijfer()
3
>>> cel = Cel('.')
>>> str(cel)
'.'
>>> cel.isgekleurd()
False
>>> cel.cijfer()
>>> Cel('?')
Traceback (most recent call last):
AssertionError: ongeldig symbool
>>> isstraat(62534)
True
>>> isstraat(91548)
False
>>> puzzel = Str8ts('puzzel.txt2')
>>> print(puzzel)
##..5..C#
.6..##1..
...#H....
9..D...#E
#....3..#
##...I.4.
4.3.##.6.
..1##....
##8....#B
>>> puzzel.horizontaal_getallen(3)
{0: '9..', 4: '...'}
>>> puzzel.horizontaal_cijfers(3)
{9, 4, 5}
>>> puzzel.verticaal_getallen(5)
{0: '.', 2: '..3', 7: '..'}
>>> puzzel.verticaal_cijfers(5)
{9, 3}
>>> puzzel.horizontaal_invullen(0, 1, 96587)
Traceback (most recent call last):
AssertionError: ongeldige vulling
>>> puzzel.horizontaal_invullen(0, 2, 34567)
Traceback (most recent call last):
AssertionError: ongeldige vulling
>>> puzzel.horizontaal_invullen(0, 2, 7658)
Traceback (most recent call last):
AssertionError: ongeldige vulling
>>> puzzel.horizontaal_invullen(0, 2, 965874)
Traceback (most recent call last):
AssertionError: ongeldige vulling
>>> puzzel.horizontaal_invullen(1, 6, 102)
Traceback (most recent call last):
AssertionError: ongeldige vulling
>>> puzzel.horizontaal_invullen(0, 2, 96587)
>>> print(puzzel)
##96587C#
.6..##1..
...#H....
9..D...#E
#....3..#
##...I.4.
4.3.##.6.
..1##....
##8....#B
>>> puzzel.verticaal_invullen(1, 1, 6587)
>>> print(puzzel)
##96587C#
.6..##1..
.5.#H....
98.D...#E
#7...3..#
##...I.4.
4.3.##.6.
..1##....
##8....#B