Weekend Challenge #3

Question

One single proposal per answer, most upvoted as of 2013-12-14 (12:00AM UTC) becomes our next challenge!

The winning entry shall be marked as the accepted answer.

_{index | previous challenge | next challenge}

Answer 1

Sudoku solver

Please tag submissions with sudoku.

Given a Sudoku puzzle as input, find its solution (or determine that it is unsolvable or ambiguous).

The program must take as input a puzzle in the form of a 9×9 grid of digits and dots (the dots representing blank squares in the puzzle). For example:

...84...9
..1.....5
8...2146.
7.8....9.
.........
.5....3.1
.2491...7
9.....5..
3...84...

The program must determine which of the following cases applies:

1. The puzzle is unsolvable: it has no solution.
2. The puzzle has exactly one solution.
3. The puzzle is ambiguous: it has two or more solutions.

In case #2, it must output the solution in the form of a 9×9 grid of digits. In the example above, there is exactly one solution:

632845179
471369285
895721463
748153692
163492758
259678341
524916837
986237514
317584926

Discussion about whether multi-solution puzzles are in fact Sudoku puzzles

 (edit by rolfl)

Since I originally suggested a Sudoku solver, perhaps I can explain my motivation for this. I have (occasionally) come across sudoku puzzles I cannot solve, for one reason or another. One application for the solution of this challenge, is to be able to, as a regular sudoku player, 'capture' the puzzle, and prove that my failure to solve is in fact my fault, and not the puzzle-setter's.

I fully intend to participate in this W-E Challenge (hopefully with my son), and the result of our work will hopefully enable us to (perhaps not on the first submission):

• capture an initial puzzle (and perhaps later also a partially completed puzzle)
• say whether there is an actual solution, and only one
• identify any inconsistencies in the puzzle (did we make a mistake somewhere?)
• suggest a potential 'move' that will assist in a solution (a 'hint' - X-Wing, Swordfish, etc.)
• brute-force the puzzle to get the solution if we 'give up' on a puzzle.

The final product will allow us to easily 'capture' a (perhaps partially completed) puzzle, and choose what sort of assistance we want.

These are the ideas that were drifting through my mind when I suggested this as a W-E topic, but I thought the first order of business was probably just a brute-force solution, which would knock 3 of the 5 requirements off the list.

Answer 2

Sentiment analysis (opinion mining)

Sentiment analysis, which is also called opinion mining, involves building a system to collect and examine opinions about some object in blog posts, comments, reviews or tweets.

This challenge will have to be watered down a bit so that people will not be overwhelmed by writing and reviewing code. Therefore, the "collecting" of the opinions can just be strings that are input into the program.

Simply put: Your job is to "weigh" the value of words from an input string on a scale based on their connotation.

This challenge can be as simple as you want (just finding the sentiment value for the whole string). It can also be as complex as you want (finding the sentiment value for certain, specific words, collecting data from social media sites, etc.).

Answer 3

Sink a Ship

Everyone has played Battleship. Let's implement the logic that sinks one.

• Ship has multiple "hit points" located at contiguous (x,y) coordinates, horizontally or vertically.
• Ship is sunken when all "hit points" are hit.

_{http://commons.wikimedia.org/wiki/File:Sinking_of_Battleship_Bouvet_at_the_Dardanelles-TSK.jpg}

Answer 4

Puzzle suggestion #2

Conway's Game of Life: aka Life is much more complex and might take too long for a weekend challenge. I've never personally created a complete solution for this one.

Answer 5

I was hoping to see a Math/Logic Puzzle of some sort.

Towers of Hanoi: Towers Of Hanoi is fairly simple and there are many solutions out there. But it seems we all have our own way of solving it.