I don't know if it will sell as a product, but it may sell you as a developer. It depends on the algorithms you're using, how you're deciding when a search fails, and so forth. Solving sudoku puzzles has a lot in common with solving other sorts of problems, particularly in inventory management, fulfillment, transportation and logistics, fleet management and so forth. If your approach is efficient and fails quickly, it makes you more valuable.
Then again, it's really hard to figure out what will be successful commercially. One of the very successful people I "know" online (we both hang out at Y Combinator's
Hacker News aggregator) is making a very good living with a
bingo card creator, which is nothing more, really, than shuffling and dealing a large deck of cards algorithmically, then arranging the numbers (or whatever you're categorizing) for print. But he's found the perfect target market -- schoolteachers who are willing to pay a little out of their own pocket to make the learning experience fun for kids -- and that's what it takes to turn something simple and even of limited utility into a money printer.
Who knows? There may be enough people who can't wait for tomorrow's newspaper to find out where they went wrong. But I think you'll find there's more value in the source code than in the running program.