The one linked to above is the Magmic game, which looks pretty but limits the number of boards.
The version I like is 5ud0ku (the number 5 instead of an "s", and a zero instead of the letter "o"). It works fine on my BB, and has pencil marks, random board generation, etc. Take a look at
start of entry :: 5ud0ku for more info.