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.

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

organization

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

Each team is responsible for:

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

  1. Go into your en47 directory and create a directory for the project (mkdir project). cd into it.
  2. 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.

  3. 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.
  4. To compile your code type make at the command line.
  5. 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:

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

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

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

test cases

How to test the coded solution?

arjf © 2008-2009