Maria: If I want to take a break from the puzzle and continue solving it at some later
time, is there a way to save my partial so lution?
Professor: You can save data loc ally using the localStora ge object, whose d escrip-
tion you will find in Appendix B on page 280. It’s not very difficult to use it and I
think you shall be able to figure it out by yourself.
Mike: Have we learned eno ugh to be able to write a program that will generate a
Sudoku puzzle?
Professor: I think so. You know what? I’ll let you do it for h omework. Because we
are not going to see each other any more, I’ll leave a solution for you in Appendix A .
However, you should really try to do it on your own and use the solution only if you
really, really have to. Promise?
Mike: Promise.
Maria: Can you at least give us some directions, ple ase?
Professor: I ’ll do that, of course.
13.5 Homework
Professor: Basically, there are three steps in g enerating a Sudoku puzzle. The easiest
one is to produce a puzzle. Somewhat more difficult is to make sur e that the puzzle
has a uniq ue solution. This is essential, or else it is n ot possible to solve it without
guessing. The most diffic ult part is to determine the puzzle’s difficulty level. I suppose
that it’s OK if you implement the first two steps for your homework.
To produce a puzzle, you simply start out with any c ompletely solved puzzle and
shuffle the numbers to get a new one. There a re some simple swapping operations you
can perform on any valid Sudoku to get a differe nt Sudoku that is still valid. You can
swap:
262 Meeting 13. User Interface
• Any two columns within any of the three columns of 3 × 3 boxes.
• Any two rows within any of the three rows of 3 × 3 boxes.
• Any two columns of 3 × 3 boxes.
• Any two rows of 3 × 3 boxes.
For example, you can swap the first and second row of cells, or the fourth and sixth
column of c ells, but you cannot swap the first and fou rth column of ce lls. You can
also swap a ll three 3 × 3 boxes in the first row w ith the three boxes in the last row.
If yo u swap r andomly selected rows and columns according to the above rules many
times, you can get almost any c onceivable puzzle . Finally, you remove some numbers
from the grid, and the numbers tha t are lef t represent clues for the n ew puz zle.
Mike: How ma ny clues should we leave?
Professor: Recently it has been shown that it is not possible to construct a Sudoku
with only 16 clues, so 17 is an absolute minimum. However, an average number of
clues is usually around 25, and I suggest that you use 30 clues if you are not imple-
menting an estimate of difficulty level. This way yo ur puzz le will most probably be
very easy or easy to solve, and it won’t take too much time to genera te it.
A puzzle that you get by randomly removing numbers from a completely solved Su-
doku will very likely have more than a sing le solution. Hence your next step is to
check how many solutions your puzzle has. If it ha s more than one, then you should
try another one, and another one, until you find a puzzle having a single solution.
To ch eck whether a Sudoku has more than one solution, you ca n simply try to system-
atically put every possible number into each of the empty cells and see if a combination
solves the puzzle. This is a possible algorithm:
Construct a one-dimensional array of all the empty cells.
Set n to zero (i.e., the position of the first cell in the array of empty cells).
Check the nth empty cell:
Repeat for every number from one to nine:
If you can place the number into the current empty cell Then
If this is the last of the empty cells Then
A solution has been found.
Else Check the (n + 1)th empty cell.
End If
End If
If more than one solution has been found so far Then
Stop checking.
End If
End Re peat
Clear the nth cell back to null.
End Check
13.5. Homework 263
The first line of this algorithm should find a ll the empty cells in the grid and place them
into a one-dimensional array. Note that you will need the row and column in dexes of
cells to be able to place them into the puzzle grid, which Cell objects don’t store. To
get around this, you can either add row and c olumn indexes to the Cell class object
or simply create an array of pairs of indexes storing positions of empty cells.
Note that Check in the above algorithm is a function, and you will notice a curious
thing: that this function in fact calls itself fr om within the inner most if/else statement.
A function that calls itself is called a recursive function, whic h offers an elegant so -
lution for types of pr oblems like this one. What you have to do is first try to place
number one in the fir st empty cell. If that is not possible, then try it with n umber two,
and number three, and so on, until either you find a pr oper number or you run out of
numbers. If you suc cessfully place a number into the grid, then repeat the whole story
with the next emp ty cell. If, however, no one number ca n be placed into the current
cell, then you should go back to the previous empty cell and try to replace its number
with a bigger one.
If you use a r ecursive fu nction to solve this problem, then lots of bookkeeping is
done automatically for you. Each time the f unction is called, a new function object
is created and appended to the current scope chain. If the function also creates loc al
variables rememb ering the index of th e cell and the number that h as been p la ced most
recently into that cell, then th ere is not much work left for you. Whenever no further
number can be placed in the current cell, the current function stops executing, which
automatically removes it fr om the scope chain and the checking continues with the
previous cell from the exact point where it left it.
I admit that this second part of the assignme nt is quite a challenge, but you shall
try to write a program nonetheless. In case you don’t succeed, there’s a solution in
Appendix A.
Which brings us to the e nd of our course. You guys have been terrific and I hop e you
enjoyed it as much as I did. Take care and keep up the good work!
In this meeting: getElementsByTagName(), getElementsByClassName(),
firstElementChild, firstChild, lastElementChild, Element object, Node
object, Document object, parentN ode, appendChild() , oninp ut, passing a rgu-
ments to event handlers, recursion, inherit, createE lement()
264 Meeting 13. User Interface
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.