Gelin kraliçe probleminde hangi yeni şeylerin keşfedildiğini bulalım. Gelin vezir problemindeki yenilikleri bulalım: Satranç tahtasında 8 vezir

Harika bir bulmaca mücadelesi Satranç tahtasında 8 vezir. Bu oyun 1848'de ünlü satranç oyuncusu Basel Maxim tarafından icat edildi. Kişisel gelişimle uğraşmak istiyorsanız ve satrançla başlamayı planlıyorsanız, bu görev harika bir başlangıç ​​olacaktır.

Buradaki fikir, hiçbiri saldırı altında olmayacak şekilde 8 parçayı, daha doğrusu vezirleri yerleştirmektir. Vezir'in herhangi bir yönde ve herhangi bir sayıda kareye hareket edebileceğini hatırlamakta fayda var.

Sorunu çözmek için seçenekler

Bugün 12 çözüm var ama simetri kurallarını uygularsanız 92'ye kadar seçenek var. Bu bulmacanın ilk çözümü iki yıl sonra Franz Nacke tarafından yayınlandı. Ondan sonra çok sayıda bilim adamı ve amatör kendi çözümünü bulmaya çalıştı. 8 vezir satranç tahtasına nasıl yerleştirilir. Örneğin dünyaca ünlü matematikçi ve fizikçi Gauss, taşları satranç tahtasına yerleştirmek için 72 seçenek buldu. Bu seçenek sayısı ilginç bir yaklaşımdan kaynaklanıyordu - bilim adamı tahtayı dönüşümlü olarak 90, ardından 180 ve 270 derece döndürdü. Böylece yeni kombinasyonlar elde ediliyor.

Satranç tahtasına 8 vezir yerleştirin Kolay değil ama herkes hemen en az bir doğru çözümü bulabilir. En ünlü çözümlerden biri parçaların şu şekilde düzenlenmesidir: h5, f1, d8, b4, g7, e3, c6, a2. Gauss'un çözümüne benzer şekilde satranç tahtasını açarsanız üç olası çözüm daha gözlemlenebilir.

Bu bulmacanın çözümünü ararken yaratıcı düşünme pratiği yapabilecek, dikkatinizi ve hafızanızı geliştirebilecek, mantıksal düşünme yeteneğinizi geliştirebileceksiniz. Bu beceriler işinize yarayacak ve gelecekte karşılaşacağınız sorunlara standart algoritmalar kullanmadan önemsiz çözümler bulmanıza yardımcı olacaktır. Bir çözüm bulmada akıl yürütmenin ve karakteristik mantıksal yapıların kullanılması, bu tür bulmacaları çözerek sizin ayırt edici özelliğiniz haline gelebilir.

Bölüm 8. Sekiz Vezir Problemi

Sekiz Vezir Problemi, At Hareketi Problemi gibi, satranç tahtasındaki en ünlü matematik problemlerinden biridir. Şövalye problemi Leonhard Euler tarafından incelendiyse, vezir problemi bir başka büyük matematikçi olan Karl Gauss'un dikkatini çekti.

Sekiz vezir bir satranç tahtasına birbirini tehdit etmeyecek şekilde, yani ikisi aynı dikey, yatay veya çapraz üzerinde olmayacak şekilde kaç farklı şekilde yerleştirilebilir?

