Survo bulmacasının oluşturulması ve çözülmesı̇ ı̇çı̇n tamsayılı programlama formülasyonu

Abstract

Bulmacalar genellikle eğlence için üretilir ancak aynı zamanda matematiksel veya mantıksal problemlerdir. Her bulmacanın kendine özgü bir mantığı ve matematiği vardır. Altta yatan mantığı kavrayıp modelleyebildiğimizde bulmacalar daha anlaşılır hale gelir. Bu nedenle bulmacalar bilim insanlarının ilgisini çeken bir araştırma alanı oluşturmaktadır. Mantık bulmacalarından biri de Survo bulmacasıdır. Bu bulmacayı oluşturmak ve çözmek için bir tamsayılı doğrusal programlama modeli formüle edilmiştir. Formülasyonun geçerliliğini göstermek için açıklayıcı örnekler verilmiştir. Modelin etkinliği internette bulunan Survo bulmacaları çözülerek test edilmiştir. Çözümler kısa işlemci sürelerinde elde edilmiştir. Daha sonra, modellerin etkinliği deneysel hesaplamalar kullanılarak analiz edilmiştir. Hesaplama sonuçları bir dizi Survo bulmaca örneği üzerinden elde edilmiştir. Önerilen matematiksel model, 50x50 boyutuna kadar bulmacaları kısa CPU sürelerinde, maksimum 254 saniyede üretmiştir. 15x15 boyutuna kadar olan bulmacalar çözülmüştür.

Puzzles are often generated for entertainment but also mathematical or logical problems. Every puzzle has its logic and mathematics. Puzzles become more understandable when we can grasp and model the underlying logic. For this reason, puzzles constitute a research area of interest to scientists. One of the logic puzzles is the Survo puzzle. We have formulated an integer linear programming model to generate and solve this puzzle. Illustrative examples have been given to show the validity of the formulation. The model’s effectiveness has been tested by solving Survo puzzles available on the internet. The solutions have been obtained in short CPU times. Then, the effectiveness of the model has been analyzed using experimental computations. The computational results have been obtained from a number of Survo puzzle instances. The proposed mathematical model has generated puzzles up to 50x50 size in short CPU times, a maximum of 254 seconds. Puzzles up to size 15x15 have been solved.