Page 4 of 62 MCM 2008 Team #3780 Candidates A set of those values which may umn has as its representative the cell at the be assigned to a square. As more informa fourth row and column tion is taken into account the set is reduced until only one candidate remains, at which point it becomes the value of the cell. We Restrictions In some cases, it is more straight denote the set of candidates for some cell x forward to discuss which values a cell can- not be assigned to than to discuss the set of candidates. Thus. the restrictions set X! for Cell A single square within a sudoku puzzle, a cell X is defined as V\X? which may have one of the integer values from 1 to 9. We denote cells using upper- case italic serif letters:X.Y.Z Rule An algorithm which accepts a puzzle P Block One of the nine 3 x 3 squares within the and produces either a puzzle P represent puzzle. The boundaries of these blocks are ing strictly more information(more restric denoted by thicker lines on the puzzle,s grid tions have been added via logical inference It is important to note that in sudoku, no or cells have been filled in) or some value two blocks overlap(share common cells that indicates that the rule failed to ad There are variants of sudoku. such vance the puzzle towards a solution persudoku in which this occurs, but w focus our attention on the traditional rules. Solution a set of assignments to all cells in a Grouping A set of cells in the same row, col- puzzle such that all groupings have exactly umn or block. We represent groupings with one cell assigned to each value uppercase boldface serif letters: X,Y, Z We refer unambiguously to the row group- value a ings Ri, the column groupings C, and the that may be assigned to a block groupings B, following the indexing tr purposes, all sudoku puzzles scheme in section 1.6. The set of all group ditional numeric value set v ings will be denoted G. (1, 2, 3, 4, 5, 6, 7, 8, 9. This can be confusing at times, since we will be discussing other Metric We call a function m: P-R(assigning numbers but we choose to do so for the sake a real number to each valid puzzle)a metric of convention. a value is denoted by a lower if it provides information about the relative case sans serif letter: x, y, z difficulty of the puzzle Puzzle a 9x 9 matrix of cells with at least one empty and at least one filled cell. For our 1.6 Indexing purposes, we impose the additional require ment that all puzzles have exactly one so- Define the following indicies using the terminal lution. We denote puzzles by boldface cap ital serif letters: P, Q, R. Since this no- ogy above(section 1.5). As a convention, all indi- tation conflicts with that for groupings, we cies will start with zero for the first cell or block will always denote that a variable is a puz zle. Moreover, we refer to cells belonging to a puzzle: X E P. Finally, in the rare in- block number stance that we wish to denote the set of all valid puzzles, we shall do so with a double- k: cell number within a block struck p: P i: row number sentative The upper-left cell in each column block is that block's representative. Fore i': representative row number ample, the cell in the 5 row and 5 col- representative column numberPage 4 of 62 MCM 2008 Team #3780 Candidates A set of those values which may be assigned to a square. As more informa￾tion is taken into account, the set is reduced until only one candidate remains, at which point it becomes the value of the cell. We denote the set of candidates for some cell X by X?. Cell A single square within a sudoku puzzle, which may have one of the integer values from 1 to 9. We denote cells using upper￾case italic serif letters: X, Y , Z. Block One of the nine 3 × 3 squares within the puzzle. The boundaries of these blocks are denoted by thicker lines on the puzzle’s grid. It is important to note that in sudoku, no two blocks overlap (share common cells). There are variants of sudoku, such as hy￾persudoku in which this occurs, but we will focus our attention on the traditional rules. Grouping A set of cells in the same row, col￾umn or block. We represent groupings with uppercase boldface serif letters: X, Y, Z. We refer unambiguously to the row group￾ings Ri , the column groupings Cj and the block groupings Bc, following the indexing scheme in section 1.6. The set of all group￾ings will be denoted G. Metric We call a function m : P → R (assigning a real number to each valid puzzle) a metric if it provides information about the relative difficulty of the puzzle. Puzzle A 9 × 9 matrix of cells, with at least one empty and at least one filled cell. For our purposes, we impose the additional require￾ment that all puzzles have exactly one so￾lution. We denote puzzles by boldface cap￾ital serif letters: P, Q, R. Since this no￾tation conflicts with that for groupings, we will always denote that a variable is a puz￾zle. Moreover, we refer to cells belonging to a puzzle: X ∈ P. Finally, in the rare in￾stance that we wish to denote the set of all valid puzzles, we shall do so with a double￾struck P: P. Representative The upper-left cell in each block is that block’s representative. For ex￾ample, the cell in the 5th row and 5th col￾umn has as its representative the cell at the fourth row and column. Restrictions In some cases, it is more straight￾forward to discuss which values a cell can￾not be assigned to than to discuss the set of candidates. Thus, the restrictions set X! for a cell X is defined as V\X?. Rule An algorithm which accepts a puzzle P and produces either a puzzle P0 represent￾ing strictly more information (more restric￾tions have been added via logical inference or cells have been filled in) or some value that indicates that the rule failed to ad￾vance the puzzle towards a solution. Solution A set of assignments to all cells in a puzzle such that all groupings have exactly one cell assigned to each value. Value A symbol that may be assigned to a cell. For our purposes, all sudoku puzzles use the traditional numeric value set V = {1, 2, 3, 4, 5, 6, 7, 8, 9}. This can be confusing at times, since we will be discussing other numbers, but we choose to do so for the sake of convention. A value is denoted by a lower case sans serif letter: x, y, z. 1.6 Indexing Define the following indicies using the terminol￾ogy above (section 1.5). As a convention, all indi￾cies will start with zero for the first cell or block. c : block number k : cell number within a block i : row number j : column number i 0 : representative row number j 0 : representative column number