Ճապոնական խաչբառ

Ճապոնական գլուխկոտրուկ (ինչպես նաև ճապոնական խաչբառ, ճապոնական նկարչություն, նոնոգրամա), գլուխկոտրուկ, որի ժամանակ, ի տարբերություն սովորական խաչբառի՝ ծածկագրված է ոչ թե բառ, այլ պատկեր։

Նկարագրություն

Պատկերը ծածկագրված է թվերի միջոցով, որոնք տեղակայված են տողերի ձախ կողմում և սյուների վերևում։ Թվերի քանակը ցույց է տալիս, թե քանի խումբ սև (գունավոր խաչբառի դեպքում համապատասխան գույնի) վանդակ կա տվյալ տողում կամ սյան մեջ, իսկ թվերը ցույց են տալիս, թե որքան ներկված վանդակ է պարունակվում այդ խմբերից յուրաքանչյուրում (օրինակ՝ երեք թվից՝ 4, 1, և 3, կազմված խումբը ցույց է տալիս, որ այդ շարքում կա երեք խումբ՝ առաջինում չորս, երկրորդում մեկ, իսկ երրորդում երեք ներկված վանդակով)։ Սև-սպիտակ խաչբառերում խմբերը պետք է միմյանցից բաժանված լինեն առնվազն մեկ դատարկ վանդակով, իսկ գունավոր խաչբառի դեպքում այդ կանոնը վերաբերում է միայն նույն գույների թվերի խմբին, մինչդեռ տարբեր գույներով խմբերը կարող են շարունակել իրար առանց դատարկ վանդակի (դրանք կարող են գտնվել շարքերի ծայրերում)։ Հարկավոր է որոշել ներկվելու ենթակա վանդակների տեղակայությունը։

Չնայած մեծ տարածվածությանը՝ ճապոնական խաչբառերին ներկայացվող պահանջների վերաբերյալ համընդհանուր կարծիք չկա։ Հիմնական կարծիքները վերաբերում են հետևյալ համոզմունքների տարբեր համադրություններին.

Ճիշտ կազմված գլուխկոտրուկը պետք է ունենա միայն մեկ լուծում։
Խաչբառի չափը (լայնությամբ և բարձրությամբ) պետք է լինի 5-ի բազմապատիկ, որպեսզի օգնող ցանցը հնարավոր լինի բաժանել 5х5 չափի բաժինների։
Գունավոր խաչբառում օգտագործվող գույների քանակը պետք է լինի սահմանափակ, իսկ գույները պետք է իրարից հեշտ տարբերակվող լինեն։
Ճապոնական խաչբառի ֆոնային գույնը (խաղադաշտի դատարկ վանդակների գույնը) պետք է լինի սպիտակ։
Խաչբառը պետք է ունենա տրամաբանական ճանապարհով ստացվող լուծում (տարաձայնություն կա այն հարցի շուրջ, թե խաչբառի լուծման մեթոդներից որն է համարվում տրամաբանական, որը՝ ոչ)։
Չի թույլատրվում չներկված (և, համապատասխանաբար, առանց թվերի) տողերի և սյուների առկայությունը։
Չի թույլատրվում այնպիսի տողերի և սյուների առկայությունը, որոնցում «լուծելու ոչինչ չկա»։

Պատմություն

Ճապոնական խաչբառերն ի հայտ են եկել Ճապոնիայում 20-րդ դարի վերջին։ Հեղինակի հավակնորդները երկուսն են։

Նրանցից մեկը ձևավորող և գրաֆիկական խմբագիր Նոն Իսիդան է (ճապ.՝ 石田のん), ով հավաստում է, որ դեռ 1970 թվականին ինքը ստեղծել է նոնոգրամաներ՝ որպես մարդկանց և կենդանիների միջև շփման միջոց։ Նոն Իսիդան հավատում էր, որ կենդանիները բանական էակներ են, սակայն մարդու և կենդանիների միջև հաղորդակցության միջոցների բացակայության պատճառով մարդիկ թերագնահատում են նրանց։ Նրա գիտական աշխատանքի արդյունքում ստեղծվեցին նոնոգրամները (Nonogram-NON + diaGRAM)՝ սև ու սպիտակ քառակուսիներով դաշտեր^[1]։

1987 թվականին Նոն Իսիդան մասնակցեց Window Art ապակիներով նկարչության մրցույթին։ Մասնակիցները պետք է երկնաքերի վրա պատկեր ստանային՝ շինության սենյակների լույսերը միացնելով և անջատելով։ Երեկոյան արդյունքները ամփոփվեցին, և Իսիդայի աշխատանքը զբաղեցրեց առաջին տեղը։ Բամբուկ կտրողի մասին հեքիաթը 8-րդ դարի ճապոնական լեգենդ է, որը դարձավ մեծ հանրությանը հայտնի առաջին նոնոգրաման։

