Минимум ферзей, необходимых для покрытия всех полей шахматной доски

Опубликовано: 16 Января, 2022

Учитывая размер шахматной доски (N x M), определите минимальное количество ферзей, необходимое для покрытия всех квадратов доски. Ферзь может атаковать любую клетку в своем ряду, столбце или диагоналях.

Примеры:

Ввод: N = 8, M = 8
Выход: 5
Макет: QXXXXXXXXXQXXXXXXXXXQ XXXXQXXXXXXXXXQXXXXXX XXXXXXXXXXXXXXXXXXXXX X 

Ввод: N = 3, M = 5.
Выход: 2
Макет: QXXXXXXXXXXXXQX

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

В этой статье делается попытка решить проблему очень простым способом без особой оптимизации.

Step 1: Starting from any corner square of the board, find an ‘uncovered’ square (Uncovered square is a square which isn’t attacked by any of the queens already placed). If none found, goto Step 4.
Step 2: Place a Queen on this square and increment variable ‘count’ by 1.
Step 3: Repeat step 1.
Step 4: Now, you’ve got a layout where every square is covered. Therefore, the value of ‘count’ can be the answer. However, you might be able to do better, as there might exist a better layout with lesser number of queens. So, store this ‘count’ as the best value till now and proceed to find a better solution.
Step 5: Remove the last queen placed and place it in the next ‘uncovered’ cell.
Step 6: Proceed recursively and try out all the possible layouts. Finally, the one with the least number of queens is the answer.

Для лучшего понимания запустите следующий код.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.