Euclidea – Geometric construction game with straightedge and compass

I am intrigued by this as well. I think they check for the existence of certain primitives and a sequence in which they are drawn. For example for level 1.1 where you need the 60 degree angle, if you use Explorer mode to view the solution and then you draw a "cheated" line on top of it, it won't give you a completed level because you don't have the sequence (2 circles and an intersection point). It also doesn't allow you to draw another line on top of an existing line, so you'd have to restart the level in this case.

My guess is that it uses analytical geometry to compute the equations of the drawn items. This also may includes a mapping to some canonical dimension(size) and orientation(rotations).

My cursory analysis suggests that there are hidden constructions invisible in the game but used for the verification (you can see a base64-encoded task file flying through the network). The actual verification happens in an Emscripten-powered C++ engine and it is pretty opaque to me---the only thing I can identify is a parser for the task file.

My best guess without the actual source code is as follows: The perfect algorithm would involve the equality between two functions returning constructible numbers [1], where each function would map from unspecified points (that you can move around with the hand tool) to the result points. As far as I concerned comparing two constructible numbers is possible but inefficient [2], and comparing two functions is probably much harder. However for the purpose of game, we can approximate the equality by randomly evaluating a difference between two functions to the reasonable accuracy and checking if it is close to zero. Theoretically exact real arithmetic would be preferable, but adaptive fixed-precision real arithmetic may be also possible as long as rounding errors are tracked.

[1] https://en.wikipedia.org/wiki/Constructible_number

[2] https://mathoverflow.net/a/211556

As others in the thread have pointed out, Euclidean geometry is decidable, but the proof of that fact corresponds to a highly inefficient algorithm for actually checking whether two points are equal.

An alternative approach would be to "cheat" and do a numeric approximation. Constructible numbers (the coordinates of any point the player can make) are always the solution to a quadratic equation whose coefficients have been previously constructed. So, especially for constructions that aren't very "deep" (as would be found in this game), we can easily find the decimal approximation to high precision very quickly. In no time at all, this approach can determine with high confidence that the player's solution and a prototype solution are probably the same.

I would speculate that constructing a near-miss that is falsely deemed correct by this method would require an inordinately complex construction.

I know of two other mathy game apps: Torus games (games like tic tac toe on a torus, Klein bottle etc.) and Pythagorea (which is about geometry)

What’s the logic game? I’d also love to find more games like these for my kids (they love playing with Euclidea, but it’s too abstract for them to grasp).

Another one they do manage to understand (and love) is Lightbot http://lightbot.com

DragonBox Algebra is tons of fun.

Came here to post this — it's one of my favourite math games.

For a really nice introduction to the more advanced uses of geometric algebra in three dimensions, there's this fantastic chapter in a book by Rudy Rucker, which you can read here: http://www.rudyrucker.com/infinityandthemind/#calibre_link-3...

The solution will rattle you! At least it did me. I happened to blindly stumble upon it while trying various approaches, but I’d love to know what sort of intuition it takes to find the solution short of brute-forcing/lucky-guessing it.

Try a stucktrace :)

In case you eventually give up - as I just did - or somebody else is interested, here [1] ist the solution. It is definitely not a straight forward construction.

[1] https://math.stackexchange.com/questions/1587861/inscribing-...

The box with the blue arrow to the right does that.

It's not open source from the looks of it. It's a freemium game, they have in-app purchases on mobile where you can unlock all levels without completing the previous ones. Some of those levels are insanely difficult, so you have to either lookup the solutions online or pay for unlocking, otherwise it's pretty much impossible to advance.