Peg solitaire - Peg solitaire - Wikipedia

Soubise Prensesi solitaire oynamak, 1697

Peg solitaire (veya Solo Noble) bir masa oyunu delikli bir tahta üzerindeki mandalların hareketini içeren bir oyuncu için. Bazı setler girintili bir tahtada mermerler kullanır. Oyun kısaca şu şekilde bilinir: Solitaire içinde Birleşik Krallık kart oyunlarının adı nerede Sabır. Aynı zamanda Brainvita (esas olarak Hindistan, setlerin ticari olarak bu isim altında satıldığı yerlerde).

Oyunun ilk kanıtı mahkemeye kadar izlenebilir. Louis XIV ve 1697 tarihli özel tarih, on yıl sonra Claude Auguste Berey tarafından Anne de Rohan-Chabot, Soubise Prensesi, yanında bulmacayla. Fransız edebiyat dergisinin Ağustos 1687 sayısı Mercure galant yönetim kurulu, kurallar ve örnek problemlerin bir tanımını içerir. Bu, oyuna basılı olarak bilinen ilk referanstır.

Standart oyun, merkezi delik haricinde tüm tahtayı mandallarla doldurur. Amaç, geçerli hamleler yapmak, merkezi delikteki tek bir mandal dışında tüm tahtayı boşaltmaktır.

Yazı tahtası

İngilizce solitaire kurulu
Avrupa peg solitaire kurulu

İki geleneksel kart vardır ("." Bir başlangıç ​​peg olarak, "o" bir başlangıç ​​deliği olarak):

ingilizceAvrupalı
     · · ·     · · · · · · · · · ·  · · · Ö · · ·  · · · · · · ·      · · ·     · · ·
     · · ·   · · · · · · · · · · · ·  · · · Ö · · ·  · · · · · · ·    · · · · ·     · · ·

Oyna

Peg solitaire oynamak
Üçgen mandal solitaire oynayan bir adam Kraker Varil restoran.

Geçerli bir hareket, bir çivi atlamaktır ortogonal olarak İki konum uzaktaki bir deliğe bitişik bir dübelin üzerinden geçirin ve ardından atlanan dübeli çıkarın.

Aşağıdaki diyagramlarda, · bir delikteki bir pimi gösterir, * kalınlaştırılmış, hareket ettirilecek pimi gösterir ve Ö boş bir deliği gösterir. Bir mavi ¤ mevcut sabitleyicinin hareket ettiği deliktir; kırmızı * bu çivinin son konumu, kırmızı Ö atlanan ve kaldırılan dübelin deliğidir.

Bu nedenle, dört dik yönün her birinde geçerli hareketler şunlardır:

* · O → ¤ Ö *  Sağa atla
Ö · *  →  * Ö ¤  Sola atla
*     ¤·  →  Ö  Aşağı atlamakÖ *
Ö *·  →  Ö  Zıpla*     ¤

Bir İngiliz tahtasında ilk üç hareket şöyle olabilir:

    · · ·             · · ·             · · ·             · · ·     · * ·             · ¤ ·             · Ö ·             · * · · · · · · · ·     · · · Ö · · ·     · ¤ Ö * · · · · O o Ö · · ·· · · Ö · · ·     · · · * · · ·     · · · · · · ·     · · · ¤ · · ·· · · · · · ·     · · · · · · ·     · · · · · · ·     · · · · · · ·    · · ·             · · ·             · · ·             · · ·    · · ·             · · ·             · · ·             · · ·

Strateji

Standart problemin birçok farklı çözümü vardır ve bunları tanımlamak için kullanılan bir gösterim, deliklere harf atar:

   İngilizce Avrupa a b c a b c d e f y d e f zg h i j k l m g h i j k l mn o p x P O N n o p x P O NM L K J I H G M L K J I H G F E D Z F E D Y C B A C B A

Bu ayna görüntüsü notasyonu, diğer nedenlerin yanı sıra kullanılır, çünkü Avrupa tahtasında, bir dizi alternatif oyun, bir konumda bir delikle başlamak ve aynalı konumunda tek bir çivi ile sona ermektir. İngiliz tahtasında eşdeğer alternatif oyunlar bir delikle başlayıp aynı pozisyonda bir çivi ile bitmektir.

