Sudoku

Published on

A Sudoku is a logic-based number placement puzzle game. The objective is to fill a 9x9 grid so that each column, row, and nine 3x3 sub-boxes contain the digits from 1 through 9, only using each digit once. A correct Sudoku solution is partially covered so that an individual can solve the rest of the numbers.

See project here

Download Project

Keywords

  • Algorithm: A step-by-step procedure for performing a calculation.
  • Sudoku: A number placement puzzle game where the objective is to fill a 9x9 grid with numbers. For information: see above.

User Documentation

How to Use It

To select a specific square/box on the Sudoku, you can directly click on it or you can navigate to it using your arrow keys. Once selected, the box should be highlighted blue to signify you are currently on this box. You can use the numbers on the top of the keyboard or you can use the numeric keypad to enter a number from 1-9 [123456789] in the box. If you make a mistake, you can delete it by selecting the box and using the “backspace” button on your keyboard or you can use the “delete” button. You can also replace the current number in the box by selecting another number. The arrow keys will allow you to traverse the Sudoku freely but will skip (miss) the unclickable grey boxes, allowing you to navigate to empty white boxes. Each arrow key represents the direction in which the selected box will move. You may use the arrow keys on the numerical keyboard, or you can use the keys “WASD” as well. The Sudoku does not wrap around, meaning you will not return to the beginning of the column or row if you reach the end of it.

White boxes indicate an empty box and can be selected or modified. Grey boxes indicate a fixed position or full box and cannot be selected or modified.

Your progress on the site is maintained with cookies, so that you can keep your score. If you delete or modify your cookies, the progress will change on the site.

The Options

Size

The size of the Sudoku is modifiable and is dynamically changable. The size is represented by the horizontal (width) and vertical (height) length of the Sudoku. The size is measured in pixels and changing the size will change every box on the board by the current pixel size. The limits for the size are 10 <= x <= 80 on both axes.

Buttons

  • New Game: This button will clear the board and generate a partially solved Sudoku or an empty board depending on which generation algorithm you have entered.
  • Validate: This button will validate the current state of the Sudoku. If there are empty spaces, it will automatically invalidate the Sudoku. It will bring up a windows dialog box whether the entered solution is valid or not. If it isn’t, the timer will continue, otherwise the timer will stop and you have completed the Sudoku.
  • Restart: The restart button will reset the clock and will remove all user entered numbers from the board.
  • Show Solution: This will reveal the correct answer/solution to the Sudoku which has been generated manually or automatically. Note: Once clicked, you cannot restart or validate the Sudoku – this is to prevent cheating–.
  • Show Statistics: This will bring up an alert windows dialog box which will display your current statistics of: games played; correct solutions; shortest time; revealed solutions. This is dependent on your local cookies and will change if you delete your cookies.
  • Show Rules: This will bring up an alert windows dialog box which will inform you of the rules of how to play.

Difficulty

The difficulty settings change the quantity of squares revealed. The harder the difficulty, the less squares revealed.

  • Easy: This mode of difficulty is for beginners and most of the boxes will be revealed.
  • Medium: This mode of difficulty is for the average player, where roughly a quarter of the boxes will be revealed. This is the default difficulty setting.
  • Hard: This mode of difficulty is for more experienced players, where very few boxes will be revealed.

Timer

The timer indicates how long you have taken on a specific Sudoku board. The timer will start as soon as you click “New Game”, will clear once a new game has started, and will stop once the Sudoku has been completed.

Random Generation

This options is for when you want to complete a randomly generated Sudoku.

  1. If the “Random Generation” tickbox is not already checked, check it.
  2. If you would like to change the difficulty of the Sudoku, go to the difficulty section and click on the tickbox which accommodate for your specific skill set. More information on the difficulties can be seen below.
  3. Click the “New Game” button, which will clear the current board and will replace it with a randomly generated board.

Manual Input

This option is for when you have a partially entered sudoku and you would like to see the solution for that sudoku.

  1. First, click the “Manual Input” tickbox.
  2. Then click the “New Game” button.
  3. Enter all the numbers into the designated boxes. If you make a mistake, you can erase that number by clicking in the same box and deleting it with backspace.
  4. Once done, click “Show Solution” to reveal the rest of the numbers.

If you want to change your input after seeing the solution, you can click the “Restart” button. This will remove all the numbers solved, leaving the numbers you have already entered in.

Technical Documentation

See source code here

Generation

The generation algorithm works by using a completed Sudoku as the parameter, which acts as a template for the algorithm. The algorithm works by swapping and relocating parts of the Sudoku, so in theory there should not be any errors.

The algorithm goes as follows:

  1. You can swap any row of three 3x3 blocks with any other row.
  2. You can swap any column of three 3x3 blocks with another column.
  3. Within each block row or block column you can swap single rows and single columns.
  4. Finally you can permute the numbers so there are different numbers in the filled positions as long as the permutation is consistent across the whole board.

This algorithm is not efficient nor is it a “perfect” solution. There are a limited amount of permutations for the Sudoku, meaning there is a limited amount of unique Sudoku boards. Using this algorithm, you cannot overcome this limitation, however it is the simpliest way of implementing a generation algorithm. The algorithm is pretty efficient compared to others due to the code merely swapped numbers from other sections of the board matrix.

Solution

There are quite a few different algorithms which will solve a partially filled Sudoku such as Crook’s algorithm, Knuth’s Algorithm X and of course brute-force (backtracking). I implemented a backtracking method which is a type of brute-force approach to solving the Sudoku. A pure brute-force method would fill up all of the empty spaces randomly with the numbers 1 to 9 until a valid solution is created for that specific board. A more efficient and reliable form of this is backtracking, where it fills up empty squares with a valid number and sequentially moves to the next square. If all possible numbers from 1 to 9 are invalid for any square that is selected, the algorithm will return to the last working solution, i.e moves back to the square where it was valid and continues from there, then iteratively repeats the process.

The backtracking approach I implemented performs a lot more efficiently than brute force algorithm. Backtracking requires about 37660 iterations, while naive brute force would probably have required about 9^{51}. iterations (51 blank spaces, 9 possible numbers each).

Validation

The program validates the solution by checking if every column, row and 3x3 row contains any duplicates and this must have a length of 9 for it to be valid. It does this by making use of sets to remove duplicates in each column, row or box and checking whether the length of that set is equal to 9. If it is, then it moves onto the next one, if not then it’s invalid and returns false. If all of them are true, then the function halts and returns true.