Page 5 of 62 MCM 2008 Team #3780 These indicies are related by the following func- 2 Background tions: 2.1 Common Solving Techniques As with any activity, several sets of techniques k i (c, k) have emerged to help solve sudoku puzzles. We collect some here so that we may refer to them in j(c, k)=(c mod 3).3+(k mod 3) our own development. In all of the techniques be- low, we assume that the puzzle being solved has a single unique solution. These techniques and j'(c)=( mod 3)3 examples are adapted from [10] and [2] ()=3|3 2.1.1 Naked pair If, in a single row, column or block grouping A Figure I demonstrates how the rows, columns there are two cells X and Y each having the same and blocks are indexed as well as the idea of a pair of candidates x?=r?=ip, q), then those block representative. In the third sudoku grid. candidates may be eliminated from all other cells the representatives for each block are denoted in A. To see that we can do this, assume for the with an“r z∈ A such that Z H p, then x≠p, which im 1.7 Formal rules of Sudoku plies that X H. This in turn means that y q, but we have from Z p that Y p, leaving We may now formally state the rules of sudoku y?=0. Since the puzzle has a solution, this is a that restrict allowable assignments using the no- contradiction, and ZH+p tation developed thus far As an example of this arrangement is shown in figure 5. The cells marked X and Y sat- (vG∈GX∈G)X+y→打∈G:Y→ v isfy X?=Y?={2,8}, and so we can remove both 2 and 8 from all other cells in R. That is pplying this sort of formalism to the rules of su- VZ E(Rs\X, Y)): 2, 8Z? doku will allow us to make strong claims about solving techniques later, and so it is useful intro duce this notation for the rules 2.1.2 Naked Triplet 1.8 Example Puzzles This rule is analogous to the Naked Pair rule(sec- tion 2.1.1), but instead it involves three cells in- The rules alone do not explain what a sudoku stead of two. Let a be some grouping(row, col puzzle looks like, and so we have included a few umn or block), and let X,Y, Z E A such that examples of well-crafted sudoku puzzles. Figure the candidates for X, Y and Z are drawn from 6 shows a puzzle ranked as "Easy by WebSudoku t, u, v). Then, by exhaustion, there is a one-to [4] one set of assignments from X,Y, Z to t,u,vI By contrast, Figures 7 and 7 show the results Therefore, no other cell in A may map to a value of two different approaches to generating difficult in t, u, v) puzzles: the first one was computer generated as An example of this is given in Figure6.Here part of an experiment in minimal sudoku puz- we have marked the cells X, Y, Z) accordingly cles, whereas the second was hand-made by the and consider only block 8. In this puzzle,x? authors at Nikoli, the company most famously (3, 7), Y?=(1, 3, 7) and Z?=(1, 3. Therefore, associated with sudoku. It is interesting that we must assign 1, 3 and 7 to these cells, and may two such completely different approaches result remove them from the candidates for those cells in very similar looking puzzles marked with an asteriskPage 5 of 62 MCM 2008 Team #3780 These indicies are related by the following func￾tions: c (i, j) = j 3 +  i 3  · 3 i(c, k) = 3 j c 3 k +  k 3  j (c, k) = (c mod 3) · 3 + (k mod 3) i 0 (c) = 3 j c 3 k j 0 (c) = (c mod 3) · 3 i 0 (i) = 3  i 3  j 0 (j) = 3  j 3  Figure 1 demonstrates how the rows, columns and blocks are indexed, as well as the idea of a block representative. In the third sudoku grid, the representatives for each block are denoted with an “r”. 1.7 Formal Rules of Sudoku We may now formally state the rules of sudoku that restrict allowable assignments using the no￾tation developed thus far: (∀G ∈ G ∀X ∈ G) X 7→ v ⇒ @Y ∈ G : Y 7→ v Applying this sort of formalism to the rules of su￾doku will allow us to make strong claims about solving techniques later, and so it is useful intro￾duce this notation for the rules. 1.8 Example Puzzles The rules alone do not explain what a sudoku puzzle looks like, and so we have included a few examples of well-crafted sudoku puzzles. Figure 6 shows a puzzle ranked as “Easy” by WebSudoku [4]. By contrast, Figures 7 and 7 show the results of two different approaches to generating difficult puzzles: the first one was computer generated as part of an experiment in minimal sudoku puz￾zles, whereas the second was hand-made by the authors at Nikoli, the company most famously associated with sudoku. It is interesting that two such completely different approaches result in very similar looking puzzles. 2 Background 2.1 Common Solving Techniques As with any activity, several sets of techniques have emerged to help solve sudoku puzzles. We collect some here so that we may refer to them in our own development. In all of the techniques be￾low, we assume that the puzzle being solved has a single unique solution. These techniques and examples are adapted from [10] and [2]. 2.1.1 Naked Pair If, in a single row, column or block grouping A, there are two cells X and Y each having the same pair of candidates X? = Y ? = {p, q} , then those candidates may be eliminated from all other cells in A. To see that we can do this, assume for the sake of contradiction that there exists some cell Z ∈ A such that Z 7→ p, then X 67→ p, which im￾plies that X 7→ q. This in turn means that Y 67→ q, but we have from Z 7→ p that Y 67→ p, leaving Y ? = ∅. Since the puzzle has a solution, this is a contradiction, and Z 67→ p. As an example of this arrangement is shown in figure 5. The cells marked X and Y sat￾isfy X? = Y ? = {2, 8}, and so we can remove both 2 and 8 from all other cells in R8. That is, ∀Z ∈ (R8\ {X, Y }) : 2, 8 ∈/ Z?. 2.1.2 Naked Triplet This rule is analogous to the Naked Pair rule (sec￾tion 2.1.1), but instead it involves three cells in￾stead of two. Let A be some grouping (row, col￾umn or block), and let X, Y, Z ∈ A such that the candidates for X, Y and Z are drawn from {t, u, v}. Then, by exhaustion, there is a one-to￾one set of assignments from {X, Y, Z} to {t, u, v}. Therefore, no other cell in A may map to a value in {t, u, v}. An example of this is given in Figure 6. Here, we have marked the cells {X, Y, Z} accordingly and consider only block 8. In this puzzle, X? = {3, 7}, Y ? = {1, 3, 7} and Z? = {1, 3}. Therefore, we must assign 1, 3 and 7 to these cells, and may remove them from the candidates for those cells marked with an asterisk