Sorunun koşullarını karşılayan şu veya bu kraliçe düzenlemesini bulmak o kadar da zor değil (Şekil 43'te dört çözüm gösterilmektedir). Mevcut düzenlemelerin toplam sayısını hesaplamak çok daha zordur; aslında bu sekiz vezir problemidir. Kalelerde olduğu gibi, birbirlerine saldırmayan sekizden fazla veziri satranç tahtasına yerleştirmenin imkansız olduğu açıktır. Ve buna göre, n×n'lik bir tahtaya n'den fazla veziri gereken şekilde yerleştirmek imkansızdır (genel olarak sorun aşağıda ele alınacaktır).

Pirinç. 43. Satranç tahtasında birbirini tehdit etmeyen sekiz vezir

Pek çok yazarın yanlışlıkla sekiz kraliçe sorununu ve çözümünü Gauss'un kendisine atfetmesi ilginçtir. Aslında bunu ilk kez 1848'de formüle eden Alman satranç oyuncusu M. Bezzel'di. Dr. F. Nauk (doğuştan kör) 60 çözüm buldu ve bunları 1 Haziran 1850 tarihli “Illustrierte Zeitung” gazetesinde yayınladı. Ancak bundan sonra Gauss sorunla ilgilenmeye başladı ve 72 çözüm buldu ve bunları bir mektupta bildirdi. arkadaşı gökbilimci Schumacher, 2 Eylül 1850 tarihli. 92 pozisyondan oluşan kararların tamamı aynı F. Sciences tarafından alındı ​​​​(21 Eylül 1850 tarihli söz konusu gazetede bunlardan alıntı yaptı). Bu kronoloji, kitaplarında ele alınan soruna çok yer ayıran ünlü Alman matematik eğlencesi araştırmacısı W. Arens tarafından oluşturulmuştur.

92 çözümün tüm olasılıkları tükettiğinin kanıtı ancak 1874'te İngiliz matematikçi D. Glasher tarafından (determinant teorisini kullanarak) elde edildi.

Prensip olarak, tahtaya mümkün olan her şekilde sekiz vezir yerleştirerek, sonunda bize uygun tüm düzenlemeleri bulacağız. Ancak bu yol çok uzun ve sıkıcıdır. Kendimizi yalnızca karşılık gelen kale probleminin çözümleri ile sınırlayabilir ve bunların arasından hiçbir kale çiftinin aynı köşegen üzerinde olmadığı çözümleri seçebiliriz. Ancak bu durumda bile arama oldukça büyük (bildiğimiz gibi 40.000'den fazla denemeye ihtiyaç duyulacak). Bu nedenle, bir sorunu "manuel olarak" çözerken (ve geçen yüzyılda yapılan da tam olarak budur), düzenlemelerin zorla numaralandırılması iyi düşünülmelidir. Kraliçelerin istenen düzenine yönelik az çok makul bir arama düzenlemenin bilinen birçok yolu vardır (Permentier, La Noe, Gunter, Glasher, Laquiere vb. yöntemleri). Bu yöntemler eğlenceli matematik üzerine çok sayıda literatürde anlatılmıştır (özellikle geçen yüzyılda ve bu yüzyılın başında). Bilgisayar çağımızda bu tür bir sorun bu kadar ilgi uyandıramazdı. Sonuçta, basit bir bilgisayar programı oluşturmak yeterlidir - ve makineye dahil edildikten birkaç dakika sonra gerekli 92 konumun tamamı yazdırılacaktır.

Vezir probleminin her çözümünden, tahtayı merkezin etrafında saat yönünde 90, 180 ve 270° döndürerek (360°'lik bir dönüş başlangıç ​​pozisyonuna döner) bir dizi başka çözüm elde edilebilir. Vezirlerin bu düzenlemesinden, tahtanın Şekil 2'deki noktalı çizgilerden birine göre yansıtılmasıyla da yeni bir kraliçe elde edilebilir. 43 (1. konum) . Örneğin, bu şekildeki ilk düzenlemeden, tahta 90° döndürüldüğünde üçüncüyü, şah ve vezir kanatlarını ayıran çizgiye göre yansıtıldığında ise dördüncüyü elde ederiz. Diğer döndürme ve yansımaları kullanarak beş çözüm daha elde edilebilir.

Yani, tahta döndürüldüğünde ve yansıtıldığında, vezirlerin bir düzenlemesinden genel olarak konuşursak, yedi yenisi elde edilir. Genel durumda, n×n'lik bir tahta üzerinde (n > 1 için) birbirini tehdit etmeyen n vezirden oluşan herhangi bir düzenleme için yalnızca üç durumun mümkün olduğu kanıtlanmıştır: a) tahtanın bir yansımasıyla yeni bir vezir. düzenleme elde edilir ve rotasyonlar ve diğer yansımalar yeni bir şey vermez; b) tahtanın 90° döndürülmesiyle yeni bir çözüm elde edilir ve yansımalar iki düzenleme daha sağlar; c) Tahtanın üç dönüşü ve dört yansıması, sekiz uyumsuz dizilişe yol açar (orijinal olan dahil).

A) durumunda orijinal çözüme çift simetrik, b) durumunda - simetrik ve c) durumunda - basit denir. Sıradan bir tahta için her çözüm ya basit ya da simetriktir ve çift simetrik çözüm yoktur. Her sınıfın çözümlerinin cebirsel bir yorumu Okunev'de bulunabilir.

