Solving 'Hundepuzzle' with High School Maths Only

[pioneerboy]

Is there a solution to this game https://prlbr.de/2011/08/hundepuzzle/alle-karten.png in the form of an equation that only requires high school mathematics but no higher maths and informatics?

 

[berkeman]

Is there a solution to this game https://prlbr.de/2011/08/hundepuzzle/alle-karten.png in the form of an equation that only requires high school mathematics but no higher maths and informatics?

Can you translate the description of the puzzle which is one level up from that figure's URL?

https://prlbr.de/2011/08/hundepuzzle/

 

[pioneerboy]

Sure. It's very easy and does not require literal translation.
You have 9 cards showing the front or back of 4 different dogs. The cards must be layed and turned so that all fronts and backs that do not touch the 9x9 card's corners or edges are complete in the sense that they match the same dog. I read somewhere that there are two solutions.
However, I am not interested in the solution 'per se' but in the equation(s) leading to those solution(s). I am wondering if there are formulas that does only require high school mathematics without any stuff at all that is taught in college - higher maths, statistics, informatics etc. Or at least an explanation about what is the very lowest level that would be needed for such equation(s). I do not ask out of lazyness, but of curiosity if there's an understandable equation for people without having studied maths and informatics and try to find an equation on the back-of-an-envelop.

Thanks very much.

 

[jbriggs444]

Sure. It's very easy and does not require literal translation.
You have 9 cards showing the front or back of 4 different dogs. The cards must be layed and turned so that all fronts and backs that do not touch the 9x9 card's corners or edges are complete in the sense that they match the same dog. I read somewhere that there are two solutions.
However, I am not interested in the solution 'per se' but in the equation(s) leading to those solution(s). I am wondering if there are formulas that does only require high school mathematics without any stuff at all that is taught in college - higher maths, statistics, informatics etc. Or at least an explanation about what is the very lowest level that would be needed for such equation(s). I do not ask out of lazyness, but of curiosity if there's an understandable equation for people without having studied maths and informatics and try to find an equation on the back-of-an-envelop.

May we also assume that the top edge must correctly mate with the bottom edge and that the right edge must correctly mate with the left edge? (as if the 9 cards were arranged on a torus).

You ask for an "equation". But It would seem more plausible that what you are after is a procedure by which the puzzle can be solved simply and efficiently. Is that correct?

 

[Vanadium 50]

You keep saying equation. An equation is a statement that two quantities are equal (hence the word). I don't see how you can make this into an equation - there are no quantities here.

I also don't see how there can be as few as two solutions. Since you can always rotate the entire thing by 90 degrees, if there is one solution, there are four.

 

[DaveC426913]

May we also assume that the top edge must correctly mate with the bottom edge and that the right edge must correctly mate with the left edge? (as if the 9 cards were arranged on a torus).

No. Unmated edges need not match.

You ask for an "equation". But It would seem more plausible that what you are after is a procedure by which the puzzle can be solved simply and efficiently. Is that correct?

Yes, I think he's looking for an algorithm.

I also don't see how there can be as few as two solutions. Since you can always rotate the entire thing by 90 degrees, if there is one solution, there are four.

Spoken like a mathematician!

A solution is definable by the relationship between the 9 tiles. Rotating the entire thing does not change the relationship between the 9 tiles.This puzzle has been reproduced with many themes other than dogs. I do NOT know if every puzzle sues the exact same pattern, or whether there are multiple configurations that result in single-solution puzzles. It would be interesting to find out.

 

[DaveC426913]

Here is the puzzle, reduced:

Black = 1, Black/Brown/White = 2, Black/White = 3, Black/Brown = 4
Clockwise from top edge:

1232 4322 1432

1314 3412 2134

2324 3214 3414

Rotating a tile clockwise is accomplished by popping a number off the end of a 4-byte and pushing it on the beginning (4322 becomes 2432). Rotating CCW is the reverse.

 

[Vanadium 50]

May we also assume that the top edge must correctly mate with the bottom edge and that the right edge must correctly mate with the left edge?

No. There aren't the right dog-halfs to make this work out.

You can quickly convince yourself that if you rotate one tile, you need to rotate all the other tiles in the same row OR column to make it work out. That immediately eliminates 98.4% of the solutions.

I would program this using backtracking.

