Regeln (Rules) • Lexikon • Links und Literatur • Strategie
Regeln: Schreiben sie in jedes leere Feld eine Zahl, die gleich ist der Summe der Differenzen der Zahl selbst und den Zahlen in den orthogonalen Nachbarfeldern. (Enthält also z.B. ein Feld mit drei Nachbarfeldern die Zahl n und stehen in den drei Nachbarfeldern die Zahlen a, b und c, so muss gelten: n = |n-a|+|n-b|+|n-c|.)
Rules: Write in each empty cell a number which is equal to the sum of the differences between the number itself and the numbers in the orthogonally adjacent cells. (For example, if the number in a cell with three orthogonally adjacent cells is n and the numbers in the orthogonally adjacent cells are a, b, and c, then: n = |n-a|+|n-b|+|n-c|.)
Bosanowa erschien erstmals in Puzzle Communications Nikoli #119 (Juni 2007). Autor dieser Rätsel war Gesaku, der diese Rätselart wahrscheinlich auch erfunden hat.
Bosanowa (ボサノワ) = Bossa Nova, benannt nach dem brasilianischen Musikstil. Bossa Nova kommt aus dem Portugiesischen und bedeutet soviel wie Neue Welle (New Wave).
Puzzle Communications Nikoli enthält sporadisch einige Bosanowa-Rätsel
Bosanowa auf indi.s58.xrea.com
Bosanowa auf Sachsentext von Uwe Wiedemann
Bosanowa Solver von Jean Christophe Goddard
If there exists a non-zero cell in the grid, then all cells must be non-zero. (Assuming all cells are connected together.)
Proof: Suppose one cell is zero. Then all its neighbors must be 0. Then all neighbors of its neighbors must be 0... and at the end all cells become zero, violating the existing non-zero cell.
Corollary: If a gap is established as the same as the cell value, then the neighbor on the other side of that gap must hold the doubled value of the cell, and all other gaps for that cell must be 0.
Example: A cell of 3 has a gap of 3. Then the neighbor on the other side must be of value 6 (instead of 0). All other neighbors (if any) must be of value 3.
Let x be the value of a cell. All its neighbors can't have a value larger than 2x or smaller than x/2.
In other words, two neighboring cells can't have a ratio of more than 2:1 or less than 1:2.
Proof: If a neighbor is larger than 2x, then the gap will be larger than x, conflicting the x-valued cell. If a neighbor is smaller than x/2, then the gap will be larger than x/2, conflicting the neighbor cell.
Examples: A cell of 3 has a gap of 2. Then that neighbor must be 5 (instead of 1). Another cell of 5 has a gap of 3. Then that neighbor must be 8 (instead of 2). (Anyone smells the Fibonacci odour here?)
More examples: The neighbors of a cell of 3 must be from the range 2..6, the neighbors of a cell of 5 must be from 3..10, etc.
If a cell of x has only one neighbor, then that neighbor cell must hold 2x.
Proof: Refer to the corollary of (1) above.
Corollary: 1 Neighbor Parity (1NP)
A cell which is the sole neighbor of another cell must be even-valued. Its gap to that neighbor must be half of its value, while all other gaps also sum to half of its value.
If a cell of x has only 2 neighbors with values A & B respectively (with A>=B), then there can't be more than 3 possible values for x: A+B, A-B or (A+B)/3.
Proof: We work from the equation x=|x-A|+|x-B|. There are 3 ranges of x:
(Range 1) x>A>=B: x=(x-A)+(x-B)=2x-(A+B) => x=A+B
(Range 2) A>=x>=B: x=(A-x)+(x-B) => x=A-B
(Range 3) A>=B>x: x=(A-x)+(B-x)=(A+B)-2x => x=(A+B)/3
Corollary 1: If A=B, i.e. the cell of x has only 2 neighbors which have the same value B, then x must be 2B or 2B/3 (if B is a multiple of 3).
Corollary 2: If A>B, then A+B>2B, so A+B is not a valid value for x (RR).
Corollary 3: x=A-B only works if 2B>=x>=B (RR, Range 2) => 2B>=A-B>=B => 3B>=A>=2B, so if A<2B or A>3B, A-B is not a valid value for x.
Corollary 4: x=(A+B)/3 only works if x<B (Range 3) => (A+B)/3<B => A+B<3B => A<2B, so if A>2B, (A+B)/3 is not a valid value for x.
Corollary 5: If A=2B, then A-B=(A+B)/3=B, so B is the only possible value for x.
Corollary 6: If A=3B, then A-B=2B, so 2B is the only possible value for x.
Summary: Suppose a cell of x has only 2 neighbors with values A & B (A>=B):
Case 1a: A=B is not divisible by 3 => x=2B
Case 1b: A=B is divisible by 3 => x=2B or 2B/3
Case 2a: 2B>A>B and A+B is not divisible by 3 => x has no possible value (invalid)
Case 2b: 2B>A>B and A+B is divisible by 3 => x=(A+B)/3
Case 3: A=2B => x=B
Case 4: 3B>A>2B => x=A-B
Case 5: A=3B => x=2B
Case 6: A>3B => x has no possible value (invalid)
Corollary: 2 Neighbors Parity (2NP)
If a cell has 2 neighbors, then the sum of these 2 neighbors must have the same parity as its cell value.
Proof: Let the cell of x has 2 neighbors of values A & B respectively (with A>=B). Then from the above x must be one of A+B, A-B or (A+B)/3, all of them have the same parity as A+B (including (A+B)/3 if A+B is divisible by 3).
Corollary: 2nd Neighbor Estimation (2NE) (credit to Pyrrhon)
If a cell of x has 2 neighbors A & B, then x+A>=B and x+B>=A.
Proof: without loss of generality, we assume A>=B. Then x+A>=B is automatically true. We only need to prove x+B>=A.
If A=B (case 1a & 1b), then x+B = x+A > A
If 2B>A>B (case 2b), then x=(A+B)/3 => x+B = (A+B)/3+B = (A+B+3B)/3 = (A+4B)/3 > (A+2A)/3 = A
If 3B>=A>=2B (case 3,4,5), then x=A-B => x+B = (A-B)+B = A
So x+B>=A must be true for all cases where x has a possible value.
A direct application is if we know the max values of x and one of its neighbors, we can determine that the 2nd neighbor must not exceed the sum of these max values.
A cell has 2 neighbors (out of a possible 4) holding the same value. Then the gaps between that cell and those 2 neighbors must be the same. If one of these 2 gaps is found then the value can be "transferred" to the other gap.
Application: This can be most useful when 2 cells next to a corner cell hold the same value:
+-----+-----+-----+ | | | | | x A ? | | | | +- -+- -+- -+ | | | | | A y | | | | +- g -+- -+- -+ | | | | | | | | | +- -+- -+- -+
The gap marked with ? must be equal to g, even if we don't know the values of x & y.
Similar to the above but here we transfer the parities (even/odd) instead of the actual gap values. We can determine whether a cell is even or odd by working out the parity of the values/gaps in nearby cells.
Application: Best demonstrated as following:
+-----+-----+-----+ | | | | | ? | | | | +- -+- -+-----+ | | | | A | | | | +- g -+-----+
In the above A & g are both found to be odd. By transferring the parities we can somehow work out whether the cell marked with ? is even or odd. I'll leave it as an exercise to the readers. (Added later: this can be alternatively worked out by applying WC & 3NP as described below.)
A "window" is a 2x2 group of cells in the grid. If 2 opposite corners of a window are isolated from outer cells (i.e. both corners have only 2 neighbors) then these 2 corners must hold the same value.
Proof: Consider the following diagram:
+-----+- -+ | | | | x A | | | +- -+- -+ | | | B y | | | | +- -+-----+
From 2N, x and y can be different only if A=B is divisible by 3 (2N case 1b), but then one of x will be 2B and the other will be 2B/3, conflicting the cell of B (with the sum of gaps >= B+B/3). Hence x and y must be the same.
If a cell has only 3 neighbors (i.e. centre of a "T-junction"), the sum of these 3 neighbors must be even (i.e. either all 3 are even or 2 odd, 1 even).
Proof: Assume the 3 neighbors of the cell of x have values A,B,C. Then from the equation:
=> 0 mod 2 = (|A-x|+|B-x|+|C-x|-x) mod 2 = ((A-x)+(B-x)+(C-x)-x) mod 2 = (A+B+C-4x) mod 2 = (A+B+C) mod 2
So (A+B+C) mod 2 = 0 i.e. A+B+C must be even.
If a cell has 4 neighbors (i.e. centre of a "Cross"), the sum of these 4 neighbors must have the same parity as its cell value.
Proof: Assume the 4 neighbors of the cell of x have values A,B,C,D. Then from the equation:
=> x mod 2 = (|A-x|+|B-x|+|C-x|+|D-x|) mod 2 = ((A-x)+(B-x)+(C-x)+(D-x)) mod 2 = (A+B+C+D-4x) mod 2 = (A+B+C+D) mod 2
So (A+B+C+D) mod 2 = x mod 2 i.e. A+B+C+D and x must have the same parity.
These 9 properties/techniques are enough for me to solve all the 7 puzzles from the blog page above, but I believe there are certainly other useful tricks which I haven't invented, and would love to see any others post their own tricks/thoughts about this!
And btw Dan, feel free to publish this guide in your blog when you release your own Bossanova puzzles!
New properties/techniques added later:
A window is a 2x2 array of cells. If 3 corners in a window are all isolated from outer cells (i.e. having only 2 neighbors), as in the following pattern:
+-----+-----+ | | | | A B | | | | +- -+- -+- | | | | C D | | | +-----+- -+- | |
Then the middle cell of these 3 isolated corners (cell
A) must be even. Let it be 2n.
Then the other 2 isolated corners (cell B & cell C) must be either n or 3n.
And the outlet corner (cell D) must be n or 5n respectively. As below:
+-----+-----+ | | n | | 2n | | | 3n | +- -+- -+- | n | n | | | 3n | 5n | +-----+- -+- | |
WC: B=C => 2NP: A must be even. So let A=2n
2N case 1b: A=2B or 2B/3 => B=A/2 or 3A/2 => B=C=n or 3n
If B=C=n, then D=n (gaps); if B=C=3n, then D=5n (RR)
Corollary: Window Outlet Exit (WOE)
If the outlet corner (cell D) has only 3 neighbors (i.e. B, C and another cell E), then E must be 2n, 4n or 6n. As below:
+-----+-----+ | | n | | 2n | | | 3n | +- -+- -+-----+- | n | n | 2n | | | 3n | 5n |4n 6n| +-----+-----+- -+- | |
Proof: If B=C=n & D=n, then E=2n (NZ); if B=C=3n & D=5n, then E=4n or 6n (gaps)
A side effect is this "exit cell" (cell E) must be even (which can be easily proved by WC+3NP).
A domino is a 1x2 or 2x1 array of cells. If one cell of the domino is isolated from outer cells (i.e. having only 1 neighbor), while the other one has only 2 neighbors, as in the following pattern:
+-----+-----+-----+- | | | | | A B C | | | | +-----+-----+- -+- | |
We call A the "dead end cell", B the "outlet cell", C the "exit cell". Let A=n, then B=2n and C=n or 3n. As below:
+-----+-----+-----+- | | | n | | n 2n | | | 3n | +-----+-----+- -+- | |
Proof: 1N: B = 2A = 2n => C = 2n-n or 2n+n = n or 3n
Corollary: The "exit cell" (cell C) is either a multiple of 3 or the outlet cell (cell B) must hold the doubled value of it, while all its other neighbors must hold the same value as it.
Proof: If C=3n then it's a multiple of 3. Otherwise C=n & B=2n and the gap between C and all other neighbors must be 0.