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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Ճապոնական խաչբառ «ֆուտբոլ» լուծման գործընթացի անիմացիայով

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

Նկարագրություն[խմբագրել | խմբագրել կոդը]

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

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

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

Պատմություն[խմբագրել | խմբագրել կոդը]

Ճապոնական խաչբառերն ի հայտ են եկել Ճապոնիայում 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) մասնակիցներին «կղզիներ ծովում» անվամբ:

Ճապոնական գունավոր խաչբառներ[խմբագրել | խմբագրել կոդը]

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

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

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

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

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

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

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

  1. «Griddler Puzzles and Nonogram Puzzles -Picture Logic Puzzles»։ puzzlemuseum.com։ Վերցված է 2018-01-08 
  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, TR96-0008, Technical Report, Department of Computer Science, Tokyo Institute of Technology 
  4. van Rijn, Jan N. (2012), Playing Games: The complexity of Klondike, Mahjong, Nonograms and Animal Chess, master's thesis, Leiden Institute of Advanced Computer Science, Leiden University, http://www.liacs.nl/assets/2012-01JanvanRijn.pdf, վերցված է 2012-06-29 .
  5. «Փորձ և սխալ» մեթոդը նախատեսված է այն խաչբառների համար, որոնք չեն պատկանում «տրամաբանական ճանապարհով ստացվող միայն մեկ լուծում» ունեցողների դասին, և, համապատասխանաբար, կարող են չպարունակել տեղեկատվություն, որը միանշանակ ցույց կտա հաջորդ քայլին բացվող վանդակները

Տես նաև[խմբագրել | խմբագրել կոդը]

Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]