Kodları lütfen aşağıdaki butonları kullanarak renklendirin. Örnek: <php> echo "Selam Dünya"; </php>
Yardım
karakter kaldı

Kare Bulmaca Algoritması

Merhabalar.

2 boyutlu harf matrisinde boş olarak verilmiş bir kare bulmacayı, sözlükteki kelimeler ile doldurmak istiyorum. Backtrack ve bruteforce yöntemlerini denedim fakat farklı bir yaklaşım gerekiyor. Bu problemin çözümü için optimum yaklaşım nasıl olmalı?

Örnek matris ektedir.

Not: Önce matris ve siyah noktalar belirleniyor, daha sonra yaklaşık 400.000 kelime barındıran sözlükten uygun kelimeler alınarak bulmaca doldurulmalı.

Ekli Dosyalar

  • Kelimeleri yatay ve dikey okutup, uygun kelimeleri ( MySQL ile "... like 'k_l_me' " veya "regexp '^k.l.me$' " tarzı sorgular ile ) arama yaptırıp kelimeleri çekiyorum.
    merter 10 yıl önce yazdı
  • o 400.000 kelimelik sözlüğü nerden bulabilirim? bana lazım öyle bişey.
    guest 8 yıl önce yazdı
+2
-0
Cevaba KatılıyorumKatılmıyorum
Cevap Yaz Yorum Yaz Arşivime Ekle Takip Et

