Ş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!

Çok uzun; Okumak

Make resilience your competitive advantage

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

About Author

YORUMLAR

ETİKETLERİ ASIN

BU YAZI

Related Stories

Sulara Yelken Açmak: Data Lakes ile Üretim Sınıfında RAG Uygulamaları Geliştirme

Telegram: Kripto Adası'nın anakaraya olan köprüsü

Kazanmak için Dokun: Telegram, Solana'dan Önce Sonraki 10 Milyar Kripto Kullanıcısına Katılabilir

Floki'den Valhalla Hindistan'ın Sri Lanka Turuna Yardımcı Sponsor Olarak Katıldı

Sulara Yelken Açmak: Data Lakes ile Üretim Sınıfında RAG Uygulamaları Geliştirme

Telegram: Kripto Adası'nın anakaraya olan köprüsü

Kazanmak için Dokun: Telegram, Solana'dan Önce Sonraki 10 Milyar Kripto Kullanıcısına Katılabilir

Floki'den Valhalla Hindistan'ın Sri Lanka Turuna Yardımcı Sponsor Olarak Katıldı

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps