Woordvlakken

Er lijken in het Nederlands niet veel woordvierkanten te zijn. Er is zelfs geen Nederlandse Wikipediapagina voor. Het enige wat ik tot nu toe op het internet heb kunnen vinden is een oude nieuwsgroepthread met twijfelachtige 8×8 vierkanten. En een pagina van Aad van de Wetering. Hij heeft een vierkant van 6×6 gevonden en een zeer leuk palindroomvierkant. Mijn doel in deze post is om een mooie verzameling Nederlandse woordvierkanten en andere woordvlakken te maken.

Woorden

Ik gebruik woorden uit de volgende bronnen:

  • 90.000 ondertitelingsbestanden
  • 5000 boeken
  • 75.000 nieuwsartikelen
  • 1.000.000 Wikipedia artikelen
  • 5 woordenboeken

Ik filter andere talen door alle zinnen die minstens één van de 100 meest voorkomende woorden in een andere taal bevatten (die niet ook een Nederlands woord kunnen zijn) niet mee te tellen. En ik maak ook kwalitatief onderscheid op basis van hoofdlettergebruik, koppeltekengebruik, frequentie en betrouwbaarheid van bron. Ik heb zo 3 lijsten van 100.000, 300.000 en 3.000.000 woorden groot gegenereerd die het algoritme als bron gebruikt.

Traditionele vierkanten

De minst beperkende en bekendste vorm van het woordvierkant gebruikt dezelfde woorden zowel horizontaal als verticaal. Hierdoor is maar de helft van de letters onafhankelijk. Volgens mij is de 9×9 het grootste Nederlandse woordvierkant tot nu toe, de 8×8 gebruikt enkel woorden uit de Dikke van Dale (14de editie):

s t r o h a l m
t j e m i n e e
r e c r e a d e
o m r o l l e r
h i e l r i n g
a n a l i s t e
l e d e n t a l
m e e r g e l d

 

f a b r i k a a t
a s i a n i s m e
b i j s l e p e n
r a s t e r i n g
i n l e v e r d e
k i e r e w i e r
a s p i r i n e s
a m e n d e e r t
t e n g e r s t e

Bronnen: asianisme kierewier amendeert

Een 10×10 heb ik met een ongefilterde woordenlijst van ~3 miljoen woorden waarvan 300.000 10-letterig nog niet gevonden. Wellicht dat het mogelijk is met namen van mensen, plaatsen, rivieren, bergen of straten.

Dubbele woord vierkanten

Veel zeldzamer zijn vierkanten waarbij de horizontale en verticale woorden verschillen. Zeker als het een eis is dat er geen dubbele woorden worden gebruikt. Deze 7×7 is moeilijker te vinden (49 afhankelijke letters) dan de 9×9 met identieke woorden horizontaal en verticaal hiervoor (44 afhankelijke letters):

s t a k k e r
t r a a n d e
a a n k e e k
l i b e l l e
k n o l l e n
e e n d e r e
r e d e n e n

Zeer zeldzaam zijn vierkanten waarbij er ook nog valide diagonalen zijn. Dit 5×5 vierkant bevat dus 12 unieke woorden:

p l a n k
l e r e n
o l i g o
e i d e r
g e e r s

Bronnen: peies

Helaas alleen in 3×3 vorm, een dubbel woordvierkant waarbij alle letters achter elkaar het woord “dierenark” vormen:

d i e
r e n
a r k

Bronnen: dra, enk

Sommige woorden zijn zowel horizontaal als verticaal leesbaar na het plaatsen in een vierkant, hier zijn de aparte regels geen woorden meer:

dir  par  ont  med
ige  ade  nie  ele
ren  ren  ter  den

Palindromen en keerwoorden

Een keerwoord is een woord wat achterstevoren ook een woord is, zoals rood en door. Het bekendste woordvierkant, het sator vierkant, bestaat enkel uit keerwoorden. Ook zijn de onderste helft van de woorden de omgekeerde versies van de woorden in de bovenste helft. Dit creërt de eigenschap dat als je alle woorden achter elkaar zet dit een palindroom vormt. Verder betekent dit dat het vierkant ook van onder naar boven en van rechts naar links leesbaar is. Mijn Nederlandse variant:

d e e n s
e t t e n
e t s t e
n e t t e
s n e e d

Als alle woorden palindromen zijn krijg je een vierkant met dubbele symmetrie, helaas is het aantal nederlandse palindromen dermate beperkt dat wat creativiteit vereist is:

