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

Şah matı kontrol edin. Çözülecek başka bir soruna hoş geldiniz! Satranç oynamayı ve kodlamayı 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.

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. Burada : Bir göz atın ve günlük zorluklarınızı da çözmeyi deneyin!
• 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:

1. Bir tahtanın üzerinde değil, bir grafiğin üzerindeyiz: problemin verdiği her noktayı tahtadaki bir vakanın merkezi olarak ele alacağız . Sonuç aynı;
2. 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;
3. Tam da bu dönüşte şahın kontrol altında olup olmadığını doğrulamamız gerekiyor; bu, bir sonraki beyaz dönüşte eğer hareket etmezse hamlenin yapılacağı anlamına gelir;
4. Pozisyonlar başlangıçta oyun tarafından verilir : Üst üste gelen parçalar veya yanlış başlangıç pozisyonları için doğrulamaya girmeyeceğim.

Çö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, bir sonraki hamlelerinin siyah şahı ele geçirmek olacağını varsayabiliriz. Bu nedenle siyah şah konumunu da bildiğimiz için, siyah şah konumunun diğer taşların olası bir sonraki hamlelerinden biri olup olmadığını kontrol etmemiz gerekiyor . Eğer öyleyse, bir sonraki beyaz dönüşte beyaz taş siyah şahı ele geçirmek için oraya hareket edecektir.

Durum şuna benziyor:
Yukarıdaki resimde (... umarım öyledir, karışıklık için özür dilerim...) beyaz tarafta farklı renklerle renklendirilmiş her bir taşın mümkün olan her hareketini 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.

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 x, y koordinat serilerini oluşturabiliriz. Bunu yapmak için önce her parça için bir sınıf tanımlıyoruz, koordinatlarını tanımlıyoruz ve ardından 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 Python'da 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 için bir sınıfın ne olduğunu bilmeniz gerekecek . İşte bu kavramın oldukça güzel bir açıklaması.

Kısaca açıklayalım: Öncelikle class Pawn sınıfını ve onun koordinatlarını x,y __init__ tanımlıyoruz. Daha sonra buradan piyonun olası hamlelerini hesaplamak için possibleMoves yöntemini tanımlıyoruz. Piyon hareketleri nispeten kolaydır, bu yüzden bunları basitçe hamle moves ekleriz, onun ızgaramızın dışına çıkmadığını kontrol ettikten sonra moves dizisini döndürürüz. Burada özellikle piyon için dikkat edilmesi gereken iki şey:

1. 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.

2. Siyah şahı ele geçirmekle ilgilendiğimiz için normal hareketi kasıtlı olarak atlıyoruz : 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.

   
   

Artık piyonun hareketlerini ona koordinatlarını vererek ve aşağıdaki gibi possibleMoves yöntemini çağırarak kontrol edebiliriz: print(Pawn(7,2).possibleMoves()) ve [(6,3),(8,3)] gibi bir şey elde etmeliyiz. [(6,3),(8,3)] .

Ayrıca, üstte ızgara boyutlarımızı değişkenler olarak tanımladığımızı görebilirsiniz, böylece algoritmayı diğer boyutlardaki panolarda çalıştırmak için bunları değiştirebiliriz.

Şimdi kuleye geçelim.

Kule

Yine Tower sınıfını koordinatlarıyla başlatıyoruz ve possibleMoves fonksiyonunu tanımlıyoruz. Olası tüm hareketleri burada toplamak için , kuledeki tüm noktaları iki eksende sıralıyoruz ve her bir koordinatı , tüm döngülerden sonra döndürülecek olan moves değişkenine ekliyoruz. Daha önce olduğu gibi, kule hareketlerini kontrol etmek için basitçe print(Tower(5,3).possibleMoves()) alabiliriz ve şunun gibi bir şey elde etmeliyiz: [(1,3), (2,3), (3,3), ..., (5,8)] .

Piskopos

Şimdi piskoposun zamanı geldi.

