Construct a Turing Machine that solves the n-queen problem. The problem is stated as follows:
Given a n x n chessboard, how can n queens be placed on the chessboard so that all the queens are unable to attack each other?

Initial condition

The border of the chessboard is marked with #-symbols and the read/write-head is on the rightmost queen ("1").
The queens fullfill the following criteria:


possible initial conditions

Final condition

The Turing Machine finds the next valid solution.

If there is no possible placing of the n queens the Turing Machine stops on an empty chessboard.