n e t t e n
e l e e l e
t e r r e t
t e r r e t
e l e e l e
n e t t e n

Eleele (plaats in Hawaï) terret (druifsoort)

Om de traditie van het combineren van Engels en Nederlands in stand te houden is dit een vierkant wat in de ene orientatie een traditioneel Nederlands woordvierkant is maar 180° gedraait ook een traditioneel Engels vierkant blijkt te zijn!

m e e s
e e r t
e r g o
s t o l

De volgende vraag is of er ook een vierkant met 4 leesbare zijden bestaat. Een dubbel vierkant met alleen keerwoorden en zonder dubbele woorden. Een 4×4 met 16 woorden lijkt helaas niet mogelijk zonder Reve er bij te betrekken. Dit noem ik een vierdubbel woordvierkant. Een leuke bijkomstigheid is dat er precies even veel letters als woorden in zitten:

m a r k
e g e l
l a v a
k r e k

Hij bevat de woorden

links-rechts: mark, egel, lava, krek
boven-onder: melk, agar, Reve, klak
rechts-links: kram, lege, aval, kerk
onder-boven: klem, raga, ever, kalk

Andere vlakken

Tot nu toe hebben we alleen vierkanten gezien maar vele andere vormen zijn natuurlijk mogelijk, zoals deze rechthoek:

k n i k k e n
r e m o l i e
a m a r a n t
n e g e n d e
k r o n k e l

Andere vormen dan rechthoeken zijn ook mogelijk zoals deze enkele driehoek, met horizontaal en verticaal dezelfde woorden:

d e s k t o p v e r s i e
e n t r e p r e n e u r
s t o o r v e l d e n
k r o m m i n g e n 
t e r m i e t e n
o p v i e l e n 
p r e n t e n
v e l g e n 
e n d e n
r e e n 
s u n
i r 
e 

IR (infrarood), sun (Chineese lengtemaat), reen (vergeten woord, synoniem met berm)

Of een dubbele driehoek, met andere woorden op zijn assen:

k
l a
e n k 
t o o g
s m e e r
k a r k a s
o l i e b o l
e i e r b o e r
k e r m i s s e n

Of veel gekkere vormen, zoals deze combinatie van een 3×3, 4×4, 5×5 en 6×6:

m a t r a s
a z i a a t
t i m b r e
r a b i d e
a a r d e n
s t e e n s t o r t
          t o f o e
h e k     o f f e r
e g o     r o e s t
k o b a l t e r t s
    a h o i
    l o o n
    t i n g

Alle voorgaande voorbeelden gebruiken een raster van vierkanten om de letters in te zetten. Dit geeft 2 assen om de woorden in te lezen. Maar hexagons zijn ook een mogelijkheid. Dit vlak is correct in 3 assen:

  s k a
 k a l k
a l l e s
 k e s p
  s p a

aks (een soort lange bijl), kesp (een extentie van een heipaal tot de vloer).

Een andere manier om 3 assen te creeën is met een kubus. Hierbij kloppen doorgestoken woorden (dezelfde letter in elk vlak) ook.

p a s t a   a p a r t   s a b e l   t r e m a   a t l a s 
a p a r t   p l o o i   a o r t a   r o t o r   t i a r a 
s a b e l   a o r t a   b r a a m   e t a g e   l a m e l 
t r e m a   r o t o r   e t a g e   m o g e n   a r e n d 
a t l a s   t i a r a   l a m e l   a r e n d   s a l d o 

Net als bij dubbele woordvierkanten kun bij een kubus de doorgestoken woorden ook uniek maken, dit maakt dat alle woordvierkanten nu ook andere woorden kunnen bevatten. Deze kubus bevat dus 26 woorden:

p a a l   a l m a   s t e n   s o n g
a c r e   l o o m   t o t o   o l i e
a r t s   m o r a   e t e r   n i k s
l e s t   a m a i   n o r m   g e s p
Als we van 2 naar 3 dimensies kunnen, dan kunnen we ook naar 4. Dit is een woordvierkant waarbij elke letter een heel woordvierkant is, je hebt dus dezelfde woordvierkanten horizontaal en verticaal. Je kan net zoals hiervoor, bij de kubussen, dezelfde letters uit een horizontale of verticale rij vierkanten nemen en weer een woord vinden:
g a a f   a r m e   a m b t   f e t a
a r m e   r o o m   m o o i   e m i r
a m b t   m o o i   b o d e   t i e t
f e t a   e m i r   t i e t   a r t s
                                     
