sudoku

EN47/COMP09-01 - Spring 2009 - Project
Project presented and demonstrated: Monday April 27, 2009
Project completion date: Monday April 27, 2009

overview

problem description

Sudoku is a logic-based number-placement puzzle. The objective is to fill a 9x9 grid so that each column, each row, and each of the nine 3x3 boxes (also called blocks or regions) contains the digits from 1 to 9 exactly once each. The puzzle consists of a partially completed Sudoku grid. [source: Wikipedia]

general strategy

Prove the values of empty position until either no more empty position is left to fill, or no more can be proven. [solver]

value proofs

Direct proofs: Deduct the value at a position based on known values at other positions.

If a position has only one possible value, then its value is known. [proof 1]
In a line/column/block, if there is only one empty position then its value is known (look for it). [proof 2]
In a line/column/block, if there is only one position in which a given value is allowed, then the value must be at that position. [proof 3]

Negative proofs: Determine which values are/ are not allowed at a position based on known values at other positions.

If a position has a known value, then no other position in the line/column/block can have this value. [proof 4]
In a line/column, if the only possible positions for a value occur in the same block, then the value cannot appear at any other position in the block. [proof 5]
In a block, if the only possible positions for a value fall in the same line/column, then the value cannot appear at any other position in the line/column. [proof 6]

organization

Sudoku solving tasks will be assigned to teams of 2 or 3 students.

Each team is responsible for:

designing an algorithm to solve their assigned task
implementing (coding) the solution
developing testing scenarios and systematically test the code
documenting: sub-problem (task), algorithm, code

Proofs that are not assigned to a team of students will be developed by "virtual teams" (i.e. simulated).

The code that successfully solves tasks will be integrated to produce a Sudoku solver as general as possible.

Performance evaluation for each team takes into consideration algorithm design, coding, documentation and presentation.

specifications

The program takes as input a Sudoku puzzle in the form of 9 lines of 9 values (starting from the top left position in the grid). values are digits from 1 to 9, and -1 for empty positions.

The program prints out the solved puzzle (Sudoku grid) or a statement that it cannot solve the puzzle.

getting started: basic code infrastructure

