Sudoku Sudoku puzzles are constructed using a 9 x 9 grid made up of nine 3 * 3 subgrids, known as blocks, as shown in Figure 2. For each puzzle, some of the 81 cells, called givens, are assigned one of the numbers 1, 2,..., 9, and the other cells are blank. The puzzle is solved by assigning a number to each blank cell so that every row, every column, and every one of the nine 3 * 3 blocks contains each of the nine possible numbers. Note that instead of using a 9 x 9 grid, Sudoku puzzles can be based on n x n grids, for any positive integer n, with the n x n grid made up of nn x n subgrids. The popularity of Sudoku dates back to the 1980s when it was introduced in Japan. It took 20 years for Sudoku to spread to rest of the world, but by 2005, Sudoku puzzles were a worldwide craze. The name Sudoku is short for the Japanese suuji wa dokushin ni kagiru, which means "the digits must remain single. The modern game of Sudoku was apparently designed in the late 1970s by an American puzzle designer. The basic ideas of Sudoku date back even further; puzzles printed in French newspapers in the 1890s were quite similar, but not identical, to modern Sudoku. Sudoku puzzles designed for entertainment have two additional important properties. First, they have exactly one solution. Second, they can be solved using reasoning alone, that is, without resorting to searching all possible assignments of numbers to the cells. As a Sudoku puzzle is solved, entries in blank cells are successively determined by already known values. For instance, in the grid in Figure 2, the number 4 must appear in exactly one cell in the second row. How can we determine in which of the seven blank cells it must appear? First, we observe that 4 cannot appear in one of the first three cells or in one of the last three cells of this row, because it already appears in another cell in the block each of these cells is in. We can also see that 4 cannot appear in the fifth cell in this row, as it already appears in the fifth column in the Page 36 fourth row. This means that 4 must appear in the sixth cell of the second row. 29 4 1 5 4 |4|2 6 7 5 7 3 5 5 1 FIGURE 2 A9 x 9 Sudoku puzzle. Many strategies based on logic and mathematics have been devised for solving Sudoku puzzles (see [Da10], for example). Here, we discuss one of the ways that have been developed for solving Sudoku puzzles with the aid of a computer, which depends on modeling the puzzle as a propositional satisfiability problem. Using the model we describe, particular Sudoku puzzles can be solved using software developed to solve satisfiability problems. Currently, Sudoku puzzles can be solved in less than 10 milliseconds this way. It should be noted that there are many other approaches for solving Sudoku puzzles via computers using other techniques. To encode a Sudoku puzzle, let pli,j, n) denote the proposition that is true when the number n is in the cell in the ith row and jth column. There are 9 x 9x9 = 729 such propositions, as i, j, and n all range from 1 to 9. For example, for the puzzle in Figure 2, the number 6 is given as the value in the fifth row and first column. Hence, we see that p(5, 1, 6) is true, but p(5.), 6) is false for j = 2, 3,..., 9. Given a particular Sudoku puzzle, we begin by encoding each of the given values. Then, we construct compound propositions that assert that every row contains every number, every column contains every number, every 3 x 3 block contains every number, and each cell contains no more than one number. It follows, as the reader should verify, that the Sudoku puzzle is solved by finding an assignment of truth values to the 729 propositions pi, j, n) with i, j, and n each ranging from 1 to 9 that makes the conjunction of all these compound propositions true. After listing these assertions, we will explain how to construct the assertion that every row contains every integer from 1 to 9. We will leave the construction of the other assertions that every column contains every number and each of the nine 3 x 3 blocks contains every number to the exercises. For each cell with a given value, we assert pli,j, n) when the cell in row i and column j has the given value n. We assert that every row contains every number: MAVpli,j, n) 999 999 We assert that every column contains every number: V prijin) It is tricky setting up the two inner indices so that all nine cells in each square block are examined. We assert that each of the nine 3 x 3 blocks contains every number: 2 293 MAVVP(3r + i, 3s +j,n) ja To assert that no cell contains more than one number, we take the conjunction over all values of n, n', i, and j, where each variable ranges from 1 to 9 and n #n' of pli,j, n) + pli,j, n'). We now explain how to construct the assertion that every row contains every number. First, to assert that row i contains the number n, we form V; -, P(i, j, n). To assert that row i contains all n numbers, we form the conjunction of these disjunctions over all nine possible values of n, giving us A... V)-1 Pli, j, n). Finally, to assert that every row contains every number, we take the conjunction of V... Pli, j.n) over Page 37 all nine rows. This gives us ^_-V-, pi, j, n). (Exercises 71 and 72 ask for explanations of the assertions that every column contains every number and that each of the nine 3 x 3 blocks contains every number.) Given a particular Sudoku puzzle, to solve this puzzle we can find a solution to the satisfiability problems that asks for a set of truth values for the 729 variables pi,j, n) that makes the conjunction of all the listed assertions true. 1. Design an algorithm which solves Sudoku puzzle by solving satisfiability problem as explained above. 2. Write a MATLAB code associated to the above algorithm
