Scala Assignment 1: Sudoku
Fall 2012, David Matuszek

Purpose of this assignment

General idea of the assignment

In Sudoku, you are given a 9x9 grid, divided into nine 3x3 "boxes," as shown on the right. Each box has nine "cells," and some of these cells have digits in them (but most are blank).

The puzzle is to fill in the rest of the grid so that every row, every column, and every 3x3 box contains the digits 1 through 9. Your assignment is to write a program to partially solve Sudoku puzzles.


This image is from http://www.sudoku.com/, which is a very nice site with additional explanations and puzzles (and a Sudoku program for sale).

 
Roll your mouse on and off the grid.
You may have to wait for the page to load fully

Details

Your job is to write a program to solve, or partially solve, Sudoku puzzles.

Ask the user to locate a text file (by using a JFileChooser) containing a Sudoku puzzle. The file should contain a Sudoku puzzle to be solved. The format should be nine lines, with nine numbers on a line, separated by whitespace (spaces and/or tabs). For extra neatness, allow blank lines in the input. Use underscore, _, to indicated a "blank" (unfilled) location in the puzzle. For example:

 _ _ 4   _ _ _   _ 6 7
 3 _ _   4 7 _   _ _ 5
 1 5 _   8 2 _   _ _ 3
_ _ 6 _ _ _ _ 3 1 8 _ 2 1 _ 5 6 _ 4 4 1 _ _ _ _ 9 _ _
7 _ _ _ 8 _ _ 4 6 6 _ _ _ 1 2 _ _ _ 9 3 _ _ _ _ 7 1 _

Algorithm

Create a 9x9 array of lists. Each list will initially contain the digits 1 through 9.

Read in a puzzle from a file. For each filled-in value in the puzzle, set the corresponding list in your array to contain just that one number. (This means that a "known" location in the array is one containing a list with a single element.

Print the array you just read in.

Repeat the following, as many times as necessary, until you can make no further changes:

Print the solved puzzle in the same format, or in a "prettier" format if you like (with vertical bars and horizontal lines).

For each remaining unsolved location in the array, print out the row and column of the location (as 1 through 9, not 0 through 8!), and the remaining digits that could possibly still be in that location.

Grading

Every method should have Scaladoc comments. Be sure to use the @author tag in the comment for the main object.

Special rules

The reasons for these rules are twofold: (1) They are intended to get you using some of the unique Scala constructs, and (2) It is easy to write a program to count these keywords.

Due date

Wednesday, November 14 16, before 6am, via Blackboard.