# The dog's game

Tags:
1. Jan 1, 2016

2. Jan 1, 2016

3. Jan 1, 2016

### 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.

4. Jan 1, 2016

### jbriggs444

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?

5. Jan 1, 2016

Staff Emeritus
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.

6. Jan 1, 2016

### DaveC426913

No. Unmated edges need not match.

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

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.

7. Jan 1, 2016

### 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.

8. Jan 1, 2016

Staff Emeritus
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.

9. Jan 1, 2016

### DaveC426913

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

10. Jan 2, 2016

Staff Emeritus
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.

11. Jan 2, 2016

### DaveC426913

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.
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.

Last edited: Jan 2, 2016
12. Jan 2, 2016

### bahamagreen

13. Jan 2, 2016

Staff Emeritus
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

14. Jan 2, 2016

### DaveC426913

It was certainly not meant to be a personal comment.

15. Jan 5, 2016

### micromass

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

16. Jan 5, 2016

### DaveC426913

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.

17. Jan 5, 2016

### micromass

Staff Emeritus
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.

18. Jan 5, 2016

### DaveC426913

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.

19. Jan 5, 2016

### micromass

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

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.

20. Jan 5, 2016

### DaveC426913

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.