Question: Should a Fathom It! solution use the fact that a solution to a board is guaranteed to be unique?
In several e-mails, Matthew Daly raised the question whether a Fathom It! solution could be based on the fact that all Fathom It! boards are guaranteed to have one, and only one, unique solution. The following is the exchange of e-mails between Daly, Wei-Hwa Huang, Shmuel Siegel and the author.
Matthew Daly (June 18, 1998):
In your analysis of problem #10 in the Intermediate set (both on your website and in Analyze1.wri), you justify placing the last cruiser at A10-C10 on the fact that a solution to a board is guaranteed to be unique. Although this turns out to be true for published puzzles in general and might be used as a shortcut for some solvers, IMHO a proof of a solution is indebted to prove that the solution is unique rather than assuming it. (I recall a thread in rec.puzzles where Wei-Hwa chastised me for even thinking about using it as a shortcut as a solver, much less as a creator!) Especially when it's just as easy to prove uniqueness: if H10-J10 were a cruiser, then the only possible location for the remaining destroyer would have to be B6-B7, but then there would be no place for the last ship square in row H.
Moshe Rubin (June 19. 1998):
Your proof of uniqueness (ie destroyer in B6-B7 closes off row H) is simple, clear, and correct. I assume the glitz of my solution kept me from seeing your simpler one.
... When solving Raymond Smullayan's chess problems using retrograde analysis, one starts with the assumption that the original board was a valid chess position (eg kings not adjacent, pieces move standardly). In other words, a solver can use the rules of the game as a valid method of solution. According to Wei-Hwa's reasoning, you must first prove the chess board began with a legal position before starting retrograde analysis (a Catch-22!). In Fathom It! (possibly (?) as opposed to the Battleships column), one of the "game ground rules" is that all boards have a unique solution. Following the analogy, a human solver should be allowed to assume and make use of it.
Matthew Daly (June 30, 1998):
Of course, it's your ship and you can do whatever you please. :-) Let me make one last attempt to convince you, though.
In Smullyan's retrograde analysis puzzles, the rule that a position is achievable from a legal game (or at least the previous n moves for some n) is used to whittle down the solution set or to achieve a solution that would otherwise be impossible. Similarly, in Fathom It!, the rule that ships cannot be adjacent or that there are exactly four submarines are also used to make the solutions smaller than "Find the number of ways to shade in this 10x10 grid with 20 blocks so that the row and column counts work out correctly.
Is the same true of the rule that the provided grid has only one solution? I would say no. I won't find multiple solutions if I fail to assume that the solution is unique, like I generally would if I failed to assume that ships couldn't be adjacent. The logic that I use to reach that solution might be shorter, but it's really an empty axiom since I could find the solution without the assumption that it's the only one.
Wei-Hwa Huang (July 14, 1998)
I don't really see how the analogy to Raymond Smullyan's retrograde analysis problem applies to the uniqueness issue. For instance, there are many retrograde analysis problems where the solution is obvious (e.g., Problem: White to mate in 1 -- Answer: White castles and checkmates Black), but the hard part is proving that White is allowed to castle. Now consider this reasoning:
"Okay, this chess problem must have a solution since it was posed. Now, if White can't castle, then there is no solution. Therefore, White must be able to castle, and since White can castle, the solution must be that White castles."
By this (valid?) meta-argument, we have successfully proved that White can castle -- although Smullyan may have actually wanted us to use retrograde analysis! I, personally, consider this sort of proof as rather unsatisfying. (Is it valid? Debatable, but I don't really care if it's valid.)
I consider a rule such as "No two ships can be adjacent to each other." a simple rule. Given a potential solution, you can easily check to see if the solution fits this rule.
I consider a rule such as "The solution to every puzzle is unique." a meta-rule. Given a potential solution, you CANNOT check that the solution satisfies this rule. This rule applies to the PUZZLE, not the solution. (The solution is an integral part of the puzzle, so if a statement about the solution is a rule, a statement about the puzzle should be a meta-rule.)
Now, I am aware of certain puzzles where you must use the information that there is a (unique) solution in the puzzle. An old one is:
There are two concentric circles, A and B. There is a line segment which is a chord of A and tangent to B. This line has length 10. What is the area of the annulus between the two circles?
There is a mathematical solution:
Finally, since we know that the extended line going through YZ is a diameter of A and that if a diameter of a circle intersects a chord at right angles then it bisect the chord, XY must be half the length of the chord, to wit, 5. By the Pythagorean theorem on right triangle XYZ, we know that 25 + b^2 = a^2, or 25 = a^2 - b^2.
Now, the area of the annulus is the area of A minus the area of B. To wit, the area is pi a^2 - pi b^2, which is equal to pi (a^2 - b^2) = 25 pi. Therefore the area is 25 pi.
There is also a "meta"-solution:
Certainly there is a lot of elegance in the latter solution. However, WHOMEVER FIRST THOUGHT OF THE PUZZLE WOULDN'T BE ABLE TO USE IT! If a mathematician was trying to solve an unsolved problem in the literature, he could hardly use an argument like: "This problem must have a solution, and since XXX works, the answer must be XXX."
The difference, of course, is that the mathematician cannot assume that the problem was "posed" by someone who had an answer in mind.
It's a question of the attitude towards the puzzle. Does one assume that a Battleships puzzle has enough information to force the solution to be unique, because the designer designed it that way? Or does one assume that the puzzle exists independent of the designer and one must check whether the solution really is unique?
When we don't assume the answer is unique, we have to go through the same thinking processes the designer used when he or she created the puzzle. Since a competent designer shouldn't give a puzzle that has more than one solution, the designer actually has to check that the solution is unique -- so the solver is essentially doing the same tasks of the designer. In many puzzles, this is what's intended. Smullyan certainly intended me to prove that the mate in 1 by taking a pawn en passant is okay by PROVING that the pawn can take it en passant, instead of me using an argument like "If there's no en passant, then there's no mate in 1, therefore en passant must be allowed."
An interesting example is Everett Kaser's "Sherlock," which I'm sure you've seen. In that game, I can get to the solution much more quickly by assuming that the answer is unique. However, in his solver he's pretty careful to not make such assumptions, and I enjoy that much better. (Good thing your solver thinks the same way.)
But my bottom line is that's it's all a matter of taste: If a solver thinks that he can assume the solution is unique and get to the answer quicker, than more power to him. I think, for ME, it's more interesting to mimic the poser's thought processes by proving to myself that the solution is unique without having to assume it. Of course, if there are other considerations, then I assume uniqueness. For instance, at the World Puzzle Competition, we have to solve puzzles quickly. In many of those logic puzzles, I can't afford the luxury of checking for uniqueness -- I have to get the answer as quick as possible and move on. But in many of those cases, I miss the elegance that the creator had. (Also, because the creator sometimes made a mistake, we ended up with DIFFERENT answers ...)
I chastised Matthew for using it on a Cross Sums because he's an experienced puzzle solver. If a novice used the method, I wouldn't degrade them at all.
To take an extreme case, imagine a Battleships solver that works like this:
Not very satisfying, is it? (But in all honesty, it's what GAMES does -- they don't give you any logical analyses...just the solution. And I had to do this at the WPC lots of times as well -- just fill ships in by trial and error until a solution works.)
Shmuel Siegel (October 18, 1998):
The question is obviously one of taste. It depends largely on the objective of the solver. Although I was the one who initially convinced you to use the uniqueness rule, I have to admit that the only time that it was really of interest to me is when I discovered that it simplified a board that I was having trouble solving.
I don't like solving a board by trial and error but rather by insights into the board structure. In fact I don't even like negative logic rules that require me to turn over water pieces. Therefore, if the only way to get a "fun" solution is to use this rule, I will use it. But, I much prefer to recognize legal combinations. As one of your correspondents stated, proving uniqueness can also be fun. In my opinion, your descriptions should give these solutions but also point out the solution that proves uniqueness.
Moshe Rubin (October 10, 2004):
See Mark Brader's thoughts in the rec.puzzles newsgroup (cached) on using the uniqueness technique on a Battleship problem. His posting is part of a longer thread that discusses the use of the uniqueness technique in different types of puzzles.
Moshe Rubin (17 August, 2007):
It's almost nine years after the initial thread, many flotillas have sailed to sea, and your editor believes he has learned some things in the interim. I have since come to realize the wisdom in Matthew's and Huang's view of not relying on the uniqueness technique. Here's why.
I've read numerous postings that say something like this: "Aw, that Battleship puzzle wasn't hard -- I just guessed the battleship's position randomly and the puzzle fell apart". Matthew's point is spot on: this "technique" fails to find multiple solutions in a flawed puzzle.
In case you think that commercial Battleship puzzles do not have multiple solutions, I've encountered multiple solutions in GAMES Magazine, in World Puzzle Championship compendiums, and in Nishio Tetsuya's excellent Battleship puzzle book, to mention a few. A puzzler using the uniqueness technique will never know that a given puzzle is flawed.
Moshe Rubin (27 January, 2008):
Peter Gordon and Mike Shenk's informative "GAMES Battleships Solving Guide" [4] recommends depending on the implicit promise of unique solutions. When analyzing the last and hardest Battleship puzzle, here's what they write:
"Our advanced strategies don't help much either. The battleship can go in a number of places, and none of the rows or columns are within one of being filled. What can we do? Sometimes solving the really hard puzzle requires trial and error. You just have to take another guess, and if it doesn't work, you have to take another.
The battleship can go in two places in column G and in six places in column I. Try them until one works. As soon as one works you can stop, because all Battleships have unique answers."
As mentioned in my previous comment, such advise suffers from two drawbacks: (1) the Battleship puzzle might just suffer from multiple solutions, and (2) the final solution does not give the intellectual satisfaction of conquering the puzzle.
Additional references:
[1] An Unmentioned Logic Technique
This is a link to the Pappocom "Sudoku Players Forum Index -> Solving techniques" forum. The issue is the validity of using the uniqueness technique when solving Sudoku puzzles.
[2] My Worry with Forced Chains
Like the previous reference, the issue of using the uniqueness technique is discussed.
[3] rec.puzzle thread: "Easier to Answer than to Solve" (cached)
An interest discussion of the (non)merits of using the uniqueness assumption. Mark Brader proves his point with a Battleship puzzle, and James Dow Allen gives the puzzle a challenging twist.
[4] Peter Gordon and Mike Shenk's informative "GAMES Battleships Solving Guide"
First published by GAMES Magazine in 1998, this pamphlet was the first serious attempt to teach how to solve Battleship puzzles. For a link to it, see the web page "How to solve Battleship puzzles".
[5] rec.puzzle thread: "sudoku, again"
Another newsgroup thread discussing the question of unique solutions in puzzles.