Pick a tile and an orientation. Place the next tile down, and the next, and the next until either I have violated the rotation rule or cannot legally place another tile. Then back up as far as I need to, changing first the rotation and then the tile, until I get a success.

 

[DaveC426913]

I would program this using backtracking.

Pick a tile and an orientation. Place the next tile down, and the next, and the next until either I have violated the rotation rule or cannot legally place another tile. Then back up as far as I need to, changing first the rotation and then the tile, until I get a success.

Yup. That would be a brute-force technique. One wonders if there is any way to do it more parsimoniously.

 

[Vanadium 50]

hat would be a brute-force technique.

I differ. Backtracking takes up an entire chapter in Horowitz and Sahni, and typically shaves 3 or 4 orders of magnitude off the execution time. Furthermore, if you want every solution, you are going to need some sort of exhaustive test.

 

[DaveC426913]

I differ.

It is the brute force technique. Although I grant that is it not automatically slower than a solving algorithm.

But brute force is not a rigorous mathematical proof.

Furthermore, if you want every solution, you are going to need some sort of exhaustive test.

Disagree. In many situations, mathematical proofs can find every solution without exhaustive tests. In fact, exhaustive tests are often insufficient to prove there are no more solutions: One can prove there are only 5 platonic solids. A brute force technique could never find every solution since you could count to infinity without proving there isn't another one hiding.

Using a brute force technique means you start from Square One for every given puzzle. An algorithm could cut down the possible configurations dramatically.

 

[bahamagreen]

See Wang Tiles...

 

[Vanadium 50]

But brute force is not a rigorous mathematical proof.

First, you continue to disparage backtracking as "brute force". It must be pretty easy to take potshots at others' solutions without providing one of your own.

Second, brute force most certainly is a rigorous proof. https://en.wikipedia.org/wiki/Proof_by_exhaustion

 

[DaveC426913]

It was certainly not meant to be a personal comment.

 

[micromass]

But brute force is not a rigorous mathematical proof.

Wow, are you serious? Brute force is not a rigorous mathematical proof? This is an insane post.

 

[DaveC426913]

Wow, are you serious? Brute force is not a rigorous mathematical proof? This is an insane post.

