Нурикабе
Нурикабе (хирагана: ぬりかべ) логичка је слагалица названа по Нурикабеу, духу који потиче из јапанске културе, који се манифестује ноћу као невидљиви зид испред путника, спречавајући га да настави свој пут. Игра је изумета и названа од стране јапанске компаније Николи.
Правила[уреди | уреди извор]
Слагалица је у облику правоугоне табле испуњена пољима. На почетку игре поља која нису попуњена бројевима су празна и могуће је попунити их белом или црном бојом. Некада су на почетку игре, празна поља попуњена белом, па се попуњавају црним тачкама, у замену за белу боју, и црном бојом. Два исто обојена поља се сматрају повезаним ако су суседна вертикално или хоризонтално, али не и дијагонално. Бела повезана поља се називају зидом, док се црна повезана поља називају током.
Циљ слагалице је обојити свако поље белом или црном бојом, тако да бојење подлеже следећим правилима:
- Број у пољу представља број поља колико један зид треба да обухвата.
- Сваки зид мора садржати тачно једно поље попуњено бројем
- У целој табли, мора да постоји тачно један ток који не сме да формира "базене", нпр. област од 2x2 поља.
Као и код осталих логичких слагалица, циљ је доћи до јединственог решења.
Методе решавања[уреди | уреди извор]
Нурикабе слагалицу не би требало решавати нагађањем. Поштујући правила, могуће је развити сопствену тактику за долазак до решења.
Највећа почетничка грешка у решавању слагалице је концентрисати се искључиво на одређивање белих или црних поља; већина слагалица захтева понављање корака у решавању. Бојење поља само белом бојом може да проузрокује да друга поља буду морала да буду обојена црном бојом, што ће некада довести до изолације црних поља, што крши постављена правила, и обрнуто.
Основна стратегија[уреди | уреди извор]
- Како два зида смеју да се додирују само на угловима, поља између два недовршена зида (поље са бројем и суседна бела поља која не дају још увек потпуни зид) морају бити попуњена црном бојом. Обично се овако започиње игра, бојењем поља која спајају поља са бројевима у црно.
- Кад је зид довршен—тј. кад је спојен одговарајући број белих поља—сва поља која су око зида морају бити обојена црно. Очигледно је да су поља са бројем '1' окружена црним пољима јер сама чине зид од једног поља.
- Кад год се формира област у облику слова L од црних поља, четврто поље које би чинило квадрат мора бити обојено белом бојом, у супротном се ствара базен.
- На крају сва црна поља морају бити повезана. Ако постоји црна област са само једним могућим начином повезивања са остатком црних области, тај пут мора бити такође црн.
- На крају сва бела поља морају бити део тачно једног зида. Ако постоји бела област која не садржи број са само једним могућим начином повезивања до свог одговарајућег броја, тај пут мора бити такође бео.
- У неким случајевима, постојаће поља до којих не може доћи ниједан број због своје удаљености. Таква поља морају бити обојена црно. Таква поља ће или представљати поље које спаја две црне области, или ће формирати област у облику слова L, где ће бело поље у тој L области моћи стићи само до једног броја.
Напредне стратегије[уреди | уреди извор]
- Ако постоји квадрат који садржи два црна поља и два непозната поља, бар једно од та два непозната мора бити бело. Стога, ако једно од та два непозната поља (назовимо га 'А') једино може бити повезано са пољем са бројем путем који би се оформио од другог непознатог поља (назовимо га 'Б'), онда Б мора бити беле боје, док А може а и не мора.
- Ако је зид величине N већ изграђен од N-1 белог поља и преостала су само два поља за изабрати за изградњу зида, и та два поља се додирују на ћошковима, онда поље које је даље од поља са бројем мора бити црно.
- Ако поље мора да буде бело, и тачно два зида могу да се повежу до њега, и након тог повезивања зидови буду комплетни, онда ако се та два зида вежу под углом од 90 степени, поље које чини тај угао мора бити црно да би се избегло повезивање два зида.
- Непозната поља суседна равној колони (или равном реду) црних поља могу бити тестирана да ли имају потенцијал да буду црна поља. Ако јесу црна, формираће L област, и постојаће два суседна бела поља до којих је могуће доћи од зида. Уколико до тог поља не може да се дође услед ограничења, то значи да поље које се тестира мора бити бело.
Референце[уреди | уреди извор]
- Brandon McPhail, James D. Fix. Nurikabe is NP-Complete NW Conference of the CSCC, 2004. Also presented at Reed Mathematics Colloquium, 2004.
- Markus Holzer, Andreas Klein and Martin Kutrib. On The NP-Completeness of The NURIKABE Pencil Puzzle and Variants Thereof. Proceedings of the 3rd International Conference on Fun with Algorithms Архивирано на сајту Wayback Machine (3. јануар 2015), 2004.