Bishop'un hamleleri kuleye göre daha karmaşıktır o yüzden burada neler olduğunu biraz açıklayabiliriz. Temel olarak başlangıç noktasından başlayarak iki çapraz eksen üzerinde puan toplamamız gerekiyor . Sınıfı ve init yöntemini bildirdikten sonra iki değişken oluşturuyoruz: daha önce olduğu gibi moves ve eksenleri boyunca hareket ederken topladığımız noktaları takip etmek için kullanılacak currentPos . Şimdi while döngüsünü kullanarak ve ızgaramızın dışına çıkmadığımızı kontrol ederek x ve y hareket etmek istediğimiz yere göre artırıp azaltıyoruz . Örneğin başlangıç konumlarından sola doğru hareket etmek istiyorsak y değerini artırırken x değerini azaltmamız gerekecek. Sağa doğru ilerlemek istiyorsak, y değerini azaltırken x değerini artırmamız gerekecek ve bu böyle devam edecek. Son olarak moves bir kez daha geri getiriyoruz.

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.

Pekala, burada neler oluyor? Peki, düşünürsek, vezir, fil ve kulenin toplam hamlelerinin aynısına sahip . 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, possibleMoves , fil ve kulenin olası hamlelerinden kaynaklanan birleşik hareket dizisi olarak tanımlıyoruz.

possibleMoves işlevinde Bishop ve Tower sınıflarının örnekleri çağrılırken, x ve y parametrelerinin self.x, self.y olarak verildiğine, dolayısıyla bunların aslında kraliçe koordinatları olduğuna dikkat edin.

Şövalye

Şimdi şövalyeye!

Şö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 , başlangıç pozisyonundan itibaren sahip olduğu 8 olası hamlenin her birini basitçe hesaplayarak zor kodladım.

Kral

Kral hakkında birkaç kısa kavram. Şahı hareket ettirmemiz gerekmediğinden, sadece kontrol edilip edilmediğini bildirdiğimizden, onun hamle setini uygulamamıza gerçekten ihtiyacımız yok . 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.

Çö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!

Şimdi sadece birkaç koordinat olarak blackKing 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 possibleMoves yöntemini çağırırız. Bunu aldıktan sonra, blackKing koordinatlarının bu hareket setlerinde mevcut olup 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:

 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 şahın hâlâ hayatta kalma şansının olup olmadığını ya da gerçekten şah mat olup olmadığını hesaplamak istersek? Bunun için şahın hamle setini hesaplamamız gerekiyor.

Biraz tarif edelim. Öncelikle sınıfımızı ve koordinatlarımızı daha önce olduğu gibi tanımlıyoruz. Bundan sonra, possibleMoves 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 hangi hareketlerin yasa dışı olduğunu kontrol ederiz (tahtanın dışına çıkın) ve yalnızca validMoves değerini döndürürüz.

Şimdi, şahın hâlâ hayatta kalma şansının olup olmadığını kontrol etmek için, olası hamlelerinden herhangi birinin başka bir hamle grubunda olup olmadığını kontrol etmemiz gerekiyor. Bunu yapmak için şahın hamleleri ve diğer hamlelerin üzerinden geçmemiz yeterli.

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 bir sınıfın örneği olduğundan, bu örneği başlatma süresini dikkate almalıyız.

• Piyon veya at 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;
• Kule 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, tahtanın neresine yerleştirilirse yerleştirilsin, hareketlerinin dikey ve yatay eksenlerdeki serbest tahta kasalarıyla sınırlı olduğunu 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:

• Ne yazık ki fil 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.

• Vezir, kulenin ve filin hamlelerinin birleşimine ihtiyaç duyar. Zaman karmaşıklığını değerlendirirken en kötü senaryoya odaklanmamız gerektiğinden , 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.

• Sonunda şahın sabit kodlanmış bir dizi hamlesi var, ama aynı zamanda for döngüsünü kullanan bir doğrulama süreci de var . 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.

  
  

Bu noktada, siyah şahın kontrol durumunu doğrulamak ve yazdırmak için her parça için bir for döngüsü 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.

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.