Ocaml track: assignment 3: Imperative programming


Goals

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.

Language concepts covered this week

Reading

Chapters 7, 8 and 9 of the textbook.


Problem description

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).

Solution strategy

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"):

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.

Program to write

Your program will read in a single Sudoku board stored in a file. The board is written in the following format:

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.

To hand in

The file sudoku.ml.

Supporting files

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:

This is a fun lab, so have fun writing the code!


References