Sekiz kraliçeden oluşan bir dizi (küme) temel olarak adlandırılır, eğer ilk olarak tahtanın dönüşleri ve yansımaları sırasında birbirlerine dönüşmezlerse ve ikinci olarak, bu dönüşümler kullanılarak bazı temel düzenlerden başka herhangi bir düzenleme elde edilirse. Sorunun her temel çözüm kümesinin tam olarak 12 konum (sekiz kraliçeden oluşan düzenlemeler) içerdiği bilinmektedir. İşte bu setlerden biri:

1)	a4, b1, c5, d8, e6, f3, g7, h2;
2)	a4, b2, c5, d8, e6, f1, g3, h7;
3)	a4, b2, c7, d3, e6, f8, g1, b5;
4)	a4, b2, c7, d3, e6, f8, g5, h1;
5)	a3, b5, c2, d8, e6, f4, g7, h1;
6)	a3, b7, c2, d8, e5, f1, g4, h6;
7)	a4, b7, c3, d8, e2, f5, g1. h6;
8)	a6, b4, c2, d8, e5, f7, g1. h3;
9)	a4, b8, c1, d5, e7, f2. g6, h3;
10)	a4, b2, c7, d5. e1. f8. g6, h3;
11)	Şekil 1'de 1. konum. 43;
12)	Şekil 2'de 2. konum. 43.

Kalan 80 pozisyon ise bu on ikiden tahtanın dönüşleri ve yansımaları sonucunda elde edilir. İlk 11 düzenleme basittir ve yalnızca sonuncusu simetriktir. Böylece tahtada birbirini tehdit etmeyen sekiz vezirden oluşan toplam 11×8 + 1×4 = 92 diziliş bulunmaktadır.

Ana düzenlemeler göz önüne alındığında, bunların bazı ilginç özelliklerini keşfedebilirsiniz. Örneğin, son düzenlemenin (Şekil 43'te 2. konum) dış simetrisini fark etmek kolaydır. Türünün tek örneği olan bu temel çözüm, aynı zamanda tahtanın yalnızca orta kısmının (4x4 kare) vezirlerden arınmış olmasıyla da karakterize edilir. Bunun bir başka özelliği de vezirlerin a1 - h8 tahtasının ana köşegenini işgal etmemeleridir (ilk ana çözüm de bu özelliğe sahiptir).

Şekil 2'deki ilk düzenleme. 43 ilginç çünkü burada alanların merkezlerinden geçen aynı düz çizgi üzerinde üç vezir durmuyor (bu sadece tahtanın dikeyleri, yatayları ve köşegenleri değil * aynı zamanda diğer eğim açılarına sahip düz çizgiler anlamına da geliyor).

Sorunun herhangi bir çözümü, 1, 2, ..., 8 sayılarının permütasyonu olan bir küme (t 1, t 2, ... t 8) olarak yazılabilir. Burada ti yatay sayının sayısıdır. i'inci dikeyin vezirinin üzerinde durduğu çizgi. İki kraliçe aynı yatay çizgi üzerinde olmadığından, tüm tx'ler farklıdır ve kraliçeler aynı köşegen üzerinde olmadığından herhangi bir i, j (i) için< j ≤ 8) имеем: |t j - t i | ≠ j - i.

Kraliçe yerleşimlerinin sayısal gösterimi bazen çok kullanışlıdır. Örneğin, vezirin a1 üzerinde sabit konumu olan dizilişleri bulmak için, sayısal biçimde yazılmış 92 konumun tamamından, ilk koordinatı 1'e eşit olanları seçmek yeterlidir. Eğer vezirin d3 üzerindeki konumu sabitse , o zaman dördüncü konumun 3 numara olduğu vb. konumları seçmelisiniz.

1, 2, ..., 8 sayılarını önce artan sırayla, sonra azalan şekilde yazalım. Bundan sonra, bu iki permütasyonun her birinin sayısını rastgele bir permütasyonun sayılarıyla toplarız, örneğin (3, 7, 2, 8, 5, 1, 4, 6):

+	1,	2,	3,	4,	5,	6,	7,	8		+	8,	7,	6,	5,	4,	3,	2,	1
	3,	7,	2,	8,	5,	1,	4,	6			3,	7,	2,	8,	5,	1,	4,	6
	4,	9,	5,	12,	10,	7,	11,	14			11,	14,	8,	13,	9,	4,	6,	7

Ortaya çıkan toplamlar iki sayı kümesi oluşturur: (4, 9, 5, 12, 10, 7, 11, 14) ve (11, 14, 8, 13, 9, 4, 6, 7). Bir sonraki sorun ortaya çıkıyor.

1, 2,..., 8 sayılarının hangi permütasyonları, belirtilen toplama işleminin sonucunda her birinde tüm sayıların farklı olduğu iki kümeyle sonuçlanır?

Sekiz kraliçe sorunu Gauss'u tam da bu saf aritmetik problemle bağlantılı olarak ilgilendiriyordu. Vezir probleminin çözümleri ile anlatılan aritmetik probleminin çözümleri arasında bire bir örtüşme olduğu ortaya çıktı. Başka bir deyişle, birbirini tehdit etmeyen sekiz vezirden oluşan her diziliş, bir aritmetik problemine çözüm sağlar - ya da tam tersi. Seçilen permütasyon için her iki küme de farklı sayılardan oluşur ve bu tesadüfi değildir - Şekil 2'deki ilk konuma karşılık gelir. 43.

Tahtanın n kez döndürülmesiyle, vezirlerin işgal ettiği karelerin koordinatları üzerinde basit aritmetik işlemler kullanılarak bazı çözümlerin diğerlerinden elde edildiğini görmek kolaydır. Bu işlemlerin incelenmesi, çözümlerin ek özelliklerini (bazıları Okunev tarafından verilmiştir) keşfetmemizi sağlar.

N vezir problemi. N × n satranç tahtasına n veziri birbirlerini tehdit etmeyecek şekilde yerleştirin.

1x1'lik bir tahtada, tek bir kareye bir vezir yerleştirilir ve bir çözüm bulunur. 2x2'lik bir tahtada, bir vezir nerede durursa dursun, tahtanın tüm karelerini tehdit eder ve ikinci bir vezir yerleştirecek yer yoktur. 3x3'lük bir tahtada üç vezirden oluşan herhangi bir düzenlemede, en az ikisi birbirini tehdit eder. Yani n'nin 2 veya 3'e eşit olması durumunda problemin çözümü yoktur.

n > 3 durumlarına gelince, herhangi bir n×n tahtada n veziri bu şekilde yerleştirmenin mümkün olduğu bilinmektedir. birbirlerini tehdit etmesinler diye. Ciddi matematik yayınlarında yer alan makaleler de dahil olmak üzere pek çok makale, bunun açık bir gerçek olmaktan uzak olduğunu kanıtlamaya adanmıştır.

4x4'lük bir tahtada yalnızca bir temel düzenleme vardır ve bu iki kat simetriktir (a2, b4, c1, d3), yani toplamda iki çözüm vardır. 5x5'lik bir tahtada iki ana diziliş vardır: 1) a2, b4, c1, d3, e5; 2) a2, b5, c3, d1, e4; Toplam on arama konumu vardır. İlginç bir şekilde, bunlardan beşini seçebilirsiniz; bunlar üst üste istiflendiğinde 5x5'lik bir tahtanın tüm karelerini 25 vezirle dolduracaktır. Genel durumda, benzer bir yükleme yalnızca 2 veya 3'e bölünemeyenler için mümkündür. Bundan özellikle, normal bir tahta için vezirlerin doldurduğu sekiz çözümü seçmenin imkansız olduğu sonucu çıkar. tüm tahta.

