Timeline for A New York Times tiles-based graph theory question
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 24, 2023 at 14:38 | comment | converted from answer | Peter | I think the challenge is to complete it in the highest number of moves. | |
| Feb 6, 2021 at 7:25 | comment | added | Ville Salo | Maybe Hamiltonin path on a 3-regular graph reduces to this with a bit of work? | |
| Oct 6, 2020 at 12:00 | comment | added | Timothy Chow | Note in particular that if A, B, C, and D all share a pattern, then initially, one can proceed directly between any two of these tiles. But if one chooses to go from A to B (say), then the pattern disappears, and it is no longer possible to go from A or B directly to C or D (unless some other pattern is shared). This feature differentiates the problem from the Eulerian trail problem and is part of what makes me suspect that it may be NP-hard. | |
| Oct 4, 2020 at 22:37 | comment | added | Timothy Chow | Some special cases have been solved. For example, suppose that for any two tiles that share a pattern, they share exactly one pattern, and that pattern doesn't appear anywhere else. Then (if I understand the rules correctly) finding a single sequence that erases all the patterns is equivalent to finding an Eulerian trail, which can be done efficiently. But Tiles allows two tiles to share more than one pattern, and for a pattern to appear multiple times. Maybe this is equivalent to a known problem, but I don't recognize it. | |
| Oct 4, 2020 at 20:37 | comment | added | David Pepper | I thought that the problem has an interesting graph structure to it, with multiple connections between points, and you have to find a complete circuit around the graph. This isn't something that's been solved yet? | |
| Oct 3, 2020 at 15:07 | comment | added | Timothy Chow | It seems like this could be an NP-hard problem. But I don't immediately see a reduction from a known NP-complete problem. | |
| Oct 2, 2020 at 17:35 | review | First posts | |||
| Oct 2, 2020 at 18:10 | |||||
| Oct 2, 2020 at 17:30 | history | edited | YCor | CC BY-SA 4.0 |
edited tags
|
| Oct 2, 2020 at 17:28 | history | asked | David Pepper | CC BY-SA 4.0 |