Homework 4: Solving Sudoku

This homework assignment is a little harder than last month’s.

I’m still strongly encouraging everyone to stick with whatever new language they chose last month. The purpose of last month’s easy assignment was to introduce you to a new language; the purpose of this month’s assignment is to get you to use a few more features and learn a little more about the new language you chose.

Bring your solutions to our November meeting.

This month, you will write a program that solves the popular Sudoku puzzles.

If you’ve never heard of them, here is a description:

There are many algorithmic descriptions and links there as well, if you get stuck thinking about the problem on your own.

As input, your program should read a file in the following format:

.243..98.
..84.15..
7.......1
.9.1.7.43
.........
48.9.3.7.
2.......8
..78.43..
.35..629.

We’ll stick with 9 rows and 9 columns. Each line in the file corresponds to a single row in the Sudoku puzzle. There are nine characters on each line, and each character is either a digit, which represents a filled-in square that can’t be changed, or a period, which represents an empty square that must be filled in by your program.

Your program should print a solution out:

124375986
368491527
759682431
592167843
673248159
481953672
246539718
917824365
835716294

The solution must follow the Sudoku rules:

Bonus: If there is more than one solution, print them all.

Bonus 2: Come up with some heuristics or techniques that speed up your solution so it is faster than brute-force search.

Here is a very hard problem to try:

.......12
3......6.
....4....
9.....5..
.....1.7.
.2.......
...35.4..
..14..8..
.6.......

A brute-force solution on this problem will take a long, long time.

Here is a web site with many problems of different difficulties:

Feel free to discuss the problem or any other topics you are interested in on our mailing list (accessible via our Meetup Group).