Cevaplar

  • cgelis adlı üyenin fotoğrafı
    10 yıl önce yazılmış
    10 cevap - 0 soru
    cevapları kelime uzunluğuna göre mi yerleştiriyorsunuz ?
    • merter adlı üyenin fotoğrafı merter
      Sorunuzu tam anlamadım ama biraz daha açıklayayım. Yukarıdaki bulmaca örneğini 2 boyutlu char matrisi olarak modelledim. Siyah noktalar da belirtilmiş şekilde. Bu hazır kalıba kelimeleri yerleştirmek istiyorum.

      Önce kelimeleri yazıp sonra noktaları koyarak yapMıyorum. Önce siyah noktalar, sonra kelimeler yerleştirilecek.

      Amacım sadece yukarıdaki matrise sözlükteki kelimeleri yerleştirmek, bunun için yaklaşım & mantık arıyorum.
      Sözlük yaklaşık 400.000 kelime barındırıyor.
      10 yıl önce yazılmış
    • cgelis adlı üyenin fotoğrafı cgelis
      yapmak istediğiniz tam olarak 400.000 kelime içerisinden bulmacayı dolduracak en uygun kelimeleri bulmak mıdır? Doğru mu anlamışım?
      10 yıl önce yazılmış
    • merter adlı üyenin fotoğrafı merter
      Evet aynen öyle. 400.000 kelime içinden kelimeleri seçip bu matrisi doldurmak istiyorum. Bu sözlükteki kelimeler 15 harfli kelimelere kadar kayıt barındırıyor.
      10 yıl önce yazılmış
    • cgelis adlı üyenin fotoğrafı cgelis
      anlatacağım yöntemle biraz memory'e yüklenmen gerekecek. ancak seni çokta sıkıntıya sokmaz diye düşünüyorum. öncelikle 400.000 kelimen var bunların hepsini memory'e attığımızı düşünelim. hepsi 15 harf olsa (en kötü ihtimal) ve her karakter 1 byte olduğu için 400.000 * 15 = 6.000.000 byte'a ihtiyacın olacak yani yaklaşık 5 mb. (pekte kötü değil). kelimelerin maximum 15 harf olduğu için 15 boyutlu bir Binary Search Tree türünde bir array açman gerekecek. Binary Search Tree'imiz alfabetik sıraya göre olacak.

      BST kelimeler[15];

      daha sonra kelimeleri bu arrayın içerisine atacağız.

      mesela 4 harfli kelimeler kelimeler[4] kısmına 15 harfliler kelimeler[15] kısmına. daha sonra bulmacada gezerken mesela 10 harfli bir alana geldiğinde kelimeler[10] kısmındaki BST'de aramaya başlayacak. tabi 10 harfli dışındaki kelimeleri elediğin için birde içeride arama yaparken BST kullandığın için inanılmaz bir performans artışın olacak. Bu verdiğim yöntem dışında şu an için daha iyi bir seçenek aklıma gelmedi. birde Treelerini oluştururken AVL Tree kullanırsan performansını daha üst seviyelere çıkartmış olursun.

      Kolay gelsin.
      10 yıl önce yazılmış
    • siyahbeyaz adlı üyenin fotoğrafı siyahbeyaz
      cgelis. cok mantıklı. gercekten. binary sistemi ve array olayı cok iyi. yükünü hafifletir. ama sole birsey var
      S a
      a h m e t
      l m
      i e
      h t


      yukardan asagı salih yaptık soldan saga ahmet yaptık yukardan asagı ahmet yaptık tekrar. soldan saga 3.satır ve dıger satırlar alakasız oldu. buraları seni epey yoracaktır.
      10 yıl önce yazılmış
    • merter adlı üyenin fotoğrafı merter
      Kelime ararken pek sıkıntım olmuyor, MySql ile sorguları uyarlayarak kelimeleri bulabiliyorum. (like veya regexp kullanıyorum). Ancak örneğin 20 kelime yerleştirdikten sonra 21. kelime bulunmuyor bu sözlükte, backtrack ile geri gidip önceki kelimeleri değiştirsem de bir noktada takılıyor, belli bir noktada kombinasyonu sağlayan kelime bulunmayabiliyor. Sanki ileriyi görebilen veya sezgisel birşeylere ihtiyacım var gibi.. Cevabınız için teşekkür ederim, ağaç aramayı araştıracağım.
      10 yıl önce yazılmış
    • siyahbeyaz adlı üyenin fotoğrafı siyahbeyaz
      kelimenın yerlestirecegi kutucuk sayısı elınde olsa kontrolerin dahada saglamlasa bilir int olayı. ama su array olayı senı kurtarır gıbıme geldi.
      10 yıl önce yazılmış
    • merter adlı üyenin fotoğrafı merter
      Kelime arayıp bulmak konusunda sıkıntım yok, onu hızlandırabilirim de cgelis'in dediği gibi. Sıkıntı işlemlerin ilerlediği durumlarda ,işlem yaptığı yere kelime bulamamasında. Kelimeleri tek tek diziye çıkartıp Backtrack ile uygun kelimeleri bulup yerleştirmeye çalıştım ancak çok uzun sürüyor öyle.
      10 yıl önce yazılmış
    • cgelis adlı üyenin fotoğrafı cgelis
      Problem sudoku problemini andırdı bana. Görünüşe göre backtrackingten başka çare yok ama bu konuda uzun süre düşünmek gerekiyor, biraz araştırma yapmakta fayda var. Sudoku problemleri ile ilgili araştırma yapmanızı öneririm. Sanırım onlarında birçoğu backtracking ve bruteforce ile çalışıyor. Birşeyler bulduğumda tekrar cevap yazarım.
      10 yıl önce yazılmış
    • merter adlı üyenin fotoğrafı merter
      Sudoku problemini Backtrack ile çok önceden çözdüm zaten. (http://merterhami.com/sudoku.php) Kare bulmaca ile 1-2 yıldır uğraşıyorum. Harf harf veya kelime kelime backtrack denedim ancak sonuç alamadım işlem süresi çok uzuyor. Bu aralar brutefoce gibi kelimeleri yazıp değiştirmeye uğraşıyorum ama içime sinmiyor öyle de. Çok dallanıyor.
      10 yıl önce yazılmış
    • cgelis adlı üyenin fotoğrafı cgelis
      Birde backtracking yaparken direk veritabanı üzerinden yaparsanız çok zaman kaybınız olur. Verdiğim algoritma üzerinden backtracking yapmanızı öneririm. Kaldığınız yerlerin pointerlarını elinizde tutarsanız bir geriye gitmek için zaman kaybetmemiş olursunuz. Şu an için en etkili yöntem bu gözüküyor. Tek yapmanız gereken tüm veritabanını anlattığım veri yapılarına inşa etmek. Kaldığınız yerleride ayrı bir yerde tutarsanız probleminizin çok hızlı çözüleceğini düşünüyorum.
      10 yıl önce yazılmış
    • merter adlı üyenin fotoğrafı merter
      B-Tree'yi deneyeceğim ilk fırsat bulduğumda. Test ettikten sonra onunla ilgili cevap yazarım.
      10 yıl önce yazılmış