Ոգևորված հաղթանակով՝ 1988 թվականին Նոն Իսիդան Ճապոնիայում հրատարակեց «Window Art Puzzles» անվամբ երեք գլուխկոտրուկ^[2]։

Միևնույն ժամանակ ճապոնացի գլուխկոտրուկների հեղինակ Տեցույա Նիսիոն (ճապ.՝ 西尾徹也) մտածում էր «Նկարչություն թվերով» (անգլ.՝ Paint by Numbers) գլուխկոտրուկներ և հրատարակում այլ հրատարակչությունում։

Սկզբնական փուլում նոնոգրամաները գլուխկոտրուկների սիրահարների շրջանում առանձնակի հետաքրքրություն չէին առաջացնում, քանի որ ոչ ոք չգիտեր դրանց լուծման եղանակը։

Ճապոնական գլուխկոտրուկները մեծ ճանաչում ստացան 1989-1990 թվականներին «The Daily Telegraph» թերթում հրատարակվելուց հետո։ Գլուխկոտրուկների բրիտանացի սիրահար Ջեյմս Դելգետին թերթի ղեկավարությանը համոզում էր ամեն շաբաթ թերթում տպագրել նաև ճապոնական խաչբառեր։ Շուտով նոնոգրամաների կամ գրիդլերների մասին իմացան նաև այլ երկրներում։

Լուծման մեթոդիկա

Ճապոնական խաչբառի լուծման ալգորիթմը ներկայացված է «սրտիկի» օրինակով։ Ավելի հեշտ է սկսել այն շարքերից, որոնք ամբողջությամբ պետք է ներկվեն։ Այս օրինակում այդպիսի շարքերը երեքն են՝ կազմված 9-ական վանդակից։

Այժմ դիտարկենք երկրորդ տողը, որը բաղկացած է 4-ական վանդակով երկու խմբից։ Այս դեպքում երկու խմբերի միջև դատարկ վանդակը գտնվում է 5-րդ շարքում։ Դրանից հետո 1 և 9 շարքերում ներկված է լինում 4-ական վանդակ, ինչը և պահանջվում է։

Այդ շարքի մյուս բոլոր վանդակները միանշանակ չեն ներկվելու։ Դրանք պետք է նշել խաչերով։ Ապա վեցերորդ շարքում պետք է ներկել մնացած 7 վանդակները։ Մեջտեղի սյան մեջ ներկված դարձան պահանջվող 7 վանդակից 4-ը։ Ավարտում ենք նաև այդ խումբը։

1 թվով շարքում ներկված վանդակ արդեն կա, հետևաբար մնացած վանդակները պետք է խաչ անել։ 3 թվով շարքում պարտադիր դատարկ են մնալու երկրորդ և ութերորդ վանդակները, իսկ 2-2 խմբերով տողում ներկվելու են երրորդ և յոթերորդ վանդակները։

Այնուհետև ավարտում ենք 3 և 7 շարքերը, պետք է միացնել 5 թվով շարքի երեք վանդակները, և 3 թվով շարքի մնացած երկու վանդակները։ Մնաց միայն ներկել երկրորդ և ութերորդ սյուների առաջին վանդակները, և նկարը պատրաստ է։

Օրինակ

դատարկ նոնոգրամա
					2	2
		0	9	9	2	2	4	4	0
	0
	4
	6
2	2
2	2
	6
	4
	2
	2
	2
	0

լուծված նոնոգրամա
					2	2
		0	9	9	2	2	4	4	0
	0
	4
	6
2	2
2	2
	6
	4
	2
	2
	2
	0

Համակարգչային լուծում

Ճապոնական խաչբառը NP-ամբողջական առաջադրանք է, գոյություն չունի դրա լուծում պոլինոմիալ ժամանակում, եթե P≠NP^[3]^[4]:

Սակայն եթե որպես ճապոնական խաչբառ դիտարկվեն միայն նրանք, որոնք «ունեն տրամաբանական ճանապարհով ստացվող միայն մեկ լուծում», ապա այդպիսի խաչբառերը չի կարելի դասել NP-ամբողջական առաջադրանքների շարքին, քանի որ խաչբառի լուծման ընթացքում ցանկացած պահի կա տեղեկատվություն, որը հստակորեն ցույց է տալիս, թե որ վանդակները պետք է բացել հաջորդիվ։ Ըստ էության, մարդու կողմից ճապոնական խաչբառի լուծման համար կիրառվող բոլոր մեթոդները (բացառությամբ «փորձ և սխալ» մեթոդի^[5]), հիմնվում են դրա վրա։

1992 թվականին ճապոնական խաչբառը պարզ տեսքով (8×8 քառակուսի) առաջարկվել է ինֆորմատիկայի միջազգային օլիմպիադայի (IOI) մասնակիցներին «կղզիներ ծովում» անվամբ։

