Shakashaka

Przykładowa łamigłówka Shakashaka

Ta sama łamigłówka z rozwiązaniem zaznaczonym kolorem turkusowym

Shakashaka ( シャカシャカ ) to łamigłówka logiczna opracowana przez wydawcę Nikoli .

Zasady

Shakashaka rozgrywana jest na prostokątnej siatce białych i czarnych kwadratów. Niektóre czarne pola mogą zawierać liczbę.

Celem układanki jest umieszczenie trójkątów w niektórych białych komórkach. Istnieją cztery rodzaje trójkątów, które można umieścić w kwadratach:

W powstałej siatce

• Białe części planszy (odkryte czarnymi trójkątami) muszą tworzyć prostokąt lub kwadrat.
• Czarne pola z liczbą muszą przylegać prostopadle do określonej liczby czarnych trójkątów.

Złożoność obliczeniowa

Jest NP-zupełne , aby zdecydować, czy dana łamigłówka Shakashaka ma rozwiązanie. Ponadto liczenie liczby rozwiązań danej łamigłówki Shakashaka jest #P-complete .