News for hackers. Stuff that matters.

gthulhu

gthulhu on Hacker News

Re:A fast 16x16 TetraVex solver on Wednesday September 23, 2015 @05:15PM (#10268290)
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!
Re:A fast 16x16 TetraVex solver on Tuesday September 22, 2015 @11:46AM (#10259321)
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.

16x16 TetraVex Solver updated (step-by-step visualization)

Posted by gthulhu on Monday September 21, 2015 @05:24PM
from the self-post dept.

Hi everyone!I have updated the solver I presented to you yesterday (16x16tetravex.xyz).- Now it is able to produce a step-by-step visualization of the solving process. For this purpose, click on [Solve (step-by-step)];- Today, during the conception of this step-by-step solution, I realized that my solver was in fact looking for ALL the solutions instead of one. I have corrected this issue: it...

( Read More... | no comments | on HN )
Re:A fast 16x16 TetraVex solver on Monday September 21, 2015 @07:42AM (#10251571)
I would never do that.
Re:A fast 16x16 TetraVex solver on Sunday September 20, 2015 @04:59PM (#10249092)
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).

Re:A fast 16x16 TetraVex solver on Sunday September 20, 2015 @04:29PM (#10248946)
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. ;)