sudoku

EN47/COMP10-04 - Fall 2008 - Project
Project presented and demonstrated: Tuesday December 2, 2008
Project completion date: Thursday December 4, 2008

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.

In a line/column/block, if there is only one empty position then its value is known (look for it). [proof 1]
If a position has only one possible value, then its value is known. [proof 2]

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

In a line/column/block, if a position has a known value, then no other position in the line/column/block can have this value. [proof 3]
In a line/column/block, if two positions have only two possible values and these values are the same, then no other position in the line/column/block can have either 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 1 to 4 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

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.

Each team has a leader (elected by the team) who will be the point of contact. It is the responsibility of everyone in a team to ensure that the team functions properly.

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

Type use leda.
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/EN47/public_html/Project/Code/* .
This will copy the following files into your directory: sudoku.cpp, visualize.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.

proof functions

Proof functions take as input the grid, a line and/or a column and/or a block, and/or a value, and return a boolean value (true/false) that indicates whether the proof was applied, 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;
    }
  }

solver infrastructure and algorithm(s)

team members

Phil (*), Ricky, David J., Kory

problem description

Create the backbone of the system and implement the main function to call the functions created by the other groups.

algorithm

Brute force: scan all lines, all columns, all blocks, all positions and call functions that apply, for all possible values if necessary.

utility functions

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 for a given position l,c:

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

proof 1

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

team members

Charlie (*), Farhan, Evan

problem description

Determine that the only empty position in a given line/column/block has exactly one value and that it is that value.

specifications

There will be three different functions, each specific for a line, column, or block. Each function will take the whole grid as input (with three dimensions [GRID_DIM] [GRID_DIM] [GRID_DIM+1]) The second parameter for each function will be a given line, column, or block given as an int.

Prototypes:

  bool OneEmptyLinePosition(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int line);
  bool OneEmptyColumnPosition(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int col);
  bool OneEmptyBlockPosition(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int block);

algorithms

OneEmptyLinePosition(__);

Loop through the line until an "unknown" position is found (empty position)
- Continue with function only if no other positions in line are "unknown"
Set values of the "unknown" position for which other positions in the line are known to "not allowed"
Look for the only "allowed" value for the "unknown" position
Set the value of this position to the "allowed" value (update the grid)
Set return value equal to "true"

OneEmptyColumnPosition(__);

Loop through the column until an "unknown" position is found (empty position)
- Continue with function only if no other positions in column are "unknown"
Set values of the "unknown" position for which other positions in the column are known to "not allowed"
Look for the only "allowed" value for the "unknown" position
Set the value of this position to the "allowed" value (update the grid)
Set return value equal to "true"

OneEmptyBlockPosition(__);

Loop through the block until an "unknown" position is found (empty position)
- Continue with function only if no other positions in block are "unknown"
Set values of the "unknown" position for which other positions in the block are known to "not allowed"
Look for the only "allowed" value for the "unknown" position
Set the value of this position to the "allowed" value (update the grid)
Set return value equal to "true"

proof 2

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

team members

Gabe (*), Mengyu

problem description

If there is only one possible value left that could occupy a space, set the value in that space to be the possible value.

specifications

Prototypes:

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

algorithm

Start checking possible Z values for each X,Y coordinate.
Once a possible value is found, if another is found, nothing more happens.
If no other possible values are found, then that value equals the possible value.

proof 3

(In a line/column/block,) if a position has a known value, then no other position in the line/column/block can have this value.

team members

Steve (*), Yushi, Justin

problem description

If rule 3 applies, disallow the value everywhere else in the line, column and block the value is in.

specifications

Prototypes:

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

algorithm

If grid[line][column][GRID_VALUE] is not UNKNOWN then

Record the value
For each position in the line:
- Set value to NOT_ALLOWED
For each position in the column:
- Set value to NOT_ALLOWED
Determine the block
For each position in the block:
- Set value to NOT_ALLOWED

proof 4

In a line/column/block, if two positions have only two possible values and these values are the same, then no other position in the line/column/block can have either value.

team members

Laura (*), James, Raymond

problem description

If two positions in the same unit can be ((only two) and (the same two)) possible values, those values cannot be used elsewhere in the same unit.

Specifications

input: 3d grid with all known values (l,c,v grid).

output: did we make any changes? (bool)

Will produce 3 separate functions for lines, columns, and 3x3 boxes.

Prototypes (public functions):

  bool Pairs_box(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int b)
  bool Pairs_line(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l)
  bool Pairs_column(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int c)

Prototypes (utility functions):

  // number of values that are ALLOWED at position
  int NumberAllowed(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l, int c);

  // check whether ALLOWED/NOT_ALLOWED values are identical at positions l1,c1 and l2,c2
  // assumes only 2 allowed values (previously checked)
  bool SameTwoAllowed(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int l1, int c1, int l2, int c2);

algorithm

Check for positions within the unit which allow only two possibilities, generate array indicating which positions have only 2 possibilities.
1. Do this by cycling through the unit and cycling through the possibilities for each position. Each time a possibility registers ALLOWED add 1 to the 2VA for that position.
Check whether the number of positions allowing two possibilities is greater than or equal to 2, if not return false.
For each position in the 2VA array that is 2, check whether one of the values is the input value. If so, set that position in the 2VA array to 0.
Check whether the number of positions allowing two possibilities, one of which is the value in question is greater than or equal to 2, if not return false.
Set changeMadeFunction to FALSE
For each position in the 2VA array that is 0, check whether the other possible values match each other for any pair of positions.
1. Use function for comparing two arrays.
2. If YES
  1. set the matching positions to -1 in the 2VA array.
  2. Then cycle through the unit and for every position not marked with a -1 in the 2VA array check whether the possibility for the value in question is NOT_ALLOWED, if not set it to NOT_ALLOWED and set changeMadeFunction to TRUE.
  3. Upon completion, return changeMadeValue.
3. If NO
  1. return changeMadeValue.
Repeat steps 1-6 for all values 1-9.

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.

team members

Mei Wei (*), Brad, Rachael

problem description

In a line or column, if the only positions allowed for a value occur in the same block, then none of the other two lines or two columns in that block may contain that value.

specifications

Prototypes:

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

algorithm

Loop through positions of given column (line) in one block
- If the value is allowed then determine the block
Repeat for other two blocks
If the value is allowed in only one block
- For the other two columns (lines) within that block set all positions to not allowed for that value

testing

Input is an empty grid via .txt

Modified main function to:

Initialize grid to ALLOWED for all values
read out the values of the grid line or column (as a check)
use PrintAllowedValues to see what values are allowed at the line or column
use SetStatus to set positions to NOT_ALLOWED for each scenario:
1. in the line or column of 1 block (True)
2. in the line or column of >1 block (False)
3. in none of the positions in the line or column (False)
use PrintGridLine or PrintGridColumn to print the 3 lines or 3 columns belonging the block

Analysis:

for True scenario: looked to see if the other 6 positions in the block has been set to NOT_ALLOWED in the output
for False scenarios: looked to see if everything else remained ALLOWED

difficulties

As we constructed the algorithm, we ran into two main problems:

We had trouble working out code that would determine whether the allowed positions were in the same block. We solved that by splitting the column (line) into three sections, one for each block.
After the block was determined we had trouble isolating only the other two columns (lines). We fixed that with an extended loop function.

During testing, it was difficult to initialize the empty grid to all ALLOWED. So the grid initialization function was altered in order for the program to set all values of an empty grid to ALLOWED.

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.

team members

Matt (*), David E.

problem description

In Sudoku, we are trying to find a set of nine numbers unique to each 3x3 block, row, and column. Because each number has a unique position in the grid, we can use this logic to derive a set of rules to help solve for all the numbers. One of these rules is defined in this task. In a 3x3 block, if possible values appear in a row or column, we can eliminate the possibility of that number appearing anywhere else in both that value's row or column. This is just one of many other rules that can help solve the puzzle. If combined with other rules, it facilitates a faster solution.

The unknown positions are effectively examined 3x3 block. If the only possible positions for a value appear in the same row or column, it can not appear again anywhere else in its respective row and column.

specifications

4 Functions:

  bool CheckBlock(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int b, int v);

This function examines all the positions in a block for a value that is specified, to see if the value is possible in each position. If all the possible positions falls in either a row or column, the function will return yes and continue to the next function. Specifically, if possible positions form a row, it will pass what row the possible values lie on and continue to the FixRow function. Likewise, if possible positions form a column, it will pas what column the possible values lie in and continue to the FixColumn function. If the possible positions are varied among multiple lines or columns, the function will return no.

  bool FixColumn(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int column, int block, int value);
  bool FixLine(int grid[GRID_DIM][GRID_DIM][GRID_DIM+1], int line, int block, int value);

These functions take the block, value, and row or column that was found in the CheckBlock function and eliminates the possibility of that number appearing in its respective row or column. It will use the row or column to determine what blocks are affected, and then remove the value from the correct blocks in the correct row or column.

algorithm

int CheckBlock(int block, int value){

  int column = 0
  int c1 = Search(column 1, VALUE)
  int c2 = Search(column 2, VALUE)
  int c3 = Search(column 3, VALUE)

  if (c1==true && c2==false && c3==false){
       column = 1
  }
  if (c1==false && c2==true && c3==false){
       column = 2
  }
  if (c1==false && c2==false && c3==true){
       column = 3
  }

  int row = 0
  int r1 = Search(row 1, Value)
  int r2 = Search(row 2, Value)
  int r3 = Search(row 3, Value)

  if (r1==true && r2==false && r3==false){
       row = 1
  }
  if (r1==false && r2==true && r3==false){
       row = 2
  }
  if (r1==false && r2==false && r3==true){
       row = 3
  }
  //Pass info to FixRow or FixColumn
}

int FixRow(int row, int block, int value){
  //Remove value from the rest of the row
}

int FixColumn(int column, int block, int value){
  //Remove value from the rest of the columb
}


int Search(int C, int c, int R, int r, int value){
  //Return true for found value
  //Return false for did not find value

  bool out = false
  Loop through columbs{
       Loop through rows{
               if (current = VALUE){
                       out = true
               }
       }
  }
  return out
}