Heyawake

Heyawake (Japans : へやわけ, verdeelde kamers) is een logische puzzel die in 1992 gepubliceerd werd in Puzzle Communication Nikolidoor van uitgeverij Nikoli. Vanaf 2013 werden vijf boeken die volledig uit Heyawake puzzels bestaan.

Spelregels

Heyawake wordt gespeeld op een rechthoekig diagram van vakjes zonder standaardgrootte; het diagram is verdeeld in rechthoekige 'kamers' van verschillende grootte waarbij dikke lijnen de randen van de vakjes volgen. Sommige kamers kunnen een enkel nummer bevatten, meestal afgedrukt in het vakje linksboven; Bij het oorspronkelijke ontwerp waren alle kamers genummerd, maar omdat dit zelden nodig is om de puzzel op te lossen wordt dit niet meer gedaan.

Sommige vakjes in de puzzel moeten zwart worden gemaakt; het doel van de puzzel is om voor elke vakje te bepalen of dit moet worden gekleurd of leeg moet blijven (wit blijft). In de praktijk is het vaak gemakkelijker om bekende 'lege' vakjes op de een of andere manier te markeren, bijvoorbeeld door een stip in het midden van het vakje te plaatsen.

De volgende regels bepalen om welke vakjes het gaat:

• Regel 1: Gekleurde vakjes mogen nooit orthogonaal met elkaar verbonden zijn (ze mogen geen zijde delen, hoewel ze elkaars diagonaal kunnen raken).
• Regel 2: Alle witte vakjes moeten met elkaar verbonden zijn (vormen een enkele polyomino).
• Regel 3: Een getal geeft precies aan hoeveel gekleurde vakjes er in die betreffende kamer moeten zijn.
• Regel 4: Een kamer zonder nummer mag een willekeurig aantal gekleurde vakjes bevatten, of geen.
• Regel 5: Waar een rechte (orthogonale) lijn van verbonden witte vakjes wordt gevormd, mag deze niet vakjes bevatten van meer dan twee kamers - met andere woorden, elke dergelijke lijn van witte vakjes die drie of meer kamers verbindt, is verboden.

Oplossingsmethoden

Merk op dat de eerste twee regels ook van toepassing zijn op (bijvoorbeeld) Hitori-puzzels, en daarom delen deze puzzels enkele van hun oplossingsmethoden:

• Als wordt ontdekt dat een vakje is gekleurd, is meteen bekend dat alle vier (orthogonaal) aangrenzende vakjes wit moeten zijn (van regel 1).
• Een deel van (orthogonaal) aaneengesloten witte vakjes kan niet worden afgesneden van de rest van het raster (van Regel 2). Zwarte vakjes mogen geen diagonale splitsing over het raster vormen, noch een gesloten lus; elk vakje dat zo'n 'kortsluiting' zou veroorzaken, moet in plaats daarvan wit zijn.

Meer complexe puzzels vereisen het combineren van Regel 1 en Regel 2 om vooruitgang te boeken zonder te raden; de sleutel is om te herkennen waar de vakjes een van de twee geruite patronen moeten aannemen en één tot een kortsluiting leidt.

De overige regels onderscheiden Heyawake van andere 'dynastie'-puzzels:

• Regel 5 is de bepalende regel van de puzzel; zwarte vakjes moeten worden geplaatst om te voorkomen dat (orthogonale) lijnen van witte vakjes twee kamergrenzen overschrijden ('spanners').
• Genummerde kamers bieden puzzelaars doorgaans een startplaats, naast andere mogelijkheden. Hieronder volgen de eenvoudigste voorbeelden van kamers die aan het begin zijn gedefinieerd:
  • Een 2×2-kamer in de hoek van het raster met een '2' moet één gekleurd vakje in de rasterhoek hebben en het tweede gekleurde vierkant diagonaal naar buiten vanaf de hoek. Aangezien gekleurde vierkanten geen zijde mogen delen (Regel 1), zou het enige alternatief de geforceerde witte cel in de hoek loskoppelen, in strijd met Regel 2.
  • Een kamer van 2×3 waarvan de zijde met 3 vakjes langs een diagramrand met daarin een '3' moet een gekleurd vakje hebben in het midden van de zijde met 3 vakjes langs de rand en de andere twee in de tegenovergestelde hoeken van de kamer, om soortgelijke redenen als hierboven.
  • In een 1×3-kamer met een '2' moeten de twee eindvakjes gekleurd zijn, omdat een gekleurd middelste vakje een overtreding van regel 1 zou opleveren. Meer in het algemeen moeten in een 1×(2 n −1) kamer met een n alle andere vakje erin gekleurd zijn.
  • Een kamer van 3×3 met daarin een '5' moet een ruitpatroon hebben, met gekleurde vakjes in alle hoeken en in het midden.

Varianten

• Heyawacky wordt gespeeld als Heyawake, maar kamers zijn niet per se rechthoekig. Orthogonale lijnen van witte vakjes mogen een kamer niet verlaten en weer binnenkomen; dat wil zeggen dat dergelijke lijnen niet meer dan één gebiedsgrens mogen overschrijden.
• Symmetry Heyawake wordt gespeeld als Heyawake, maar aanwijzingen geven aan of het patroon van zwarte vakjes in een kamer wel/niet rotatiesymmetrisch rond het midden is.

Computationele complexiteit

Zoals ook gebeurde bij veel vergelijkbare puzzels, is de computationele complexiteit van Heyawake geanalyseerd: bepalen of een gegeven puzzel een oplossing heeft is NP-volledig. Dit betekent dat er geen efficiënt algoritme bestaat dat het probleem oplost (tenzij P = NP), maar wel een efficiënt algoritme dat bepaalt of een gegeven oplossing correct is.