| making a list of rules |
Tilps
Kwon-Tom Obsessive
Puzzles: 6720
Best Total: 18m 37s | Posted - 2008.09.01 06:37:52
So long as none of your patterns involve highlander based logic, you should be fine. |
chairman
Kwon-Tom Obsessive
Puzzles: 1397
Best Total: 17m 32s | Posted - 2008.09.01 19:47:55
Quote: Originally Posted by ferkel Hi veenca,
Any puzzle that has a diagonal full of 2's will have two solutions, I think. I've never seen any other examples though - I would love to know if they exist. Maybe we should search for them.
Ferkel |
Hi Veenca & Ferkel,
A 2x2 matrix filled with 2's is a counter example. This is another one:
|
v_e_e_n_c_a
Kwon-Tom Obsessive
Puzzles: 2080
Best Total: 32m 53s | Posted - 2008.09.01 20:12:55
Hi chairman, you are right.. thanks.. |
v_e_e_n_c_a
Kwon-Tom Obsessive
Puzzles: 2080
Best Total: 32m 53s | Posted - 2008.09.02 13:20:47
Do anybody know what is the edsf data structure? I looked over a source code of the Loopy just in a while and I don't know this data structure (or its abberviation). I am asking just for information. I use also in my source code structure for maintaining equivalence classes, but i use dfu (disjoint-union-find), which is fine, i think. With ranks and path compression it has constant amortized time complexity.. So does anybody know what edsf is? Thanks for reply.. |
pqg
Kwon-Tom Obsessive
Puzzles: 6383
Best Total: 15m 37s | Posted - 2008.09.02 18:14:23
I think there've been some misunderstandings over what exactly is being asked in this thread, possibly due to language issues. My attempt to clarify matters:
Veenca's original query was about layouts where every number is given and yet there are multiple solutions. We all know there are plenty of multiple solution layouts where some squares are blank (they are the foundation for highlander reasoning), but that's not relevant.
By the way, here's one reason why it's a good question: A simple way to generate puzzles is by drawing a random closed loop, adding every number, and then removing numbers one at a time, checking that the solution is still unique at each step. If the starting layout is ambiguous, even with all numbers supplied, then this approach won't work. It would therefore be interesting and useful to discover exactly which conditions result in multiple solutions despite having no blank squares, so that they can be avoided in puzzle generation)
Ferkel suggested that having a diagonal column of 2's is both a necessary and sufficient condition, but Chairman provided counter-examples that show it is not sufficient. The 2 questions then remaining are:
Is it necessary? Are there any examples of layouts (with no blanks) which have multiple solutions but don't include a diagonal row of 2s?
What are the sufficient conditions? It's been shown that the row of 2's is not enough to guarantee ambiguity, so what is? |
chairman
Kwon-Tom Obsessive
Puzzles: 1397
Best Total: 17m 32s | Posted - 2008.09.02 19:08:56
The following matrix is symmetric in the middle column, but the solution is not, so it is not unique. I think it will be very hard to find necessary or sufficient conditions, but I like to think about it.
|
v_e_e_n_c_a
Kwon-Tom Obsessive
Puzzles: 2080
Best Total: 32m 53s | Posted - 2008.09.02 20:08:17
Yes, this symetric puzzle has 4 solutions. But the nonuniqueness is also caused by diagonals of 2's. Maybe the puzzle has multiple solutions iff it contains at least one diagonal of 2's which is not affected by surrounding clues - i mean that from clues doesn't imply any cross or line on this diagonal (from the rest of clues we can't deduce any x or line on cells of 2's laying on these diagonals) . So if it contains n diagonals of such 2's it would have 2^n solutions. But the other question is how to recognize that the diagonal is not affect by surrounding clues. I think it is impossible without solving the puzzle in general situations. In some special cases such as Chairman posted, where one of surrounding cells was number 0 - it can be recognized without solving.. But it is only my opinion, may be i am wrong...
To pqg: you are right - i was trying to explain what i exactly mean, but my english is horrible - so sorry..
Edit: i was actually wrong with the number of solutions - this puzzle has only 2 solutions - it is caused by the fact that these two diagonals aren't independent - they are connected by number 2 in the middle bottom. So if they are independent, then the number of solutions should be 2^n
I am interested if exists any puzzle with multiple solutions if all clues are supplied without it having a diagonal of 2's... I think that no, but i am not able to prove it..  maybe it could be proved by properties of numbers and with use of locks/antilocks...
Last edited by v_e_e_n_c_a - 2008.09.02 20:34:13 |
chairman
Kwon-Tom Obsessive
Puzzles: 1397
Best Total: 17m 32s | Posted - 2008.09.03 08:56:52
This one only has subdiagonals consisting of 2's of size 2. I would not be surprised either if these were needed to create ambiguity.
So far I could not find a fully clued puzzle with three or more solutions. It could be a challenge to find one. |
