4 8
3   9
  2 5
2 4  
8   4
4 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
answer was "Who hasn’t?".

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
    .  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!