Sudoku çözme algoritmaları - Sudoku solving algorithms

Tipik bir Sudoku bulmacası, birkaç sayı eksik olan 9x9 ızgara
Tipik bir Sudoku bulmacası

Bir standart Sudoku 9 × 9 ızgarada 81 hücre içerir ve 9 kutuya sahiptir; her kutu ilk, orta veya son 3 satır ile ilk, orta veya son 3 sütunun kesişimidir. Her hücre birden dokuza kadar bir sayı içerebilir ve her sayı her satırda, sütunda ve kutuda yalnızca bir kez oluşabilir. Sudoku, sayı içeren bazı hücrelerle başlar (ipuçları) ve amaç kalan hücreleri çözmektir. Uygun Sudokus'un bir çözümü var. Oyuncular ve araştırmacılar, Sudokus'u çözmek, özelliklerini incelemek ve ilginç simetrilere ve diğer özelliklere sahip Sudokus dahil olmak üzere yeni bulmacalar yapmak için çok çeşitli bilgisayar algoritmaları kullanabilir.

Çoğu 9 × 9 bulmacayı çözecek birkaç bilgisayar algoritması vardır (n= 9) saniyenin kesirlerinde, ancak kombinatoryal patlama olarak oluşur n Sudokus'un özellikleri için inşa edilebilen, analiz edilebilen ve çözülebilen sınırlar yaratarak artar, n artışlar.

Teknikler

Geri izleme

Çözülen bir Sudoku (üstte) geri izleme. Her hücre geçerli bir sayı için test edilir, ihlal olduğunda "geri" hareket edilir ve bulmaca çözülene kadar tekrar ileri alınır.
Kaba kuvvet algoritmasına karşı çalışmak üzere tasarlanmış bir Sudoku.[1]
Ana makale: Kaba kuvvet arama

Bazı hobiciler, Sudoku bulmacalarını çözen bilgisayar programları geliştirdiler. geri izleme bir tür olan algoritma kaba kuvvet araması.[2] Geri izleme bir derinlik öncelikli arama (bir enine arama ), çünkü başka bir şubeye geçmeden önce bir dalı olası bir çözümü tamamen keşfedecektir. Yaklaşık 5.96 x 11 olduğu tespit edilmiş olmasına rağmen26 son ızgaralar mevcutsa, bir kaba kuvvet algoritması Sudoku bulmacalarını çözmek için pratik bir yöntem olabilir.

Bir kaba kuvvet algoritması boş hücreleri bir sırayla ziyaret eder, rakamları sırayla doldurur veya numaranın geçerli olmadığı tespit edildiğinde geriye doğru izler.[3][4][5][6] Kısaca, bir program bir bulmacayı ilk hücreye "1" rakamını yerleştirerek ve orada olmasına izin verilip verilmediğini kontrol ederek çözecektir. İhlal yoksa (satır, sütun ve kutu kısıtlamalarını kontrol ederek), algoritma bir sonraki hücreye ilerler ve bu hücreye bir "1" yerleştirir. İhlalleri kontrol ederken, "1" e izin verilmediğinin tespit edilmesi durumunda, değer "2" ye yükseltilir. 9 haneden hiçbirine izin verilmeyen bir hücre keşfedilirse, algoritma bu hücreyi boş bırakır ve önceki hücreye geri döner. Bu hücredeki değer daha sonra bir artırılır. Bu, son (81.) hücrede izin verilen değer keşfedilene kadar tekrarlanır.

Animasyon, bir Sudoku'nun bu yöntemle nasıl çözüldüğünü gösterir. Algoritma çözülmemiş her hücreyi olası bir çözümle test ederken bulmacanın ipuçları (kırmızı sayılar) sabit kalır. Algoritmanın, mevcut setin Sudokunun kısıtlamalarını karşılamadığını tespit etmesi durumunda daha önce test edilen tüm değerleri atabileceğine dikkat edin.

Bu yöntemin avantajları:

  • Bir çözüm garantilidir (bulmaca geçerli olduğu sürece).
  • Çözme zamanı çoğunlukla aşağıdakilerle ilgisizdir: zorluk derecesi.
  • Algoritma (ve dolayısıyla program kodu) diğer algoritmalardan daha basittir, özellikle en zor bulmacalara çözüm sağlayan güçlü algoritmalarla karşılaştırıldığında.

Bu yöntemin dezavantajı, tümdengelimli yöntemlerden sonra modellenen algoritmalara göre çözme süresinin yavaş olabilmesidir. Bir programcı, böyle bir algoritmanın bir Sudoku'yu çözmek için tipik olarak 15.000 döngü veya 900.000 döngü gerektirebileceğini bildirdi; her döngü, bir Sudoku'nun hücrelerinde hareket ederken bir "işaretçinin" konumundaki değişikliktir.[7][8]