Sekiz kraliçe probleminin çözümlerinin yukarıdaki cebirsel özelliğini genelleştirerek, n ​​× n'lik bir tahta üzerindeki (t 1, t 2, … t n) n kraliçelerin düzenlemesinin, herhangi bir i, j (i) için istenen düzenleme olduğunu elde ederiz.< j < n): |t j - t i | ≠ j - i. Здесь по-прежнему t i - номер горизонтали, на которой стоит ферзь i-й вертикали, а набор t 1 , …, t n есть перестановка чисел 1, …, п. Таким образом, для решения задачи в общем случае достаточно найти перестановку чисел 1, …, n, удовлетворяющую указанному условию.

Şimdi n > 5 için n × n'lik bir tahta üzerinde n kraliçenin istenen düzenlemesi için olası bir şemayı tanımlayacağız. Sonuçta ortaya çıkan düzenlemede koşulumuzun karşılandığının kanıtı, örneğin Okunev veya Yaglomov'da bulunabilir.

Bir dizi durumu sırasıyla ele alalım. İlk başta n çift olsun, n = 6k veya n = 6k + 4. Tüm vezirlerin yarısını, ikinci yataydan başlayıp her seferinde 2 kare yukarı ve 1 kare yukarı hareket ettirerek atı hareket ettirerek ilk n/2 dikey üzerine yerleştiririz. Sağa. İkinci yarıyı kalan n/2 dikey üzerine aynı şekilde yerleştireceğiz, ancak ilk yataydan başlayarak. 6x6'lık bir tahta için (n = 6k, k = 1) bu, aşağıdaki kraliçe düzenlemesini verir: a2, b4, c6, d1, e3, f5 (n = 10 için Şekil 45'te sunulan çözüm farklı şekilde elde edilir).

n = 6k + 2 olduğunda önceki teknik artık işe yaramaz ve vezirlerin daha "kurnaz" bir şekilde yerleştirilmesi gerekir. Atını ikinci dikeyden hareket ettirerek bunları düzenleyelim.

(n/2 - 2)., üçüncü yataydan başlayarak ve sonra

Altıncı yataydan başlayarak (n - 1)'inci boyunca (n/2 + 3)'üncü dikey. Sonuç olarak, tahtanın altı dikey ve altı yatay noktası serbest kalacak ve altı vezir aşağıdaki koordinatlara sahip kareleri işgal etmelidir: (1, n - 3), (n/2 - 1, 1); (n/2, n - 1), (n/2 + 1, 2), (n/2 + 2, n), (n, 4). n = 14 (n = 6k + 2, k = 2) için Şekil 2'deki düzenlemeyi elde ederiz. 44. Bu arada, 8x8'lik normal bir tahtada (8 = 6k + 2, k = 1) sekiz vezirin bu şekilde yerleştirilmesi, Şekil 2'deki aynı harika çözümle örtüşmektedir. 43 (2. konum), ancak burada vezirlerin dizilişinde bir model fark etmek pek mümkün değil.

Sorunu n'nin tek değerleri için dikkate almak bize kalıyor. Bu durumda çözüm elde etmek için “çift” tahtalar üzerinde önerdiğimiz düzenlemede ana köşegenin (sol alt köşeden sağ üst köşeye doğru giden) serbest kaldığını belirtmek yeterlidir. Bu durum dikkate alındığında, n×n'lik bir tahta üzerinde (tek n için) n vezirlerin istenen düzenlemesi aşağıdaki şekilde elde edilebilir. 1'den (n - 1)'e kadar sayıların bulunduğu bu tahtanın dikey ve yatay kısımlarına, tahtada yapıldığı gibi (n - 1) vezir yerleştireceğiz (n - 1)×(n - 1) (n - 1, hatta!) ve ardından n'inci veziri tahtanın sağ üst köşesine yerleştireceğiz. Açıklanan yöntemi kullanarak, vezirlerin 5×5'lik bir tahta üzerindeki ilk dizilişini, 4×4'lük bir tahtadaki belirtilen düzenlemeden elde edebiliriz ve vezirlerin 6×6'lık bir tahta üzerindeki dizilişinden n = 7 için aşağıdakileri elde ederiz: : a2, b4, c6, d1, e3, f5, g7 .

Pirinç. 44. n vezirle ilgili problem

4 boyutlu bir tahta aramaya başlayalım:

Çöz(createEmptyBoard(4));

Bu diziyi geri alıyorum:

