Все комбинации шахматной игры 2d array

Question

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

Я назову любой набор позиций для слонов и королев на доске:сочетание.Комбинация считается решением, если все квадраты атакованы (проблема доминирования в шахматах).

Так, например, если пользователь дает 1 Королеву и 3 Епископа на шахматной доске 5x5, возможное решение может быть:

- - B - -
- - - - -
- B Q B -
- - - - -
- - - - -

Теперь у меня проблемы с созданием программы, которая находит все возможные позиции заданного набора фигур, без дубликатов.Дубликаты могут возникать, потому что пользователь может указать несколько епископов, например.Решение должно быть рекурсивным.

Answer 1

Вы не показываете свое текущее решение, но я / предполагаю / вы выбираете каждый квадрат для первого куска, затем выбираете каждый квадрат для второго куска и продолжаете, если этот квадрат еще не занят.Затем повторите для третьего и т. Д.

Если первый и второй фрагмент одного типа, то это приведет к дублированию.Первая фигура в первой позиции, вторая во второй против первой во второй позиции, вторая в первой.

Если у вас есть две фигуры одинакового типа, вы можете просто наложить порядок на позиционирование второй фигуры: неПоместите второй идентичный кусок с более низким индексом, чем первый.Это позволяет избежать дублирования, но все равно посещает каждую перестановку позиций.Вы можете наложить этот порядок на более одинаковые типы частей.

Когда у вас есть другой тип фигуры, два порядка становятся разными.Если первый и второй являются разными типами элементов, то первый элемент в первой позиции, второй во второй по сравнению с первым во второй позиции, второй в первом - это отдельные случаи.Однако, когда вы опускаете второй экземпляр нового типа, вы можете применить правило упорядочения к первому.

[В качестве альтернативы вы можете настаивать на том, чтобы второй фрагмент был помещен перед первым фрагментом - результатто же самое]

В качестве второй оптимизации вы можете заметить, что если у вас есть 3 слона, а третий должен быть расположен после двух других, то первый не может быть помещен в последний или предпоследний квадрат, поэтому выможет оптимизировать ваше размещение первого очень немного.

Это становится более сложным, когда это фигура второго типа, и, возможно, это не стоит делать.

Третья оптимизация - сохранить список доступных квадратов.После того, как кусок положен, его квадрат удаляется из списка, поэтому список для размещения следующего фрагмента короче, и вам не нужно «проваливаться», когда вы пытаетесь поставить королеву поверх слона, так какты не попробуешь.Вы можете использовать длину этого списка, чтобы упростить вторую оптимизацию.

Вы можете сделать несколько хитрых трюков с std :: list :: splice, чтобы означать, что вы не перераспределяете или дублируете этот список, когда просматриваете части и позиции.