Yalnızca ortogonal hareketlere izin veriliyorsa, ilk deliğin merkezi olarak konumlandırıldığı Avrupa panosu için bir çözüm yoktur. Bu, aşağıdaki gibi kolayca görülebilir. Hans Zantema. Yönetim kurulunun pozisyonlarını aşağıdaki şekilde A, B ve C pozisyonlarına ayırın:

    A B C A B C A BA B C A B C AB C A B C A BC A B C A B C B C A B C A B C

Başlangıçta sadece merkezi konum serbestken, kapsanan A konumlarının sayısı 12, kapsanan B konumlarının sayısı 12 ve ayrıca kapsanan C konumlarının sayısı 12'dir. Her hareketten sonra kapsanan A konumlarının sayısı artar veya azalır. kapsanan B pozisyonlarının sayısı ve kapsanan C pozisyonlarının sayısı için aynıdır. Bu nedenle, çift sayıda hamleden sonra tüm bu üç sayı çifttir ve tek bir hamle sayısından sonra bu üç sayı da tekdir. Bu nedenle, bu sayılardan birinin bir (sabitleyicinin konumu, biri tek), diğer iki sayı sıfır, dolayısıyla çift olması gerektiğinden, yalnızca bir sabitleyici ile son konuma ulaşılamaz.

Bununla birlikte, tek bir ilk deliğin tek bir pime indirgenebileceği birkaç başka konfigürasyon vardır.

Kullanılabilecek bir taktik, tahtayı üçlü paketlere bölmek ve bunları fazladan bir peg, yani katalizör kullanarak tamamen temizlemek (çıkarmaktır). dışarı atlar ve daha sonra tekrar geri atlar. Aşağıdaki örnekte, * katalizör:

* · Ö ¤ Ö *      Ö * ·      * Ö ¤  ·     →    ·    →     Ö     → o · · ¤          Ö

Bu teknik, 3'lü bir çizgi, 2 · 3'lük bir blok ve 3'lü bir tabanı ve 4'ü 4 dik olan 6'lı bir L şekli ile kullanılabilir.

Diğer alternatif oyunlar arasında iki boş delikle başlamak ve bu deliklerde iki mandalla bitirmek yer alır. Ayrıca bir delikten başlayarak İşte ve bir peg ile biten Orada. Bir İngiliz tahtasında, delik herhangi bir yerde olabilir ve son çivi yalnızca üçün katlarının izin verdiği yerde sona erebilir. Böylece bir delik a sadece tek bir mandal bırakabilir a, p, Ö veya C.

Peg solitaire ile ilgili çalışmalar

Oyunun kapsamlı bir analizi bilinmektedir.[1] Bu analiz, pagoda işlevi verili, genelleştirilmiş, peg solitaire, problemin uygulanabilirliğini göstermek için güçlü bir araçtır.

Belirli bir problemin uygulanabilirliğini gösteren bir pagoda fonksiyonu bulmak için bir çözüm, doğrusal bir programlama problemi olarak formüle edilir ve polinom zamanda çözülebilir.[2]

1990'da bir makale, peg solitaire problemlerine eşdeğer olan genelleştirilmiş Hi-Q problemlerini ele almış ve NP-tamlık.[3]

1996 tarihli bir makale, bir peg solitaire problemini bir kombinatoryal optimizasyon problemi olarak formüle etti ve 'solitaire cone' olarak adlandırılan uygulanabilir bölgenin özelliklerini tartıştı.[4]

1999'da peg solitaire, tüm olası varyantlarda kapsamlı bir arama kullanılarak bir bilgisayarda tamamen çözüldü. Simetriler, tahta takımyıldızlarının verimli depolanması ve hashing kullanılarak elde edildi.[5]

2001 yılında peg solitaire problemlerini çözmek için etkili bir yöntem geliştirildi.[2]

İngiliz tahtasında oyunun genelleştirilmiş bir versiyonu üzerine 1989'dan yayınlanmamış bir çalışma, genelleştirilmiş oyundaki olası her sorunun 29 İngiliz panosu 9 farklı 3x3 alt kare içerdiğinden, simetriler hariç olası farklı çözümler. Bu analizin bir sonucu, olası "ters pozisyon" problemlerinin boyutuna daha düşük bir sınır koymaktır, burada başlangıçta işgal edilen hücreler boş bırakılır ve bunun tersi de geçerlidir. Böyle bir soruna yönelik herhangi bir çözüm, sorunun tam ayrıntılarına bakılmaksızın en az 11 hareket içermelidir.

