Şah matı kontrol edin. Çözülecek başka bir soruna hoş geldiniz! Satranç oynamayı ve seviyorsanız bu tam size göre! Bugün kralın savaş alanında bir gün daha hayatta kalmasına yardımcı olacağız ve ayrıca bol miktarda kod yazacağız. kodlamayı Lafı fazla uzatmadan sorunumuza bakalım. Ancak başlamadan önce, her zaman olduğu gibi iki sorumluluk reddi beyanı: Bu sorunlar, abone olabileceğiniz harika Günlük Kodlama Sorunu haber bülteni tarafından sağlanmaktadır. : Bir göz atın ve günlük zorluklarınızı da çözmeyi deneyin! Burada Ben uzman bir programcı değilim, sadece girişimlerini (ve başarısızlıklarını) paylaşmayı seven bir adamım. Daha iyi bir fikriniz veya çözümünüz varsa, bunu paylaşmaktan memnuniyet duyarız: Bunu çözdüğünüzü görmeyi çok isterim! Sorun Bugünün sorunu başlangıçta Oracle tarafından soruldu. Size satranç . 8 taşların konumlarını temsil eden 8 8'lik bir matris sunulur Tahtadaki tek taşlar siyah şah ve çeşitli beyaz taşlardır. Bu matris göz önüne alındığında şahın şahda olup olmadığını belirleyin. Her parçanın nasıl hareket ettiğine ilişkin ayrıntılar için bkz. Burada . Örneğin aşağıdaki matris verildiğinde: ...K.... ........ .B...... ......P. .......R ..N..... ........ .....Q.. . Fil krala çapraz olarak saldırdığı için True döndürmelisiniz Sorun oldukça açık olduğundan bu konuda daha fazla ayrıntıya girmeyeceğiz. Ancak bazı başlangıç spesifikasyonlarına ihtiyacımız var: Bir tahtanın üzerinde değil, bir grafiğin üzerindeyiz: . Sonuç aynı; problemin verdiği her noktayı tahtadaki bir vakanın merkezi olarak ele alacağız Beyaz şah diğer 7 piyonla birlikte tatile çıktı: Şah ve piyonlar tüm taşlar arasında en sıkıcı olanlardır ve bunları ortadan kaldırmak çözümümüzü o kadar da değiştirmeyecektir; gerekiyor; bu, bir sonraki beyaz dönüşte eğer hareket etmezse hamlenin yapılacağı anlamına gelir; Tam da bu dönüşte şahın kontrol altında olup olmadığını doğrulamamız : Üst üste gelen parçalar veya yanlış başlangıç pozisyonları için doğrulamaya girmeyeceğim. Pozisyonlar başlangıçta oyun tarafından verilir Çözüm Her şeyden önce, parçaların ve hareket setlerinin kısa bir özeti: Her bir parçanın başlangıç konumu ve hamle seti göz önüne alındığında, . her bir parçanın olası her bir sonraki hamlesini "kolayca" hesaplayabiliriz Ve hepsi şahı olabildiğince çabuk ele geçirmekle ilgilendiğinden, varsayabiliriz. Bu nedenle siyah şah konumunu da bildiğimiz için, . Eğer öyleyse, bir sonraki beyaz dönüşte beyaz taş siyah şahı ele geçirmek için oraya hareket edecektir. bir sonraki hamlelerinin siyah şahı ele geçirmek olacağını siyah şah konumunun diğer taşların olası bir sonraki hamlelerinden biri olup olmadığını kontrol etmemiz gerekiyor Durum şuna benziyor: Yukarıdaki resimde (... umarım öyledir, karışıklık için özür dilerim...) beyaz tarafta farklı renklerle renklendirilmiş ve yukarıda yakalanmayı bekleyen siyah şahı görebilirsiniz. Yani örneğin fil (2,7)'den başlayarak (1,6), (1,8), (3,8), (3,6), (4,5), (5, 4) vb. her bir taşın mümkün olan her hareketini Nihai sonucu etkilemediği için bu parçaların başlangıç konumlarına rastgele karar verdim. 8x8'lik bir grafik üzerinde olduğumuz için (açık olmak gerekirse, diğer boyutlar da aynı şekilde çalışacaktır) ve her parçanın başlangıç koordinatlarına sahip olduğumuz için, bir sonraki hamlemizde parçalarımız olacak koordinat serilerini oluşturabiliriz. Bunu yapmak için önce koordinatlarını tanımlıyoruz ve ardından x, y her parça için bir sınıf tanımlıyoruz, oradan mümkün olan her hareketi hesaplamak için kuralları tanımlıyoruz. Parçalar – Piyon Piyon ile basit bir başlangıç yapalım. Bu arada, bunu yapıyorum çünkü şu anda en popüler dillerden biri ve tartışmasız herkes tarafından en okunabilir dillerden biri. Yine de bundan sonra takip edebilmek . bu kavramın oldukça güzel bir açıklaması. Python'da için bir sınıfın ne olduğunu bilmeniz gerekecek İşte https://Gist.github.com/NicolaM94/ae4e0e850250a6974042b0ac72be7585?embedable=true#file-pawn-py Kısaca açıklayalım: Öncelikle sınıfını ve onun koordinatlarını tanımlıyoruz. Daha sonra buradan piyonun olası hamlelerini hesaplamak için yöntemini tanımlıyoruz. Piyon hareketleri nispeten kolaydır, bu yüzden bunları basitçe hamle ekleriz, onun ızgaramızın dışına çıkmadığını kontrol ettikten sonra dizisini döndürürüz. Burada özellikle piyon için dikkat edilmesi gereken iki şey: class Pawn x,y __init__ possibleMoves moves moves Beyaz piyonun, sanki piyonunu rakibine doğru ilerleten beyaz oyuncuymuşuz gibi aşağıdan yukarıya doğru hareket ettiğini düşünüyoruz. Bu aslında hiçbir şeyi değiştirmiyor, sadece işleri düzene sokuyor. Siyah şahı ele geçirmekle ilgilendiğimiz için : piyon yalnızca çapraz olarak ele geçirebildiğinden ve taşları başka yönlere hareket ettirmeyi umursamadığımızdan, onun normal hareketini atlayabiliriz. normal hareketi kasıtlı olarak atlıyoruz Artık piyonun hareketlerini ona koordinatlarını vererek ve aşağıdaki gibi yöntemini çağırarak kontrol edebiliriz: ve gibi bir şey elde etmeliyiz. . possibleMoves print(Pawn(7,2).possibleMoves()) [(6,3),(8,3)] [(6,3),(8,3)] Ayrıca, üstte görebilirsiniz, böylece algoritmayı diğer boyutlardaki panolarda çalıştırmak için bunları değiştirebiliriz. ızgara boyutlarımızı değişkenler olarak tanımladığımızı Şimdi kuleye geçelim. Kule https://Gist.github.com/NicolaM94/7897939bdd7933cb09d8915b7b8bc0b5?embedable=true#file-tower-py Yine Tower sınıfını koordinatlarıyla başlatıyoruz ve fonksiyonunu tanımlıyoruz. Olası tüm hareketleri burada toplamak için , tüm döngülerden sonra döndürülecek olan değişkenine ekliyoruz. Daha önce olduğu gibi, kule hareketlerini kontrol etmek için basitçe alabiliriz ve şunun gibi bir şey elde etmeliyiz: . possibleMoves , kuledeki tüm noktaları iki eksende sıralıyoruz ve her bir koordinatı moves print(Tower(5,3).possibleMoves()) [(1,3), (2,3), (3,3), ..., (5,8)] Piskopos Şimdi piskoposun zamanı geldi. https://Gist.github.com/NicolaM94/a6ae6f6138b78d550b2f2e27d5c453aa?embedable=true#file-bishop-py Bishop'un hamleleri kuleye göre daha karmaşıktır o yüzden burada neler olduğunu biraz açıklayabiliriz. Temel olarak . Sınıfı ve init yöntemini bildirdikten sonra iki değişken oluşturuyoruz: daha önce olduğu gibi ve eksenleri boyunca hareket ederken topladığımız noktaları takip etmek için kullanılacak . Şimdi döngüsünü kullanarak ve ızgaramızın dışına çıkmadığımızı kontrol ederek ve hareket . Örneğin başlangıç konumlarından sola doğru hareket etmek istiyorsak değerini artırırken değerini azaltmamız gerekecek. Sağa doğru ilerlemek istiyorsak, değerini azaltırken değerini artırmamız gerekecek ve bu böyle devam edecek. Son olarak bir kez daha geri getiriyoruz. başlangıç noktasından başlayarak iki çapraz eksen üzerinde puan toplamamız gerekiyor moves currentPos while x y etmek istediğimiz yere göre artırıp azaltıyoruz y x y x moves Kraliçe Şimdi düşünebilirsiniz: Eğer kule hareketleri karmaşıksa ve fil daha da karmaşıksa, veziri nasıl kodlayacağız? Aslında vezir hamleleri basit bir numara yardımıyla kodlanması en kolay hareketlerdir. O zaman kraliçeyi görelim. https://Gist.github.com/NicolaM94/22bd55aab7a0976f4656403c3749a6ee?embedable=true#file-queen-py Pekala, burada neler oluyor? Peki, düşünürsek, . Bir kraliçeden çok, kule şeklindeki fil mecha-botuna benziyor. Bu nedenle hareketlerini kodlamak gerçekten çok basit. Sınıfını açıkladıktan sonra, olarak tanımlıyoruz. vezir, fil ve kulenin toplam hamlelerinin aynısına sahip possibleMoves , fil ve kulenin olası hamlelerinden kaynaklanan birleşik hareket dizisi işlevinde ve sınıflarının örnekleri çağrılırken, ve parametrelerinin olarak verildiğine, dolayısıyla bunların aslında kraliçe koordinatları olduğuna dikkat edin. possibleMoves Bishop Tower x y self.x, self.y Şövalye Şimdi şövalyeye! https://Gist.github.com/NicolaM94/c19d2c41e4461c66fca54aab239ede9e?embedable=true#file-knight-py Şövalye benim için en özel olanıdır. Hareket seti "L" şeklinde gibi garip, bu yüzden onu kodlamanın özellikle akıllıca veya hızlı bir yolunu bulamadım ve hareketlerini basitçe hesaplayarak zor kodladım. , başlangıç pozisyonundan itibaren sahip olduğu 8 olası hamlenin her birini Kral Kral hakkında birkaç kısa kavram. Şahı hareket ettirmemiz gerekmediğinden, sadece kontrol edilip edilmediğini bildirdiğimizden, . Ancak yazının sonunda kısa bir uygulamasını da göreceğiz. Ayrıca bunu kodlamak, daha sonra göreceğimiz gibi, vezirin hareket setini zayıflatmak kadar basit değil. Şimdilik onun hareketlerini geçelim ve çözüme bakalım. onun hamle setini uygulamamıza gerçekten ihtiyacımız yok Çözüm kodu Her bir parça için olası konumlara sahip olduğumuz göz önüne alındığında, çözüm artık oldukça basit: sadece siyah şahın koordinatlarının diğer parçalardan birinin veya daha fazlasının hareket kümesinde olup olmadığını kontrol etmemiz gerekiyor. Hadi kodlayalım! https://Gist.github.com/NicolaM94/75826a753105c3a3aecae4f6890b631a?embedable=true#file-check-py Şimdi sadece birkaç koordinat olarak değişkenini oluşturuyoruz. Daha sonra her parça için yeni oluşturduğumuz sınıfın bir örneğini yaratırız ve onun tüm hareket kümesini hesaplamak için yöntemini çağırırız. olmadığını kontrol ederiz: eğer öyleyse, şahın o belirli taş tarafından kontrol edildiğinin çıktısını alırız. Buradaki sonuç şunun gibi bir şeydir: blackKing possibleMoves Bunu aldıktan sonra, blackKing koordinatlarının bu hareket setlerinde mevcut olup Pawn moves: [(8, 3), (6, 3)] Tower moves: [(1, 3), (2, 3), (3, 3), (4, 3), (6, 3), (7, 3), (8, 3), (5, 1), (5, 2), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8)] Check by the tower! Bishop moves: [(3, 8), (1, 6), (1, 8), (3, 6), (4, 5), (5, 4), (6, 3), (7, 2), (8, 1)] Queen moves: [(4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (2, 1), (2, 3), (1, 4), (4, 1), (1, 2), (2, 2), (4, 2), (5, 2), (6, 2), (7, 2), (8, 2), (3, 1), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8)] Knight moves: [(4, 7), (4, 5), (8, 7), (8, 5), (5, 4), (7, 4), (7, 8), (5, 8)] Check by the knight! Yukarıdaki dağınık görüntüyü referans olarak kullandım, böylece şahın kule ve at tarafından gerçekten kontrol edilip edilmediğini kontrol edebilirsiniz. Şah Mat Peki ya ya da gerçekten şah mat olup olmadığını hesaplamak istersek? Bunun için şahın hamle setini hesaplamamız gerekiyor. şahın hâlâ hayatta kalma şansının olup olmadığını https://Gist.github.com/NicolaM94/cca18293bedb2293bbc621e86236571f?embedable=true#file-king-py Biraz tarif edelim. Öncelikle sınıfımızı ve koordinatlarımızı daha önce olduğu gibi tanımlıyoruz. Bundan sonra, yöntemini yaratıyoruz ve şahın olası hareketlerini kodluyoruz (yine, daha hızlı bir yol olduğundan oldukça eminim, ancak yalnızca 8 olası hamle var yani…). Bundan sonra ve yalnızca değerini döndürürüz. possibleMoves hangi hareketlerin yasa dışı olduğunu kontrol ederiz (tahtanın dışına çıkın) validMoves Şimdi, şahın hâlâ hayatta kalma şansının olup olmadığını kontrol etmek için, Bunu yapmak için şahın hamleleri ve diğer hamlelerin üzerinden geçmemiz yeterli. olası hamlelerinden herhangi birinin başka bir hamle grubunda olup olmadığını kontrol etmemiz gerekiyor. https://Gist.github.com/NicolaM94/9bdb64c10e2d039905e6353ed37cc101?embedable=true#file-checkmate-py Yani kralımızın hayatta kalması için hâlâ umut var! Onun için şanslıyım sanırım… Zaman karmaşıklığı Her zaman olduğu gibi, bu çözümün zaman karmaşıklığına kısa bir bakış. Öncelikle, her parça olduğundan, bu örneği başlatma süresini dikkate almalıyız. bir sınıfın örneği gibi taşların içlerinde herhangi bir döngü yoktur ve herhangi bir değişken boyuta bağlı değildirler, dolayısıyla onları O(1) olarak kabul edebiliriz; Piyon veya at biraz çetrefilli: 4 for döngüsü içerdiğinden, zaman karmaşıklığının O(n) olduğunu hemen düşünebilirsiniz, değil mi? Aslında kulenin nasıl hareket ettiğini düşünürsek, fark ederiz. Ve tahta kare olduğundan, kulemizi hareket ettirmek için her zaman 14 boş kasamız olacak. Yani zaman karmaşıklığı aslında O(1) olmalı, 14 çift koordinata sabit olmalıdır. İşte grafik bir örnek: Kule tahtanın neresine yerleştirilirse yerleştirilsin, hareketlerinin dikey ve yatay eksenlerdeki serbest tahta kasalarıyla sınırlı olduğunu Ne yazık ki için aynı şeyi söyleyemeyiz, çünkü bu hareket dizisi biraz daha karmaşık görünüyor. Temel olarak tahtanın neresine yerleştirildiğine bağlı olarak 7, 9, 11 veya 13 hamleden oluşur. Bu nedenle, hamle kümesini hesaplamak için gereken adımlar konumuna bağlıdır, dolayısıyla O(n)'nin tc'sini düşünebiliriz. fil kulenin ve filin hamlelerinin birleşimine ihtiyaç duyar. , filin TC'si kulenin TC'sine üstün gelir. Bu nedenle kraliçe için de O(n)'nin tc'sini dikkate almalıyız. Vezir, Zaman karmaşıklığını değerlendirirken en kötü senaryoya odaklanmamız gerektiğinden Sonunda sabit kodlanmış bir dizi hamlesi var, ama aynı zamanda . Yani teknik olarak şahın hamle dizisi her halükarda nispeten küçük olsa bile, tahtadaki konumuna da bağlı olarak onun tc'sini O(n) olarak düşünmeliyiz. şahın for döngüsünü kullanan bir doğrulama süreci de var Bu noktada, kullanıyoruz. Bu bize tc'nin sabit olduğu durumlarda hiçbir sorun yaratmaz (örneğin kuleyi ele alalım: 14 hareketini hesaplıyoruz ve ardından bunların üzerinden en fazla 14 kez daha döngü yapıyoruz, böylece onu sabit zaman olarak da düşünebiliriz). Yine de, hamle sayısı arttıkça büyüyecek bir döngü eklediğimiz için tc'nin O(n) veya üzerinde olduğu durumlarda sorun yaşayacağız. siyah şahın kontrol durumunu doğrulamak ve yazdırmak için her parça için bir for döngüsü Son olarak, şahın hamle sayısına ve diğer taşların hamlelerine bağlı olarak kesinlikle O(n²)'nin tc'si olacak . şah matını doğrulamak için double (iç) for döngüsü kullanırız Bu kadar; işte benim çözümüm. Bazı noktaların mümkün olduğu kadar verimli olmadığının farkındayım, ancak yazarken mükemmel çözümü oluşturmaktan çok süreci açıklama fikrini sevdim. Bunun hakkında ne düşünüyorsun? Bu konudaki fikrinizi bana bildirin ve çözümlerinizi yorumlarda tartışalım! Her zaman olduğu gibi, makaleyi beğendiyseniz lütfen bir veya iki alkış bırakın ve abone olun veya mümkünse bu tür algoritmalarla ilgilenebilecek biriyle paylaşın! Sonuna kadar okuduğunuz için teşekkürler, bu sefer bu çözümün uzunluğu her zamankinden daha fazla! Her zamanki gibi okuduğunuz için teşekkürler.

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Read My Stories

Bu ses hikayenin orijinal dilinde üretilmiştir!

Günlük Kodlama Problemi: Şah Matı Kontrol Etmek için Kodlama Becerilerinizi Kullanın

Çok uzun; Okumak

People Mentioned

@nicolam94

Credibility

İLGİLİ ÖYKÜLER