| You are given an 8 x 8 chessboard, and you must place the minimum possible number of queens onto the board such that all cells are under attack from at least one queen, and no queens attack each other. Some of the cells on the board are destroyed. A queen cannot be placed on a destroyed cell, and destroyed cells don't need to be under attack. A queen attacks a cell if it is in the same row, same column, or same diagonal as that cell (even if there are destroyed cells between them). Rows are labelled from 1 to 8 and columns from 'A' to 'H'.
You are given a String[] board, where the jth character of the ith element represents the cell at row i, column j. A '.' denotes an empty cell, and a '#' denotes a destroyed cell. A solution is represented by a string which concatenates the positions of the queens. Each queen will be represented by two characters rc, where r is the row label and c is the column label. For example, if the solution contains one queen at row 1, column H and another at row 5, column C, it can be represented as "1H5C" or "5C1H". If there are several solutions which use the minimal number of queens, return the one that comes first lexicographically. |