The Turing Machine solves the problem by using backtracking.
At first the Turing Machine has to decide if it has been started on a partial solution, this is done in the states "Search" and "Complete?".
Whenever it places a queen on the chessboard it hast to make sure, that the new queen cannot attack any previously placed queen. Since the Turing Machine works from left to right, all previously placed queens are on the left side. More precisely the Turing Machine has to assert that there is no other queen:
The three different "lines" that have to be checked.
If there is a queen attacking the newly placed one, the Turing Machine starts to backtrack (state "Backtrack"). If there is no such queen, the Turing Machine tries to place the next queen (states "Next" and "Search")
Contributions by Wang Zirui and Toh Kaiyang from the National University of Singapore (NUS).