A fast 16x16 TetraVex solver | Hacker News Reader

A fast 16x16 TetraVex solver

16x16tetravex.xyz

21 pointsgthulhu10 comments

my school server redirected me because "the site you are trying to enter is infected with malware."

I would never do that.

but did you win ?

Oh no (alas). This solver only works with TetraVex-type puzzles, that is puzzles for which you cannot rotate the pieces. My algorithm only permutes the pieces, like a 256-card deck. But if someone finds a way to transform the Eternity II puzzle to a TetraVex (the hardest part, IMO), then a solution can be found with this program... in the blink of an eye. ;)

How does it work?

Right now: it works badly with a lot of users at the same time (it solves puzzles generated by other people...). I will then have to deactivate it very (very) soon in order to fix this issue.

In general: I explain the outlines of the way it works on this page (http://www.lthr.xyz/programming/13/6/2015/eternity-ii-solver...). This is the technical aspect. But because not everyone likes the technical details, I wrote a parable on this very subject (Theseus, Penepos [a name I created to anthropomorphize P?=NP {PeNePos}], and the Eternal Labyrinth: http://www.lthr.xyz/blog/7/6/2015/theseus-penepos-and-the-et...). This is a core aspect of my project.

You will probably think that I am crazy, but my goal with my program is to simulate, as subtly as possible, the idea that Penepos symbolizes.

But wait, TetraVex puzzles are NP-complete (http://www.sciencedirect.com/science/article/pii/S0020019006...), and my algorithm solves large ones almost as fast it is possible to check them, so maybe Penepos is not just a fantasy... (You may understand with this sentence that I am a strong believer that P = NP).

So it is backtracking with pruning? You write that it is sub exponential, what is the running time?

A specific and very efficient pruning yes.

I have updated my algorithm (when I worked on the step-by-step visualization process, I realized that sometimes it was doing worthless extra steps), then it is faster than the first version. The new version is online. You can also upload your own puzzles now.

For 16x16 TetraVex puzzles with 23 different colors, it takes, for about 80% of them, less than 10 milliseconds on a regular computer with no parallelization (I use two instances: one on a Surface Pro 3 and another on a EC2 t2.micro).

For the others, it takes about 100 to 200 milliseconds to solve.

Then, IMO, it takes 'almost' the same time to generate a solution than to check it.

I sure seems very fast. I'm just wondering if you know anything about how fast it would be on a worst-case NxN board? When you write 'sub exponential', do you mean that literally? Or do you just mean that it seems fast?

Hi. Sorry for the late reply: I do not check often this account. Feel free to contact me via the contact page (where my email address is displayed) on my website to ask me any question!

Reply on news.ycombinator.com