Picross uniqueness???
I just bought a DS game called Picross DS. I have played Picross before on SNES. If I recall it correctly I completed all the puzzles in that game. It was like 10 years ago though.
After playing the DS version for a while, I asked myself if the clue on the side of the puzzle and the solution a one to one set? After thinking for a while the answer is No (in general). A counter example is very simple. Take a 2×2 picross puzzle.
On this picture, you might ask what color is the marked vs unmarked block?. My answer would be try them both. You will see that both colors are solution to the number on the side. You many notice that this picture has a very high degree of symmetry. The one that matters to this counter example is the flipping along vertical and horizontal axis. You can try build up a bunch of counter example for any size using the similar trick.
I’ll end this post with a conjecture.
If the puzzle doesn’t have any symmetry (along vertical axis or along horizontal axis), then the solution is unique.
I have a feeling that there is a short proof for this (5-10 lines) though (Not that I have proved it).
[update] That conjecture above is so wrong. Try padding the 2×2 with empty blocks so that it’s 4×4. This conjecture is also wrong but a little more interesting.
(another wrong) Conjecture: Lets represent the puzzle(assume it’s a square one) with a matrix of 1 and 0(1 for marked 0 for unmarked). If the determinant of the matrix is not zero then we have a puzzle that has a unique solution. (I thought of this because switching any row or column put a negative sign in front of the determinant; however, you can switch row even number of times :s)
Add comment August 4th, 2007