@1a@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ÚÓ‘Ój�n€a@Î@Úœäñ€a@‚Ï‹»‹€@·rÓ:a@Âig@Ú‹©@Ü‹26@@ÖÜ»€a@I1@‚b«@H2013 Ibn Al-Haitham Jour. for Pure & Appl. Sci. Vol. 26 (1) 2013 Using Magic Square of Order 3 To Solve Sudoku Grid Problem Israa N. Alkallak Department of Basic Sciences / College of Nursing / University of Mosul Received in: 19 June 2011, Accepted in : 15 October 2012 Abstract The research tackled to solve Sudoku grid problem 9×9 , one of artificial intelligence problems. This problem has many of solutions in search space to generate Sudoku grid by using magic square of odd order as 3. This research concludes solution by proposed heuristic algorithm from magic square of odd order as 3 and no given numbers (from 1 to 9) in each cell of nine Sudoku grid cells in starting of problem solution, this is not similar the solution in old classic methods to generate all sub grids in Sudoku grid. The experimental results in this paper show the easily implementation to solve the problem to manage without manual method, additional to position of numbers (1, 2,..9) in center of each sub grid in Sudoku grid (the second element from second row and second column), and without duplicate each of sub grid in arranging of numbers. A program is written in MATLAB 6.5 language to simulate the proposed algorithm. Key words : Sudoku grid, heuristic. 358 | Computer Science @1a@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ÚÓ‘Ój�n€a@Î@Úœäñ€a@‚Ï‹»‹€@·rÓ:a@Âig@Ú‹©@Ü‹26@@ÖÜ»€a@I1@‚b«@H2013 Ibn Al-Haitham Jour. for Pure & Appl. Sci. Vol. 26 (1) 2013 Introduction Artificial intelligence has directly influenced many areas of computer science [1]. The general problem of solving Sudoku on n2 ×n2 boards of n×n blocks is known to be NP- complete. The solution method that solve very quickly the 9×9 boards take exponential time in the board size in the worst case [2]. Sudoku was originally named Number Place, was created by Howard Garnes in the U.S. In 1979 and was first published later that year in Dell Pencil and Puzzle Games [3]. At first, interest in Sudoku was minimal until it reappeared in print and was given its current name by the Japanese publisher Nikoli in 1984. The game grew in popularity in Japan and was renamed by publisher Nikoli to "suji wa dokushin ni kagiru" which is translated as the "the digits must remain single". This was eventually shortened to "Sudoku" or " single number " [1,4,5,6,7]. Sudoku most commonly appears in its 9×9 matrix form. The rules simply fill in the matrix so that every row, column, and 3×3 sub matrix contains the digits 1 through 9 exactly once. Each puzzle appears with a certain number of "givens". The number and location of these determine the game level of difficultly. Figure (1) is an example of 9×9 Sudoku puzzle with 9 regions. The object of Sudoku is simply given an n2× n2 grid is divided into n× n distinct square, the aim is to fill each cell. Sudoku is a logic puzzle that has a great deal of appeal and is easily encoded as constraint satisfaction problem domain [1]. The goal of the game is to fill in every empty grid location with a number from 1 through 9 that the values in each column, row, and 3-by-3 subregion are unique. The subregions are determined by subdividing the 9-by-9 grid into 9 (3-by-3) mini-grids [1]. Heuristic algorithm is an algorithm that is able to produce an acceptable solution to a problem in many practical scenarios, in the fashion of a general heuristic, but for which there is no formal proof of its correctness acceptance method is taken as an optimal solution to the specified problem. The research aims to show how can Sudoku problem to be solved efficiently mathematically and by computer. Proposed algorithm solves this problem through magic square and several operations as well as in the starting of solution, the Sudoku grid is empty. In this research, besides this introductory section, Sudoku problem, magic square and heuristic algorithm are described in section 2. Section 3 presents the proposed algorithm. Experimental results and discussions are examined in section 4. Finally, section 5 concludes this paper. Sudoku Problem Sudoku is a popular logic based combinatorial optimization problem [4,5,6,8]. Sudoku problem is known to be NP-complete [4,6]. The puzzle starts with certain locations filled it, which can be a great number or very few depending on the puzzle complexity [1,5]. A Sudoku puzzle consists of (81) cells, contained in a 9×9 grid. Each cell contains a single integer ranging between one and nine. The grid is further split up into nine 3×3 sub grids. The purpose of Sudoku is to fill up the entire 9×9 grid such that the following constraints are met: 1. Each row of cells is only allowed to contain the integers one through to nine exactly once. 2. Each column of cells is only allowed to contain the integers one through to nine exactly once. 3. Each 3×3 sub grid is also only allowed to contain the integers one through to nine exactly once [2,4,5,6,8] Magic Squares Magic square is a square matrix n×n with integer elements between 1 and n2 and where the sums of the elements of all lines, columns and the two main diagonals are equal to the magic sum (magic constant) which is given by the rule: [9]. 359 | Computer Science @1a@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ÚÓ‘Ój�n€a@Î@Úœäñ€a@‚Ï‹»‹€@·rÓ:a@Âig@Ú‹©@Ü‹26@@ÖÜ»€a@I1@‚b«@H2013 Ibn Al-Haitham Jour. for Pure & Appl. Sci. Vol. 26 (1) 2013 Cn = n (n2 +1)/2 The symbol Cn denoted the magic sum (magic constant), also an order n magic square is an n-by-n matrix containing the numbers 1 to n2, where each row, column and main diagonal are equal to the same sum. The Figure (2) shows a sample magic square with n = 3, where the magic sum (C3) is 15. This line sum invariance depends only on the order n, of the magic square [10]. MATLAB 6.5 language actually has a built in function that creates magic squares of almost any size. This function is named magic. Below Figure (3) illustrates several samples of magic square. Heuristic Algorithm The term “heuristic” stands for “thumb rules” the rules which work successfully in many cases but its success is not guaranteed [11]. Heuristic algorithms (or simply heuristics) have to be used in order to find near-optimal (locally optimal) solutions. Heuristic algorithms seek for high quality solutions at a reasonable computational time, but cannot guarantee that a problem will be solved in terms of obtaining the exact solution. It may not even be possible to state how close to optimality a particular heuristic solution is. Heuristic algorithms can also be seen as intelligent techniques that are based upon human’s intuition [12,13,14,15]. A heuristic is a kind of an algorithm, but one that will not explore all possible states of the problem, or will begin by exploring the most likely ones. A heuristic has no proof of correctness, often involves random elements, and may not yield optimal results. A heuristic method is used to rapidly come to a solution that is hoped to be close to the best possible answer, or (optimal solution). The proposed Algorithm The research proposed ten steps to solve Sudoku grid problem 9×9 by using magic square of odd order as 3 as follows: Step 1: Initializes the Sudoku grid is empty. Step 2: Generates the first sub grid (first region) in Sudoku by magic square of odd order 3. Step 3: Generates the second sub grid (second region) in Sudoku grid by rotating the matrix (sub grid) in step 2. Third, second and first rows are first, third and second rows respectively. Step 4: Generates the third sub grid (third region) in Sudoku grid by rotating the matrix (sub grid) in step 3. Third, second and first rows are first, third and second rows respectively. Step 5: Generates the fourth sub grid (fourth region) in Sudoku grid by shifting to right the matrix (sub grid) in step 2. First, second and third columns are second, third and first columns respectively. Step 6: Generates the fifth sub grid (fifth region) in Sudoku grid by shifting to right the matrix (sub grid) in step 3. First, second and third columns are second, third and first columns respectively. Step 7: Generates the sixth sub grid (sixth region) in Sudoku grid by shifting to right the matrix (sub grid) in step 4. First, second and third columns are second, third and first columns respectively. Step 8: Generates the seventh sub grid (seventh region) in Sudoku grid by shifting to left the matrix (sub grid) in step 2. Third, second and first columns are second, first and third columns respectively. Step 9: Generates the eighth sub grid (eighth region) in Sudoku grid by shifting to left the matrix (sub grid) in step 3. Third, second and first columns are second, first and third columns respectively. Step 10: Generates the ninth sub grid (ninth region) in Sudoku grid by shifting 360 | Computer Science @1a@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ÚÓ‘Ój�n€a@Î@Úœäñ€a@‚Ï‹»‹€@·rÓ:a@Âig@Ú‹©@Ü‹26@@ÖÜ»€a@I1@‚b«@H2013 Ibn Al-Haitham Jour. for Pure & Appl. Sci. Vol. 26 (1) 2013 to left the matrix (sub grid) in step 4. Third, second and first columns are second, first and third columns respectively. Experimental Results and Discussion In this research, all cells in Sudoku grid are empty. This empty increase the game level of difficultly but the proposed algorithm solved easily. To illustrate the steps in proposed algorithm, below Figure (4) illustrates first step. Figure (5) illustrates the second, third and fourth steps. While Figure (6) illustrates the fifth, sixth and seventh steps. In addition, Figure (7) illustrates the eighth, ninth and tenth steps. The object of the game is to place the numbers 1 through 9 on the grid so that each column, row, and each 3x3 sub grid contains the digits only once. The proposed solution facilitates the difficultly in solving the problem that satisfied the constraints of the problem. Figure (8) illustrates problem solution completely. When select any sample of magic square in Figure (3), the proposed algorithm runs and generates the solution of Sudoku grid which accordingly concludes the best solution and also number position (1,---9) in center (the second element from second row and second column) of each sub grid in Sudoku grid, without duplicating each of sub grid in arranging of numbers. Appendix (a) illustrates two solutions by selecting other samples of magic square for proposed algorithm. Conclusion Sudoku problem can be solved efficiently by proposed algorithm and thus minimizes the search space. A computer can solve this problem by using the proposed algorithm very quickly. The proposed algorithm is the best technique to solve Sudoku problem because an interesting to find feasible solution satisfying constraints of the problem. Magic square facilities to create the solve. The proposed method provides to solve a Sudoku problem very easily rather than solving the problem with pencil, paper, and difficult for human solver. All references about the Sudoku problem noticed some static numbers givens in the puzzle that are given according to the difficulty rating in the initial Sudoku configuration. The number and location of these determine the game level of difficultly, but in this research, the proposed method supposes empty all positions in Sudoku grid. Often heuristics do not guarantee you that will lead you to the correct answer, but the proposed algorithm often gets answer which is close to the best in much shorter time. Here, the proposed algorithm is efficient algorithm to find a solution that yields near-optimal results very quickly. References 1. Teaching Artificial Intelligence Across the Computer Science Curriculum Using Sudoku as a Problem Domain: Pfaffmann, J. O. and Collins, W. J., (2007), American Association for Artificial Intelligence, :327-332. www.aaai.org. 2. Geometric Particle Swarm Optimization for the Sudoku Puzzle: Moraglio, A. and Togelius, J., (2007), ACM, GECCO 2007 Workshop on Theory of Representations, :118-125. http://julian.togelius.com/Moraglio2007Geometric.pdf. 3. Garns, H., (1979), Number Place. Dell Pencil Puzzle & Word Games, 16,6. 4. Metaheuristics Can Solve Sudoku Puzzles: Lewis R., (2007), Journal of Heuristics Archive, 13 (4), :387-401. 5. Sloving and Rating Sudoku Puzzles with Genetic Algorithms, Mantere, T. and Koljonen, J., (2006), Proceedings of the 12th Finish Artificial Intelligence Conference STeP. Hut, Espoo, Finland, October 26-27, , :86-92. 6. http://www.sets.fi/scai2006/proceedings/STeP2006-86-mantere-solving-and-rating-sudoku- puzzles.pdf. 361 | Computer Science http://www.aaai.org/ http://julian.togelius.com/Moraglio2007Geometric.pdf http://www.sets.fi/scai2006/proceedings/STeP2006-86-mantere-solving-and-rating-sudoku-puzzles.pdf http://www.sets.fi/scai2006/proceedings/STeP2006-86-mantere-solving-and-rating-sudoku-puzzles.pdf @1a@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ÚÓ‘Ój�n€a@Î@Úœäñ€a@‚Ï‹»‹€@·rÓ:a@Âig@Ú‹©@Ü‹26@@ÖÜ»€a@I1@‚b«@H2013 Ibn Al-Haitham Jour. for Pure & Appl. Sci. Vol. 26 (1) 2013 7. Solving Sudoku Puzzles with Rewriting Rules, Santos-Garcia, G. and Palomino, M., (2007), Electronic Notes in Theoretical Computer Science, , 17(4), :79-93. www.elsevier.nl/locate/entcs. 8. Sudoku Easy Presented by Will Shortz , Shortz, W. (2005),. New York, NY: St. Martin's Griffin. 1,100. 9. Lawler, E.L.; Lentra, J.K.; Rinnooy, A. H.G. and Shmoys, D.B. (eds.), (1985), The Traveling Salesman Problem_ A Guided Tour of Combinatorial Optimization, John Wiley & sons, New York. 10. Magic Rectangles and Modular Magic Rectangles, Evans, A. B., (1996), Journal of Statistical Planning and Inference, 51, :171-180. 11. Franklin Squares- A chapter in the Scientific Studies of Magical Squares, Complex Systems publications, Loly, P., (2007), , Inc., 17, :143-161. 12. Konar, A. (2000), Artificial Intelligence and Soft Computing Behavioral and Cognitive Modeling of the Human Brain, CRC Press, Boca Raton London New York Washington, Printed in USA. :129. 13. Michalewicz, Z. and Fogel, D. B., (2000), How to Solve It: Modern Heuristics, Springer, Berlin-Heidelberg. 14. Meta-Heuristics Theory and Applications, Osman, I. H. and Kelly, J. P., (1996), Meta- Hueristics: An Overview. In I. H. Osman, J. P. Kelly (eds.), Kluwer, Norwall, 1-21. 15. Reeves, C. R., (1996), Modern Heuristics Techniques. In V. J. Rayward-Smith, I. H. Osman, C. R. Reeves, G. D. Smith (eds.). Modern Heuristics Search Methods, Wiley, Chichester, 1-25. 16. An Overview of Some Heuristic Algorithms for Combinatorial Optimization Problems, Misevicius, A.; Blazauskas, T.; Blonskis, J. and Smolinskas, J., (2004), Informacines Technologijos IR Valdymas, Nr. 1(30), ISSN 1392-124X, :21-31. 1 2 3 4 5 6 7 8 9 Fig.(1): Sudoku Board Grid with 9 Regions 2 7 6 magic sum =15 9 5 1 magic sum =15 4 3 8 magic sum =15 magic sum = 15 magic sum = 15 magic sum = 15 magic sum = 15 magic sum =15 Fig.(2): Magic Square of Order 3 362 | Computer Science http://www.elsevier.nl/locate/entcs @1a@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ÚÓ‘Ój�n€a@Î@Úœäñ€a@‚Ï‹»‹€@·rÓ:a@Âig@Ú‹©@Ü‹26@@ÖÜ»€a@I1@‚b«@H2013 Ibn Al-Haitham Jour. for Pure & Appl. Sci. Vol. 26 (1) 2013 4 9 2 2 7 6 6 7 2 8 1 6 3 5 7 9 5 1 1 5 9 3 5 7 8 1 6 4 3 8 8 3 4 4 9 2 4 3 8 2 9 4 6 1 8 8 3 4 9 5 1 7 5 3 7 5 3 1 5 9 2 7 6 6 1 8 2 9 4 6 7 2 Fig.(3): Magic Square of Odd Order 3 Samples Fig.(4): An initial Sudoku configuration is empty 2 7 6 4 3 8 9 5 1 9 5 1 2 7 6 4 3 8 4 3 8 9 5 1 2 7 6 6 2 7 8 4 3 1 9 5 1 9 5 6 2 7 8 4 3 8 4 3 1 9 5 6 2 7 7 6 2 3 8 4 5 1 9 5 1 9 7 6 2 3 8 4 3 8 4 5 1 9 7 6 2 Fig.(5): Illustrates first, second and third region Fig.(6): Illustrates fourth, fifth and sixth region Fig.(7): Illustrates seventh, eighth and ninth region 363 | Computer Science @1a@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ÚÓ‘Ój�n€a@Î@Úœäñ€a@‚Ï‹»‹€@·rÓ:a@Âig@Ú‹©@Ü‹26@@ÖÜ»€a@I1@‚b«@H2013 Ibn Al-Haitham Jour. for Pure & Appl. Sci. Vol. 26 (1) 2013 2 7 6 4 3 8 9 5 1 9 5 1 2 7 6 4 3 8 4 3 8 9 5 1 2 7 6 6 2 7 8 4 3 1 9 5 1 9 5 6 2 7 8 4 3 8 4 3 1 9 5 6 2 7 7 6 2 3 8 4 5 1 9 5 1 9 7 6 2 3 8 4 3 8 4 5 1 9 7 6 2 Fig.(8): Sudoku grid solution Appendix (a) illustrates two solutions, after the proposed algorithm run on other samples of magic square. 8 1 6 4 9 2 3 5 7 3 5 7 8 1 6 4 9 2 4 9 2 3 5 7 8 1 6 6 8 1 2 4 9 7 3 5 7 3 5 6 8 1 2 4 9 2 4 9 7 3 5 6 8 1 1 6 8 9 2 4 5 7 3 5 7 3 1 6 8 9 2 4 9 2 4 5 7 3 1 6 8 Solution 1 4 9 2 8 1 6 3 5 7 3 5 7 4 9 2 8 1 6 8 1 6 3 5 7 4 9 2 2 4 9 6 8 1 7 3 5 7 3 5 2 4 9 6 8 1 6 8 1 7 3 5 2 4 9 9 2 3 1 6 8 5 7 3 5 7 4 9 2 4 1 6 8 1 6 8 5 7 3 9 2 4 Solution 2 364 | Computer Science @1a@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ÚÓ‘Ój�n€a@Î@Úœäñ€a@‚Ï‹»‹€@·rÓ:a@Âig@Ú‹©@Ü‹26@@ÖÜ»€a@I1@‚b«@H2013 Ibn Al-Haitham Jour. for Pure & Appl. Sci. Vol. 26 (1) 2013 لحل مسألة شبكة سودوكو 3استخدام مربع ماجك ذو الترتیب إسراء نذیر الكالك جامعة الموصل/ كلیة التمریض/ فرع العلوم األساسیة 2012تشرین األول 15البحث في قبل ، 2011حزیران 19استلم البحث في الخالصة الت�ي تع�د إح�دى مس�ائل ال�ذكاء االص�طناعي، إذ تمل�ك كم�اً ھ�ائالً م�ن 9×9تطرق البحث إلى حل مسألة ش�بكة س�ودوكو ، تمخض البحث إلى حل المسألة من خالل خوارزمیة 3الحلول لتولید تلك الشبكة، بأستخدام مربع ماجك ذو الترتیب الفردي وم�ن دون تخص�یص أي ع�دد (م�ن الواح�د إل�ى التس�عة) ألی�ة 3ینیة مقترحة ناتجة من مربع ماجك ذي الترتی�ب الف�ردي تخم خلیة من خالیا شبكة سودوكو عند بدای�ة ح�ل المس�ألة، وھ�ذا خالف�اً للح�ل ف�ي الطرائ�ق التقلیدی�ة الس�ابقة، وذل�ك لتولی�د جمی�ع نتائج البحث التوصل إل�ى الس�ھولة المتاح�ة ف�ي ح�ل المس�ألة واألس�تغناء الشبكات الفرعیة األخرى في شبكة سودوكو. أثبتت عن الطرائق الیدویة، فضالً عن تموضع األعداد (م�ن الواح�د إل�ى التس�عة) ف�ي مرك�ز ك�ل ش�بكة فرعی�ة م�ن ش�بكة س�ودوكو برن��امج حاس�وبي بلغ��ة . أُع�د ، وع�دم تك�رار أی��ة ش�بكة فرعی�ة بترتی��ب أرقامھ�ا(العنص�ر الث�اني م��ن الص�ف والعم�ود الث��اني) لیحاكي الخوارزمیة المقترحة. 6.5ماتالب شبكة سودوكو، ھیورستك. : الكلمات المفتاحیة 365 | Computer Science