Page 2 of 24 Control #2858 1 Introduction Sudoku is a logic puzzle that has recently become extremely popular. In Sudoku, a player is presented with a 9 x9 grid divided into nine 3 x 3 regions. Some of the 81 cells of the grid are initially filled with digits between 1 and 9 such that there is a unique way to complete the rest of the grid while satisfying the following rules Each cell contains a digit between 1 and 9 2. Each row, column, and 3 x3 region contains exactly one copy of the digits (1, 2,..., 91 A Sudoku puzzle consists of such a grid together with an initial collection of digits that guarantees a unique final configuration. Call this final configuration a solution to the puzzle The goal of Sudoku is to find this unique solution from the initial board Below is an example of a Sudoku puzzle and solution from the February 16th, 2008 editio of the London Times [18 218971563|4 山8[67534192 9|34682517 526819473 8|9山|43|5268|9 s|9437265 In this particular example, we cannot have the numbers 8, 3, or 7 appear anywhere else on the bottom row, since each number can only show up in the bottommost row once. Similarly, the number 8 cannot appear in any of the empty squares in the lower-left-hand region 1. 1 Notation We first introduce some notation. Number the rows and columns from 1 to 9. beginning at the top and left, respectively, and number each 3 x 3 region of the board as follows:Page 2 of 24 Control #2858 1 Introduction Sudoku is a logic puzzle that has recently become extremely popular. In Sudoku, a player is presented with a 9 × 9 grid divided into nine 3 × 3 regions. Some of the 81 cells of the grid are initially filled with digits between 1 and 9 such that there is a unique way to complete the rest of the grid while satisfying the following rules: 1. Each cell contains a digit between 1 and 9 2. Each row, column, and 3×3 region contains exactly one copy of the digits {1, 2, . . . , 9}. A Sudoku puzzle consists of such a grid together with an initial collection of digits that guarantees a unique final configuration. Call this final configuration a solution to the puzzle. The goal of Sudoku is to find this unique solution from the initial board. Below is an example of a Sudoku puzzle and solution from the February 16th, 2008 edition of the London Times [18]: 7 9 5 3 5 2 8 4 8 1 7 4 6 3 1 8 9 8 1 2 4 5 8 9 1 8 3 7 8 6 1 7 9 4 3 5 2 3 5 2 1 6 8 7 4 9 4 9 7 2 5 3 1 8 6 2 1 8 9 7 5 6 3 4 6 7 5 3 4 1 9 2 8 9 3 4 6 8 2 5 1 7 5 2 6 8 1 9 4 7 3 7 4 3 5 2 6 8 9 1 1 8 9 4 3 7 2 6 5 In this particular example, we cannot have the numbers 8, 3, or 7 appear anywhere else on the bottom row, since each number can only show up in the bottommost row once. Similarly, the number 8 cannot appear in any of the empty squares in the lower-left-hand region. 1.1 Notation We first introduce some notation. Number the rows and columns from 1 to 9, beginning at the top and left, respectively, and number each 3 × 3 region of the board as follows: 1 2 3 4 5 6 7 8 9 2