AN INTEGER PROGRAMMING FORMULATION FOR GENERATING AND SOLVING SURVO PUZZLE

Abstract

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.

Alternate 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.