MINOR PROJECT REPORT DEPARTMENT OF INFORMATION TECHNOLOGY SCHOOL OF TECHNOLOGY NORTH EASTERN HILL UNIVERSITY SHILLONG-22 DESIGN AND IMPLEMENTATION OF THE PUZZLE GAME µSUDOKU¶ In partial fulfilment of requirements for the award of degree in Bachelor of Technology in Information Technology (2010-11) Submitted By: Anjan Bora (BT/IT/0706) Firoz Ahmed Choudhury (BT/IT/0714) Hriday Das (BT/IT/0719) Pranjal Bharali (BT/IT/0740) Trinayan Chakraborty (BT/IT/0755) Under the Supervision of: Mr. A.K. Maji Assistant Professor Department of Information Technology Department of Information Technology NORTH EASTERN HILL UNIVERSITY UM ING, SHILLONG, M GHALAYA ± 793022 Department of Information Technology NORTH-EASTERN HILL UNIVERSITY UMSHING, SHILLONG ² 793 022. Date: T whom it may concern This is t certi that Anjan Bora (BT/ T/ Firoz Ahmed Choudhury (BT/ T/ Hriday Das (BT/ T/ Pranjal Bharali (BT/ T/ Trinayan Chakraborty (BT/ T/ worked on the project Desi n and Implementation of the puzzle game µSUDOKU¶ from August-2010 to December-2010 and has successfull completed the minor project in order to partial fulfilment of the requirements for the award of the degree of Bachelor of Technology in Information Technology under my supervision and guidance. A.K.Maji Assistant Professor Department of Information Technology North Eastern Hill University, Shillong-22 Department of Information Technology NORTH-EASTERN HILL UNIVERSITY UMSHING, SHILLONG ² 793 022. Date: To whom it may concern This is to certify that Anjan Bora (BT/IT/ Firoz Ahmed Choudhury (BT/IT/ Hriday Das (BT/IT/ Pranjal Bharali (BT/IT/ Trinayan Chakraborty (BT/IT/ worked in the project Design and Implementation of the puzzle game µSUDOKU¶ from August-2010 to December-2010 and has successfully completed the minor project in order to partial fulfilment of the requirements for the award of the degree of Bachelor of Techno logy in Information Technology. B. Bhuyan Head of Department Department of Information Technology North Eastern Hill University, Shillong-22 Department of Information Technology NORTH-EASTERN HILL UNIVERSITY UMSHING, SHILLONG ² 793 022. Date: To whom it may concern This is to certify that Anjan Bora (BT/IT/ Firoz Ahmed Choudhury (BT/IT/ Hriday Das (BT/IT/ Pranjal Bharali (BT/IT/ Trinayan Chakraborty (BT/IT/ worked in the project Design and Implementation of the puzzle game µSUDOKU¶ from August-2010 to December-2010 and has successfully completed the minor project, in order to partial fulfilment of the requirements for the award of the degree of Bachelor of Technology in Information Technology. External Examiner ACKNOWLEDGEMENT The ati faction that accompanie that the ucce ful completion of any ta k would be incomplete without the mention of people who e cea ele cooperation made it po ible, who e con tant guidance and encouragement crown all effort with ucce . We are grateful to our project guide Mr. A.K. Maji, A i tant Profe or, ept of I.T. NEHU, for hi guidance, in piration and con tructive ugge tion that helped u in the preparation of thi project. He wa alway there guiding and correcting u with attention and care. He took immen e pain going through the project and al o the documentation and made nece ary correction a and when required. We would al o take thi opportunity to thank our In titution, our Head of the epartment and other faculty member without whom thi project would have been a di tant reality. ate : Anjan Bora (BT/IT/0706) Firoz Ahmed Choudhury (BT/IT/0714) Hriday a (BT/IT/0719) Pranjal Bharali (BT/IT/0740) Trinayan Chakraborty (BT/IT/0755) ABSTRACT: "Sudoku" i the Japane e abbreviation of a longer phra e, "Suuji wa doku hin ni kagiru", meaning "the digit mu t remain ingle". It i a challenging numeric puzzle that train our logical mind. Solving a Sudoku puzzle require no math, not even arithmetic. Even o, the game po e a number of intriguing mathematical problem . The fir t Sudoku puzzle wa publi hed in the United State , but Sudoku initially became popular in Japan, in 1986, and did not attain international popularity until 2005. Our project deal with the ta k of de igning a game of Sudoku u ing variou algorithm . The e are algorithm , both for generating game of variou difficultie for the u er and al o for olving the puzzle provided by the u er. A u er will be able to a k for a random puzzle (generated ba ed on the difficulty level elected), or the u er will be able to manually input a puzzle. In either ca e, the oftware will be able to olve the puzzle completely, or equentially tep by tep. The u er will at any time be able to a k for a hint howing the next ea ie t tep. The u er will al o be able to perform ome other ta k uch a aving the current game, loading a game of the pecified format, changing the look of the oftware di abling ound, a k for help and o on. The project i done u ing Micro oft Vi ual Ba ic 2008 on a computer running Window Vi ta. .NET framework of 3 or higher i required for the game to run. i TABLE OF CONTENTS: ABSTRACT «««««««««««««««««««««««««««««« 1 INTRO UCTION i 1.1 Goal and Objective «««««««««««««««««««««««..1 1.2 A general de cription on Sudoku««««««««««««««««««...1 1.3 Analy i of the problem/Complexity Analy i «««««««««««««...2 1.4 Literature Survey«««««««««««««««««««««««««2 1.5 Application of our project«««««««««««««««««««««.3 1.6 Propo ed Solution Strategy«««««««...«««««««««««.«....4 2 SOFTWARE REQUIREMENT SPECIFICATION OCUMENT (SRS) 2.1 Introduction««««««««««««««««««««««««««....5 2.1.1 Purpo e««««««««««««««««««««««««....5 2.1.2 Scope«««««««««««««««««««««««««...5 2.1.3 efinition «««««««««««««««««««««««...5 2.2 Overall e cription«««««««««««««««««««««««....5 2.2.1 Product Function «««««««««««««««««««.«...5 2.2.2 User Characteristics««««««.««««««««««««.«...6 2.2.3 ependencies«««««««.«««««««««««««.«.....6 2.3 Functional Requirements«««««««««««««««««««..«.....6 2.3.1 Use Case iagram««««««««««««««««««.«.....6 2.3.2 Use Case Specification««««««««««««««««««...7 2.3.3 Performance Requirement««..««««««««««««.«..«..7 2.4 Non Functional Requirement««««««««««««.«««««««...7 2.4.1 Performance«««««««««««««««««.«««««..7 2.4.2 Reliability««««««««««««««««««««««.«..7 2.4.3 Portability«««««««««««««««««««««.««..8 3 ESIGN STRATEGIES 3.1 Flowcharts««««««««««««««««««««««««««8 3.1.1 Flowchart showing steps to generate puzzle«««««««««.8 3.1.2 Flowchart for hint and show solution««««««««««««9 3.1.3 Flowchart for Undo move button««...««««««««««.10 4 IMPLEMENTATION ETAILS 4.1 Solving the puzzle«««««««««««««««««««««««11 4.1.1 The CRME technique««««««««««««««««««11 4.1.2 The Lone Ranger Technique«««««««««««««««.15 4.1.3 The Twins button«««««««««««««««««««..17 4.1.4 The Brute Force Elimination Method««««««««««.«..21 4.2 The Undo Button««««««««««««««««««««.«««.23 4.3 The interface«.«««««««««««««««««««««««....24 4.3.1 The main interface««««««««««««««««««...24 4.3.2 The interface after clicking game«««««««««««««25 4.3.3 The interface after clicking new puzzle««««««««««...25 4.3.4 Saving a game«.«««««««««««««««««««.26 4.3.5 Statistics«««««««««««««««««««««.«..26 4.3.6 The exit menu«««.«««««««««««««««.««.27 4.3.7 The interface on clicking option button««.««««««.««.27 4.3.8 The Give Up interface«««««««««««««««.««28 4.3.9 The Change Appearance button««««««««««««.«.28 4.3.10 The Create Puzzle interface«««««««««««««.«..29 4.3.11 The change user interface««««««««««««««.«.29 4.3.12 The difficulty setting interface«««.«««««««««.«.30 4.3.13 The about box«««««««««««««««.«««.«..30 4.3.14 evelopers Information««««««.««««««««««31 4.3.15 The help interface««««««««.««««««««««.31 5 TEST PLAN 5.1 Start-up screen display««««««««««««««««««««..32 5.2 Game Grid«««««««««««««««.«««««.««««..32 5.3 Level and Appearance settings«««««««..«««««««««...33 5.4 Game Solver««««««««««««««..««««««««««33 5.5 Comparison««««««««««««««...««««««««««.34 6 USER MANUAL 6.1 Welcome to Sudoku«««««««««««««««««««......35 6.1.1 What is Sudoku?....................... ..................................................35 6.1.2 History of Sudoku«««««««««««««««««..35 6.2 Getting Started««««««««««««««««««««««..35 6.2.1 Install/Uninstall Sudoku«««««««««««««««.35 6.3 Rules of the game««««««««««««««««««««..«36 6.3.1 General Rules«««««««««««««««.««««36 6.3.2 How to play?..............................................................................36 6.4 Options««««««««««««««««««« ««««««.36 6.4.1 GamePlay««««««««««««««««««««..36 6.4.2 Look and Feel«««««««««««««««««««38 6.5 About««««««««««««««««««««««««««39 6.5.1 About the developers««««««««««««««««.39 6.5.2 Contact Information««««««««««««««««..39 7 RESULTS AN CONCLUSION 7.1 Result««««««««««««««««««««««««««.39 7.2 Conclusion«««««««««««««««««««.«««««40 REFERENCE«««««««««««««««««««««.«««««.«««..ii APPEN IX A««««««««««««««««««««« «««««..«««.iii 1. INTRODUCTION: 1.1 Goals and objecti es The algorithms used in Sudoku find huge application right from routing a flight path for an aircraft to hiding data as in Steganography. These algorithms have huge potential and if properly utilised can be used in many applications like in Artificial Intelligence and ata Encryption techniques. While developing this product we have kept in mind these facts and tried to create an application which is efficient in case of time consumption. The algorithms we have developed are by far the most efficient algorithms till date beating its nearest contender by taking less than half the time to solve the most difficult of puzzles. This ensures that if our algorithms are used to tackle any real-life problems, then optimum solutions are guaranteed. By using efficient algorithms, if we were to perform Steganography on any file, then the encrypted file will be optimum which will result in less use of bandwidth and thus faster data transfer. Also if the aircrafts are routed using these optimum algorithms, it will result in the most proficient route saving us both time and money. 1.2 A general description on Sudoku Sudoku is a game made up of 81 cells organized into 9 rows, 9 columns, and 9 boxes. A puzzle will start with 17 or more cells already filled in. The challenge is to fill in the rest. To solve a puzzle, the user places 1 through 9 in each row, each column, and each minigrid such that no number repeats itself in that particular row, column or minigrid. Once all the cells have been filled the user gets a notification stating whether or not his solution is correct. If there is any error on the part of the user he can undo his move and then try again. This will result in higher time required to solve the puzzle. If an invalid puzzle is submitted by the user, the Sudoku Solver returns an error message. Two pictures, a partially solved puzzle and its solved version are shown below. A glossary of the terms used here is given in the appendix. Fig. : The original puzzle Fig. : The solved puzzle 1.3 Analysis of the problem/Comple ity Analysis An n²×n² Sudoku grid (consisting of n×n blocks) is an NP complete problem. So, development of a heuristic algorithm is the only way out. In our project we have developed a heuristic algorithm that follows a set of organized moves to solve a given Sudoku puzzle. Needless to mention that the space complexity of the algorithm is O(m²), as a constant number of elimination techniques has been adopted on the given grid structure of size O(m²), where m= n². On the other hand, for each of the O(m²) cells O(m) alternatives are applied to find out the desired unique entries, if any, in the worst case. This results the overall time complexity of the algorithm is O(m³), where m = n². 1.4 Literature Sur ey An n²×n² Sudoku grid (consisting of n×n blocks) is an NP-complete problem. So, it is unlikely to develop a polynomial time algorithm to solve this problem. Hence, we have developed some heuristic algorithm that follows a set of organized moves to solve a given Sudoku puzzle. There are quite a few logic techniques we have used to solve this problem. Some are basic simple logic, some are more advanced. epending on the difficulty of the puzzle, a mixture of techniques may be needed in order to solve a puzzle. In fact, most computer generated Sudoku puzzles rank the difficulty based upon the number of empty cells in the puzzle and how much effort is needed to solve each of them. Table 1 shows a comparison chart of the number of empty cells for different difficulty levels. Table 1 showing no. of empty cells. Now we review on the backtracking technique that has been adopted for solving Sudoku puzzles. The basic backtracking algorithm works as follows. The program places number 1 in the first empty cell. If the choice is compatible with the existing clues, it continues to the second empty cell, where it places a 1 (in some other row, column, and minigrid). When it encounters a conflict (which can happen very quickly), it erases the 1 just placed and inserts 2 or, if that is invalid, 3 or the next legal number. After placing the first legal number possible, it moves to the next cell and starts again with a 1. If the number that has to be changed is a 9 (which cannot be raised by one in a standard Sudoku grid), the program backtracks and increases the number in the previous cell (the next-to-last number placed) by one. Then it moves forward until it hits a conflict. In this way, the program may sometimes backtrack several times before advancing. It is guaranteed to find a solution if there is one, simply because it eventually tries every possible number in every possible location. This algorithm is very effective for size two puzzles. Unfortunately, for size three puzzles, there are nine possibilities for each square. This means that there are roughly 981ín possible states that might need to be searched, where n is the number of given values. Obviously this version of backtracking search does not work for size 3 puzzles. Fortunately, there are several means by which this algorithm can be improved: µconstraint propagation¶, µforward checking¶, and µchoosing most constrained value first¶ are some of them. 1.5 Applications of the Project There are various applications of our product some of which but not limited to are: The game uses some searching (depth-first-search) and back-tracking techniques which are based on the algorithms of artificial intelligence. Sudoku puzzles have been translated into colouring problems that links the game to class of important mathematical problems. The Sudoku puzzle is used in data hiding techniques like Steganography. The Sudoku is used like a key to hide data behind images. 1.6 Proposed Solution Strategy For the interface part we will use dynamic textboxes as the cells. The users will be able to input numbers from the keyboard or from the virtual keypad through the mouse. For the solver and the generator part of our program we will try to use the following as given below. A detailed description of the algorithms is given in the implementation part of the report. The Column, Row, Minigrid elimination (CRME) method. The Lone Ranger method. The Twins method. The Brute-Force elimination method. All these algorithms are very efficient due to the fact that these are organized; systematic heuristic methods where no guessing is involved (except the Brute Force Elimination Method) are used in our product. This makes our program more efficient than the others available in the current scenario. And since our program is efficient it can be used in various situations discussed in the µapplications of the project part¶. We will try to avoid the use of external databases since it will hamper the usage of the product where database products are not available. (Oracle, MS Access etc). We will try to use lifetime variables to keep track of the user and the game settings. To store puzzles we will use a special file type and store the puzzle as a set of strings. We will also maintain a stack to keep track of every user move. In this way we will be able to µundo¶ user moves as and when desired. 2 SOFTWARE REQUIREMENT SPECIFICATION DOCUMENT (SRS) : 2.1 Introduction 2.1.1 Purpose The main objective of this project is to create a game through which the user will be able to play a Sudoku puzzle. Our goal is to build a software product that can create, modify, solve and save Sudoku Puzzles. The hope is that a person will after time, gain expertise regarding Sudoku by using this product. A user will be able to ask for a random puzzle (generated based on the difficulty level selected), or will be able to manually input a puzzle. In either case, the software will be able to solve the puzzle completely, or sequentially step by step. The user will at any time be able to ask for a hint for showing the next easiest step. The algorithms we have developed are by fast the most optimum. So, we hope that the algorithms will be useful in various other applications other than our product. 2.1.2 Scope The system can be broken up into three fundamental functions. 1. Sudoku Gameplay: At the heart of the program will be the various ways to play the game of Sudoku. The user will have an intuitive interface for communicating with the product. He will be able to generate puzzles of his choice of difficulty and will also be able to generate his own puzzle. 2. Sudoku Game Helper: On top of the basic gameplay, there will be a Sudoku helper. Additional interface controls will allow the user to ask for hint or see the solved puzzle. 3. Sudoku Appearance: The user will also have some basic options such as change the background theme, toggle the sound etc. 2.1.3 Definitions All the definitions are explained in Appendix A. 2.2 O erall Description 2.2.1 Product Function There is only one kind of user for our product. The general user will be able to perform all the operations on the product after installing the product on his machine. Microsoft .NET Framework 3.0 or higher is required to install the product. 2.2.2 User Characteristics Any user with a little knowledge of computers and the game will be able to operate our system. 2.2.3 Dependencies The system only depends on the fact that Microsoft .NET Framework 3.0 or higher is installed. 2.3 Functional Requirements 2.3.1 Use Case Diagram 2.3.2 Use Case Specification y y y Primary actor: The general targeted audience are the only primary users for our system. Pre condition: Microsoft .NET framework 3.0 is installed. The user has to start a new game, load a game or give a game. Main Scenarios: There are a number of main scenarios in our project. 1. Create a new puzzle ± The puzzle generator will be called and a new puzzle based on the difficulty will be generated. 2. Load a saved puzzle - The user can load an already saved puzzle to resume play. 3. Insert a puzzle ± The user can insert a new puzzle from outer sources and ask the computer to solve them. 4. See help file ± The user can see a detailed help file in .chm format. 5. Look and Feel ± The user can change the theme of the software and can also toggle sound. 6. View Statistics ± The user can view his game statistics to see his progress. 2.3.3 Performance Requirements A computer running Windows XP/Vista/7 is required for the game to run. Microsoft .NET Framework 3.0 or higher is required. A keyboard or a mouse is required to operate the game. 2.4 Non Functional Requirements 2.4.1 Performance The Puzzle generator should be able to generate distinct puzzles every time based on given difficulty. The puzzle solver should be fast enough to solve even the hardest puzzles under a second. 2.4.2 Reliability The product should not crash under any circumstance such as user entering invalid values, user trying to load unsupported files etc. Also the solver should be able to solve any kind of puzzle and should be able to detect an illegal or invalid puzzle. 2.4.3 Portability Our product will be portable to carry and will run in any machine provided it runs a Windows Operating System. We have created an installer which compiles all files into a single executable (.msi). Only this file is required to successfully install the game on any computer. 3 DESIGN STRATEGY: 3.1 Flowcharts 3.1.1 Flowchart showing steps to generate a puzzle 3.1.2 Flowchart for hint and show solution Basically the same algorithm is used for both showing the hint and solving the whole puzzle. The only difference is that if hint is wanted the loop runs only once revealing only one value, while if the whole solution is wanted, the algorithm is recursed so that it runs until all the empty cells are filled. 3.1.3 Flowchart for Undo mo es button We will maintain a stack to keep track of every user move. In this way we will be able to µundo¶ user moves as and when desired. If the stack is empty at any point, an error message is displayed. 4. IMPLEMENTATION DETAILS: 4.1 Sol ing the puzzle. The following algorithms are used to solve the puzzle generated by the program or puzzle inserted by the user. These are by far the most efficient algorithms to solve a Sudoku puzzle. These algorithms are described in details below. 4.1.1 THE COLUMN, ROW AN TECHNIQUE MINIGRI ELIMINATION (CRME) Most Sudoku puzzles can be solved by a process of elimination. For example, if eight out of nine cells in a row are filled, then the remaining cell must be the number that has not been used in the row. In the case of Figure 1, the value of the remaining cell, (5,1), must be 5, since 1 through 4 and 6 through 9 have already been used in that row. Fig.: 1. Deriving the number for a cell based on elimination When we try to place a number in a cell, examining just its row usually is insufficient, because typically, unlike Fig.: 1, not all the other cells in the row are filled. We have to also scan its column and, if that is not enough, scan within its minigrid. Therefore this technique is called the Column, Row, and Minigrid Elimination (CRME) technique. The algorithm for CRME: Scan each cell in the grid from left to right, top to bottom For each cell: Set possible values for each cell to 123456789 Scan its column and eliminate the values already present in the column Scan its row and eliminate the values already present in the row Scan its minigrid and eliminate the values already present in the minigrid If there is only one possible value for the cell, the number for the cell is confirmed Until no more cells can be confirmed. To see how CRME works, let¶s start off with the simplest scenario. Figure 2 shows a partially filled Sudoku puzzle. Fig. 2 : A partially filled grid. Scanning each cell from left to right, top to bottom, the first empty cell we encounter is (2,1). Examining the column that it is in tells us that the possible values left for this cell are 2, 3, 4, 6, 7, 8, and 9 (see Figure 3). Fig. 3: Scanning by column However, scanning horizontally across the row reduces the number of possible values to one, which is 9, because all the other values have already been used, as shown in Figure 4. Fig. 4: Scanning by row Since the only possible value is 9, we can now fill in (2, 1) with 9 (see Figure 5). Fig. 5: Filling in the value for (2, 1) Continuing with the scanning, the next empty cell is (2, 2). Scanning by its column and row, as shown in Figure 6, yields the possible values of 3, 4, 6, 7, and 8. Fig. 6: Scanning by column and row By scanning the minigrid next (see Figure 7), we see that it already has the values of 1, 2, 3, 4, and 9, so the possible values are now reduced to 6, 7, and 8. Because (2, 2) has more than one possible value remaining after we have searched the column, row, and minigrid to eliminate values, the answer is not conclusive. But at least we now know that only the values 6, 7, and 8 are possibilities for (2, 2). Fig. 7: Scanning within the minigrid 4.1.2 THE LONE RANGER METHOD Lone ranger is a term used to refer to a number that is one of multiple possible values for a cell but appears only once in a row, column, or minigrid. Consider the row shown in Figure 1. In this row, six cells have already been filled in, leaving three unsolved cells (shown as shaded cells) with their possible values written in them (derived after applying the CRME technique). The second cell is the only cell that contains the possible value 8. Since no other cells in this row can possibly contain the value 8, this cell can now be confirmed with the value 8. In this case, the 8 is known as a lone ranger. Fig. 1 Confirming Lone Rangers in a row. Lone rangers are extremely useful in helping to confirm the number for a cell and are often useful in more complex Sudoku puzzles. Lone rangers can appear in a row, column, or minigrid. Algorithm for the Lone Ranger Method Scan every cell of each minigrid number 1 through 9 For each cell Find the µlone ranger¶ numbers and place them in respective minigrids; Apply CRME again, if any change is made; Scan every cell of row number 1 through 9 For each cell Find the µlone ranger¶ numbers and place them in respective minigrids; Apply CRME again, if any change is made; Scan every cell of column number 1 through 9 For each cell Find the µlone ranger¶ numbers and place them in respective minigrids; Apply CRME again, if any change is made until no more changes can be confirmed. Lone Rangers in a Minigrid Let us consider the following the grid in figure 2. Fig. 2: A partial Sudoku puzzle Let¶s examine the possible values for all other cells. Figure 3 shows the possible values after partially applying the CRME technique. Fig. 3: Possible values after applying CRME One interesting observation is found by looking at the third minigrid, shown in Figure 4 . Fig4. : Examining the third minigrid If we observe cell (7,2), one of the possible values is 1, along with the other numbers like 3, 4, and 5. However, the number 1 appears as a possible value only for (7,2) and not for the other cells within the minigrid. Logically, we can now conclude that as long as a number appears only once (as a possible value) within the minigrid, that number can be confirmed as the number for the cell. This is logical, because cells (7,1), (8,1), and (9,1) cannot contain the value 1, and hence only (7,2) can contain 1. Following this argument, we can now put a 1 in (7,2), as shown in Figure 5. Fig. 5: Confirming the value. Likewise we can also apply the Lone Ranger method to rows and columns. 4.1.3 THE TWINS APPROACH Let us consider the partial Sudoku puzzle shown in Figure 1, which includes lists of possible values for unresolved cells. Fig. 1: A partially solved Sudoku puzzle with the possible values for empty cells We observe the two cells (5, 2) and (6, 2) in Figure 5-2. They both contain possible values of 2 and 3. In this scenario, if (5, 2) takes the value 2, then (6, 2) must take the value 3. Conversely, if (6, 2) takes the value 2, then (5, 2) must take 3. All other cells in row 2 besides these two cells cannot contain either 2 or 3. Because the two cells (5, 2) and (6, 2) have identical lists of possible values and are in the same row, they are known as twins. Algorithm for twins approach Scan each cell of row number 1 through 9 Find out the clones present in any two cells; Eliminate the component of the clone found in any other cell; Scan each cell of minigrid number 1 through 9 Find out the clones present in any two cells; Eliminate the component of the clone find in any other cell; Scan each cell of column number 1 through 9 Find out the clones present in any two cells; Eliminate the component of the clone find in any other cell; Now apply CRME and Lone Ranger once again for each cell in the grid until no more cells can be confirmed. Fig. 2: Identifying the twins Scanning across the row, we now can eliminate 2 and 3 as possible values for any of the other cells, as shown in Figure 3, in which 2 has been deleted as a possible value for cells (1,2) and (3,2). Fig. 3: Eliminating 2 and 3 as possible values for other cells in the same row as the twins Similarly, because the twins appear in the same minigrid, all the other cells in this minigrid cannot possibly take the values 2 and 3. Thus, we can eliminate 2 and 3 as possible values for cells (4,1) and (5,1), as shown in Figure 4. Fig. 4: Eliminating 2 and 3 as possible values for other cells in the same minigrid as the twins There are now three pairs of twins in the grid, as identified in Figure 5. Two pairs are in the first two rows and the third pair is in column 5. Fig. 5: New pairs of twins emerging after the first scanning For the twins 23,´ we can scan the column they are in and remove all occurrences of 2 and 3. For example, if we examine the possible values for column 5, we can see that the values 2 and 3 can be eliminated from many of the cells in this column (shown in Figure 6 with the possible values for all the cells in the column). Fig.6: Scanning the column the twins are in For the twins 45,´ scanning by their minigrid allows us to remove the 4 and 5 in cell (2, 1), as shown in Figure 7. oing so causes cell (2, 1) to be confirmed with 2, which in turn causes (2, 4) to be confirmed with 4. Fig.7: Confirming cell (2,1) and subsequently (2,4) For the twins 89,´ there isn¶t much we can do to the row and minigrid that they are in. This leaves the grid as shown in Figure 5-8. As you can see, scanning for twins in rows, columns, and minigrids leaves us better off than before the scanning. In our example, two cells get confirmed in the process. Fig. 8: The grid after scanning for twins in the rows, columns, and minigrids 4.1.4 BRUTE FORCE ELIMINATION TECHNIQUE Up to this point, we should be able to solve most Sudoku puzzles using the techniques described above. However, sometimes (especially for difficult puzzles) all the techniques seem to be useless. In such cases, we really need to make an educated guess and put a value in a cell and then apply all the techniques covered so far. This technique is called brute-force elimination technique. We consider the partially solved Sudoku puzzle shown in Figure 1. Applying all the other techniques could not solve the puzzle. Fig. 1: A partially solved Sudoku puzzle Figure 2 shows the list of possible values for each of the unsolved cells. Fig.2: A partially solved Sudoku puzzle with its lists of possible values The most natural way to solve the puzzle would be to do some guesswork. We can select a value for an unsolved cell and apply the earlier techniques to see if that will solve the puzzle. If that doesn¶t solve the puzzle, select a value for the next unsolved cell and repeat the same process until the puzzle is solved. Now, the question is: which cell do we start with? Well, quite obviously you should start with the cell with the least number of possible values. Scanning from left to right, top to bottom, you can see that cell (1,1) is the first choice. In (1,1) there are two possible values, 5 and 8. You can choose either 5 or 8, but for simplicity you can always start with the first number. So let¶s choose 5 for (1,1) and then proceed to solve the puzzle using the techniques we have discussed. The puzzle gets solved, as shown in Figure 3. Fig. 3: The solved puzzle Based on the description of the brute-force elimination technique, we observe the following: The brute-force elimination technique can be implemented programmatically using recursion. To allow for moves to backtrack, you need to remember´ the state of the grid before assigning a value to a cell, which enables us to restore the grid to its previous state. Selecting the right number to assign to a cell is important. In the example, selecting a 1 for (5,4) causes the puzzle to have no solution, but selecting 4 for (5,4) solves the puzzle. To solve a puzzle, we can always start from the first possible number and work our way toward the solution. To minimize the possibility of backtracks; always select the cell with the least number of possible values when applying the brute-force technique. Even though this technique is called brute-force elimination, solving the puzzle using this technique does not imply that we are solving the entire puzzle by guesswork. In fact, for most puzzles, we need to apply the brute-force elimination technique only a few times, and then we can solve the rest of the grid by other logical techniques. 4.2 The undo button When ever a user inserts any number to the grid we store the number in a stack in the following format: [Row No.] [Column No.] [Actual no.] Now when a user presses the Undo button, the topmost entry is popped out from the stack and the value is deleted from the grid. If the stack is empty, it gives an error report. It is shown diagrammatically below: 4.3 The Interface Whether it be a software or some games it is of outmost importance that the interface is intuitive and pleasing. We have tried to develop a very user friendly, easy and pleasing to the eye interface through which the user can interact. All the actions are through the menu and to enter values we have also developed a virtual keypad apart from the traditional keyboard input. The user have the freedom to play a game at his time and then save the game for later use. The snapshots of the interface we have developed are given below: 4.3.1 The main interface. As we can see the main interface consists of the main grid distinctly separated using colours. The tool bar below shows the name of the person currently playing the game. 4.3.2 The interface after clicking Game 4.3.3 The interface after clicking New Puzzle As we can see the game has started and two new labels are shown displaying the time elapsed and the no. of hints left. 4.3.4 Saving a game. The saved game has a extension µtrisshh¶ and is stored in the ocuments Folder by default. The saved game is stored as a set of strings having the value for the filled grid and a µ0¶ for the empty cells. When a game is loaded it takes the numbers from the file and fills up the grid. 4.3.5 Statistics The statistics page gives us detailed description of the no. of games played, games won and games lost. 4.3.6 The exit menu The exit menu gives us the option to save the game before quitting or to simply quit without saving the game. We can also cancel if we want. 4.3.7 The interface on clicking the Options button Here the user can undo a move or give up the game. This will call the Puzzle Solver Algorithms and will solve the game. 4.3.8 The Give Up Interface. This interface shows the solved puzzle with the amount of time required by the computer to solve the puzzle. 4.3.9 The Change Appearance Interface It just changes the background to give the user a view of his choice. 4.3.10 The create puzzle Interface It makes all the cells editable so that the user can enter value of his choice in the cells. He can then ask the solver to solve the puzzle for him. 4.3.11 The change User Interface This lets the user change the username which is displayed below. It is stored in the internal database so that the next time the user opens the program the name is displayed. 4.3.12 The ifficulty Setting Interface It shows the varying level of difficulty which can be selected. It will take effect only after a New Game is selected. 4.3.13 The about box It shows general information about the program 4.3.14 evelopers Information It gives information about the developers with their contact details. 4.3.15 The help Interface The help interface is created using Compiled HTML (.chm) format which gives the user ease to navigate to the part he wants to see. It contains detailed information on every topic right from installing the game to rules of the game. 5 TEST PLAN Tests have been performed throughout the implementation of the application. When the tests have found an error, the problem was found and resolved. The following tests cases are done after the system was completed´. 5.1 Start-up screen display Test 5.1.1 5.1.2 5.1.3 5.1.4 5.1.5 Description Expected Outcome As Expected Yes Yes Yes Yes Yes Open The Game Of Sudoku.exe File > New Game File > Save File > Load File > Exit The game grid loaded up as designed. The grids are partially filled with number 1 to 9. Saves the puzzle to the hard disk. Loads the game from the H . A menu item is displayed from which a user can save the game or exit without saving. 5.2 Game Grid: Test 5.2.1 5.2.2 Description Expected Outcome As Expected Yes Yes Click on a cell before game started Try to enter digits 1 to 9 for all cells, deleting the value using backspace before inserting the next value For all cells, try to enter in a digit when the cell already have a value For all cells, try to enter a nonnumerical value A message pops up asking to start a game. Every cell will allow all the input from 1 to 9 and backspace will elete the value from the cell. 5.2.3 A message pops out showing error Nothing happens. Yes 5.2.4 Yes These tests show that the Application reacts according to mouse and keyboard inputs. This is critical as modern day Sudoku puzzle only uses digits 1 to 9. Each cell also only contains a single digit. 5.3 Le el and Appearance Settings: Test 5.3.1 5.3.2 5.3.3 Description Level >Easy/Intermediate/Legend Expected Outcome As Expected Yes Yes Yes Game level changes according to the choice Appearance will be change according to the choice Sound will be on or off Option >Change appearance Option >Sound on/off 5.4 Game Sol er Test 5.4.1 5.4.2 5.4.3 5.4.4 Description Expected Outcome As Expected Yes Yes Yes Yes Option > Create puzzle Game >Hint Option >Undo move Option >Give up All cells can be selected One of the empty grid will be filled up automatically Recent filled grid will become empty The game will be solved and time taken by the computer will be shown. It is known that the Sudoku is an NP-complete class of problem and moreover all its applications are of heuristic in nature. In our project, the solver part of the developed application has been compared to some other solver applications that are available. We have analyzed our solver algorithm with those applications and have experienced a significant reduction in the time to solve a valid Sudoku puzzle. The comparisons of our puzzle with some other readily available puzzles are given below. 5.5 Comparison The product we created was compared with some of the available products. There is a significant reduction in the time required to solve the puzzles. A comparison chart is given below: Figure : Average times (in milliseconds) taken in the experimentation to solve a set of 60 valid Sudoku instances using Sudoku solvers V2.0 andV1.01, The Game of Sudoku and using our approach. 6 USER MANUAL 6.1 Welcome to Sudoku: 6.1.1 What Is SuDoKu: Sudoku is an application to generate and play the popular Sudoku logic puzzles (also known as Number Place). The rules of Sudoku are quite simple. In order to complete the puzzle, you must fill each square with a number between 1 and 9 such that every row, column and 3x3 box on the board contains the numbers 1 through 9. Stated another way, you must fill each square such that no number appears twice in the same row, column, or 3x3 box. In spite of the simplicity of the game, Sudoku puzzles can vary widely in their difficulty. Sudoku allows you to select the difficulty of the puzzle you want to play. By default, it will begin with intermediate puzzles and user can change the difficulty of puzzles from easy to legend with the help of level menu. 6.1.2 History of SuDoKu: Sudoku was incepted in 1979. It was known as NumberPlace´ in the ell Magazines.Later in April 1984, the puzzle was released in Japan by Nikol i as Suuji wa dokushin ni kagiru´. Maki Kaji shortened the name as SUDOK U. The first Sudoku puzzle was published in the United States, but Sudoku initially became popular in Japan, in 1986, and did not attain international popularity until 2005. 6.2 Getting Started: 6.2.1 Install / Uninstall Sudoku: Steps to Install: 1. Copy the game setup . 2. Run the setup file and select the directory where to install the game. Steps to Uninstall: 1. Go to Control Panel Add or Remove Programs. 2. Right click on the Sudoku and click Uninstall. 6.3 Rules of the game: 6.3.1 General Rules The aim of the game is to place a number from 1 to 9 into each of the cells, such that each number must appear exactly once in each row and in each column in the grid. Additionally, each minigrid must contain all the numbers 1 through 9. It is also possible to use any other set of symbols. However, using numbers is the obvious choice. 6.3.2 How to play To play the game, start filling numbers 1-9 in the squares such that no row, column, or 3x3 mini grids has any number more than one time. You can fill a number in a square with the keyboard or the mouse. The user can use mouse or keyboard to fill numbers as follows: Keyboard Use the arrow keys or the mouse to select the square you would like to fill. Then type the number you want to put in the square. Typing Backspace will remove the number. Trying to enter a number more than 9 or putting invalid characters will result in an error message. Mouse Double click on a square to bring up a virtual keypad. Click on a number to select it, or click on cancel to clear the square. 6.4 Options 6.4.1 Game Play How to start a New Game: User can start the game by clicking Game New Puzzle If there were a game running while this button is clicked, a dialog box will appear giving the options to save the current game or continue without saving. How to save a Game: User can save the game by clicking Game Save Game. The game will be stored in a file format known as 'trisshh'. You can take the save games to another computer for playing. How to load a Game: User can load the game by clicking Game Load Game. Load a game of only the file format 'trisshh'. Other format will result in an error. To see the statistics of the Game: User can see the statistics by clicking Game Statistics The total number of games played, games won and games lost are kept in record. To use the hint button: User can use the hint button by clicking Game Hint Each level of difficulty has a different number of hints available. The LEGEND! difficulty level has no hint available. To exit from the game: User can exit from the game by clicking Game Exit If a game is running a dialog box will appear allowing the user to save the game for future playing. How to create a Puzzle: User can create a new game by clicking Option Create Puzzle. This is a unique feature of our game. On clicking this button, an empty grid is created giving the users to enter any puzzle of their choice. (For e.g. from newspapers or magazines). He can then ask the application to solve the puzzle for him. How to undo a move: User can undo his move by clicking Option Undo Move It clears the square which was filled last. How to give up : User can give up if he wants by clicking Option Give Up This causes the solver to solve the puzzle and show the result to the player. The game is counted as a loss in the statistics. How to change user: To change user Option Change user User name once changed will be stored and will be stored every time the user runs the application. How to change difficulty level: User can change the difficulty level according to his choice by clicking Level Easy/Intermediate/Champion/Legend !. The default level is Intermediate. 6.4.2 Look and Feel Appearance Settings: User can change the appearance by Option change appearance This causes a change in the background of the application. Sound Settings User can on or off the sound by clicking Option sound ON/OFF 6.5 About 6.5.1 About the de elopers This application was developed as a minor project for 7th semester in NEHU, Shillong. Project Members: Anjan Borah. Firoz Ahmed Choudhury. Hriday Das. Pranjal Bharali. Trinayan Chakraborty. 6.5.2 Contact Information Email Id:
[email protected] Phone Number:+918011284486 7 RESULTS AND CONCLUSION 7.1 Result The Sudoku mathematical game, born about two centuries ago, but largely spread in Europe only during the last few years, has been studied and analyzed in details in this report. A mathematical model has been formulated. In addition, the mathematical model has been implemented in a computer solver and in parallel a program has been developed able to generate Sudoku games. Some applications of this analytical and numerical work have been presented too. Finally the problem of mathematical complexity has been dealt with, by the comparison with another game for which the complexity level is known. It has been also shown that Sudoku has a level of complexity not smaller than the one of crossword puzzle construction´. Further developments in this field should consider the uniqueness of solution in relation to the minimum number of input data necessary for this condition. Further work could explore a more direct puzzle generation algorithm that makes use of the unique nature of our difficulty metric. By applying the logical strategies we consider in reverse to selectively remove given from a completed grid, a puzzle that requires certain strategies to solve could be constructed, effectively tailoring the puzzle to conform to a desired difficulty. This could potentially generate puzzles of a desired difficulty more efficiently. 7.2 Conclusion The Sudoku is an NP-complete problem. So, developing heuristic algorithms is the only way out. There are several existing solvers for solving the problem including backtracking; the algorithm is highly time-consuming. In this project we have developed an organized method to solve the problem. It takes O(m³) time and O(m²) space, where m = n², for solving a Sudoku grid of size n2×n2 (consisting of n×n blocks). Our proposed algorithm solves a 9(32)×9(32) Sudoku puzzle for all difficulty levels, and the results obtained using our approach is highly interesting in terms of computation time in comparison to that of other existing Sudoku solvers. REFERENCE 1] Berthier D., The Hidden Logic of Sudoku, Second Edition, Lulu, Morrisville, France, 2007. 2] Lee W.-M., Programming Sudoku, First Edition, Apress Inc., New Jersey, USA, 2006. 3] Narendra J., A to Z Sudoku, Second Edition, ISTE Limited Publications, United Kingdom, 2007. 4] http://www.userweb.cs.utexas.edu/~kuipers/readings/Sudoku-sciam-06.pdf 5] Bau, D. (2006, September 4). Sudoku Generator. Retrieved October 24, 2007, from davidbau.com: http://davidbau.com/archives/2006/09/04/sudoku_generator.html 6] Stuart, A. (2006, November 21). Sudoku Solver. Retrieved October 24, 2007, from Scanraid Ltd: http://www.scanraid.co.uk/sudoku.html 7] http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf 8]M. Hal orson,. Visual basic 2008, Step by Step. 9] E angelos Petroutsos and Mark Ridgeway,: Mastering Microsoft Visual Basic 2008 10] Rod Stephens,: Visual Basic 2008-Programmers Reference. 11] Microsoft MSDN help. ii APPENDIX A Glossary of the terms: Cell : A puzzle has 1 cells. Each cell can be empty or can have a value from 1 to 9. Each cell may be editable or predefined depending on the puzzle. Each cell belongs to exactly one row, one column and one minigrid. The combination of all the 91 cells is known as the puzzle grid. iii Row : A row is a set whose cells are aligned horizontally. Each puzzle has exactly nine rows. Column : A column is a set whose cells are aligned vertically. Each puzzle has exactly nine columns. Minigrid : A minigrid(also called a box) is a group of nine cells which are not linear. Each puzzle has exactly nine minigrid. THANK YOU