Redi Gokaj – Blog

SUDOKU GAME GENERATOR AND SOLVER

This assignment consists of implementing a sudoku game solver and a random puzzle generator (of course, a solved sudoku puzzle). The interface is done in C, and the program functions are done in assembly. So, the C code calls the assembly code in order to accomplish the right creation of a random sudoku, and in the same time, to accomplish a right solution for the given sudoku which is taken from the user. The way that this program takes the sudoku from the user is in this way: firstly, the user enter how many number he/she will put on the grid. After that, he/she will have to enter the coordinates of the numbers and the corresponding values. Remember that when you enter the coordinates you should start counting form index 0. So, the matrix where the sudoku is stored is thought as a matrix 9×9 which its coordinates are [0,8]x[0,8].

The C Code

The code written in C doesn’t have so many explanations because it is very simple. Firstly it starts by defining the function prototype of the asm code. After that, there is a prototype defining the function which takes the values from the user and processes them. In the C code there is an array with length 81, and this is defined as an array filled with zeros. The assembly code takes the address of the start of this array called grid. After that, it will be manipulated according to the used_i[] and used_j[]. used_i contains the i coordinates of the entered values. In the same manner used_j contains the j coordinates of the entered values. Here, i is the horizontal coordinate expressing the row (range: [0,8]).And, j is the vertical coordinate expressing the column (range: [0,8]). n is the number of elements that the user will enter. According to this number a loop to take the values one by one is arranged. GetCountTick() is a function which produces a random number according the the current time. This number is used as a seed to create random numbers inside the assembly code. Another thing that the C code does, is that it prints in the screen the grid[]. So, we print it after modifying it. Assembly directly modifies it because the grid[] is called by reference. is_true is a variable which will store 1 or 0. Assembly code returns 0 if the given sudoku puzzle doesn’t have any solution.

The Assembly Code

Firstly the procedure prototypes are defined. After that using EQU, the addresses of the variables coming from C code are given some names like grid, used_i, used_j, n, seed. The proper ebp + 8, 12, 16, 20, 24 is used to set the address name. As you see, it is increased by 4 because we are using long, which is taken as a DWORD in assembly. Many explanations about the variables or the procedures of this code are explained with the comments inside the code. Here I will mention the logic of the program. The generator is done using the solver, so I will firstly explain the solver. The procedure called solve makes a double loop for current_i and current_j. So, both start from zero, but when current_j reaches 8 after that current_i increases and curret_j becomes again zero. So this is the loop to imagine the one dimensional array[81] as a two-dimensional array[9][9]. To calculate the place in theone-dimensional array this formula is used: 4*(current_i*9 + current_j). After that, the program adds this to the esi which shows the address of the start of the grid. As you see, the formula above is multiplied by 4 because DWORD is used and this is composed from 4 bytes.

To solve the sudoku, here is the short algorithm called backtracking:

current_i and current_j are initiated as 0, but they are just a “make up” because the real thing are the numbers [0, 80] but they are expressed [0, 120] after multiplying it by 4.

lCheck if the value is a default one. If it is, go to the next value.

lIf it is not, increase the current value by 1.

lIf the current value is greater than 9, then call backtracking.

lIf the current value is smaller or equal to 9, then check row, column, group to see if it is an appropriate place for it.

lIf the check results positive, go to the next value.

lIf the check results negative, increase the current value by 1.

This algorithm will be repeated until current_i will be greater then 8, which means all the rows are filled with correct values. The backtracking procedure makes this job:

lIt makes 0 the current value.

lIt goes back one value.

lIf it i a default value which cannot be changed, it goes again back one value.

lIf it is a value that can be changed, it increases by 1 that value.

Because that current_i and current_j are global variables, after the backtracking is called, the current value’s coordinate is the value which the backtracking sets last. And this can be used to go on with the procedure solve. Because in the procedure solve the main job takes place. In the backtracking procedure if current_i tries to be less then zero it means that none of the tried values doesn’t solve the sudoku. Because that the backtracking is a brute-force like procedure, it tries all the possible values. So, if current_i tries to be less than 0, then the program returns 0 to eax which will mean that the given sudoku doesn’t have any solution.

The program also checks the initial puzzle if it has any same values in the same row, column or group. This is done by three procedures: checkRow, checkColumn, checkGroup. The first two procedures are similar to each other. When checking the row, for each check, the index is increased by 4. But when checking the column the index is increased by 9*4 = 36. Because you should remember that in assembly we are using the one-dimensional array. And when added 36 to the index, it is same as going to the next row but remaining still in the same column. Checking the group is a bit different. It requires to check the current_i and current_j order to know in which one of the 9 groups we are talking about. You can see the comparisons inside the code. cmp is used for them. After finding the current group coordinates, then there will be a small loop by moving 3 to ecx. This checks the 3 values in the current row, and does the same thing for the two preceding rows.

After these checks have been successfully completed it means that the value in the current position is appropriate for that place. The procedure check_coordinate checks if the current value is a default value or not. By using the current coordinates, the current value is stored in the variable value by the use of the getValue procedure. This is all about the solver. So, it is mainly a simple algorithm but using a brute-force like algorithm.

The sudoku generator is done by the help of the sudoku solver. So, randomly values 1-9 are put randomly on the grid. A current_i and a current_j is generated randomly. Whatever the random coordinate is, it is impossible to be a wrong place for the value [1, 9] because just 9 values are put on the board. Even if they coincide to be in the same row, column or group, there is no problem. When these 9 values are put in the empty board, then the solve procedure is called, and this is solved. After that this is shown to the user. There is also another procedure to hide the cells, in order to make the new generated puzzle a real sudoku which can be solved then by the user (of course, if he wants). _hideCells procedure generates random coordinates and puts 0 on them. In the code it generates 70, but some times it coincides that the same coordinate is generated, so it will never hide 70 cells. Anyway, it makes a new sudoku puzzle.

Click to Download