当前位置：和泉文库 > 数学 > 浏览文档

《数学建模》美赛优秀论文：ease and toil analyzing sudoku[1].pdf

文件格式：PDF，文件大小：764.2KB，售价：16.98元

文档详细内容（约62页）

Page 6 of 62 MCM 2008 Team #3780 p■■■■■pm2B46Z 4■5■ ■■_口■口■■■■■■■■■ Figure 1: Demonstration of indexing schemes. 78 45 874593|1 9|2B584 463m9815 69 Figure 2: Puzzle generated by WebSudoku (ranked as "Easy) 2.1.3 Hidden pair and z can take on the values of 1.2 and 7. We would thus conclude that any candidate of X, y Informally, this rule is conjugate to the Naked or Z that is not either 1, 2 or 7 may be eliminated Pair rule(section 2.1.1). Here, we also consider the condition is that there exist two values u andy 2.1.5 Multi-Line such that at least one of u, v is in each of X? and We will develop this technique for columns, but Y?, but such that for any cell QE(AX,Y1, it works for rows with trivial modifications. Con ? Thus, since A must contain a cell with sider a three blocks Ba, Bb and Bc such that they each of the values, we can force X,, r?ct, u,v. all intersect the columns C. C, and C,. If for An example of this is given in Figure 7. We some value v, there exists at least one cell X focus on the grouping Rs, and label X and Y in each of C and C, such that e X? but that there the puzzle. Since X and Y are the only cells in exists no such X E C, then we know that the cell Rs whose candidate lists contain 1 and 7, we can V B such that v H, v satisfies V EC.Were eliminate all other candidates for these cells. this not the case. then we would not be able to satisfy the requirements for B and Bb 2.1.4 Hidden Triplet An example of this rule is shown in Figure 9 In that figure, cells that we are interested in, and As with the Naked Pair rule (section 2.1.1), we for which 5 is a candidate are marked with can extend the Hidden Pair rule(section 2. 1.3)so asterisk. We will be letting a=0, b=6, c that it applies to three cells. In particular, let A T=0, y=l and z= 2. Then, note that all be a grouping, and let X, Y,ZE a be cells such the asterisks for blocks 0 and 6 are located in the that at least one of (t, u, v) is in each of X?, y? first two columns. Thus, in order to satisfy the and Z? for some values t, u and v. Then, if for constraint that a 5 appear in each of these blocks, any other cell QE(A\X,Y, 21),t, u, v Q?, we block 0 must have a 5 in either column 0 or 1 claim that we can force X?, Y?, Z?Ct, u,vh while block 6 must have a 5 in the other column An example of this is shown in Figure 8, where This leaves only column 2 open for block 3, and so in the grouping Rs, only the cells marked X, y we can remove 5 from the candidate lists for all

