Kare Bulmaca Algoritması

Cevaplar

• 

  11 yıl önce yazılmış

  cgelis

  10 cevap - 0 soru
  cevapları kelime uzunluğuna göre mi yerleştiriyorsunuz ?

  • 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.
    11 yıl önce yazılmış
  • 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?
    11 yıl önce yazılmış
  • 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.
    11 yıl önce yazılmış
  • 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.
    11 yıl önce yazılmış
  • 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.
    11 yıl önce yazılmış
  • 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.
    11 yıl önce yazılmış
  • 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.
    11 yıl önce yazılmış
  • 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.
    11 yıl önce yazılmış
  • 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.
    11 yıl önce yazılmış
  • 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.
    11 yıl önce yazılmış
  • 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.
    11 yıl önce yazılmış
  • merter
    B-Tree'yi deneyeceğim ilk fırsat bulduğumda. Test ettikten sonra onunla ilgili cevap yazarım.
    11 yıl önce yazılmış