I should have said brute force is not always a rigorous proof. And I was looking for an algorithm that would do for ALL puzzles of this type (I don't know how many there are - there might be one, there might be fifty).

Van's solution would work fine because there is a fixed number of configurations to this puzzle.

 

[micromass]

I should have said brute force is not always a rigorous proof.

It doesn't really sound like you understand brute force/rigorous proof. If you obtain a solution by brute force, then it's a rigorous proof.

 

[DaveC426913]

It doesn't really sound like you understand brute force/rigorous proof. If you obtain a solution by brute force, then it's a rigorous proof.

But it only works if there are a limited set of configurations.

If you applied a brute force technique to discovering the Platonic solids, you would never finish, since, after hitting the first five, you could never be sure there weren't more based on a 100-sided or thousand-sided polygon. You would have to use an algorithm to conclusively limit the possible configurations.

What's more, an algorithm
- is applicable to other puzzles of this type (there's more than one). The Proof by Exhaustion solves it for one example then you start again on hte next puzzle.
- can show some puzzles that might have zero solutions without having to go through every step.

 

[micromass]

It only works if there are a limited set of configurations.

Obviously. That just means a brute force attack doesn't exist in other situations, it doesn't mean that it's not rigorous.

If you applied a brute force technique to discovering the Platonic solids, you would never finish, since, after hitting the first five, you could never be sure there weren't more based on a 100-sided or thousand-sided polygon.

Here is a proof of the uniqueness of the Platonic solids that most mathematicians would consider brute force:

The Platonic solids consist of regular n-sides polygons. We know that n-sided polygons have interior angles of $180\frac{n-2}{n}$ degrees. At a given vertex of a regular polygon, we have $k$ polygons meeting. Obviously, the combined angles at that point must add up to less than 360 degrees. Here are the possibilities:

If $n=3$, then either $k=3$ which gives a tetrahedron, $k=4$ which is an octahedron, $k=5$ which is an icosahedron. For $k>5$, we have combined angles of
180k\frac{n-2}{n} = 60k\geq 360
so they are ruled out.
If $n=4$, then either $k=3$, which gives a cube. If $k\geq 4$, then
180k\frac{n-2}{n} = 90k\geq 360
so they are ruled out.
If $n=5$, then either $k=5$ which gives a dodecahedron. Similarly as in the last case, if $k\geq 5$, then this $k$ is ruled out.

If $n\geq 6$, then it is easily seen that we have $\frac{n-2}{n}\geq 2/3$. Since $k\geq 3$, we have
180k\frac{n-2}{n} \geq 180\cdot 3\cdot \frac{2}{3} = 360
so all of those are ruled out.

 

[DaveC426913]

Here is a proof of the uniqueness of the Platonic solids that most mathematicians would consider brute force:

OK, I would not have labeled that as brute force.
Brute force would be starting with sides=3 and seeing what shapes we can get, then proceeding to 4, 5, 6, 7 etc.

The method you list is ruling out whole categories. I was hoping to look for this kind of method for the puzzle.

 

[micromass]

OK, I would not have labeled that as brute force.

Yep, like I thought: you don't know what brute force means.

 

[DaveC426913]

You stopped at 6. You had to know rules about defect angles etc of polyhedra to stop at six. Brute force would have had you continue 7 and beyond.

My suggestion was to look for the same kinds of rules so that, like your example, we could know when a configuration fails without examining every permutation.

 

[micromass]

You stopped at 6. You had to know rules about defect angles etc of polyhedra to stop at six. Brute force would have had you continue 7 and beyond.

My suggestion was to look for the same kinds of rules so that, like your example, we could know when a configuration fails without examining every permutation.

You seem to have this weird notion that brute force involves examining all possibly cases individually. It doesn't. A proof by brute force involves splitting up a conjecture in different cases and then checking those cases individually.

For example, the proof of the four colour theorem first reduced the theorem to about 1900 cases and then checked these individually. This is a proof by brute force.

Please read this wikipedia article before replying further: https://en.wikipedia.org/wiki/Proof_by_exhaustion Note specifically that they say explicitely that brute force is a rigorous proof.

 

[DaveC426913]

I should clarify that you are correct. I did not know that brute force was also a well-defined term specific to mathematics.

It is a term I commonly encounter outside of mathematics, where it simply means, essentially, try every possibility until you can't try any more. It was in this sense that I used it initially, which certainly muddied the waters. Outside the mathematical context, it does not necessarily only apply to things with limited configurations, so it is not necessarily synonymous with proof by exhaustion.

 

[DaveC426913]

Please read this wikipedia article before replying further:

Not necessary. I grant the mathematical definition. Yes. Van's method works.

To get back on-track, there are other ways that might help solve the OP's puzzle.

 

[Vanadium 50]

there are other ways that might help solve the OP's puzzle.

Then for heaven's sake, show one. You don't like my solution? Fine - post a better one.

 

[DaveC426913]

No way man. This thread lost all its fun about 10 posts ago.

 

[pioneerboy]

Although not having posted anything, I would like to write that I am pleased that my question also is of interests to others and that got you all into this discussion - unfortunately, with crossed wires about the meta-discussion about the nature of mathematical proofs...but at least these misunderstandings were solved. Unfortunately, I can't contribute to the solution as such else than an algorithm might be best built up upon the declaration of the 4 dogs as letters A, B, C, and D and the differentiation of heads and tails into small and large letters (a, b, c, d, A, B, C, D), whereas on a card heads and tails are always opposite of each other and two neighbouring cards would result in a whole dog of the form of e.g. a¦A.

 

[bahamagreen]

See Wang Tiles...

It's still Wang Tiles...

"Robert Berger... ...proved that no algorithm for the problem can exist, by showing how to translate any Turing machine into a set of Wang tiles that tiles the plane if and only if the Turing machine does not halt. The undecidability of the halting problem (the problem of testing whether a Turing machine eventually halts) then implies the undecidability of Wang's tiling problem.

 

[Vanadium 50]

So, I spent a few moments coding this up with backtracking. It takes 58164 trials to find the 8 solutions, a factor of ~1600 less than an exhaustive search. This takes 1/30 of a second. My observation that a complete row or column needs to be rotated proved unhelpful, as you cannot test this early enough in the game to do any good. This code finds rotated solutions; one could determine a canonical form, e.g. "Tile 0 remains unrotated" and save a factor of up to 4.

The most interesting thing I found is that my code fails under -O1 (gcc 4.8.3) but not if each individual -O1 optimization is turned on. (!)