N-Queens
Hard · Backtracking · about 30 minutes
Asked at Amazon, Microsoft, Apple.
Place n queens on an n × n chessboard so that no two attack each other (no shared row, column or diagonal). Return every distinct solution, each as a board of n strings where 'Q' marks a queen and '.' an empty square. The solutions may be in any order.