Page 6 of 62 MCM 2008 Team #3780 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 r r r 0 1 2 r r r 3 4 5 r r r 6 7 8 Figure 1: Demonstration of indexing schemes. 7 8 3 2 4 5 8 7 4 5 9 3 1 8 1 9 2 3 5 8 4 7 9 4 6 3 1 9 8 5 8 1 4 6 6 9 Figure 2: Puzzle generated by WebSudoku (ranked as “Easy”). 2.1.3 Hidden Pair Informally, this rule is conjugate to the Naked Pair rule (section 2.1.1). Here, we also consider a single grouping A and two cells X, Y ∈ A, but the condition is that there exist two values u and v such that at least one of {u, v} is in each of X? and Y ?, but such that for any cell Q ∈ (A\ {X, Y }), u, v ∈/ Q?. Thus, since A must contain a cell with each of the values, we can force X?, Y ? ⊆ {t, u, v}. An example of this is given in Figure 7. We focus on the grouping R8, and label X and Y in the puzzle. Since X and Y are the only cells in R8 whose candidate lists contain 1 and 7, we can eliminate all other candidates for these cells. 2.1.4 Hidden Triplet As with the Naked Pair rule (section 2.1.1), we can extend the Hidden Pair rule (section 2.1.3) so that it applies to three cells. In particular, let A be a grouping, and let X, Y, Z ∈ A be cells such that at least one of {t, u, v} is in each of X?, Y ? and Z? for some values t, u and v. Then, if for any other cell Q ∈ (A\ {X, Y, Z}), t, u, v ∈/ Q?, we claim that we can force X?, Y ?, Z? ⊆ {t, u, v}. An example of this is shown in Figure 8, where in the grouping R5, only the cells marked X, Y and Z can take on the values of 1, 2 and 7. We would thus conclude that any candidate of X, Y or Z that is not either 1, 2 or 7 may be eliminated. 2.1.5 Multi-Line We will develop this technique for columns, but it works for rows with trivial modifications. Consider a three blocks Ba, Bb and Bc such that they all intersect the columns Cx, Cy and Cz. If for some value v, there exists at least one cell X in each of Cx and Cy such that v ∈ X? but that there exists no such X ∈ Cz, then we know that the cell V ∈ Bc such that V 7→ v satisfies V ∈ Cz. Were this not the case, then we would not be able to satisfy the requirements for Ba and Bb. An example of this rule is shown in Figure 9. In that figure, cells that we are interested in, and for which 5 is a candidate, are marked with an asterisk. We will be letting a = 0, b = 6, c = 3, x = 0, y = 1 and z = 2. Then, note that all of the asterisks for blocks 0 and 6 are located in the first two columns. Thus, in order to satisfy the constraint that a 5 appear in each of these blocks, block 0 must have a 5 in either column 0 or 1, while block 6 must have a 5 in the other column. This leaves only column 2 open for block 3, and so we can remove 5 from the candidate lists for all

Page 10 of 62 MCM 2008 Team #3780 3 Metric Design of referencing all cells in a puzzle p which are 3.1 Overview E(P)={X∈P|w∈v:Xy The metric that we designed to test the difficult By binning each empty cell based on the choice of puzzles was the weighted normalized ease func- function, we obtain the choice histogram c(P)of tion(WNeF), and was based upon the calculation of a normalized choice histogram a puzzle P As the first step in we first step in calculat- cn(P)=HXEPIc(X)=n=RXEPIIX?=nHl ing this metric, we count the number of choices for each empty cell's value. Next, we compile Examples of these histograms with and without these values into a histogram with nine bins. Fi- the mean control histogram(obtained from the nally, we multiply these elements by empirically- control puzzles described in Section 4. 1)removed determined weights and sum the result to obtain may be found in Figures 10(a)and(b) the WNEF. The implementations of this calcula- From this histogram, we obtain the value of the tion process are shown on pages 28 and 42 (unnormalized)weighted ease function, wef (P) by convoluting the histogram with a weight func 3.2 Assumptions tion w(n) The design of the WNEF metric was predicated (3) on two basic and important assumptions where cn(P)is the nn value in the histogram We assumed that difficulty of a puzzle ex- c(P). This function, however, has the absurd ists; that is, that there exists some objective trait that removing information from a puzzle re- standard by which we may rank puzzles in sults in more empty cell, which in turn causes the function to strictly increase. We therefore calcu- We assumed that the diffic late the weighted and normalized ease functio zle is roughly proportional to the number (4) of choices that a solver may make without wef (P)= (1)·|E(P川 directly contradicting any of the basic con- This calculates the ratio of the weighted ease straints outlined in Sections 1.4 and 1.7 function to the maximum value that it can have (all empty cells completely determined, but have In addition, in testing and analyzing this metric, not been filled in; that is, all cells may be as we included a third assumption signed by elimination alone). We experimented with three different weight functions, before de- We assume that the difficulty of the indi- ciding upon the exponential weight function. This vidual puzzles are independently and iden- decision was made in response to tests performed tically distributed over each source. during metric calibration, and thus a full discus- sion of why we chose that particular weight func 3. 3 Mathematical basis for WNEF tion will be deferred to Section 4.2. wheneve the choice of weighting function is ambiguous, we For this metric, we started by defining the choice shall indicate the choice with a subscript exp, sq function of a cell c(X): or lin corresponding to the exponential, squared c(X)=|X? a and linear functions That is the choice function indicates the number 3.3.1 Complexity of possible choices that, in the worst case, must be Essentially, the level of complexity involved in explored. This function is only useful for empty finding the Wnef is the same as that of find cells, and so it is convenient to introduce a way ing the choice histogram(normalized or not). To

