From 1b5109d410ebb04f741408727e6378f066a30991 Mon Sep 17 00:00:00 2001 From: "W. Trevor King" Date: Wed, 6 Oct 2010 16:58:35 -0400 Subject: [PATCH] Updated with first two Fall 2010 assignments. --- .../archive/submit_command/index.shtml | 6 +- assignments/archive/sudoku/1.cfg | 20 +++ assignments/archive/sudoku/2.cfg | 20 +++ assignments/archive/sudoku/3.cfg | 20 +++ assignments/archive/sudoku/index.shtml | 134 ++++++++++++++++++ assignments/current/1 | 2 +- assignments/current/2 | 2 +- 7 files changed, 199 insertions(+), 5 deletions(-) create mode 100644 assignments/archive/sudoku/1.cfg create mode 100644 assignments/archive/sudoku/2.cfg create mode 100644 assignments/archive/sudoku/3.cfg create mode 100644 assignments/archive/sudoku/index.shtml diff --git a/assignments/archive/submit_command/index.shtml b/assignments/archive/submit_command/index.shtml index 8fa597c..8aec137 100644 --- a/assignments/archive/submit_command/index.shtml +++ b/assignments/archive/submit_command/index.shtml @@ -1,7 +1,7 @@ -

Assignment #1

-

Due Friday, October 2, 2009

+

Assignment #2

+

Due Friday, October 8, 2010

Purpose

@@ -14,7 +14,7 @@ command on all the nodes of a virtual machine. The command to execute will be extracted from the command line arguments. For instance,

-mpicc -np 4 ./submit rm /tmp/a
+mpiexec -np 4 ./submit rm /tmp/a

will remove the file a from the local diff --git a/assignments/archive/sudoku/1.cfg b/assignments/archive/sudoku/1.cfg new file mode 100644 index 0000000..2fd0850 --- /dev/null +++ b/assignments/archive/sudoku/1.cfg @@ -0,0 +1,20 @@ + + - - - - 2 8 - 5 - + + - 7 4 6 1 - 2 8 - + + - - 2 - 7 - 9 - 1 + + + - 8 - - - - 3 9 5 + + - - 5 7 - 6 1 - - + + 3 4 1 - - - - 2 - + + + 4 - 9 - 8 - 5 - - + + - 2 8 - 5 3 6 7 - + + - 5 - 4 6 - - - - diff --git a/assignments/archive/sudoku/2.cfg b/assignments/archive/sudoku/2.cfg new file mode 100644 index 0000000..714a72a --- /dev/null +++ b/assignments/archive/sudoku/2.cfg @@ -0,0 +1,20 @@ + + - 6 - - 3 - - - - + + - 3 1 9 - 8 - 5 - + + 2 7 - - - - 6 3 - + + + - - - - 9 1 - - 3 + + - 1 - - 2 - - 9 - + + 9 - - 6 8 - - - - + + + - 9 6 - - - - 4 7 + + - 4 - 2 - 9 5 6 - + + - - - - 1 - - 8 - diff --git a/assignments/archive/sudoku/3.cfg b/assignments/archive/sudoku/3.cfg new file mode 100644 index 0000000..2e21724 --- /dev/null +++ b/assignments/archive/sudoku/3.cfg @@ -0,0 +1,20 @@ + + - 2 - - - - 6 - 9 + + 3 - - 9 - 4 - 5 - + + - - - 8 1 - - - - + + + 6 - - 5 - - - 1 - + + 8 1 - 3 - 9 - 6 5 + + - 4 - - - 1 - - 3 + + + - - - - 7 6 - - - + + - 6 - 4 - 5 - - 8 + + 9 - 1 - - - - 7 - diff --git a/assignments/archive/sudoku/index.shtml b/assignments/archive/sudoku/index.shtml new file mode 100644 index 0000000..45b35f1 --- /dev/null +++ b/assignments/archive/sudoku/index.shtml @@ -0,0 +1,134 @@ + + +

Assignment #1

+

Due Friday, October 8, 2010

+ +

Purpose

+ +

Remind ourselves of the C or C ++ syntax, in particular: arrays, +loop, conditional, functions, ...

+ +

