An Efficient Sudoku Solver Application Based on Graph Theory

Year 2021, , 218 - 224, 31.12.2021

Mustafa Batar

https://doi.org/10.46460/ijiea.982908

Abstract

This article has explained in detail what the puzzle of Sudoku is – the meaning of Sudoku –, where it comes from – the origin of Sudoku – and how it can be solved – the solution way of Sudoku. Especially, this paper has analyzed the solution of the problem – Sudoku can be taken as a problem – based on the graph theory. This theory consists of several algorithms, methods, rules and principles which are about the graph in general. In addition, this study has focused on the Welsh-Powell algorithm – greedy coloring algorithm – and Karger’s algorithm – contraction algorithm – among those graph algorithms by trying to give explanations about them (these two methods). Also, based on the rules and principles of those two algorithms, “Sudoku Solver Application” has been designed and developed in order to solve the puzzle of Sudoku. Moreover, the paper has presented a specific solution way of the puzzle Sudoku, and has showed its efficiency and usability by showing complexity and run time of the application among several available solutions based on the graph theory. So, the study has offered “Sudoku Solver Application” to the game world, science world, and education world as well for its use.

Keywords

Graph theory, Sudoku, Welsh-Powell algorithm, Karger’s algorithm.

Grafik Teorisine Dayalı Etkin Bir Sudoku Çözücü Uygulaması

Abstract

Bu makale, Sudoku bulmacasının ne olduğunu (anlamını), nereden geldiğini (kökenini) ve nasıl çözülebileceğini (çözüm yolunu) açıklamaktadır. Özellikle, problemin çözümünü – Sudoku bulmacası bir problem olarak ele alınabilir – grafik teorisine dayalı olarak analiz etmektedir. Bu teori, genel olarak grafiklerle ilgili çeşitli algoritmalar, yöntemler, kurallar ve ilkelerden oluşmaktadır. Ayrıca, grafik algoritmalarından Welsh-Powell (açgözlü renklendirme algoritması) ve Karger (daraltma algoritması) algoritmaları üzerinde durularak bu iki yöntem hakkında bu çalışmada detaylı bir bilgilendirme yapılmıştır. Bununla birlikte, bu iki algoritmanın kural ve prensipleri dikkate alınarak, bu makalede, “Sudoku Çözücü Uygulaması” tasarlanmış ve geliştirilmiştir. Ayrıca, uygulamanın çalışma süresi hesaplanıp etkinliği ve kullanılabilirliği ortaya konmuştur. Buna ek olarak, bu çalışma, Sudoku bulmacasının belirli bir çözüm yolunu grafik teorisine dayalı algoritmalar yardımıyla bulup, kullanımı için hem oyun dünyasına, hem bilim dünyasına, hem de eğitim dünyasına sunmuştur.

Keywords

Grafik teorisi, Sudoku, Welsh-Powell algoritması, Karger algoritması.

References

• Maji, A., Roy, S., & Pal, R. (2013). A novel algorithmic approach for solving Sudoku puzzle in guessed free manner. European Academic Research, 1(6), 1126-1154.
• Semeniuk, I. (2005). Stuck on you. New Scientist, 31, 45-47.
• Mandal, S., & Sadhu, S. (2013). Solution and level identification of Sudoku using harmony search. International Journal of Modern Education and Computer Science, 5(3), 49-55.
• Mandal, S., & Sadhu, S. (2011). An efficient approach to solve Sudoku problem by harmony search algorithm. An International Journal of Engineering Sciences, 4, 312-323.
• Crook, J. F. (2009). A pencil-and-paper algorithm for solving Sudoku puzzles. Notices of the American Mathematical Society, 56(4), 460-468.
• Majumder, A., Kumar, A., Das, N., & Chakraborty, N. (2010). The game of Sudoku-advanced backtrack approach. International Journal of Computer Science and Network Security, 10(8), 22-33.
• Herzberg, A. M., & Murty, M. R. (2007). Sudoku squares and chromatic polynomials. Notices of the AMS, 54(6), 708-718.
• Deng, X., Li, J., & Li, G. (2013). Research on Sudoku puzzles based on metaheuristics algorithm. Journal of Modern Mathematics Frontier (JMMF), 2(1), 25-32.
• Crawford, B., Castro, C., & Monfroy, E. (2013). Solving Sudoku with constraint programming. In Y. Shi, S. Wang, Y. Peng, J. Li, & Y. Zeng (Eds.), Cutting-Edge Research Topics on Multiple Criteria Decision Making SE - 52, 35, 345-348.
• Deng, X., Li, Y., & Cai, R. (2011). Solving Sudoku puzzles based on improved genetic algorithm. Comput. Appl. Softw, 28(3), 68-70.
• Lewis, R. (2007). Metaheuristics can solve Sudoku puzzles. Journal of Heuristics, 13(4), 387-401.
• Pillay, N. (2012). Finding solutions to Sudoku puzzles using human intuitive heuristics. South African Computer Journal, 49, 25-34.
• Soto, R., Crawford, B., Galleguillos, C., Monfroy, E., & Paredes, F. (2013). A hybrid AC3-tabu search algorithm for solving Sudoku puzzles. Expert Systems with Applications, 40(15), 5817-5821.
• Boryczka, U., & Juszczuk, P. (2012). Solving the Sudoku with the differential evolution. Zeszyty Naukowe Politechniki Białostockiej. Informatyka, 9, 5-16.
• Deng, X., & Li, Y. (2013). A novel hybrid genetic algorithm for solving Sudoku puzzles. Optimization Letters, 7(2), 241-257.
• Rosenhouse, J, & Taalman, L. (2011) Taking Sudoku seriously: The math behind the world’s most popular pencil puzzle. Oxford University Press.
• Olariu, S., & Randall, J. (1989). Welsh-Powell opposition graphs. Information Processing Letters, 31(1), 43-46.
• Zhou, S. (1999). A sequential coloring algorithm for finite sets. Discrete Mathematics, 199(1-3), 291-297.
• Karger, D. R., Klein, P. N., & Tarjan, R. E. (1995). A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM, 42(2), 321-328.
• Neumayera, S., Efrat, A., & Modianoa, E. (2015). Geographic max-flow and min-cut under a circular disk failure model. Computer Networks, 77, 117-127.
• Karger, D. R., & Motwani, R. (1997). An $\NC$ algorithm for minimum cuts. SIAM Journal on Computing, 26(1), 255-272.
• Karger, D. R. (1999). Random sampling in cut, flow, and network design problems. Mathematics of Operations Research, 24(2), 383-413.
• Doumont, J., & Vandenbroeck, P. (2002). Choosing the right graph. IEEE Transactions on Professional Communication, 45(1), 1-6.
• Sharieh, A., & Sabri, K. E. (2008). Parallel graph colouring based on saturated degree ordering. Basic Sci. & Eng., 17(2), 489-503.
• Yamamoto, T., Brewster, R., & Safran, S. A. (2010). Chain ordering of hybrid lipids can stabilize domains in saturated/hybrid/cholesterol lipid membranes. EPL (Europhysics Letters), 91(2).
• Omari, H., & Sabri, K. E. (2006). New graph coloring algorithms. American Journal of Mathematics and Statistics, 2(4), 439-441.