Page 10 of 62 MCM 2008 Team #3780 3 Metric Design 3.1 Overview The metric that we designed to test the difficulty of puzzles was the weighted normalized ease function (WNEF), and was based upon the calculation of a normalized choice histogram. As the first step in we first step in calculating this metric, we count the number of choices for each empty cell’s value. Next, we compile these values into a histogram with nine bins. Finally, we multiply these elements by empiricallydetermined weights and sum the result to obtain the WNEF. The implementations of this calculation process are shown on pages 28 and 42. 3.2 Assumptions The design of the WNEF metric was predicated on two basic and important assumptions: • We assumed that difficulty of a puzzle exists; that is, that there exists some objective standard by which we may rank puzzles in order of difficulty. • We assumed that the difficulty of a puzzle is roughly proportional to the number of choices that a solver may make without directly contradicting any of the basic constraints outlined in Sections 1.4 and 1.7. In addition, in testing and analyzing this metric, we included a third assumption: • We assume that the difficulty of the individual puzzles are independently and identically distributed over each source. 3.3 Mathematical Basis for WNEF For this metric, we started by defining the choice function of a cell c (X): c (X) = |X?| (1) That is, the choice function indicates the number of possible choices that, in the worst case, must be explored. This function is only useful for empty cells, and so it is convenient to introduce a way of referencing all cells in a puzzle P which are empty: E (P) = {X ∈ P | ∀v ∈ V : X 67→ v} By binning each empty cell based on the choice function, we obtain the choice histogram ~c (P) of a puzzle P. cn (P) = |{X ∈ P | c (X) = n}| = |{X ∈ P | |X?| = n}| (2) Examples of these histograms with and without the mean control histogram (obtained from the control puzzles described in Section 4.1) removed may be found in Figures 10 (a) and (b). From this histogram, we obtain the value of the (unnormalized) weighted ease function, wef(P), by convoluting the histogram with a weight function w (n): wef (P) = X 9 n=1 w (n) · cn (P) (3) where cn (P) is the n th value in the histogram ~c (P). This function, however, has the absurd trait that removing information from a puzzle results in more empty cell, which in turn causes the function to strictly increase. We therefore calculate the weighted and normalized ease function: wnef (P) = wef (P) w (1) · |E (P)| (4) This calculates the ratio of the weighted ease function to the maximum value that it can have (all empty cells completely determined, but have not been filled in; that is, all cells may be assigned by elimination alone). We experimented with three different weight functions, before deciding upon the exponential weight function. This decision was made in response to tests performed during metric calibration, and thus a full discussion of why we chose that particular weight function will be deferred to Section 4.2. Whenever the choice of weighting function is ambiguous, we shall indicate the choice with a subscript exp, sq or lin corresponding to the exponential, squared and linear functions. 3.3.1 Complexity Essentially, the level of complexity involved in finding the WNEF is the same as that of finding the choice histogram (normalized or not). To

点击进入文档下载页（PDF格式）

共62页，可试读20页，点击继续阅读 ↓↓

您可能感兴趣的文档

点击购买下载（PDF）

下载及服务说明

购买前请先查看本文档预览页，确认内容后再进行支付；
如遇文件无法下载、无法访问或其它任何问题，可发送电子邮件反馈，核实后将进行文件补发或退款等其它相关操作；
邮箱：

文档浏览记录