I've just released a new Sudoku app for the iPhone - Sudoku Warrior. It automatically generates puzzles as you play, using a new algorithm based on human solving techniques. Depending on the level you select, different techniques will be necessary to solve the puzzles, so you can choose the level that suits your ability. If you get stuck, there is a "Hint" button that will explain and demonstrate a strategy for you to use, so you can learn as you go.
You can search on the AppStore, or go to www.ideasoftware.com.au. There is a link there to the app store page, so you can read more details, download the app and have a look!
I'd love to hear feedback and suggestions, so if you have any thoughts, let me know.