Kullanılarak kanıtlanabilir soyut cebir oyunun bir peg ile başarılı bir şekilde bitebileceği sadece 5 sabit tahta pozisyonu vardır.[6]

İngilizce oyun için çözümler

Standart İngilizce oyununun en kısa çözümü, birden fazla atlamayı tek hareket olarak sayan 18 hamle içerir:

Bu çözüm 1912'de Ernest Bergholt tarafından bulundu ve 1964'te John Beasley tarafından mümkün olan en kısa çözüm olduğu kanıtlandı.[7]

Bu çözüm ayrıca şurada da görülebilir: Wolstenholme gösterimini de tanıtan bir sayfa, çözümü ezberlemeyi kolaylaştırmak için tasarlanmıştır.

Diğer çözümler aşağıdaki listeyi içerir. Bunlarda kullanılan gösterim

  • Başlangıç ​​deliklerinin listesi
  • Kolon
  • Son hedef sabitleme listesi
  • Eşittir işareti
  • Kaynak peg ve hedef deliği (atlanan mandallar okuyucuya alıştırma olarak bırakılır)
  • , veya / (eğik çizgi, altılı temizleme gibi 'parçaları' ayırmak için kullanılır)
x: x = ex, lj, ck, Pf, DP, GI, JH, mG, GI, ik, gi, LJ, JH, Hl, lj, jh, CK, pF, AC, CK, Mg, gi, ac, ck, kI, dp, pF, FD, DP, Pp, oxx: x = ex, lj, xe / hj, Ki, jh / ai, ca, fd, hj, ai, jh / MK, gM, hL, Fp, MK, pF / CK, DF, AC, JL, CK, LJ / PD, GI, mG, JH, GI, DP / Oxj: j = lj, Ik, jl / hj, Ki, jh / mk, Gm, Hl, fP, mk, Pf / ai, ca, fd, hj, ai, jh / MK, gM, hL, Fp, MK, pF / CK, DF, AC, JL, CK, LJ / Jji: i = ki, Jj, ik / lj, Ik, jl / AI, FD, CA, HJ, AI, JH / mk, Hl, Gm, fP, mk, Pf / ai, ca, fd, hj, ai, jh / gi, Mg, Lh, pd, gi, dp / Kie: e = xe / lj, Ik, jl / ck, ac, df, lj, ck, jl / GI, lH, mG, DP, GI, PD / AI, FD, CA, JH, AI, HJ / pF, MK, gM, JL, MK, Fp / hj, ox, xed: d = fd, xe, df / lj, ck, ac, Pf, ck, jl / DP, KI, PD / GI, lH, mG, DP, GI, PD / CK, DF, AC, LJ, CK, JL / MK, gM, hL, pF, MK, Fp / pdb: b = jb, lj / ck, ac, Pf, ck / DP, GI, mG, JH, GI, PD / LJ, CK, JL / MK, gM, hL, pF, MK, Fp / xo, dp, ox / xe / AI / BJ, JH, Hl, lj, jbb: x = jb, lj / ck, ac, Pf, ck / DP, GI, mG, JH, GI, PD / LJ, CK, JL / MK, gM, hL, pF, MK, Fp / xo, dp, ox / xe / AI / BJ, JH, Hl, lj, exa: a = ca, jb, ac / lj, ck, jl / Ik, pP, KI, lj, Ik, jl / GI, lH, mG, DP, GI, PD / CK, DF, AC, LJ, CK, JL / dp, gi, pd, Mg, Lh, gi / iaa: p = ca, jb, ac / lj, ck, jl / Ik, pP, KI, lj, Ik, jl / GI, lH, mG, DP, GI, PD / CK, DF, AC, LJ, CK, JL / dp, gi, pd, Mg, Lh, gi / dp

Standart İngiliz peg solitaire üzerinde kaba kuvvet saldırısı

Tek bir çivi ile sonuçlanmanın mümkün olduğu tek yer, kenarlardan birinin merkezi veya ortasıdır; son atlamada, her zaman ortada mı yoksa kenarda mı sonlandırılacağını seçme seçeneği olacaktır.

Aşağıda sayı üzerinde bir tablo bulunmaktadır (Pkemikli Bmeşe Polası yönetim kurulu pozisyonları) sonra n zıplar ve aynı piyonun olasılığı başka bir sıçrama yapmak için hareket etti (NÖ Fdaha fazla Jumps).

