Geri Dön

Sudoku bulmacasının kuyruk liste veri yapısı tabanlı paralel önce-derine-arama yöntemiyle çözülmesi

Solving sudoku puzzle with parallel depth-first-search method based on the list of queues data structure

  1. Tez No: 535422
  2. Yazar: ZEYNEP FEYZA ESEN
  3. Danışmanlar: DOÇ. DR. CİHAN KALELİ
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2018
  8. Dil: Türkçe
  9. Üniversite: Anadolu Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Bilişim Bilim Dalı
  13. Sayfa Sayısı: 59

Özet

NP-Complete bir oyun olan sudoku bulmacası dünya genelinde oldukça ilgi gören bir bulmaca çeşididir. Sudokuya olan ilginin yoğunluğu ilk kez 2006'da şampiyona düzenlenmesine neden olmuştur. Sayıların dizilim ve kullanılan sayı miktarına bağlı olarak farklı zorluk seviyelerinde oluşturulabilen sudokunun kolay seviyeleri klasik kağıt kalem ile basitçe çözülebilirken, zor seviyesindeki sudoku bulmacaları için çeşitli deneme yanılma yöntemleri geliştirilmiştir. Bu tez çalışmasında sudoku bulmacasının kuyruk liste veri yapısı tabanlı paralel önce derine arama yöntemi ile çözülmesi amaçlanmıştır. Paralelleştirme yapılırken farklı sayıda thread'ler ve parametreler denenmiş ve bunların optimum değerleri bulunmaya çalışılmıştır. Kuyruk listesi veri yapısı tabanlı paralel önce derine arama yöntemi ile geleneksel önce derine arama algoritması karşılaştırılmıştır. Bu çalışmada iki farklı zorluk seviyesinden 2'şer adet sudoku bulmacası kullanılmıştır. Her bir sudoku bulmacası 10'ar kez çözülerek çözüm süresinin ortalamaları alınarak incelemeler yapılmıştır. Denemeler sonucunda kuyruk listesi veri yapısı tabanlı paralel önce derine arama yönteminin, belirli thread sayısı ve parametreler ile geleneksel önce derine arama algoritmasından daha hızlı çözdüğü görülmüştür.

Özet (Çeviri)

The sudoku puzzle, an NP-Complete game, is a puzzle that is highly popular around the world. The intensity of the interest in the sudoku has resulted in the first championship being held in 2006. Sudokus can be in different levels of difficulty depending on the number of sequences and the number of digits used. Sudoku puzzles at easy levels can be solved with a classic paper-pencil. On the other hand, trial-and-error methods have been developed for puzzles in different levels of difficulty. The aim of this study was to solve sudoku puzzles by using the parallel depth-first-search method based on the list of queues data structure. Different numbers of threads and parameters were tested in parallelling process. Optimal thread and parameters were examined. The parallel depth-first-search method based on the list of queues data structure was compared with the traditional depth-first-search search algorithm. Two sudoku puzzles were used in each of two different levels of difficulty in the study. Each sudoku puzzle was solved ten times and analyses were performed by taking the averages of solution. As a result of the experiments, the parallel depth-first-search method based on the list of queues data structure was found to solve sudokus faster than the traditional depth-first-search algorithm with a certain number of threads and parameters.

Benzer Tezler

  1. Mimari tasarımın üretilmesinde genetik algoritma ve parametrik tasarım ile bir yöntem arayışı

    Searching for a method with genetic algorithm and parametric design in the production of architectural design

    ŞULE BETÜL DEMİRKOL

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    MimarlıkGazi Üniversitesi

    Mimarlık Ana Bilim Dalı

    DOÇ. DR. ARZU ÖZEN YAVUZ

  2. Sudoku probleminin matematiksel programlama ile çözümü ve bulmaca oluşturma

    Solving the sudoku problem with mathematical programming and puzzle creation

    TUĞÇE ATEŞ

    Yüksek Lisans

    Türkçe

    Türkçe

    2023

    Endüstri ve Endüstri MühendisliğiBursa Uludağ Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. FATİH ÇAVDUR

  3. Sudoku deneme deseninin tarımsal araştırmalarda kullanımı

    Use of sudoku experimental desing in agricultural studies

    BUĞRA HOŞGÖNÜL

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    ZiraatOndokuz Mayıs Üniversitesi

    Biyometri ve Genetik Ana Bilim Dalı

    PROF. DR. HASAN ÖNDER

  4. Sudoku, Futoshiki ve Kakuro bulmacalarının 8. sınıf öğrencilerinin denklemler ve eşitsizlikler konusundaki başarılarına etkisi

    The effect of Sudoku, Futoshiki and Kakuro puzzles on 8th grade students' achievement on equality and inequality subjects

    ŞENOL NAMLI

    Yüksek Lisans

    Türkçe

    Türkçe

    2016

    Eğitim ve ÖğretimAkdeniz Üniversitesi

    İlköğretim Ana Bilim Dalı

    PROF. DR. GABİL ADİLOV

  5. A study on metaheuristic algorithms for solving sudoku puzzles

    Metasezgisel algoritmalar ile sudoku bulmacalarını çözmek üzerine bir çalışma

    KHORSHİD HAMZA

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolFatih Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. AİŞE ZÜLAL ŞEVKLİ