Try, check, undo, try again — see recursion think.
Place queens that cannot attack each other
O(N!) worst case→
Generate a maze, then solve it with DFS, BFS or A*
O(cells)→
Fill, check, undo
O(9^m) worst case (m = empty cells)→