NOT: Bir kart pozisyonu döndürülebiliyor ve / veya başka bir kart pozisyonuna çevrilebiliyorsa, kart pozisyonları aynı olarak sayılır.

Yalnızca 31 atlama olabileceği için modern bilgisayarlar tüm oyun konumlarını makul bir sürede kolayca inceleyebilir.[8]

Yukarıdaki "PBP" dizisi şu şekilde girilmiştir: A112737 içinde OEIS. Ulaşılabilir pano konumlarının toplam sayısının (dizinin toplamı) 23.475.688 olduğunu, olası pano konumlarının toplam sayısının ise 8.589.934.590 (33bit-1) (2 ^ 33) olduğunu unutmayın. Yani tüm olası kartların yalnızca yaklaşık% 2,2'si pozisyonlara merkez boştan başlayarak ulaşılabilir.

Tüm yönetim kurulu pozisyonlarını oluşturmak da mümkündür. Aşağıdaki sonuçlar, mcrl2 araç seti (dağıtımdaki peg_solitaire örneğine bakın).

Aşağıdaki sonuçlarda tüm yönetim kurulu pozisyonlarını oluşturur Gerçekten mi merkez boştan başlayarak ulaşılır ve orta delikte biter.

Avrupa oyununa çözümler

3 tane başlangıç ​​var uyumlu olmayan çözümleri olan pozisyonlar.[9] Bunlar:

1)

          0 1 2 3 4 5 6 0 o · · 1 · · · · · 2 · · · · · · · · 3 · · · · · · · · 4 · · · · · · · 5 · · · · · 6 · · ·

Olası çözüm: [2: 2-0: 2, 2: 0-2: 2, 1: 4-1: 2, 3: 4-1: 4, 3: 2-3: 4, 2: 3-2: 1, 5: 3-3: 3, 3: 0-3: 2, 5: 1-3: 1, 4: 5-4: 3, 5: 5-5: 3, 0: 4-2: 4, 2: 1-4: 1, 2: 4-4: 4, 5: 2-5: 4, 3: 6-3: 4, 1: 1-1: 3, 2: 6-2: 4, 0: 3-2: 3, 3: 2-5: 2, 3: 4-3: 2, 6: 2-4: 2, 3: 2-5: 2, 4: 0-4: 2, 4: 3- 4: 1, 6: 4-6: 2, 6: 2-4: 2, 4: 1-4: 3, 4: 3-4: 5, 4: 6-4: 4, 5: 4-3: 4, 3: 4-1: 4, 1: 5-1: 3, 2: 3-0: 3, 0: 2-0: 4]

2)

          0 1 2 3 4 5 6 0 · · · 1 · · o · · 2 · · · · · · · 3 · · · · · · · · 4 · · · · · · · 5 · · · · · 6 · · ·

Olası çözüm: [1: 1-1: 3, 3: 2-1: 2, 3: 4-3: 2, 1: 4-3: 4, 5: 3-3: 3, 4: 1-4: 3, 2: 1-4: 1, 2: 6-2: 4, 4: 4-4: 2, 3: 4-1: 4, 3: 2-3: 4, 5: 1-3: 1, 4: 6-2: 6, 3: 0-3: 2, 4: 5-2: 5, 0: 2-2: 2, 2: 6-2: 4, 6: 4-4: 4, 3: 4-5: 4, 2: 3-2: 1, 2: 0-2: 2, 1: 4-3: 4, 5: 5-5: 3, 6: 3-4: 3, 4: 3- 4: 1, 6: 2-4: 2, 3: 2-5: 2, 4: 0-4: 2, 5: 2-3: 2, 3: 2-1: 2, 1: 2-1: 4, 0: 4-2: 4, 3: 4-1: 4, 1: 5-1: 3, 0: 3-2: 3]

ve 3)

          0 1 2 3 4 5 6 0 · · · 1 · · · · · 2 · · · o · · · 3 · · · · · · · · 4 · · · · · · · 5 · · · · 6 · · ·

