This blog post talks about the Talos Principle puzzle solver I wrote to help solve the Sigil puzzles.
The game “The Talos Principle” has points where you need to place a series of Tetris pieces, called sigils in the game, onto a puzzle board to move onto the next area. Some of the smaller boards requiring less sigils are easier, but the larger ones can take considerable time to complete.
So, instead of doing it manually I coded up a brute force solution which will attempt every single possible solution until it finds a working one.
In the above image you can see the current interface. First the width and height is typed up and then each Tetris piece is added to the list by pressing the blue buttons.
Once entered, pressing the solve button will either draw a grid below as shown or display that it cannot solve the puzzle.
Pressing reset will allow entering a new set of pieces.
To start with, an empty board is created with all the sigils added as possible pieces to place. This creates the first board state.
Then until it finds a solution it will take a board state object from the list and perform the following operations:
Takes the next sigil to place, and then finds every location that the sigil could be placed. (This also takes into account some sigils have one, two or four rotations.
Once it finds every location that it can be placed it creates a new state for every placement
If that placement has placed all pieces, it will be returned as a finished board
If no more sigils can be placed then it ignores that state, and continues to the next one
This continues until it no longer has any more attempts, or it has found an instance that works.
The basic web application has been added on my website here. Please note the code isn’t cleaned up, or commented well as I threw this together. These improvements are planned for the future.
What can be done to speed it up
There are a couple of logic checks that can be made to speed up the calculations. These will probably be added in the future as for larger puzzles this solver is quite slow.
Ignoring solutions that have impossible gaps
Every Tetris piece that is to be placed is 4 connected squares.
This means that for any hole in the puzzle to be filled it must be a multiple of four squares. This means that if there is a hole in the puzzle with only three squares, no piece will be able to be placed to fill it.
This means that if any puzzle state has a hole that is not a multiple of four it will be invalid. These could be checked as they are generated and the invalid states removed.
Smart corner placement
All these puzzles are a rectangle which means that there must always be a piece in each of the corners.
By creating a set of states with every possible combination of corner pieces it should reduce the state space to brute force. This is because you know that one of the generated state spaces must be correct as each corner must be filled.
This will likely cause a number of states of quickly be found as invalid and will speed up the state space checking.
Using a web worker to perform the checking
This means that for larger puzzles it locks up the page and may appear unresponsive.
Using a WebWorker to calculate the maths would stop it slowing down the UI. In addition while it is running it will be relatively easy to show the progress of the computation.
Converting the Web Worker to WebAssembly
WebAssembly allows you to write code in a lower level language and compile it to run in the browser. This has advantages as it allows more control over the memory and runtime of the application.
Therefore rewriting the computation into a lower level language and compiling it into WebAssembly may speed up the calculations.
However it is not supported in all browsers so potentially it will need a fallback method, possibly to a Web Worker
Summary of Solver
This solver can help you solve the sigil puzzles in “The Talos Principle”. It still needs some work but as a basic solver it works quite well.
The future plans are to speed it up and document it better so people can see how it works.