Solve the following problem:
We recall that a Sudoku is a 9x9 grid that is partly filled with numbers between 1 and 9 such that any number between 1 and 9 only appears once in a row, a column, or a 3x3 bloc of the grid. This exercise solves a simple Sudoku grid where there exists a path over the empty entries that fills them one at a time by excluding all possibilities but one. The Sudoku we solve is given by
> s = matrix(0,ncol = 9,nrow = 9)
> s[1,c(6,8)] = c(6,4)
> s[2,c(1:3,8)]=c(2,7,9,5)
> s[3,c(2,4,9)]=c(5,8,2)
> s[4,3:4]=c(2,6)
> s[6,c(3,5,7:9)] = c(1,9,6,7,3)
> s[7,c(1,3:4,7)] = c(8,5,2,4)
> s[8,c(1,8:9)] = c(3,8,5)
> s[9,c(1,7,9)] = c(6,9,1)
a. Print the grid on-screen.
b. We define the array pool = array (TRUE, dim = c(9,9,9)) of possible values for each entry (i, j) of the grid, pool [i,j,k] being FALSE if the value k can be excluded. Give the R code that updates pool for the entries already filled.
c. If i is an integer between 1 and 81, explain the meaning of s[i].
d. Show that, for a given entry (a, b), the indices of the integers in the same 3x3 box as (a, b) are defined by
boxa=3*trunc((a-1)/3)+1
boxa=boxa:(boxa+2)
boxb=3*trunc((b-1)/3)+1
boxb=boxb:(boxb+2)
e. Deduce that values at an entry (a,b) that is not yet determined can be excluded by
for (u in (1:9) [pool [a,b,]])
pool [a,b,u] = (sum(u==s[a,])+sum(u==s[,b])+
sum(u==s[boxa,boxb]))==0
and that certain entries correspond to
if (sum(pool[a,b,])==1) s[i] = [pool [a,b,]]
f. Solve the grid above by a random exploration of entries (a,b) that continues as long as sum(s==0) > 0.