Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Логикалық жұмбақ Light Up, Nikoli баспасынан жарық көрген.
Logic puzzle
the logic puzzle Light Up, published by Nikoli
Light Up (жапонша: 美術館 bijutsukan, өнер галереясы), сондай-ақ Акари (明かり, жарық) деп те аталады – Nikoli баспасынан шыққан бинарлық анықтау логикалық жұмбақ. 2011 жылға дейін Nikoli толыққандай Light Up жұмбақтарынан тұратын үш кітап шығарды.
Light Up (Japanese: 美術館 bijutsukan, art gallery), also called Akari (明かり, light) is a binary determination logic puzzle published by Nikoli. As of 2011, three books consisting entirely of Light Up puzzles have been published by Nikoli.
Ережелер
"Light Up" ойыны ақ және қара түсті шаршы торда ойналады. Ойыншы ақ шаршыларға шамдарды орналастырады, екі шам бір-біріне бағытталмауы керек, бүкіл тор жарықтанғанша. Шам горизонтальды және вертикальды бағытта жарық сәулелерін жібереді, қара шаршылармен тоқтатылмаса, толық қатар мен бағананы жарықтандырады. Қара шаршыда 0-ден 4-ке дейінгі сан болуы мүмкін, ол оның төрт жағына қанша шам орналастыру керектігін көрсетеді; мысалы, 4 саны бар шаршының әр жағында бір-бірден төрт шаммен қоршалуы керек, ал 0 саны бар шаршының ешбір жағында шам болмауы керек. Сансыз қара шаршының жанында кез келген санында шам болуы мүмкін немесе шам болмауы да мүмкін. Санды шаршыға диагональды түрде іргелес орналасқан шамдар шамдардың жалпы санына есептелмейді.
Light Up is played on a rectangular grid of white and black cells. The player places light bulbs in white cells such that no two bulbs shine on each other, until the entire grid is lit up. A bulb sends rays of light horizontally and vertically, illuminating its entire row and column unless its light is blocked by a black cell. A black cell may have a number on it from 0 to 4, indicating how many bulbs must be placed adjacent to its four sides; for example, a cell with a 4 must have four bulbs around it, one on each side, and a cell with a 0 cannot have a bulb next to any of its sides. An unnumbered black cell may have any number of light bulbs adjacent to it, or none. Bulbs placed diagonally adjacent to a numbered cell do not contribute to the bulb count.
Ерітінді әдістері
Light Up жұмбағын шешудегі әдеттегі бастапқы нүкте – 4 саны бар қара ұяшықты табу немесе бір немесе бірнеше жағынан тосылған кішірек саны бар ұяшықты табу (мысалы, қабырғаға тірелген 3 немесе бұрыштағы 2), осылайша айналасындағы шамдардың жалғыз конфигурациясы болуы мүмкін. Осы қадамнан кейін, басқа нөмірленген ұяшықтардың бір немесе бірнеше жағы жарықтандырылуы мүмкін, олардың айналасындағы шамдардың ықтимал конфигурацияларын тарылтады және кейбір жағдайларда тек бір конфигурацияны ғана мүмкін етеді. Тағы бір жиі қолданылатын тәсіл – әлі жарықтанбаған ұяшықты іздеп, оны жарықтандыру үшін шамды орналастыруға болатын жалғыз ұяшықты анықтау. Егер шамды қайда орналастыру белгісіз болса, 0-дың маңында немесе шамға қайшылық тудыратын жерлерде шамдар бола алмайтын ақ ұяшықтарға нүктелер қоюға болады. Мысалы, 3-ке диагональды түрде іргелес орналасқан шам, оның айналасындағы екі ұяшықты тосып, оның айналасында үш шам болуына мүмкіндік бермейді; сондықтан 3-тің айналасындағы диагональды ұяшықтарда шамдар болмайды және оларға әрқашан нүкте қоюға болады. Сол сияқты, шам жарықтанбаған басқа ұяшықты "қоршап" алатын жерлерге нүктелер қоюға болады, осылайша ережелерді бұзбай оны жарықтандыру мүмкін болмайды. Күрделірек тәсілдер әдетте әртүрлі қысқарулардың комбинацияларына назар аударады. Мысалы, араларында немесе аралық ұяшықтың басқа екі жағында ештеңе жоқ екі 3 саны бір-бірінен бір ұяшық қашықтықта орналасқан болса, олардың арасында шам болуы керек, сондай-ақ оларды байланыстыратын түзу бойындағы екі 3-тің жанындағы екі ұяшықта да шам болуы керек. Әйтпесе, екі шам бір-бірін жарықтандырады. Бұл қорытындыдан, үштіктерді қоршап тұрған қалған төрт ұяшықта екі шам болуы керек. Еске сақтаңыз, төрт орын екі қатарға орналасқандықтан және олардың арасында ештеңе жоқ болғандықтан, әр қатарда бір шам болуы керек, сондықтан сол қатардағы қалған барлық орындарды бос деп белгілеуге болады. Тағы бір жиі кездесетін үлгі – 1 саны 2 санына диагональды түрде іргелес орналасқанда, 2 санының жанындағы орындардың бірі, бірақ 1 санына іргелес емес, бос немесе қабырғамен тосылған. Екі қысқаруға ортақ екі ұяшыққа ең көп дегенде бір шам орналастырылуы мүмкін, сондықтан соңғы шам 2 санының айналасындағы соңғы бос орынға орналасуы керек. Осы ұяшықтарда бір ғана шам бар екені белгілі болғандықтан, 1 санына жақын ұяшықтардың екеуі де бос болуы керек.
A typical starting point in the solution of a Light Up puzzle is to find a black cell with a 4, or a cell with a smaller number that is blocked on one or more sides (for example, a 3 against a wall or a 2 in a corner) and therefore has only one configuration of surrounding bulbs. After this step, other numbered cells may be illuminated on one or more sides, narrowing down the possible bulb configurations around them, and in some cases making only one configuration possible. Another common technique is to look for a cell that is not yet lit, and determine if there is only one possible cell in which a bulb can be placed to light it up. When it is unclear where to place a bulb, one may also place dots in white cells that cannot have bulbs, such as around a 0 or in places where a bulb would create a contradiction. For example, a light bulb placed diagonally adjacent to a 3 will block two of its surrounding cells, making it impossible to have three bulbs around it; therefore, the diagonal cells around a 3 can never have lights in them and can be always dotted. Similarly, one may put dots in places where a bulb would "trap" another unlit cell, making it impossible to light it up without breaking the rules. More advanced techniques tend to focus on different combinations of clues. Two 3s that are one space apart, for example, with nothing between them or to the other two sides of the cell in between, must have a lightbulb in that space, and the two spaces next to the two threes, on the line joining them. If not, then one would have two lightbulbs illuminating each other. Also, from this deduction, the remaining four cells surrounding the threes must contain two lightbulbs. Note that as the four spaces are arranged in two rows with nothing in between, one must have one lightbulb to each row, so one can mark all other spaces in those rows as empty. Another fairly common pattern is a 1 diagonally adjacent to a 2, with one of the spaces next to the 2 but not adjacent to the 1 either empty or walled off. At most one lightbulb can be placed in the two cells common to the two clues, so the last lightbulb must go in the last space around the 2. Now, it is known that there is exactly one lightbulb in those cells, so the other cells next to the 1 must both be empty.
Есептеу күрделілігі
Light Up жұмбағының шешімі бар-жоғын анықтау NP-толық мәселе. Бұл, NP-толық екені белгілі Схемалық SAT мәселесінен Light Up жұмбақтарына полиномиалдық уақытта келу арқылы дәлелденеді. Light Up жұмбағының бастапқы нұсқаларында, сандары жоқ қабырғалармен қатар, бір нақты сан бар қабырғалар (яғни 0, 1, 2, 3 немесе 4) кездеседі, мұндай нұсқаларды біз Акари деп атаймыз, олардың күрделілігі де зерттелді. Схемалық SAT мәселесінен полиномиалдық уақытта келу арқылы Акари 1, Акари 2 және Акари 3 NP-толық екендігі көрсетілді; ал Акари 4 және сандары жоқ жұмбақтар P класына жататыны дәлелденді; Акари 0 әзірге жіктемелген жоқ.
Determining whether a given Light Up puzzle is solvable is NP complete. This is proved by a polynomial time reduction from Circuit SAT, which is known to be NP complete, to Light Up puzzles. Variations on the original Light Up puzzle in which there are walls without numbers plus walls with one certain number, so either 0, 1, 2, 3 or 4 (we call these variations Akari ), have also been researched in complexity. It is shown, by a polynomial time reduction from Circuit SAT, that Akari 1, Akari 2 and Akari 3 are NP complete; for Akari 4 and puzzles without any numbers it is shown that these are in P; Akari 0 is thus far uncategorized.