#1: Mark Conger (aruba) on Apr 4, 2006
While doing puzzle 403, I had to fill in several long columns which contained no blank squares. Each square was an apparently random color, so counting the numbers in each column was difficult. I found it simpler to start at the top of each column, click once on the top square to make sure the autochecker said "blank" was wrong, then click as many more times as it took to make the red error dot go away. Then repeat for the next square.#2: Jan Wolter (jan) on Apr 4, 2006
This method can't produce an error, because the fact that the top square can't be blank means that the column must be "full", so the correct color of each square is determined.
However, it made me wonder if the same method can work on any square that can't be blank. In other words, the question is, could there be a square in a puzzle that can't be blank, according to current information, but whose color hasn't been determined, by that same information? For instance, a square that can't be blank, but could be either blue or black. Can anyone give an example?
My guess is that it's not possible. If there is more than one possibility for the color of a square, white is always one of the possibilities.#3: Jan Wolter (jan) on Apr 6, 2006
I'm going to try to do a hand-waving partial proof.
Let's assume we are looking at just one row. Some cell, call it x, can be either black or red. If this is true, then the clue must contain a black and a red interval. Without loss of generality, we assume that the black interval is to the left of the red interval. So the clue looks like this:
a1 a2 ... ak B b1 b2 ... bn R c1 c2 ... cm
Here B is the black interval that can contain x, and R is the red interval that can contain x. We know that the
sequence a1 through bn can fit to the left of x, and we know that b1 through cm can fit to the right of x. So we can put a1 through B to the left of x, and b1 through cm to the right of x, leaving x blank. So white is also a possibility for x.
That doesn't prove that the combination of row and column clues can't have the desired effect. My guess is not.
I think you can take this question two different ways. I answered the question for the case where we are considering just a single row or column. You can also ask the question about an entire puzzle. Of course, if the puzzle has a unique solution, then there is only one possible color for every square, so the whole thing is moot. It only gets interesting for puzzles with multiple solutions. So, can there be a puzzle that has a cell which is black in some solutions, red in some solutions, but not white in any solutions.#4: Martial (marso) on Nov 3, 2007
I don't really have any idea how to address that.
That's an easy one: you just need quantic squares. From there, the answer is yes.#5: Mark Conger (aruba) on Apr 11, 2006
Quantic squares?#6: Jan Wolter (jan) on Apr 12, 2006
I think they are made of dilithium.#7: lisa hamm (lisylocket) on May 6, 2006
I read this post and my head started hurting : s#8: Jan Wolter (jan) on May 7, 2006
Heh. Mark's working on his PhD in mathematics. I used to be a computer science professor and I still drool at the scent of a theorem in the distant hope that there might be a paper in there somewhere, or at least a better solver algorithm.#9: Mark Conger (aruba) on Sep 18, 2006
It's really just another kind of puzzle, but it's kind of like those cryptic crosswords. You have to get into the special langugae rules before it makes any sense. Once you do, you'll see that the proof I sketched above is really rather trivial. Mark's original observation was more interesting, but doesn't off-hand seem to lead anywhere.
I came across a counterexample to Jan's proof while doing puzzle #368. Suppose the clues are#10: Mark Conger (aruba) on Sep 18, 2006
and in the middle of the row somewhere we have
where the R's are red squares and the x is empty. Then x can be either red or black, but it can't be blank.
(The dots there are elipses, not white squares.)#11: Jan Wolter (jan) on Sep 18, 2006
Hmmm...I agree. So there's something wrong with my proof.#12: Jan Wolter (jan) on Sep 18, 2006
Yeah, I kind of see where I went wrong. It's hard to explain, but I was kind of assuming that the intervals that could match the x were both size 1 intervals, so I didn't have to worry about what ELSE they matched. Or something like that. I need a clearer head to think this through.#13: Mark Conger (aruba) on Sep 19, 2006
I realize now that one can construct a situation where any color except white is valid in a particular square. If the clue is
black 1, red 1, black 1, green 1, black 3, blue 1, black 1
and the row contains ...BxB... where B is black and x is blank, then x cannot be white, but it can be anything else.
Goto next topic
You must register and log in to be able to participate in this discussion.