Page 7 of 24 Control #2858 (d)Compute E(p, u), the expected number of possible applications that will be ex amined before a valid application is found (e) Increment d by E(p, u).t, where t is the standard check time. Pick a random application in V and apply it to the board 3. Return the value of d and the final solved board While hsolve is mostly a direct implementation of Human Solve, it does not actually perform a random search through possible applications; instead it uses the expected search time E(p, u)to simulate this search. Note that the following lemma gives an extremely convenient closed form expression for E(p, u) that we use in hsolve Lemma 1. Assuming that all search paths through p possible approaches are equally likely, the expected number e(p, a) of checks required before finding one of v valid approaches is given by E(p, U) p+ U+1 Proof. For our purposes, to specify a search path it is enough to specify the v indices of the valid approaches out of p choices, so there are()possible search paths. Let I be the random variable equal to the smallest index of a valid approach. Then, we have that E(,0)=∑iP(=)=∑∑P(I=j=∑P(≥) +1 +)=曾 where we've used the Hockeystick identity Given a Sudoku puzzle B, then, we calculate m(B) by running hsolve several times and taking the average of the returned difficulties. To increase the level of accuracy, the number of runs can be increased; 20 runs per puzzle was found to give a ratio of standard deviation to mean of about ga 1, so we use this value throughout the rest of the paper 3.3 Analysis Our evaluation of hsolve consists of three major components 1. Checking that hsolve's conception of difficulty is correlated with existing conceptions of difficulty 2. Comparing the distribution of difficulties generated by hsolve to established distribu- tions for solve time 3. Finding the runtime of the algorithmPage 7 of 24 Control #2858 (d) Compute E(p, v), the expected number of possible applications that will be ex￾amined before a valid application is found. (e) Increment d by E(p, v) · t, where t is the standard check time. Pick a random application in V and apply it to the board. 3. Return the value of d and the final solved board. While hsolve is mostly a direct implementation of HumanSolve, it does not actually perform a random search through possible applications; instead it uses the expected search time E(p, v) to simulate this search. Note that the following lemma gives an extremely convenient closed form expression for E(p, v) that we use in hsolve. Lemma 1. Assuming that all search paths through p possible approaches are equally likely, the expected number E(p, a) of checks required before finding one of v valid approaches is given by E(p, v) = p + 1 v + 1 . Proof. For our purposes, to specify a search path it is enough to specify the v indices of the valid approaches out of p choices, so there are ￾ p v
possible search paths. Let I be the random variable equal to the smallest index of a valid approach. Then, we have that E(p, v) = p−Xv+1 i=1 iP(I = i) = p−Xv+1 i=1 p−Xv+1 j=i P(I = j) = p−Xv+1 i=1 P(I ≥ i) = 1 ￾ p v
p−Xv+1 i=1  p + 1 − i v  = 1 ￾ p v
X p−v j=0  v + j v  = ￾ p+1 v+1
￾ p v
= p + 1 v + 1 , where we’ve used the Hockeystick identity. Given a Sudoku puzzle B, then, we calculate m(B) by running hsolve several times and taking the average of the returned difficulties. To increase the level of accuracy, the number of runs can be increased; 20 runs per puzzle was found to give a ratio of standard deviation to mean of about σ µ ≈ 1 10 , so we use this value throughout the rest of the paper. 3.3 Analysis Our evaluation of hsolve consists of three major components: 1. Checking that hsolve’s conception of difficulty is correlated with existing conceptions of difficulty. 2. Comparing the distribution of difficulties generated by hsolve to established distribu￾tions for solve time. 3. Finding the runtime of the algorithm. 7