Ճապոնական գունավոր խաչբառներ

Գունավոր և սև-սպիտակ խաչբառերի հիմնական տարբերությունն այն է, որ գունավոր խաչբառերում առկա են երկու և ավելի գույնի վանդակներ (ֆոնի գույնն առանձին գույն չի համարվում), ինչն իր հերթին մեկ էական տարբերություն է մտցնում խաչբառի լուծման մեջ. ճապոնական գունավոր խաչբառերում տարբեր գույնի վանդակների խմբերի միջև կարող են նաև սպիտակ վանդակներ չլինել։

Համապատասխանաբար, եթե սև-սպիտակ խաչբառի լուծման ժամանակ թվերի խմբերը պետք է իրարից բաժանվեն առնվազն մեկ չներկված վանդակով, ինչը հաշվի է առնվում հաշվարկների ժամանակ, ապա գունավորի դեպքում այդպես չպետք է անել, քանի որ վանդակների խմբերը կարող են սահուն հաջորդել իրար։

Ավելի բարդ գունավոր խաչբառերում լրացուցիչ պետք է հաշվի առնել նաև հատվող վանդակների գույները։

Մնացած դեպքերում գունավոր խաչբառերի լուծման սկզբունքները նույնն են, ինչ որ սև-սպիտակի դեպքում.

որոշել անպայման ներկվող վանդակների տարածքը,
որոշել ներկված վանդակներ չպարունակող հատվածները։

Սովորաբար գունավոր խաչբառերն ավելի հեշտ են լուծվում, քան սև-սպիտակները։

Ծանոթագրություններ

↑ «Griddler Puzzles and Nonogram Puzzles -Picture Logic Puzzles». puzzlemuseum.com. Վերցված է 2018 թ․ հունվարի 8-ին.
↑ Games Magazine Presents Paint by Numbers. Random House. 1994. ISBN 0-8129-2384-7.
↑ Ueda, Nobuhisa; Nagao, Tadaaki (1996), NP-completeness results for NONOGRAM via Parsimonious Reductions, vol. TR96-0008, Technical Report, Department of Computer Science, Tokyo Institute of Technology, CiteSeerX 10.1.1.57.5277{{citation}}: CS1 սպաս․ location missing publisher (link)
↑ van Rijn, Jan N. (2012), Playing Games: The complexity of Klondike, Mahjong, Nonograms and Animal Chess (PDF), master's thesis, Leiden Institute of Advanced Computer Science, Leiden University, Վերցված է 2012-06-29-ին.
↑ «Փորձ և սխալ» մեթոդը նախատեսված է այն խաչբառների համար, որոնք չեն պատկանում «տրամաբանական ճանապարհով ստացվող միայն մեկ լուծում» ունեցողների դասին, և, համապատասխանաբար, կարող են չպարունակել տեղեկատվություն, որը միանշանակ ցույց կտա հաջորդ քայլին բացվող վանդակները

Տես նաև

Արտաքին հղումներ

Pattern, Նոնոգրամա Սայմոն Թաթհամի հավաքածուից
Nonograms (Brain teasers) Արխիվացված 2017-10-03 Wayback Machine, Նոնոգրամաներ DMOZ կայքում
Nonograms (Video games)(չաշխատող հղում), Նոնոգրամաներ DMOZ կայքում

[1] «Griddler Puzzles and Nonogram Puzzles -Picture Logic Puzzles». puzzlemuseum.com. Վերցված է 2018 թ․ հունվարի 8-ին.

[2] Games Magazine Presents Paint by Numbers. Random House. 1994. ISBN 0-8129-2384-7.

[3] Ueda, Nobuhisa; Nagao, Tadaaki (1996), NP-completeness results for NONOGRAM via Parsimonious Reductions, vol. TR96-0008, Technical Report, Department of Computer Science, Tokyo Institute of Technology, CiteSeerX 10.1.1.57.5277{{citation}}: CS1 սպաս․ location missing publisher (link)

[4] van Rijn, Jan N. (2012), Playing Games: The complexity of Klondike, Mahjong, Nonograms and Animal Chess (PDF), master's thesis, Leiden Institute of Advanced Computer Science, Leiden University, Վերցված է 2012-06-29-ին.

[5] «Փորձ և սխալ» մեթոդը նախատեսված է այն խաչբառների համար, որոնք չեն պատկանում «տրամաբանական ճանապարհով ստացվող միայն մեկ լուծում» ունեցողների դասին, և, համապատասխանաբար, կարող են չպարունակել տեղեկատվություն, որը միանշանակ ցույց կտա հաջորդ քայլին բացվող վանդակները

[1]

[2]

[3]

[4]

[5]