The sudoku solver
Surviving in a terminal (not graded)
As a first step, you will have to learn how to survive on a Unix-like system where you only have a terminal. It's important for this course because you will have to manually compile and execute your code. If you are already comfortable with a terminal, you can skip this exercise.
So, first, you have to know that when you launch a terminal, the terminal executes a process named bash (Bourne-Again shell). bash is what we name an interactive shell in command line. You type commands, and the shell executes them.
Any Unix system is organized with folders that contain files and sub-folders. On a Unix system, we don't use the term "folder", but we use the term "directory". The root directory is named / (slash) on any Unix system, and the directory separator is also /. With that, you can give full paths, for example, /usr/bin/tar is the full path that names the file tar located in the directory bin, which is itself located in the usr sub-directory of the root directory (note that you have three directory: /, /usr/ and /usr/bin/).
At any time, bash considers two directories:
- The home directory: it's the basic directory where you have all your user files. Typically, in this directory, you will find the Desktop directory, where you have the files that you show in the graphical user interface of your system, or the Document directory, where the applications store by default your documents (e.g., word files etc...).
- The working directory: it's the directory that bash considers as the default directory when it is looking for a file. You can change it with the cd name command. If name is the name of a directory located in your working directory, then the new working directory becomes name. At a high-level, it's exactly like double-clicking on a directory in your file explorer. When bash starts, it initializes the working directory to the home directory.
A Unix system considers also two special directories:
- .: is the working directory. For example the path hello.txt and the path ./hello.txt both represent the same file: the file hello.txt located in the working directory. The usage of . is not very obvious at a first glance, but when you write scripts, it becomes very useful.
- ..: is the parent directory. For example the path /usr/bin/.. and /usr represents the same directory: the directory usr located in the root directory.
The most important Unix command to manage directories are:
- pwd (print working directory): print the working directory,
- echo $HOME: print the home directory,
-
cd path (change directory): change the working directory to path (path can be . or ..)
- cd (without any argument): when you omit the path, you just go back to your home directory
-
ls (list): list the content of the working directory:
- ls path lists the content of the directory path, for example ls .. lists the content of the directory that is the parent of the working directory.
- ls -a (all) lists also the hidden files. A hidden file is a file that begin with a dot (.),
- ls -l (long) display many useful information (size of the file, owner etc...).
- mkdir path (make directory): create the directory path,
- rmdir path (remove directory): remove the directory path,
-
cp from to (copy): copy the file from the name from to the name to (copy to to and keep from).
Only works if from is not a directory.
- cp -a from to: copy recursively from from to to. If from is a directory, copy all the sub-directories and files of the sub-directories.
- cp -i / cp -f: copy in interactive or force mode. In interactive mode, ask before destroying the destination. In force mode, silently override the destination (be careful!).
-
mv from to (move): move the file from the name from to the name to (copy to to and destroy from).
- mv -i / mv -f: move in interactive or force mode. In interactive mode, ask before destroying the destination. In force mode, silently override the destination (be careful!).
-
rm path (remove): delete the file path. Only works if path is a file.
- rm -r path: remove recursively path. If path is a directory, it means that you remove all the files and sub-directories reachable from path, use with caution!
- rm -f / rm -i: as for cp or mv (interactive or force mode).
Be careful with the -i, -a, -r switches of cp, mv and rm: you can easily loose files with that because bash does not manage a trashcan like your graphical user interface!
A final note: in bash, when you type the tab key, bash can complete the command. If bash has several possibilities to complete the command, it emits a bip and nothing else happens. You just jave to re-type tab to see the possibilities, and to continue to type your command. It's very useful. Otherwise, bash memorizes the last commands in a history. You can retrieve them simply by using the up and down arrows.
Home directory
By using a bash command, find your home directory. Try to also find it in the (graphical) file explorer of your operating system (e.g. windows explorer, finder).
Create a directory for the course
Create a directory named cse201 in your home directory. Check with a graphical file explorer that the directory exists.
Hello World!!! (not graded)
Create a directory lab1 in the cse201 directory. In lab1, create a file hello.c with a code editor (e.g., vscode, emacs, vim, please don't use gedit, nano or notepad which are really not designed to write code). In hello.c, write an application that prints Hello World!!! in the terminal and exits by returning the value 0. This value 0 means "the command ended successfully" for a bash. Any other value means that an error occurred.
In the terminal, use gcc to compile your amazing application. For that, you have to use the command:
- gcc: gcc is the program that compiles a c file into an executable,
- -Wall: indicates that you want gcc to report any warning. This is very useful to avoid mistakes that may lead to bugs.
- -Werror: indicates that you want gcc to consider any warning as an error. In conjunction with -Wall, -Werror is very helpful to avoid bugs.
- hello.c: the source file that you want to compile,
- -o hello: generates the executable in the file hello.
By using ls, check that the directory now contains a hello.c and a hello file.
Finally, start your application in the terminal with the command ./hello. This command means that you want to execute the program hello located in the working directory (i.e., the . directory).
The sudoku solver
In this exercise, you will write a sudoku solver. A sudoku is defined by a grid of 9 columns by 9 rows. Each cell must contain a number between 1 and 9. The aim of the game is to fill in the grid in such a way that each number between 1 and 9 appears at most once in (i) each row, (ii) each column and (iii) each of the sub-squares shown in the figure below. At the start of the game, some numbers are placed in the grid, and the player has to find the remaining ones.
The grid solving the sudoku shown above is shown below:
To represent a grid in C, we could use a two-dimensional array of size 9 by 9. However, a two-dimensional array will turn out to be difficult to manage with the algorithm that we will implement to solve the sudoku. For this reason, we advise you instead to implement the grid with a one-dimensional array of 81 elements. With such a an implementation, you access the j th column of the ith line of the grid simply by accessing the element at position i*9 + j in the one-dimentional array.
In order to test your application, you first need some sudoku grids. For that, you have to go to the directory cse201/lab1, and then to execute the following commands in the terminal:
If everything went well, you should now have a sub-directory named grids, which contains some sub-directories that start with the name grid. Among the grids, they all have a solution except grid02, which cannot be solved. You can use this one to check if your sudoku solver can also handle unsolvable properly.
Write a sudoku.c file that:
- quits with a message if the program does not exactly receive one argument,
- and prints this argument in the terminal.
For example, running ./sudoku grids/grid01/grid.bin should output grids/grid01/grid.bin.
To manage the arguments, you have to know that:
- The signature of the main function is int main(int argc, char* argv[]),
- argc gives the number of arguments, knowing that the name of the program itself account for one argument,
- argv[i] is the ith argument (argv[0] is the name of the program).
The argument provided to the program is a path to a binary file that contains a grid. In details, the binary file contains 81 integers (4 bytes each). Write a function int read_sudoku(const char* path, int grid[]) that reads the content of the file path into the grid grid. The function has to return -1 if an error occurred and 0 otherwise. In the main function, instead of writing the argument of the program, you have to call read_sudoku with the argument.
In order to read a file, you need these functions:
- int open(const char* path, int oflags) (provided by fcntl.h): open the file path and returns a file descriptor that can be used to access the file. oflags indicates how you want to open the file (read, write, create etc...). In our case, we want to read from the file, so we will use the flag O_RDONLY.
-
ssize_t read(int fd, void* buf, size_t nbytes) (provided by unistd.h): read nbytes in buf from the file descriptor fd. You will better understand what is void* in the next labs.
For the moment, imagine that void* means "any array".
As a result, to read the content of the file identified by the file descriptor fd,
you have to insert this code:
Thanks to that, read will read 81 times the size of a int from the file identified by fd, and put these bytes into the grid.read(fd, grid, 81 * sizeof(int));
In order to test your program, you have to run ./sudoku grids/grid01/grid.bin.
Note that you can find a lot of useful information about the open and read by typing the command man 2 open or man 2 read in the terminal.
Write a void print_sudoku(int grid[]) function that prints the sudoku grid in the terminal.
In order to test your program, you have to run ./sudoku grids/grid01/grid.bin.
We propose that you solve your grid using a backtracking method. This method involves trying out values and, if they lead to an inconsistent grid, going back to try a different value. Modify your program so that it solves the sudoku using this method.
At a high level, you need to iterate through the grid with a variable cur. This variable is initialized to 0, and the algorithm loops while cur has not reached 81 (which means the grid has been solved) and while cur has not dropped below 0 (which means the grid cannot be solved).
For a given cur, the algorithm must try a new value for the cell grid[cur] (if it is not initially given) by incrementing its value. If this value reaches 10, it means that a value tried in a previous cell does not lead to a solution for the grid, so the algorithm must backtrack. Otherwise, if this new value conflicts with a value already in the grid, the algorithm should try the next value. Finally, if the new value does not conflict, the algorithm can attempt to solve the rest of the grid by moving to the next cell.
Since the algorithm modifies the grid in place, the grid contains both initial values and tried values. When the algorithm backtrack, cur has to go back to the previously tried value by jumping the initial values. For this reason, the algorithm has to know which cells initially contain a value. For that, you should define a boolean array named fixed and set a cell's value to true if and only if that cell initially contains a value (i.e., if the corresponding cell in grid initially has a value other than 0).
Once you know where the initial values are, at each iteration, your code has to handle these cases:
- If grid[cur] contains an initial value, the algorithm has to increment cur,
- Otherwise, the algorithm has to increment grid[cur] by 1.
At this step, you have different choices:
- If grid[cur] is equal to 10, it means that a previous cell contains a value that makes the grid unsolvable.
The algorithm has thus to backtrack by:
- Setting the value of grid[cur] to 0 for the next attempts.
- Decrementing cur to the previous non initial value. Note that, cur can become lower than 0. If this happens, it means that the grid does not have a solution.
- If grid[cur] is strictly lower than 10, you have to check that the new value of grid[cur] is valid. For that, you have to verify that the value of grid[cur] only appears once in (i) the column of grid[cur], (ii) the line of grid[cur], and (iii) the square of grid[cur]. If the value is valid, you can increment cur to work on the next cell in the next loop iteration. If the value is not valid, you don't have anything to do: a new value for grid[cur] will be tested in the next loop iteration.
- If grid[cur] is equal to 10, it means that a previous cell contains a value that makes the grid unsolvable.
The algorithm has thus to backtrack by:
In order to test whether a value is correct, you need two variables column and line, which give the coordinate of cur in the 2-dimensional grid. In details, column is equal to cur % 9, while line is equal to cur / 9.
- To test the line of cur, you have to compare the value of grid[cur] with the value located at grid[line * 9 + i], where i goes from 0 to 9.
- To test the column of cur, you have to compare the value of grid[cur] with the value located at grid[i * 9 + column], where i goes from 0 to 9.
- To test the square of cur, it's slightly more complex. You need the coordinate of the upper left corner of the square that contains cur. The column csquare of this upper left corner is equal to 3 * (column / 3) and its line cline is 3 * (line / 3). Then, you have to compare the value of grid[cur] with the value of grid[9 * ((cline * 3) + i) + (ccolumn * 3) + j] where i and j go from 0 to 3.
