Timeline for Covering of a surface of a cube $n\times n \times n$ by pieces of paper $1\times 6$
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 2, 2016 at 19:57 | comment | added | Peter Mueller | @fedja: Oh, I had stopped the programs after a few days :-( | |
| Jan 2, 2016 at 1:43 | comment | added | fedja | "I don't know yet about 13×13×7 and 13×13×13" Any update after 2 months of "running the programs"? :-) | |
| Nov 2, 2015 at 21:25 | comment | added | fedja | Also, since we can cover $11\times 11\times 11$ by $6\times 1$, we can cover $55\times 55\times 55$ by $30\times 5$ and, thereby, by $6\times 1$, which takes care of $n=6m+1$ for $m\ge 9$. Thus, the number of exceptional cubes is finite. | |
| Nov 2, 2015 at 10:11 | history | edited | Peter Mueller | CC BY-SA 3.0 |
added 733 characters in body
|
| Oct 31, 2015 at 2:06 | comment | added | fedja | Actually, it is easy to show that if $m\times n\times k$ is coverable, then so is $(m+6)\times n\times k$ (just think of all strips crossing the edges of the face to move and elongate them by 6 units inserting formal $0\times 1$ strips along the edge where nothing is really bent; then split each $12\times 1$ into two $6\times 1$). Thus, to finish off the cube problem for good, it would be nice to do the $n=13$ case as well. I don't think it should be much harder for the computer than $n=11$ and I'll be quite surprised if nothing shows up. :) | |
| Oct 28, 2015 at 19:15 | comment | added | David Eppstein | Re the time complexity of Algorithm X: see 11011110.livejournal.com/128249.html — there are faster algorithms known (in theory) for exact satisfiability, but they are all still exponential, and X is fast in practice. | |
| Oct 26, 2015 at 17:00 | comment | added | Peter Mueller | @FedorPetrov: Sorry, my remark was for the general exact cover problem. I do not know about the cases where the sets have a fixed small size. | |
| Oct 26, 2015 at 15:01 | comment | added | Fedor Petrov | @PeterMueller is it NP-complete for $1\times 6$? For $1\times 2$ probably no, as it is a partial case of the perfect matching problem. | |
| Oct 26, 2015 at 14:51 | comment | added | Peter Mueller | @FedorPetrov: I know nothing about the complexity of Knuth's algorithm X which is a straightforward idea to solve exact cover problems by backtracking. However, the exact cover problem is NP complete, so this algorithm certainly works only for not too big problems. | |
| Oct 26, 2015 at 12:51 | comment | added | polyanom | @PeterMueller: Wow!!! | |
| Oct 26, 2015 at 12:50 | comment | added | Fedor Petrov | Oh, I am impressed that this is not computationally hopeless. 349 squares, 49 tiles, so many variants to put them! What is general complexity of the algorithm? | |
| Oct 26, 2015 at 12:44 | vote | accept | polyanom | ||
| Oct 26, 2015 at 12:38 | vote | accept | polyanom | ||
| Oct 26, 2015 at 12:39 | |||||
| Oct 26, 2015 at 12:18 | comment | added | Peter Mueller | @Fedor Petrov: Just by brute force checking whether there is an exact cover. For $n=7$ Knuth's program took 8 seconds, while it took several hours for $n=11$ until it started to through out some solutions. | |
| Oct 26, 2015 at 12:02 | comment | added | Fedor Petrov | How do you prove that there are no tilings for $n=7$? | |
| Oct 26, 2015 at 11:55 | history | answered | Peter Mueller | CC BY-SA 3.0 |