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

Abstract

Sudoku dünya çapında popülerlik kazanmış bir mantık bulmacasıdır. Bu tez çalışmasında, öncelikle matematiksel programlama kullanılarak sudoku probleminin çözümü incelenmiş ve sonrasında ise bir sudoku bulmacası oluşturma algoritması geliştirilerek oyun tasarımları gerçekleştirilmiştir. Çalışma kapsamında standart sudoku bulmacası dikkate alınmış olmakla birlikte, önerilen yaklaşımların geliştirilip genelleştirilerek diğer sudoku çeşitleri üzerinde de uygulanabileceği belirtilebilir. Tez çalışması kapsamında öncelikle sudoku probleminin çözümü için bir matematiksel programlama formülasyonu dikkate alınmış, problem bir sağlanabilirlik veya uygunluk problemi olarak modellenerek, Visual Studio ortamında C# programlama dili ve Gurobi çözücü ile çözülmüştür. Buna ek olarak, yine Visual Studio ortamında bir oyun tasarımı gerçekleştirilmiştir. Tez çalışmasının ikinci kısmında, herhangi bir çözücü kullanılmadan kaba-kuvvet algoritmasıyla Sudoku problemini çözmenin yanı sıra, ayrıca bir sudoku bulmacası oluşturma algoritması geliştirilip Unity ortamında C# programlama dili ile kodlanıp bir oyun tasarımı gerçekleştirilmiştir. Çalışmanın her iki aşamasında da önerilen yaklaşımlar test edilmiş, örnek problemler ve bulmacalar oluşturulmuştur.

Sudoku is a popular logic puzzle that has gained worldwide popularity. In this thesis, the solution of the sudoku problem was first studied using mathematical programming, and then a sudoku puzzle creation algorithm was developed and game designs were implemented. While the standard sudoku puzzle was considered in the scope of the study, it can be mentioned that the proposed approaches can be developed and generalized to be applied on other sudoku types. In the scope of the thesis, a mathematical programming formulation was first considered for solving the sudoku problem, and the problem was modeled as a feasibility or suitability problem and solved using the C# programming language and the Gurobi solver in the Visual Studio environment. In addition, a game design was also implemented in the Visual Studio environment. In the second part of the thesis, in addition to solving the Sudoku problem with the brute-force algorithm without using any solver, a sudoku puzzle creation algorithm was developed and coded in the Unity environment using the C# programming language and a game design was implemented. Both stages of the study have tested the proposed approaches, and sample problems and puzzles have been created.