Note: Please identify all your work.

+ +

Write a C or C ++ code to +solve sudoku +puzzles.

+ +

Sudoku is a one player board puzzle in which the player fills in +the empty cells on a 9x9 board with digits 1 to 9. The rules are +simple:

+ + + +

The tiles in the rules refer to 3x3 sub-regions that cover +the 9x9 board with no overlap. A game is seeded by having some digits +1 to 9 placed on the board (satisfying the rules above). The player +needs to complete the filling the board with digits 1 to 9 while +respecting the rules above.

+ +

Algorithm — key steps

+ +
    +
  1. Set the geometry of the board, i.e., the tiles.
    2. +
  2. Read in the starting configuration on the board.
    3. +
  3. Initialize in a trial array all the candidate digits for every + unfilled cell, i.e., digits 1 to 9.
    4. +
  4. For an unfilled cell on the board and for one of the digits in + the trial array corresponding to this cell, scan the row, column + and block for digit repetition.
    5. +
  5. If a repetition is found, eliminate this trial digit.
    6. +
  6. Repeat the two steps above for every unfilled cell on the board + and for every digit left in the trial array corresponding to these + unfilled cell 1.
  7. +
  8. If at any time the trial array contains only one (1) trial digit + for an unfilled cell on the board, this digit is part of the solution + of the sudoku puzzle and marked as such.
    9. +
  9. Accumulate the number of events in the steps above. An event + could be removing a digit from the trial array or selecting a + digit as part of the solution.
    10. +
  10. Repeat the scans above until the number of events is zero (0), + i.e., a steady state is reached, at which time the solution of the + sudoku puzzle is either obtained or the puzzle is too hard to + solve by this simple algorithm.
    11. + + +

    I/O

    + +

    A simple file interface should prove sufficient to check your +code. Namely, the initial configuration of digits on the board could +be typed in a file with an obvious format

    + +
    +- - 1   3 - -   - 6 -
+- 5 -   - - 1   - - 3
+...
+
    + +

    The output of any configuration could follow the same format.

    + +

    A run would then be

    + +
    +cat initialboard | ./sudoku
+
    + +

    Suggested functions

    + +

    Please write a modular code. Functions could be

    + +
    +
    geometry()
    +
    set the geometry of the board (rows, column, tiles)
    +
    read_config()
    +
    read in a board configuration
    +
    print_config()
    +
    print a board configuration
    +
    is_forbiden()
    +
    check if a trial digit is forbidden in a cell
    +
    check_cell()
    +
    finds and removes forbidden digits in a cell
    +
    check_all_cells()
    +
    scans over all cells to remove forbidden trial digits
    +
    + +

    Sample puzzles

    + +
    +5 3 -   - 7 -   - - -
+6 - -   1 9 5   - - -
+- 9 8   - - -   - 6 -
+
+8 - -   - 6 -   - - 3
+4 - -   8 - 3   - - 1
+7 - -   - 2 -   - - 6
+
+- 6 -   - - -   2 8 -
+- - -   4 1 9   - - 5
+- - -   - 8 -   - 7 9
+
    + +
    +5 3 4   6 7 8   9 1 2
+6 7 2   1 9 5   3 4 8
+1 9 8   3 4 2   5 6 7
+
+8 5 9   7 6 1   4 2 3
+4 2 6   8 5 3   7 9 1
+7 1 3   9 2 4   8 5 6
+
+9 6 1   5 3 7   2 8 4
+2 8 7   4 1 9   6 3 5
+3 4 5   2 8 6   1 7 9
+
    + + + + diff --git a/assignments/current/1 b/assignments/current/1 index fe9059c..4e538d1 120000 --- a/assignments/current/1 +++ b/assignments/current/1 @@ -1 +1 @@ -../archive/submit_command/ \ No newline at end of file +../archive/sudoku/ \ No newline at end of file diff --git a/assignments/current/2 b/assignments/current/2 index 7b06667..13520d3 120000 --- a/assignments/current/2 +++ b/assignments/current/2 @@ -1 +1 @@ -../archive/average_and_standard_deviation/ \ No newline at end of file +../archive/submit_command \ No newline at end of file -- 2.26.2