# Weekend Challenge #3

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

# Sudoku solver

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.

• FYI, the definition of a Sudoku puzzle includes the constraint that "there must be one and only one solution". If it doesn't meet that, it's not a valid Sudoku puzzle. Commented Dec 12, 2013 at 17:36
• @JohnDeters I believe the Sudoku puzzle definition itself doesn't specify whether or not one and only one solution must exist, see Wikipedia article (which says "The puzzle setter provides a partially completed grid, which typically has a unique solution.") and this blog post Commented Dec 12, 2013 at 17:50
• The books state fairly strongly that a proper puzzle has one and only one solution. There's a reference here: en.wikipedia.org/wiki/Mathematics_of_Sudoku#Terminology : "A proper puzzle has a unique solution." Commented Dec 12, 2013 at 19:58
• The only reason I say something is that if a proper puzzle is a given, there's no reason to go on processing once a solution has been reached. Makes for a logical stopping point. Commented Dec 12, 2013 at 20:01
• But how do you know that the puzzle you are given is proper if you don't check? All programs that take input need to check for erroneous input. Commented Dec 12, 2013 at 23:17
• @JohnDeters added some blurb which may add to, or reduce the confusion. Commented Dec 13, 2013 at 16:03
• The example you give, am I correct that you can only solve this by some guessing/trying ? Commented Dec 16, 2013 at 14:18
• @tomdemuyt - I 'picked' the example from a 'diabolical' section... not one I have solved..... Commented Dec 16, 2013 at 14:49

## 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.).

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

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.

• How easy this is depends on the matrix handling facilities of your language of choice. APL can implement this in a single line, a concise scripting language can do with a dozen. If efficiency does not matter, it really isn't that complicated.
– amon
Commented Dec 12, 2013 at 22:03
• @amon Just because it doesn't need to be complicated. Doesn't mean you can't complicate it. Commented Dec 12, 2013 at 22:35
• Maybe implementing Bill Gosper's Hashlife algorithm would be about the right level of difficulty? Commented Dec 15, 2013 at 23:52

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.