a r m e   r o o m   m o o i   e m i r
r o o m   o u z o   o z o n   m o n o
m o o i   o z o n   o o r d   i n d o
e m i r   m o n o   i n d o   r o o i
                                     
a m b t   m o o i   b o d e   t i e t
m o o i   o z o n   o o r d   i n d o
b o d e   o o r d   d r i e   e d e l
t i e t   i n d o   e d e l   t o l k
                                     
f e t a   e m i r   t i e t   a r t s
e m i r   m o n o   i n d o   r o o i
t i e t   i n d o   e d e l   t o l k
a r t s   r o o i   t o l k   s i k h

De mogelijkheden zijn eindeloos, ik hoop in een volgende post een poging te doen om woordvierkantgedichten te maken met een daadwerkelijke betekenis maar voor nu hoop ik dat je van deze in elkaar hakende woorden net zo hebt genoten als ik.

Algoritme

Het algoritme dat ik gebruik om al deze vlakken te genereren is net iets anders dan je vaak ziet. Laten we als voorbeeld eerst een vierkant nemen met nog ongevulde letters:

0 1 2
3 4 5
6 7 8

Het algoritme heeft echter geen interesse in de daadwerkelijke vorm. Op die manier kan hetzelfde algoritme zowel vierkanten als driehoeken of zelfs kubussen genereren. Een vormloze definitie van het bovenstaande vierkant maakt expliciet welke cijfers samen valide woorden moeten vormen, dit noem ik de topologie van dit vierkant:

0 1 2
3 4 5
6 7 8
0 3 6
1 4 7
2 5 8

Als we nu bijvoorbeeld een driehoek van deze vorm willen definiëren:

c
a f
k i p
e n i g

We geven eerst als hulp voor onszelf elke onafhankelijke letter een cijfer:

c           0
a f     >   1 2
k i p       3 4 5
e n i g     6 7 8 9

En nu maken we een lijst van alle cijfers die valide woorden moeten zijn, dit is dus de topologie:

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

Het doel van het algoritme is om letter waardes te kiezen voor elk cijfer zodat alle woordpaden in de topologie bestaande woorden zijn. Naïef zijn er 26¹⁰ (141 biljoen) mogelijke manieren om dit te doen voor het bovenstaande voorbeeld. Het is echter handiger om tijdens het plaatsen van de letters te bekijken of er nog valide woorden over zijn en te stoppen als dit niet het geval is. Als we bij letter ‘0’ beginnen kunnen we zien dat dit cijfer bij één woordpad wordt gebruikt (0 1 3 6) dus moet er een vierletter woord zijn wat begint met de letter ‘0’. Alle letters die passen moeten worden geprobeert. Bij elk van deze pogingen kijken we naar de volgende letter met het nummer 1, hierbij hebben we te maken met twee woordpaden(1 2 en 0 1 3 6) waardoor letter ‘1’ dus een letter moet zijn die het begin van een 2-letter kan staan een hij moet de tweede letter kunnen zijn van een 4-letterwoord waarbij de eerste letter ‘0’ is (die we al hadden bepaald). Dit process wordt herhaald todat we hopelijk bij letter ‘9’ aankomen en zo een oplossing hebben.

Deze implementatie is zeer afhankelijk van het snel kunnen bepalen of een woord met bepaalde beginletters bestaat en zo ja welke letters kunnen volgen. Hiervoor is gelukkig een datastructuur, namelijk een trie. Dit is een boomstructuur die er bijvoorbeeld als volgt uitziet:

graph.png

We maken simpelweg een boomstructuur aan voor elk woordpad en houden de positie in de boom bij terwijl we volgende letters bekijken op deze manier hoeven we nooit herhaaldelijk door de boom heen te lopen.

Verder kun je door het zorvuldig definiëren van de topologien ook optimaliseren. Dit zijn de slechts 4 woordpaden en 9 letters voor een 4×4 woordvierkant waarbij de horizontale en verticale woorden identiek zijn:

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

Bij sommige topologiën kunnen er woorden bestaan die letters in een andere dan opwaardse volgorde bevatten in dit geval is het voldoende om dezelfde transformatie die je moet toepassen op dit woordpad om hem in volgorde te krijgen ook toe te passen op het woord alvorens je hem in zijn trie plaatst. Dan werkt de rest van het algoritme identiek.

Verder zijn er nog een aantal technische optimalisaties zoals bijvoorbeeld een bitmask voor alle valide letters in elke node van elke trie waarmee je heel snel overlappende letters kunt vinden.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s