Kol (o'yin) - Col (game)

Kol a qalam va qog'oz o'yini, xususan, a xaritalarni bo'yash o'yini, qoidalarga muvofiq chiziq chizig'ida maydonlarni soyalashni o'z ichiga oladi Grafikni bo'yash. Har bir harakat bilan grafik qolishi kerak to'g'ri (bir xil rangdagi ikkita maydon tegishi mumkin emas) va qonuniy harakatni amalga oshira olmaydigan o'yinchi yutqazadi. O'yin tavsiflangan va tahlil qilingan Jon Konvey, kim buni unga bog'ladi Kolin Vout, yilda Raqamlar va o'yinlar to'g'risida.[1]

O'yin namunasi

Keyingi o'yinda ikkala o'yinchining birinchisi foydalanmoqda qizil, ikkinchisi esa foydalanmoqda ko'k. Har bir rasmdagi so'nggi harakat boshqa joylarga qaraganda yorqinroq ko'rsatilgan.

Boshlang'ich grafik:
ColAndSnortGraph blank.png

Birinchi o'yinchi boshlash uchun har qanday maydonni rangga solishi mumkin. Biroq, grafika tashqarisidagi mintaqa ushbu o'yin uchun maydon sifatida kiritilmagan.

Birinchi harakatdan keyin:
ColAndSnortGraph C1.png

Endi ikkinchi o'yinchi oq katakchani ranglaydi. Hozirda biron bir joy ko'k rangga ega bo'lmaganligi sababli, har qanday oq hujayraga ruxsat beriladi.

Ikki harakat:
ColAndSnortGraph C2.png

Shu nuqtada, grafikaning to'g'ri bo'lishi talabi kuchga kiradi, chunki qizil maydon mavjud maydonga tegmaydigan qilib qo'yilishi kerak:

Uchinchi mintaqa ranglangandan so'ng:
ColAndSnortGraph C3.png

Shuni esda tutingki, maydonlar faqat vertikallarni baham ko'rsalar emas, balki qirralarni ulashgan taqdirdagina tegishga to'g'ri keladi, shuning uchun bu harakat qonuniydir.

O'yin davom etmoqda, o'yinchilar navbatma-navbat harakat qilmoqdalar, bitta o'yinchi harakat qilolmaguncha. Ushbu o'yinchi yutqazadi. O'yinning mumkin bo'lgan davomi quyidagicha (har bir harakat aniqligi uchun raqamlangan):

O'yin tamom:
ColAndSnortGraph C end.png

Ushbu natijada ko'k futbolchi yutqazdi.

Snort

Snort, tomonidan ixtiro qilingan Simon P. Norton, ikkita rangning o'xshash partizan topshirig'idan foydalanadi, ammo antiklassik cheklov bilan: qo'shni viloyatlarga turli xil ranglarni berishga yo'l qo'yilmaydi. Hududlarni bo'yash buqalar va sigirlarga dalalarni berish bilan izohlanadi, bu erda qo'shni dalalarda qarama-qarshi jinsdagi mollar bo'lmasligi mumkin, shunda ular yaylovdan chalg'itmasliklari uchun.

Snortda natijani hal qilish PSPACE tugallandi umumiy grafikalar bo'yicha.[2] Bu kamaytirish orqali isbotlangan partizan tuguni Kayles Snort o'yiniga PSPACE bilan yakunlangan.

Tahlil

Col pozitsiyasining qiymati har doim ham raqam yoki plyusga teng Yulduz[3] Bu Snort bilan solishtirganda o'yinni nisbatan sodda qiladi, bu juda ko'p turli xil qadriyatlarga ega.

Adabiyotlar

  • Berlekamp, ​​Elvin R.; John H. Conway; Richard K. Guy (1982). Matematik o'yinlaringiz uchun yutuqlar. Akademik matbuot. ISBN  978-0-12-091101-1. Qayta ko'rib chiqilgan va qayta nashr etilgan
  •  ———  (2004) [2001]. Matematik o'yinlaringiz uchun yutuqlar (2-nashr). A K Peters Ltd. ISBN  978-1-56881-130-7.CS1 maint: qo'shimcha tinish belgilari (havola) CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)
  • Konvey, Jon Xorton (1976). Raqamlar va o'yinlarda. Akademik matbuot. ISBN  978-0-12-186350-0. Qayta ko'rib chiqilgan va qayta nashr etilgan
  •  ———  (2000). Raqamlar va o'yinlarda. A K Peters Ltd. ISBN  978-1-56881-127-7.CS1 maint: qo'shimcha tinish belgilari (havola) CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)
  1. ^ Raqamlar va o'yinlar to'g'risida: 1
  2. ^ Demeyn, Erik; Xearn, Robert (2001). "Algoritmlar bilan o'yinlarni o'ynash: algoritmik kombinatoriya o'yinlari nazariyasi". arXiv:cs / 0106019v2.
  3. ^ G'oliblik usullari: 2

Tashqi havolalar

  • [1] Google Play-da Col va Snort o'yinlari