Evet, çözüm bu. Boyutu 2 olan bir kart için çözüm aramaya çalışalım, bu kart için bir çözüm olmadığından fonksiyonun false değeri döndürmesi gerekir:

Çöz(createEmptyBoard(2)); // > yanlış

Evet program olması gerektiği gibi çalışıyor. Şimdi donanımımızın ve algoritmamızın neler yapabileceğini görelim. Küçük bir performans testi oluşturalım:

// Performans testi, // @param (Natural) startSizeOfBoard Başlangıç ​​kart boyutu // @param (Natural) endSizeOfBoard Son kart boyutu // @return (true) Test sona erdi fonksiyon kıyaslaması(startSizeOfBoard, maxSizeOfBoard)( if(startSizeOfBoard>maxSizeOfBoard) ( return true; )else( console.log("Boyutlu bir pano için hesaplayın:", startSizeOfBoard); var startTime = Date.now(); var çözüm = solvent(createEmptyBoard(startSizeOfBoard)); var endTime = Date.now ( ); console.log("Çözüm:", çözüm.toString()); console.log("Alınan süre:", endTime - startTime, "milisaniye");

Bu testin ilk parametresi, ilgilenilen ilk kart boyutunu geçmelidir ve son kart boyutu, ikinci parametreye aktarılmalıdır. Test, boyutları iletilen başlangıç ​​boyutu ile son boyut arasında olan kartlar için bir çözüm arayacaktır. Başlangıç ​​ve bitiş boyutu bu aralığa dahildir. Ayrıca bu aramaya harcadığı süreyi de milisaniye cinsinden sayacak.

MacBook Air'deki (1,8 gigahertz "Intel core i5", 4 gigabayt RAM) 1'den 9'a kadar olan anakartlar için sonuçlarım:

Karşılaştırma(1,9);

Bu tür testler oluşturarak ve verilere dayalı grafikler oluşturarak problem ve algoritma hakkında birçok ilginç şey öğrenebiliriz. Örneğin n=6 boyutlu bir kart için çözüm bulmak neden 442 milisaniye sürerken, n=7 boyutlu bir kart için çözüm bulmak neden sadece 5 milisaniye sürüyor? Bulunan çözümlere bakalım:

Evet, boyutu n=7 olan bir tahtanın çözümü ağacın ilk dalında yatıyor çünkü vezir tam ilk karede duruyor. Ancak boyutu n=6 olan bir tahtayla şanssızdık ve algoritma ağacın daha fazla dalını ortaya çıkarmak zorunda kaldı. Kart boyutu arttıkça algoritmamızdaki arama hızının doğrusal olarak artmayacağı ortaya çıktı, ancak görev tüm olası çözümleri bulmak olsaydı ne olurdu? Bunu düşün.

Bu çözümler ayrıca ilginç bir model daha içeriyor: 6 hücreli bir tahtanın çözümü, sanki 7 hücreli bir tahtanın çözümüne gömülmüş gibi. Yani 7 elemanlı bir tahta için çözümden ilk satırı ve ilk sütunu çıkarırsak 6 elemanlı bir tahta için çözüm elde ederiz. Komik, bunu ancak görselleştirmeyi yaparken fark ettim.

Çözüm

Performans testlerinden de görebileceğimiz gibi algoritmamız dünyanın en hızlısı değil ve parmak şıklatarak cevap almanıza izin vermiyor. Ancak ondan alınamayacak olan şey, ağaçların ve özyinelemenin gücünü mükemmel bir şekilde ortaya koymasıdır.

Ağaçların yardımıyla verilerimizi depolamak için basit ve etkili bir yapı düzenledik ve özyineleme, bunların işlenmesini uygun şekilde organize etmemize yardımcı oldu. Bu çiftte hoşuma giden şey birinin diğerine çok güzel uyum sağlaması. Sanki aynı şeymiş gibi, sadece farklı bir perspektiften sunulmuş gibi.

Sonraki yazılarımızda ağaç aramalarını hızlandırmanın yöntemlerinden bahsedeceğiz.