Go into your en47 directory and create a directory for the project (mkdir project). cd into it.
You will need to copy several files into your project directory using this command:
cp /comp/9/public_html/Project/Code/* .
This will copy the following files into your directory: sudoku.cpp, Makefile and test-grid1.txt.
Open sudoku.cpp in Emacs (emacs sudoku.cpp &). For now, this file defines a few useful constants, data structures and printout functions. This code is intended to serve as reference when you start coding the solution for your task.
To compile your code type make at the command line.
To run the resulting executable type ./sudoku at the command line. Note that to avoid typing the values of a grid everytime (81 values!), you can type them in a text file (test-grid1.txt is an example of such a file) and feed the text file as input to your program when you run it. For example:
```
./sudoku < test-grid1.txt
```

sudoku grid

The sudoku grid is encoded as a 3-dimensional array:

  const int GRID_DIM=9;
  const int GRID_VALUE=0;
  ...
  int grid[GRID_DIM][GRID_DIM][GRID_DIM+1];

grid[l][c][GRID_VALUE] contains the value at the position at line l and column c.

grid[l][c][v] for v=1..9 contains ALLOWED if value v is allowed, NOT_ALLOWED otherwise.

text input

Read 9 lines of 9 integers, line by line, starting from the top left position:

  cin >> grid[l][c][GRID_VALUE];

The values can be entered interactively (keyboard). To save time, the values can be read from a text file, which contains the same text as would be entered on the keyboard, for example:

  ./sudoku < test-grid.txt

Empty positions are indicated with value UNKNOWN (const int UNKNOWN=-1;).

text output

The code base contains simple functions allow to print the whole grid, a line, a column, a block or a single value, to the terminal. Another function prints all allowed values for a given position.

Constants and arrays of constants encode block identifiers, and line/column boundaries for each block.

Function prototypes:

  void PrintGrid(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1]);
  void PrintGridLine(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l);
  void PrintGridColumn(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int c);
  void PrintGridBlock(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int b);
  void PrintGridValue(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l, int c);
  void PrintAllowedValues(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l, int c);

code architecture

main

The main function reads the puzzle, implements the general strategy for solving the puzzle, and prints out the result.

Algorithm

Brute force approach:

Read puzzle values
Initialize grid
Print message and puzzle grid
WHILE the puzzle is not solved, and progress can be made:
- For each line, apply all line proofs
- For each column, apply all column proofs
- For each block, apply all block proofs
- For each position, apply all position proofs
Print message (solved or cannot solve) and grid

proof functions

Proof functions take as input the grid, a line and/or a column and/or a block, and/or a value, and may return a boolean value (true/false) that indicates whether the proof was applied (and resulted in a change), for example:

  bool Proof(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l, int c, int b, int v){

    if(cond1 && cond2 && ... ){
      ...
      return true;
    }
    else{
      return false;
    }
  }

utility functions

Apart from the print functions listed above, some additional utility functions might be useful in the implementation of the various proof functions.

These functions will be identified and implemented as needed. Examples include:

// A function that returns true if value v is allowed at position l,c, false otherwise:
bool IsAllowed(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l, int c, int v);

// A function that sets the status (ALLOWED/NOT_ALLOWED) of value v at position l,c: 
void SetStatus(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l, int c, int v, int status);

// A function that returns true if the puzzle is solved, false otherwise: 
bool IsSolved(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1]);

// A function that returns the block in which the given location falls
int WhatBlock(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l, int c);

proof 1

team members

Dan M, Matt, Andre

problem description

Design an algorithm and write the functions that implement proof 1:

If a position has only one possible value, then its value is known.

specifications

Function:

bool OnePossibleValue(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l, int c);

Input: grid, line index (int l), column index (int c)

Output: true if the rule was successfully applied and resulted in a change, false otherwise.

algorithm

input: line l, column c

if value is already known, return false
set v to 1
while v is a valid value and v is not allowed
- increment v
if v is a valid value
- set allowed to v
- increment v
while v is a valid value and v is not allowed
- increment v
if v is a valid value
- more than one allowed value: return false
set value at position l,c, to allowed
return true

test cases

How to test the coded solution?

proof 2

team members

Virtual team

problem description

Design an algorithm and write the functions that implement proof 2:

In a line/column/block, if there is only one empty position then its value is known (look for it).

specifications

Functions:

bool OneEmptyLinePosition(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l);
bool OneEmptyColumnPosition(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int c);
bool OneEmptyBlockPosition(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int b);

Input: grid, line/column/block index (int l/c/b)

Output: true if the rule was successfully applied and resulted in a change, false otherwise.

algorithm

Sequence of steps that solve the task (go from inputs to output)

test cases

How to test the coded solution?

proof 3

team members

Virtual team

problem description

Design an algorithm and write the functions that implement proof 3:

In a line/column/block, if there is only one position in which a given value is allowed, then the value must be at that position.

specifications

Functions:

bool OnePossibleLinePosition(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l, int v);
bool OnePossibleColumnPosition(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int c, int v);
bool OnePossibleBlockPosition(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int b, int v);

Input: grid, line/column/block index (int l/c/b), column index (int c)

Output: true if the rule was successfully applied and resulted in a change, false otherwise.

algorithm

Sequence of steps that solve the task (go from inputs to output)

test cases

How to test the coded solution?

proof 4

team members

Chris, Dan F, Bill

problem description

Design an algorithm and write the functions that implement proof 4:

If a position has a known value, then no other position in the line/column/block can have this value.

specifications

Function:

void KnownValue(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l, int c);

Input: grid, line index (int l), column index (int c)

Output: none

algorithm

Take input of a given position
Test if the value at this position is known
If value is not known, return false
If value is known, proceed
Loop through the line, change the status of every position in that line to NOT_ALLOWED, except the original position
- First, change the status of every position less than the original position
- Second, change the status of every position more than the original position
Loop through the column, change the status of every position in that column to NOT_ALLOWED, except the original position
- First, change the status of every position less than the original position
- Second, change the status of every position more than the original position
Loop through the block, change the status of every position in that block to NOT_ALLOWED, except the original position
- First, loop through both lines within the block that the known value is not in
- Second, loop through both columns within the block that the known value is not in

test cases

We tested our code using the test-grid1 text provided in the project file, and modifying the program to print out the allowed values at all positions, then manually checking to ensure that no values that should not be allowed were listed as allowed, and no values that should be allowed weren't listed.

proof 5

team members

Virtual team

problem description

Design an algorithm and write the functions that implement proof 5:

In a line/column, if the only possible positions for a value occur in the same block, then the value cannot appear at any other position in the block.

specifications

Functions:

void LineInBlock(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l, int v);
void ColumnInBlock(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int c, int v);

Input: grid, line/column index (int l/c), value (int v)

Output: none

algorithm

Sequence of steps that solve the task (go from inputs to output)

test cases

How to test the coded solution?

proof 6

team members

Ellen, Sarah

problem description

Design an algorithm and write the functions that implement proof 6:

In a block, if the only possible positions for a value fall in the same line/column, then the value cannot appear at any other position in the line/column.

specifications

Functions:

void BlockLine(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int b, int v);
void BlockColumn(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int b, int v);

Input: grid, line/column index (int l/c), value (int v)

Output: none

algorithm

Set record=-1
FOR each line/column
- FOR each position
  - IF the value is possible
    - THEN IF record == -1
      - THEN set record=line#/column#
    - ELSE IF record != line#/column#
      - RETURN false
IF record != -1
- FOR every position in the line/column that is outside of the block,
  - set the position's value to not allowed

test cases

How to test the coded solution?