Geriye dönük izlemeye karşı çalışmak için bir Sudoku oluşturulabilir. Çözücünün yukarıdan aşağıya doğru çalıştığını varsayarsak (animasyondaki gibi), birkaç ipucu (17) içeren, üst satırda ipucu olmayan ve ilk satır için "987654321" çözümü olan bir bulmaca, algoritmanın tersine çalışacaktır. . Böylece program, bulmacayı tatmin eden ızgaraya ulaşmadan önce yukarı doğru "saymak" için önemli ölçüde zaman harcayacaktır. Bir vakada, bir programcı bir kaba kuvvet programının böyle bir Sudoku için çözüme ulaşması için altı saat gerektiğini keşfetti (her ne kadar 2008 dönemi bir bilgisayar kullanıyor olsa da). Böyle bir Sudoku, günümüzde kapsamlı bir arama rutini ve daha hızlı işlemciler kullanılarak 1 saniyeden daha kısa sürede çözülebilir.[kaynak belirtilmeli ]

Stokastik arama / optimizasyon yöntemleri

Sudoku, stokastik (rastgele tabanlı) algoritmalar kullanılarak çözülebilir.[9][10] Bu yöntemin bir örneği şudur:

  1. Izgaradaki boş hücrelere rastgele numara atayın.
  2. Hata sayısını hesaplayın.
  3. Hata sayısı sıfıra düşene kadar eklenen sayıları "karıştırın".

Daha sonra bulmacaya bir çözüm bulunur. Sayıları karıştırmak için yaklaşımlar şunları içerir: benzetimli tavlama, genetik Algoritma ve tabu araması. Stokastik tabanlı algoritmaların hızlı olduğu biliniyor, ancak belki de tümdengelimli teknikler kadar hızlı değil. Bununla birlikte, ikincisinden farklı olarak, optimizasyon algoritmaları, problemlerin mantıksal olarak çözülebilir olmasını gerektirmez, bu da onlara daha geniş bir problem yelpazesini çözme potansiyeli verir. Grafik renklendirme için tasarlanan algoritmaların da Sudokus ile iyi performans gösterdiği bilinmektedir.[11] Ayrıca bir Sudoku'yu bir tamsayı doğrusal programlama sorun. Bu tür yaklaşımlar hızla bir çözüme yaklaşır ve daha sonra sonuna doğru dallanma kullanabilir. simpleks algoritması uygun olmayan Sudokus'u çözebilir, Sudoku'nun geçerli olup olmadığını (çözüm yok) veya birden fazla çözüm olduğunda yanıt setini sağlayabilir.

Kısıt programlama

Bir Sudoku, aynı zamanda bir kısıtlama tatmin problemi. Onun makalesinde Kısıtlama Sorunu Olarak Sudoku,[12] Helmut Simonis birçok kişiyi anlatıyor muhakeme algoritmaları problemleri modellemek ve çözmek için uygulanabilecek kısıtlamalara dayanır. Bazı kısıt çözücüler, Sudokus'u modellemek ve çözmek için bir yöntem içerir ve bir program basit bir Sudoku çözmek için 100 satırdan daha az kod gerektirebilir.[13][14] Kod güçlü bir muhakeme algoritması kullanıyorsa, geriye dönük izlemeyi dahil etmek yalnızca en zor Sudokus için gereklidir. Kısıtlama modeline dayalı bir algoritmayı geri izleme ile birleştiren bir algoritma, hızlı çözme süresi avantajına ve tüm sudokusu çözme yeteneğine sahip olacaktır.

Tam kapak

Ana makale: Tam kapak § Sudoku

Sudoku bulmacaları şu şekilde tanımlanabilir: tam kapak sorun. Bu, sorunun zarif bir tanımına ve etkili bir çözüme olanak tanır. Sudoku'yu tam bir kapsam problemi olarak modellemek ve aşağıdaki gibi bir algoritma kullanmak Knuth Algoritması X bir Sudoku'yu genellikle birkaç milisaniye içinde çözer. Alternatif bir yaklaşım, Gauss eliminasyonunun sütun ve satır vuruşu ile birlikte kullanılmasıdır.

Sudokus geliştirmek (aramak)

17 ipucu ve çapraz simetriye sahip bir Sudoku.
Bir otomorfik 18 ipucu ve iki yönlü çapraz simetriye sahip Sudoku.
Benzer bir modele sahip 17 ipucu bir Sudoku. (Turuncu daireler: kaldırılmış ipuçları, yeşil daireler: eklenmiş ipuçları, mavi alt çizgi: farklı rakamlar).
18 ipucu Sudoku.
(Yatay simetri).