Birkaç ay önce, vezirleri satranç tahtasına yerleştirme konusundaki klasik problemin bir analiziyle karşıma çıktım (aşağıdaki ayrıntılara ve geçmişe bakın). Sorun inanılmaz derecede iyi biliniyor ve zaten mikroskop altında incelendi, bu nedenle gerçekten yeni bir şeyin ortaya çıkması şaşırtıcıydı.

(burada maksimum kraliçe sayısı vardır ve çarpı yerine beyaz bir tane ve siyah nokta yerine koyabilirsiniz - ancak ikisini birden değil; makaleden alınmıştır)

Modeller ve problem karmaşıklığı

Gerçekten tartışmanın zamanı geldi: Bütün bunlar nasıl çözülebilir ve ne kadar hızlı yapılabilir?

Klasik problem için doğrusal arama

En ilginç nokta, uzmanların bile bazen kafası karışıyor ve N-kraliçeleri çözmenin kombinatoryal bir araştırma gerektirdiğini düşünüyor ve problemin karmaşıklığının P'den daha yüksek olduğunu düşünüyor. Bir keresinde Habré'de P ve NP'nin ne olduğu hakkında yazmıştım: ve . Ancak sorun çözüldü aşırıya kaçmadan seçenekler! Yani, herhangi bir boyuttaki bir tahta için vezirleri her zaman diğer merdivenin arkasına yerleştirebilirsiniz:

Buradan N = 1 ve N > 3 için her zaman bir çözümün olduğu (algoya bakın) ve N = 2 veya N = 3 için her zaman bir çözüm olduğu sonucu çıkar.
her zaman hayır (tahtadan önemsiz bir şekilde takip eder). Bu, N kraliçe için çözülebilirlik probleminin (bir çözümün olup olmadığını söylemeniz gereken) sabit zamanda önemsiz bir şekilde çözüldüğü anlamına gelir (tamam, yapıcı bir şekilde doğrusal zamanda - düzenleyin/kontrol edin).

Okuduğunuzu tekrar kontrol etmenin zamanı geldi, "N kraliçe sorunu NP-tamamlanmış bir sorun olarak kabul edildi" şeklindeki tipik başlığı okuduk - gözleriniz parladı mı?

Pratikte çözüm sayısı nasıl sayılır?

Eğlencenin başladığı yer burasıdır: Vezir yerleştirme sorununun çözüm sayısının kendi adı bile vardır - “dizi A000170”. İyi haberin bittiği yer burası. Sorunun karmaşıklığı: NP ve P#'dan daha yüksek, pratikte bu, en uygun çözümün dizi verilerini bir sözlüğe indirmek ve istenen sayıyı döndürmek olduğu anlamına gelir. N=27 için zaten paralel bir kümede kaç hafta boyunca hesaplanmıştı.

Çözüm: bir işaret yazın ve n'ye n, a(n) değerini döndürün
n a(n)
1: 1
2: 0
3: 0
4: 2
5: 10
6: 4
7: 40
8: 92
9: 352
10: 724
…
21: 314666222712
22: 2691008701644
23: 24233937684440
24: 227514171973736
25: 2207893435808352
26 22317699616364044
27: 234907967154122528

Bununla birlikte, zor türde bir probleminiz varsa ve hala çözümleri saymanız gerekiyorsa (ve bunların sayısı bilinmiyorsa ve daha önce kimse saymadıysa), o zaman en iyi prototip seçeneği aşağıda tartışılacaktır.

N'nin Tamamlayıcı ve Cevap Seti Programlaması

Eğlencenin başladığı yer burası: Makalenin yeni sonucu nedir? N kraliçenin tamamlayıcısı problemi NP-tamdır! (Latin karesinin tamamlayıcısının NP-tamlığının 1984'te bilinmesi ilginçtir.)

Bu pratikte ne anlama geliyor? Bu sorunu çözmenin en kolay yolu (veya bunun bir varyasyonuna ihtiyaç duyarsak aniden) SAT'ı kullanmaktır. Ancak aşağıdaki benzetmeyi daha çok seviyorum:

SAT, kombinatoryal NP problemleri için bir birleştiricidir ve Yanıt Kümesi Programlama (ASP) C++'tır (ASP'nin ayrıca gizemli bir Rus ruhu vardır: bu konuda bilgi sahibi olmayanlar için zaman zaman kafa karıştırıcı ve öngörülemezdir; bu arada, modern ASP'nin altında yatan teori 1950'lerde icat edilmiştir). 1988, daha sonra sırasıyla Texas ve Stanford üniversitelerinde çalışan Mikhail Gelfond ve Vladimir Lifshits tarafından).