Olası çözüm: [2: 1-2: 3, 0: 2-2: 2, 4: 1-2: 1, 4: 3-4: 1, 2: 3-4: 3, 1: 4-1: 2, 2: 1-2: 3, 0: 4-0: 2, 4: 4-4: 2, 3: 4-1: 4, 6: 3-4: 3, 1: 1-1: 3, 4: 6-4: 4, 5: 1-3: 1, 2: 6-2: 4, 1: 4-1: 2, 0: 2-2: 2, 3: 6-3: 4, 4: 3-4: 1, 6: 2-4: 2, 2: 3-2: 1, 4: 1-4: 3, 5: 5-5: 3, 2: 0-2: 2, 2: 2- 4: 2, 3: 4-5: 4, 4: 3-4: 1, 3: 0-3: 2, 6: 4-4: 4, 4: 0-4: 2, 3: 2-5: 2, 5: 2-5: 4, 5: 4-3: 4, 3: 4-1: 4, 1: 5-1: 3]

Yönetim kurulu çeşitleri

Peg solitaire, yukarıda verilen ikisi en popüler olmasına rağmen, diğer boyuttaki tahtalarda oynanmıştır. Ayrıca, her 3 yönde de zıplamalara izin verilen üçgen bir tahtada oynanmıştır. Varyant uygun "pariteye" sahip olduğu ve yeterince büyük olduğu sürece, muhtemelen çözülebilir olacaktır.

Peg solitaire oyun tahtası şekilleri:
(1) Fransız (Avrupa) stili, 37 delik, 17. yüzyıl;
(2) J. C. Wiegleb, 1779, Almanya, 45 delik;
(3) George Bell tarafından tanımlandığı gibi asimetrik 3-3-2-2, 20. yüzyıl;
(4) İngiliz stili (standart), 33 delik;
(5) Elmas, 41 delik;
(6) Üçgen, 15 delikli.
Gri = hayatta kalan için delik.

Yaygın bir üçgen varyantın bir tarafında beş mandal vardır. Üç merkezi konumdan birinde bir delik için son pimin ilk boş deliğe ulaştığı bir çözüm mümkün değildir. Boş bir köşe deliği kurulumu on hamlede çözülebilir ve boş bir orta-delik kurulumu dokuz hamlede çözülebilir (Bell 2008):

Video oyunu

26 Haziran 1992'de Game Boy için peg solitaire tabanlı bir video oyunu piyasaya sürüldü. Basitçe "Solitaire" başlıklı oyun Hect tarafından geliştirilmiştir. Kuzey Amerika'da DTMC, oyunu "Lazlos 'Leap" olarak yayınladı.

Referanslar

  1. ^ Berlekamp, ​​E.R.; Conway, J. H.; Guy, R. K. (2001) [1981], Matematik Oyunlarınız için Kazanma Yolları (ciltsiz) | format = gerektirir | url = (Yardım) (2. baskı), A K Peters / CRC Press, ISBN  978-1568811307, OCLC  316054929
  2. ^ a b Kiyomi, M .; Matsui, T. (2001), "Peg Solitaire Problemleri için Tamsayı Programlama Tabanlı Algoritmalar", Proc. 2nd Int. Conf. Bilgisayarlar ve Oyunlar (CG 2000): Peg solitaire problemleri için tamsayı programlama tabanlı algoritmalar, Bilgisayar Bilimleri Ders Notları, 2063, s. 229–240, CiteSeerX  10.1.1.65.6244, doi:10.1007/3-540-45579-5_15, ISBN  978-3-540-43080-3
  3. ^ Uehara, R .; Iwata, S. (1990). "Genelleştirilmiş Hi-Q, NP-tamamlandı". Trans. IEICE. 73: 270–273.
  4. ^ Avis, D.; Deza, A. (2001), "Solitaire konisi ve çoklu mal akışlarıyla ilişkisi üzerine", Matematiksel Programlama, 90 (1): 27–57, doi:10.1007 / PL00011419
  5. ^ Eichler; Jäger; Ludwig (1999), c't 07/1999 Spielverderber, Solitaire mit dem Computer lösen (Almanca'da), 7, s. 218
  6. ^ "Matematik ve brainvita", Matematik Üzerine Notlar, 28 Ağustos 2012, alındı 6 Eylül 2018
  7. ^ Beasley'in kanıtı için bkz. Kazanma yolları, cilt # 4 (ikinci baskı).
  8. ^ "solboard". github. 2020-08-31. Alındı 2020-08-31. Peg solitaire oyununun kaba kuvvet hesaplamasının uygulanması
  9. ^ Brassine, Michel (Aralık 1981), "Découvrez ... le solitaire", Jeux et Stratégie (Fransızcada)

daha fazla okuma

Dış bağlantılar