Bilgisayar programları genellikle az sayıda gibi belirli özelliklerle Sudokus'u "aramak" için kullanılır. ipuçları veya belirli türleri simetri. 17 ipucu içeren 49.000'den fazla Sudoku bulundu, ancak keşfedilmemiş olanlar daha nadir hale geldikçe yeni farklı olanları keşfetmek (mevcut bilinen Sudokus'un dönüşümlerini değil) daha zor hale geliyor.[15]

Belirli bir özelliğe sahip Sudokus'u aramak için yaygın bir yöntem denir komşu arıyor. Bu stratejiyi kullanarak, aranan özelliği tatmin eden veya neredeyse tatmin eden bir veya daha fazla bilinen Sudokus, bir başlangıç ​​noktası olarak kullanılır ve bu Sudokus daha sonra, aranan özellik ile başka Sudokus'u aramak için değiştirilir. Değişiklik, bir veya daha fazla ipucu pozisyonunu yeniden konumlandırmak veya az sayıda ipucunu kaldırmak ve bunları farklı sayıda ipucu ile değiştirmek olabilir. Örneğin, bilinen bir Sudoku'dan, iki ipucu kaldırılarak ve yeni bir konuma bir ipucu eklenerek bir tane daha az ipucu içeren yeni bir arama gerçekleştirilebilir. (Buna {-2, + 1} araması denilebilir). Her yeni Desen daha sonra, bir veya daha fazla kişinin geçerli bir Sudoku vermesi (yani çözülebilir ve tek bir çözüme sahip olması) umuduyla tüm ipucu değerleri kombinasyonları için ayrıntılı bir şekilde araştırılır. Esasen eşdeğer Sudokus'un fazladan test edilmesini önlemek için yöntemler de kullanılabilir.

Spesifik bir örnek olarak, 17 ipuçlu bir Sudoku için arama, bilinen bir 18 ipucu Sudoku ile başlayabilir ve sonra onu kaldırarak değiştirebilir. üç ipucuve bunların yerine yalnızca iki ipucu, farklı pozisyonlarda (son iki resme bakın). Bu, yeni Sudokus'u keşfedebilir, ancak bunların halihazırda bilinen Sudokus'tan esasen farklı olduğuna dair anında bir garanti olmayacaktır. Gerçekten yeni (keşfedilmemiş) Sudokus arıyorsanız, her bulgunun zaten bilinen bir Sudoku'nun dönüşümü olmadığından emin olmak için daha fazla onay gerekir.[16][daha iyi kaynak gerekli ]

Ayrıca bakınız

Referanslar

  1. ^ "Yıldız Patlaması - Kutup Grafiği" Kapsamlı bir arama rutini kullanarak bir Sudoku (Yıldız Patlaması) için bir çözüm yolunu gösteren kutup şeması ve 17 ipucu Sudoku hakkında yorum.
  2. ^ http: //intelligence.worldofcomputing/brute-force-search Brute Force Search, 14 Aralık 2009.
  3. ^ "Geri izleme - Set 7 (Sudoku)". GeeksforGeeks. GeeksforGeeks. Arşivlenen orijinal 2016-08-28 tarihinde. Alındı 24 Aralık 2016.
  4. ^ Norvig, Peter. "Her Sudoku Bulmacasını Çözme". Peter Norvig (kişisel web sitesi). Alındı 24 Aralık 2016.
  5. ^ "Çözüm İçin Ziyaret Edilen Hücrelerin Tablosu" Zor bir Sudoku'ya giden çözüm yolunu gösteren bir grafik.
  6. ^ Zelenski, Julie (16 Temmuz 2008). Ders 11 | Programlama Soyutlamaları (Stanford). Stanford Bilgisayar Bilimleri Bölümü.
  7. ^ "Yıldız Patlaması Aslan - Kutup Grafiği" Kapsamlı bir arama rutini kullanarak bir Sudoku (Yıldız Patlaması Aslanı) için bir çözüm yolunu gösteren bir kutup şeması.
  8. ^ "Çözüm İçin Ziyaret Edilen Hücrelerin Tablosu" Kapsamlı bir arama rutini kullanarak zor bir Sudoku için bir çözüm yolunu gösteren bir grafik.
  9. ^ Lewis, R (2007) Meta-sezgiseller Sudoku Bulmacalarını Çözebilir Journal of Heuristics, cilt. 13 (4), s. 387-401.
  10. ^ Perez, Meir ve Marwala, Tshilidzi (2008) Sudoku Çözmek İçin Stokastik Optimizasyon Yaklaşımları arXiv: 0805.0697.
  11. ^ Lewis, R. Grafik Renklendirme Rehberi: Algoritmalar ve Uygulamalar. Springer International Publishers, 2015.
  12. ^ Simonis, Helmut (2005). "Kısıtlama Problemi Olarak Sudoku". University College Cork'taki Cork Kısıtlı Hesaplama Merkezi: Helmut Simonis. CiteSeerX  10.1.1.88.2964. Eleventh International Conference on Principles and Practice of Constraint Programming Alıntı dergisi gerektirir | günlük = (Yardım)
  13. ^ Birden Çok Yazar. "Java Kısıt Programlama çözücü" (Java). JaCoP. Krzysztof Kuchcinski ve Radoslaw Szymanek. Alındı 8 Aralık 2016.
  14. ^ Rhollor. "Sudokusolver" (C ++). GitHub. Rhollor. Alındı 8 Aralık 2016.
  15. ^ Royle, Gordon. "Minimum Sudoku". Arşivlenen orijinal 19 Ekim 2013. Alındı 20 Ekim 2013.
  16. ^ http://forum.enjoysudoku.com Yeni Sudoku Oyuncuları Forumu "{-3 + 3} içinde yeni 17'ler yok".

Dış bağlantılar