2
 7 4 8 2
 5 6 3 9
 9 7 2 5
 6 2 1
 2 4 8 3
 8 4 6 9
 9 4 8 3
 8

Have you been sucked into Sudoku yet?  If not, here is your chance.

Fill the grid above with numbers from 1 to 9, making sure that each row,
each column and each box (the nine smaller 3×3 grids) contain each number
exactly once.

Sudoku is a fiendishly addictive puzzle that has been gaining an
extraordinary popularity these past months.  Three Sudoku books are listed
in the New York Times’ top 50 list, I have seen dozen of people playing Sudoku
in buses and airports, but what really made me realize how big the craze was is
when I asked my brother, who lives in France, if he had heard of it, and his

I like solving Sudoku grids myself but I find the software challenges
even more interesting.  If you are up for a little exercise, here
are a few problems for you to solve:

1. Write a program that solves a Sudoku grid.  It doesn’t look
too hard at first, but you need to know that there are
much more Sudoku
grids than you think
, and therefore, brute force will only take you so far.
You will need to apply a few selected strategies to prune the solution
space, or your program will never complete in acceptable time.

2. Now the reverse problem:  write a program that generates Sudoku
grids
.  It’s fairly easy to accomplish for someone who has some
basic computer science training, and if you don’t, you will probably want to
Google the terms "backtracking algorithm" (which is not the only way to
solve this problem).

3. And finally, now that you have all these Sudoku grids, rank them by
order of difficulty
, 1 being an easy grid and 5 being a very difficult
one.  In other word, I should be able to ask your program to give me a
rank 1 grid, which will be very easy, and a rank 5 grid that will take me
much longer to solve.  When solving this problem, you will probably end
up realizing that what is difficult for a human is not necessarily difficult
for a computer, and vice versa.  As a hint, you might want to generate
grids, solve them with the first program you wrote and then have this
program report to you how hard it was.

Happy hacking!