Basitçe söylemek gerekirse: ASP, Prolog sözdizimine sahip kısıtlamalar (İngiliz edebiyatındaki kısıtlamalar) için bildirimsel bir programlama dilidir. Yani çözümün hangi kısıtlamaları karşılaması gerektiğini yazıyoruz ve sistem her şeyi SAT seçeneğine indirgeyip bize bir çözüm buluyor.

Çözümün ayrıntıları burada o kadar önemli değil ve Cevap Kümesi Programlama ayrı bir gönderiyi hak ediyor (bu, uygunsuz bir süredir taslağımdaydı): o halde hadi kavramsal noktalara bakalım

% etki alanı satırı(1..n). sütun(1..n). % hepsi farklı 1 ( kraliçe(X,Y) : sütun(Y)) 1:- satır(X). 1 ( kraliçe(X,Y) : satır(X) ) 1:- sütun(Y). % çelişkili yanıtları kaldırın:- kraliçe(X1,Y1), kraliçe(X2,Y2), X1< X2, Y1 == Y2. :- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2. :- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.

Satır 1 ( kraliçe(X,Y) : sütun(Y)) 1:- satır(X). - seçim kuralı olarak adlandırılır ve geçerli bir arama alanının ne olduğunu belirler.

Son üç satıra bütünlük kısıtlamaları denir ve çözümün hangi kısıtlamaları karşılaması gerektiğini tanımlarlar: aynı satırda bir kraliçe olamaz, aynı sütunda bir kraliçe olamaz (simetri nedeniyle atlanmıştır) ve bir kraliçe olamaz aynı diyagonal üzerinde.

Deneysel bir sistem olarak Clingo'yu öneriyorum.
Yeni başlayanlar için eğitimlerini izlemeye ve www.hakank.org adresindeki bloglarını okumaya değer.

Elbette ilk kez ASP'de yazıyorsanız, ilk model inanılmaz derecede verimli ve hızlı olmayacak, ancak büyük olasılıkla aceleyle yazılmış bir dönüşle kaba kuvvetten daha hızlı olacaktır. Ancak sistemin temel prensiplerini anlarsanız, ASP "NP-tam problemler için regexp" haline gelebilir.

ASP modelimizle basit bir sayısal deney yapalım. Modele 5 hain kraliçe ekledim ve 1'den 150'ye kadar N için bir çözüm aradım ve ortaya çıkan şey bu (normal bir ev dizüstü bilgisayarında çalıştırın):

Toplamda, ASP modelimiz N'nin tümleyen problemine yaklaşık bir dakika içinde çözüm bulabilir.<= 150 (в обычном случае). Это показывает, что система отлично подходит для прототипирования моделей сложных комбинаторных задач.

sonuçlar

• Yeni sonuç klasik 8 vezir problemiyle ilgili değil, genelleştirilmiş vezir probleminin eklenmesiyle ilgilidir (ki bu ilginç ama genel olarak mantıklıdır);
• Karmaşıklık önemli ölçüde artar, çünkü vezirleri tahtaya kurnazca yerleştirerek, vezirleri sabit bir düzene göre yerleştiren algoritmayı bozabilirsiniz;
• Çözümlerin sayısını etkili bir şekilde saymak imkansızdır (tabii ki, hiç de değil; ta ki bir tür korku gerçekleşene ve P, NP'ye eşit olana kadar vb.);
• Belki de bu sonuç modern SAT sistemlerinin çalışmasını etkileyecektir, çünkü bazı uzmanlar bu problemin klasik NP-tamamlama problemlerinden biraz daha basit olduğuna inanmaktadır (ancak bu sadece bir fikirdir)
• Herhangi bir nedenden dolayı aniden benzer bir sorunu çözmeniz gerekirse, bu amaç için özel olarak tasarlanmış Cevap Seti Programlama sistemlerini kullanmak en iyisidir.