Sudoku

Answer Question 1 - What is a "Sudoku".

A "Sudoku" game starts with a 9 by 9 matrix which contains 81 places. Most of the places are blank and some contain a number between 1 and 9.
The object of the game is to place a number between 1 and 9 (1 and 9 included) at each place.
There are two constraints:

• Each row and each column should contain all the numbers between 1 and 9. That means one of each.
  
• A 9 by 9 matrix can be subdivided in 9 "3 by 3" matrixes. Each of these sub matrixes should only contain one of the numbers between 1 and 9
• some times there are additional constraints. For example that both diagonals also should contain the numbers between 1 and 9

Answer Question 2 - What is involved in solving "Sudoku".

There are two ways to solve a "Sudoku": By Hand or automatic with a program.
The following picture shows the steps involved in solving a 4 by 4 "Sudoku"
Step 1 shows the situation that you have to solve.

1 2     3 
3       1 
    
2 3     
       
  Step 1

1 2     3 
3 4     1 

2 3     
     
   Step 2

1 2     34 
3 4     12 

2 3     
4 1    
   Step 3

1 2     34 
3 4     12 

2 3     4
4 1    
   Step 4

1 2     3 4
3 4     1 2

2 3     4 1
4 1     2 
   Step 5

1 2     3 4
3 4     1 2

2 3     4 1
4 1     2 3
   Step 6

The following explains what is done in each step.

1. In step 1 the top left 2 by 2 square is investigated. This sub matrix shows 3 numbers. The number 4 is missing and filled in.
2. In step 2 the top 2 lines and the 2 most left colums are investigated. Each one shows 3 numbers. The missing values are filled in.
3. In step 3 column #3 and row #3 are investigated. They contain the numbers 1,2 and 3. The number 4 is missing.
4. In step 4 column #3 and row #3 are completed
5. In step 5 the last missing number is filled in
6. Step 6 shows the solution.

You can solve a "Sudoku" by writing a program. This is an interesting tasks because you have to implement all the rules that are used to solve the game.
To test this program you start with a simple game that you know that can be solved. When the program finds the missing numbers your program is correct.
Next you test a more complex game and you try again etc etc.

Answer Question 3 - What is involved in making your own "Sudoku".

In order to make your own "Sudoku" you have to divide the program into two subroutions.

• One subroutine is called "Solve" which function is to solve the game.
• One subroutine is called "Make" which function is to create a game.

The general functionalty of the subroutine "Solve" is explained in Answer Question 2 .
The following functionality should als be implemented in subroutine "Solve":

1. The first is give all the rules you have a number, a level. The easiest one becomes level #1 etc. The most difficult one for example the level #8.
   This belongs to the subroutine "Solve".
2. The second is to test subroutine "Solve" how it handles errors. That means you use examples which the program cannot solve.

The following should be implemented as part of subroutine "Make":

1. The first step is to make the solution matrix. This matrix must be build accordingly to the constraints of the game. That means each of the rows and columns should contain one of the numbers between 1 and 9, both included. The same for each of the 3 by 3 matrixes.
   In order to make different games a random number generator has to be used.
2. The second step is to remove one randomly selected number from the matrix and to test with the subroutine "Solve" if this can be done. That means subroutine "Solve" should not generate an error.
3. The third step is to repeat step #2 as long as possible.
   Each time there are two possibilities.
   1. You remove a number and subroutine "Solve" does not find an error. That means you remove this number permanently and you try an other one.
   2. You remove a number and subroutine "Solve" finds an error. That means you restore the number and you try an other one.
   In the second case you also increase an error counter. When you find a solution this error counter is reset. When the counter reaches 20 (For example) you stop the make subroutine and you have your new game.

What you can also do is monitor the (highest) levels of the rules used. When the level reaches 4 you can also stop subroutine "Make" in order to make easier games.

Answer Question 4 - What is the relation a "Sudoku" and the "P = NP problem"

For comments about the "P = NP problem" in Wikipedia read this: "P versus NP problem" in Wikipedia
The "P versus NP problem" has to do with: if it is as easy to solve the problem as to test the answer.
In the case of a "Sudoku" it is in general much easier to test the solution than to solve the game (assuming that there is only one solution)
The interesting part of a "Sudoku" is that it is much more difficult to make a "Sudoku" than to solve a "Sudoku"

Reflection

Back to my home page Contents of This Document