Question

Su Doku Problem 96 Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult puzzle idea called Latin Squares. The objective of Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid and its solution grid. 0 0 3 0 2 0 6 0 0 90 03 0 5 0 0 1 0 0 1 8 0 6 4 0 0 OO81 0 29 0 0 7 0 0 0 0 0 0 0 8 0 0 67 08200 0 0 260 95 0 0 80 02 03 00 9 0 0 50 10300 4 8 319 2 11 6 5 7 9 6 7 3 4 5 8 2 1 2 5 1 8 7 6 4 9 3 1 3 29 76 15 6 41 1 3 6 7 9 8124 3 7 2 6 8 915 1 4 81 412 5 37 69 6 9 5 4 1 73 8 2 N inco A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ "guess and test" methods in order to eliminate options (there is much contested opinion over this). The complexity of the search determines the difficulty of the puzzle; the example above is considered easy because it can be solved by straight forward direct deduction The 6K text file, sudoku.txt (right click and 'Save Link/Target As..."), contains fifty different Su Doku puzzles ranging in difficulty, but all with unique solutions (the first puzzle in the file is the example above). By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left comer of each solution grid; for example, 483 is the 3-digit number found in the top left corner of the solution grid above.

Answer 1

this is the full explanation of suduku using java algoritim
Introduction Sudoku puzzle is a puzzle that uses player's logical thinking to solve it. They need to insert a number according to its rule. Sudoku is a popular game since it has more than 97 million results in Google search. Playing the Sudoku will improve the capabilities of thinking logically and critically. Sudoku game will enhance mathematical skills and confidence to the players. There are no specific mathematical calculations required to solve Sudoku, but it will use some of mathematical methods and techniques depending on the type of Sudoku that being played. According to Jr. (2005), Sudoku comes from the Japanese words which are "su" and "doku", means "number" and "single". In English, it is also being called as “number place". Sudoku presented with square grid. Inside the square grid there is a single square. Basically, Sudoku contains various sizes of grid such as 4x4 grids, 8x8 grids up to 100x100 grids. But 9x9 grids are the most popular among others. There are many types of Sudoku that have been invented such as the normal Sudoku, Geometry Sudoku, Diagonal Sudoku and others. 29 13 4 15 13 Figure 1: Normal Sudoku Figure 2: Diagonal Sudoku Sudoku have been found in United States and United Kingdom many years ago and before it became in Japan. Around 1070's, the first publisher of Sudoku in New York was "Dell Magazines". Dell published Sudoku in its Math Puzzles and Logic Problems magazines using the named as "Number Place". The first designer of the Sudoku is unknown, but Walter Mackey was one of the constructors of Sudoku puzzles in Dell's Magazine. In 1984, Sudoku was first introduced in Japan by Nikoli. Currently, there are five Sudeku magazines that have been published in Japan every month with a total circulation over 600.000. Semeniuk (2005) claim that the huge popularity of Sudoku mainly because it is very challenging puzzle but have a very simple rule. Sudoku was very popular, se many people examine and studies about Sudoku. They studied and designed many methods to complete this game. Most of the method that will be used is mathematics. From those studied. Sudoku and mathematics are related to cach other. There are so many mathematical techniques used to construct or to solve Sudoku. From the different sources that have been found, most of the researchers were discuss about the mathematical techniques that commonly involve in the Sudoku games which are Permutations, Latirn Square and Enumeration. This method has been invented te determine the number of invented methods are confirmed by liuckvale (2005) that stated, a good Sudoku puzzle is one that can be solved without guessing method. sible unique grids that will exist inside the Sudoku. All these Simonis (2005) is one of the first who published Sudoku based paper in the computer science literature. Ile has formulated sudoku as a constraint satistaction problem. This work has been continued by 1.vnce (2006). They show that Sudoku puzzle can be solved using propositional satistiability techniques. This technique demonstrated on how individual Sudoku puzzle may be converted into conjunctive normal form. 72

One of the advantages of playing this puzzle is high ability in solving logical problems. This is the reason why Sudoku puzzle is commonly used by parents to educate their children during free time. With the popularity of Sudoku, there are various competition that has been held world wide. In order to solve Sudoku puzzle, we must know the technique that basically use in solving the puzzle in a fastest way. Most of the techniques that player used are difficult to understand. Thus, the player will solve the puzzle in longest time. Other than using the Human Solvers' solution to solve a Sudoku puzzle, a player can retrieve the solution by using Computer's Solution. Algorithms to achieve the solutions will be needed in order to construct the Computer's Solution programs. Some of the algorithms are likely to imitate the human solver methods by showing the step by step solving methods, while others are using the guessing strategy that will find and directly show the solution for the given puzzle. Solving a Sudoku puzzle with the aid of some computer's solver can achieve the solution casily. Due to technology sophisticated, this games not only available in the newspapers, but it is can be found on a computer via internet and digital games via application. Various programming language are used in order to construct the digital games. The programming language commonly used in constructing Sudoku games are Java, Hypertext Markup Language (HTML) and C or C++. All programming language will not give the same result. The result of the games is related to the algorithm of finding the solutions to the puzzle. This paper focus to 9x9 grids Diagonal Sudoku and Java programming language will be used to solve the 9x9 grids of diagonal Sudoku. It can help many people to solve diagonal Sudoku by using Java language. Therefore, the objective of this paper is to construct a diagonal Sudoku solver program using Java programming language. Literature Review Lawler et al (1985), stated that Sudoku is a combinatorial optimization problem. In order to solve a normal Sudoku puzzle, the number 1 until 9 must be filled up in all grids with no number duplication conflict in the row, column and box (a 3x3 grid inside the Sudoku puzzle). In other hands, to solve the diagonal Sudoku not only all the above rule have to been considered but number 1 until 9 must also be fill in a diagonal place and we have to make sure the number does not conflict with other grid in its diagonal region. Diagonal place is a set of grid which start from the most upper-left or bottom-left to the most upper-right or bottom-right of the puzzle. According to Sopitan (2012), there is a question about how many possible Sudoku puzzle can be created. In order to know how many of possible diagonal Sudoku puzzles can be made, some permutations must be used while considering the the symmetrical of a Sudoku grid. By applying a brute-force computation, the result of valid Sudoku grids arrived at 6670903752021072936960 (6.67 x 10). Furthermore. Sopitan (2012) claim that the minimum number givens or hints must be at least 17-hints number in erder to achieved a unique solution for a diagonal Sudeku. Therefore. the puzzle can be considered valid if the puzzle has unique solution. Unfortunately. he said that Sudoku puzzle has the minimum number of clues, which is seventeen dees not truly has unique solution because the choice of seventeen as the minimunm number of required clues must have for a puzzle is just a general acceptance among the Sudoku enthusasts. According to Semeniuk (2005). the number of given hint does net determine the level el diliculiy of the pazzle.

3 / 12 66.7% Sopitan (2012) has categorized human solvers' solution into two categories. There are Logical Deduction and Process of Elimination. Logical deduction is a process that can achieve the solution value for the grids, while process of elimination is to reduce the possible numbers (which will be called "candidate" later on) in certain grids. Davis (2005) has discussed about techniques that can be used, the situation effect to the techniques used, the outcome by applying the techniques, and others. He also stated that not all techniques can be used in order to achieve the solution. Meanwhile, to achieve some solutions from certain puzzle, especially the hard and diabolic level puzzle, he suggested to use almost all the techniques that has been discussed. Rhyd (2007) has invented the first application of a metaheuristic technique in order to solve the puzzle. He use simulated annealing to complete logic-solvable puzzle. The other methods that can be used are Genetic Algorithm (GA). Many researcher have been using GA to solve the puzzle. Mantere (2006), has run a test to find if a genetic algorithm optimization is an efficient method to solve sudoku and generate the Sudoku puzzle. They also investigate whether Sudoku puzzle are difficult for human solver and difficult to solve using genetic algortihm. In 2006, Nicolau (2006) has presented a different approach to solve this puzzle. They optimizes the sequence of logical operations and applied it to find the solution by developing a system named GAUGE (Genetic Algorithm using Grammatical Evolution). Perez (2008), they have been using four different methods. There are cultural genetic algorithm, repulsive particle swarm optimization, quantum simulated annealing and genetic algortihm or simulated annealing hybrid (HGASA). By applying all methods, the result indicated that HSAGA was the most efficient method to solve the puzzle. Mantere (2009) has also proposed another method to solve the puzzle using evolutionary algorithm (EA) example genetic algorithm (GA), cultural algorithm (CA), optimization(ACO) and genetic algorithm or ant colony optimization hybrid (GA/ACO). Based on these methods, the researcher found that GA/ACO method is the most efficient of all. Xiu (2011) has improved the previous method by using hybrid genetic algorithm. However, Gold (2005) stated that genetic algorithm seem inefficient since it need 35700 generations to come up with a new puzzle. colony ant Another approach that can be used is Artificial Bee Colony algorithm. This algorithm was first developed in 2005. Jaysonne (2009), has explored the possibility of using improved variant of the Artificial Bee Colony algorithm. He concluded that this algorithm can be used to solve Sudoku problem effectively and efficiently. According to Li (2009), they have introduced a graph search strategy on the basic of knowledge representation and deduction base in artificial intelligence. Methodology This study has introduced algorithm to solve diagonal Sudoku 9x9 grid. This algorithm created by using guessing method with backtracking approach for constructing Java programming language. According to Sopitan (2012), some of the computer's solvers algorithms that solve Sudoku puzzles imitate the human solver while others use the guessing strategy. Guessing involves inserting values and secing if they lead to a solution. If breaks diagonal sudoku rules, another guess must be made. This strategy is for human selver because a guess could look correct until very late into solving of puzzle until at which point, it become almost impossible to keep in track. Ilowever, this strategy is much casier for computer to handle due to its processing power. Carpenter (2013) has used Java programming language to develop his Sudoku solver program by using guessing algorithm with bactracking appreach. Algarithm for solving diagonal Sudoku puzrle is really difficult

4 / 12 66.7% similarly to the standard Sudoku puzzle. Due to some of differences of rule to solve, some modification from the algorithm to solve the standard one has been made due to the rules to get the diagonal Sudoku solver's algorithm. The diagonal Sudoku puzzle that being used in this paper is 9x9 grids, it is square and has two dimensions (2D). Thus, to construct the coding for this paper, 2D-arrays has been used to store all the value for the Sudoku puzzle in the correct order due to its ability to store several values with same data type in a single variable in 2D. To implement this coding, the coordinate of the Sudoku puzzle grids is needed in order to put them in 2D-arrays in the coding. The coordinate of the grids is stated in the figure 3. (2) (201 1211 122 (231 2 125) 1216) (2][*] (2][8] [4 (41ro1 (41| (42) (41 4(4 141 1461 14 (4[8] [61 6101 16U 16121 16131 1614] 1651 (5161 161I 161181 Figure 3: Grids Coordinate The guessing method with backtrack algorithm that has been selected will search the first suitable value for each grid in the puzzle. The scarching for the value will be done from column to column, which means starting from column [0] where the initial grid [0][0] be and go down to grid [8]|01. Then, it is continuing to next column, column |1] and so on until column [8]. In order to solve a diagonal Sudoku puzzle using this Java programming algorithm. the clues need to be key in first. The clues will be stored in order to be used in scarching the solution for the puzzle. The clues that have been keying will be check whether it follows the rule of the diagonal Sudoku or not. If it follows, then the searching process for the unoccupied grid will be started. Il it follow the rule, the searching process will begin. Otherwise, it will halt and stated that the puszie is invalid. Then, to start scarching the value for the grid, it will cheek whether the grid already has a elue given or not. Il a clue has existed in the grid, move on to next grid. If it is empty or 0, the searching process will be start by trying from I until 9. The value that is being trying will be cempared in row, colunmn. box and diagonal region one by one. If the first trying value has been found and follow ing the rules. the value will be stored in the grid and the searching will be move tn the next grid. I it is not found until number 9, the grid will be set to 0 and will be meve backward to the previous searched grid. Then, the previous searched grid will be trying to search again lor another new value until it has found a new one or until number 9 This process will continue until it has found the solutions for the puzzle hy successfully lound all the values for the empty grids. ur it it has net found ans suitalble values for the enmpty grids, whish means the puzzle has no solution.

5 / 12 100% The result will shows whether it has successfully found the solution by displaying the solution, or an error message stated that there is no solution for the puzzle. The figure 4 shows Java programming algorithm. Begin Key in puzle ches Does the clues following the ruler? Searching for the sohution Raach to tha end of the Fuzzle Shcur the sclurica End Figure 4: Java Programming Algorithm Implementation Java programming language is used to create the diagonal Sudoku 9x9 grid only. Graphic User Interface (GUI) has been implemented to make it look nicer rather than just using the black sereaned command promnt windeu With some enu ontione that can be choce pon-

Seerdi nksa Show ener Hed Figure 4: Java Programming Algorithm Implementation Java programming language is used to create the diagonal Sudoku 9x9 grid only. Graphic User Interface (GUI) has been implemented to make it look nicer rather than just using the black-screened command prompt window. With some menu options that can be chose, pop- up message boxes, and also option message box. Pop-up message boxes is created to interact with the user while option message box to give options to the user to choose the clue's value in the grids. It can be convenience to the user to use it. In the next section is the full description manual of Java programming output. Main Graphic User Interface (GUI) This is the main GUI for the 9x9 diagonal sudoku puzzle programming where it has menu bar that contains options and help. Other than that, this main GUI also has diagonal Sudoku grids panel for user to insert the puzzle and it will shows the solution for the puzzle. 76 Meni bar

Sudabu X Selver Menu bar Detion Hep Diagonal Sudoku grids panel Figure 5: Main GUI Option Menu In the option menu, there will be "Solve", "Clear" and "Exit" options. "Solve" option will solve the diagonal Sudoku puzzle that has been inserted in the diagonal Sudoku grids panel. "Clear" option will clear the diagonal Sudoku grids panel. "Exit" will close the diagonal Sudoku programming. Figure 6: Option Menu Options IHelp Menu In the help menu. there will be "How to use? and "About" options. How to use?" option will tell the user how to use the program. llowever,About" option wili tell the user brielly about the diagonal Sudoku programming.

Figure 7: Help Menu Options Diagonal Sudoku Grids Panel Solving a puzzle by using this program will need a some clues to be inserted. Thus, to insert a clue in a grid in the panel, just simply click any of the grids in the panel, and a pop-up window will be shown to select the clue's value in the clicked grid. The value that can be chose to be inserted in the grid panel is from 1 until 9. In order to erase back the input value that has been chose, the user can click again the wronged inserted grid. Then, click "Erase" button to erase the value in the current grid. Value Input Value button Choone value Erase -Lrase button Figure 8: Valuc Input Panel Box

Solving a Given Puzzle After inserting the clues, to show the solution for the given puzzle by click the Option menu, then click Solve option. However, if there is no clue being given or less than seventeen clues is given in the panel to be solved, the program will definitely show the solution from the given clue in the grid. The solution will be shown in just a few seconds. From figure 10 and figure 11, the blue value in diagonal Sudoku grids panel is the clues, and the red value is the solution. Figure 10: Solving a Puzzle Figure 11: F.xamples of Solution For Empty Cirids Panel and A Cue Given Puzale

66.7% Clearing Grids Panel Figure 12 shows how to clearing the grids panel. For clearing the grids panel, click the Option menu, then choose Clear option. Etcku1 Schr Opdes Opte tels Sale 7. Exit 4. 2 214 7. 4. 3. Figure 12: Clearing The Grids Panel Giving Error Puzzle To Be Solved Figure 13 shows the examples of violated rule puzzle. If the given puzzle is violated the diagonal sudoku puzzle rule, there was an error pop-up message box appeared to notify the user like in figure 14. Figure 13: Fxamples of Violated Rule Puzzle

NOT A VALID PUZZLE OK Figure 14: Error Message Box For Solving Violated Rule Puzzle Given Puzzle Does Not Has Solution If the given puzzle does not has any solution, a pop-up error message box will come to state that the given puzzle does not has solution. Figure 15 shows an example of a puzzle that does not have solution and its eror message box. tea Solution Figure 15: A Puzzle That Does Not Have Solution (Left) and Its Error Message Box (Right) Results and Discussion Java programming is built to hclp human for solving Sudoku problem. The puzzles that have been inserted can be solved using Java Programming. Either the problem is cas intermediate, difficult or even diabolie level: all can be solved within a few seconds. Unfortunately, this program cannet differentiate the given puzzles whether it has unique or many solutions. Furthermore, even the puzzle has many solutions, the program will only show the first solution that it has found while searching the sulution. Conclusion and Recommendations In conclusion, Java programming is reeded for solving diagonal Sudoku 9x9 grid hecause it is usefully to Sudoku player o find the solution. Just by inserting the clue of the pazale, add with some elicks. and the solition will be shown in the panel Even any levei of puzzle has been inserted: the program still can show the solutivn of the given pzle. I is very helplul for human. especially lor thie diaganal Sudoku player to se it as an wid in their waay to lind their diagonal Sudoku pazzle solution.