Although ocaml is normally used as a functional programming language (or, more often, as a mostly-functional programming language), it possesses all the imperative features that programmers in languages like C, C++, Java etc. are used to. Sometimes the syntax is a bit unpleasant, but you can always write imperative code if you feel the need. In this lab we will do just that by writing a program which is a solver of the popular Sudoku puzzle.
Chapters 7, 8 and 9 of the textbook.
We will be writing a program which will solve instances of the Sudoku puzzle. A good description of this puzzle is in the Wikipedia article on the puzzle. In brief, a Sudoku puzzle is a 9x9 grid, some of whose squares are empty and some of whose squares contain a number between 1 and 9 (inclusive). The goal is to fill all empty squares with numbers between 1 and 9 such that three constraints are satisfied:
That's it. It's a very simple puzzle, but fairly difficult to solve by hand. You'll see that a program can make short work of the toughest Sudoku problems (at least with a 9x9 board).
It's possible to write very elaborate Sudoku solvers that use intelligent searching methods, but we won't be doing that here. Instead, we'll use a simple brute force recursive algorithm (described below in "sudokode"):
Find the next empty square. By "next" we mean the next in the row (starting from the first row), or if the row has no more empty squares, the next empty square in the next row, etc.
For each number between 1 and 9:
Fill the square with that number.
Check to see if any of the constraints are violated. If they are, go on to the next number.
Try to solve the resulting board using the same algorithm we're describing now.
If that works, we're done. Otherwise, try the next number.
If none of the 9 numbers leads to a solution, the board is unsolveable.
If you think about it, we are simply trying every possible number combination that will fit into the blank squares, subject to the constraints. Though seemingly dumb, this algorithm will be able to solve any 9x9 Sudoku puzzle in a few seconds.
Your program will read in a single Sudoku board stored in a file. The board is written in the following format:
There are nine lines, one for each row of the board.
Each line has exactly nine digits in it, followed by a newline.
Each digit is between "0" and "9". "0" means that the correct number at that location is unknown; any other digit means that the correct number at that location is that number.
For instance, here is a sample board:
000000000 000010092 086000040 001560000 000003620 000000507 030000080 090802000 007004300
And here is its solution:
412985763 753416892 986327145 271568934 549173628 368249517 634751289 195832476 827694351
Your program will read in a board from a file, solve it using the algorithm described above, and output it in the format given above.
Since the purpose of this lab is to teach imperative programming in ocaml, feel free to be as imperative as you like in the solution method. It's possible to write a very brief functional solution, but we want to see at least some imperative code (probably involving mutable arrays as a data structure for the board).
This program may sound hard, but it really isn't; our solution is only 154 lines of code, and we're providing you with 70 lines of it for free. You don't have to use our code as a starting point to write your solution, but we recommend it.
The file sudoku.ml
.
We've collected all the supporting files into a gzipped tarball which you should download, unpack
(with the command "tar zxvf lab3.tar.gz
") and edit as needed.
We provide:
An incomplete version of the program, which you can use as a template for building your own solution.
A Makefile
for compiling your code. Type
make
to make your code, make test
to run the test
program, and make clean
to get rid of the compiled programs and
intermediate files.
Notice that we use the ocamlopt.opt
program as the compiler
instead of ocamlc
. This is the native-code compiler; it will
make your program run much faster.
A test script and 10 boards which should be solvable by the program.
The test script will run through them and test if your program solves them
correctly. There is also a file called "correct_solutions
"
which contain the correct solutions; this file is used by the test
script.
This is a fun lab, so have fun writing the code!