Internet Problem Solving Contest

IPSC 2007

Solution to Problem F – Finally some Sudoku

This task was solvable in two different ways: either solve the puzzle by hand, or write a program that does the job for you. (Logical programs are good at solving Sudoku, so a reasonable option was to rewrite the input to a set of constraints and feed it into a logical program solver.)

The easy puzzle was probably more approachable to a pen-and-paper solution. Each of the boards A and B has a unique solution. We can find those separately, fill in C using the colored squares and solve it.

As for the computer assisted approach, a simple backtracking algorithm that keeps track of all the constraints was enough to solve both inputs.

In our program we are using a recursive function solve(). For each of the empty cells we keep a set of values that can still be used there. In each step we choose to fill a square where the number of possibilities is lowest. (I.e., if we are sure about some square, fill it, otherwise we sequentially try all possible values for some square.)

After we fill a square, traverse all affected cells (row, column, 3×3 square, same color), update their allowed sets and store these changes. Recursively try to solve the rest of the puzzle. If unsuccessful, use the stored changes to quickly undo them and proceed to try a different value.

Here are some pictures of both solutions:

Larger versions: easy output, hard output.