Алгоритм, чтобы узнать все возможные позиции

Question

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

Например, в шахматном пронумерованных как декартовы системы координат, любая часть будет находиться в положении

(x,y) where 1 <= x <= 8 and 1 <= y <= 8 

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

for(int i = 0; i<= 8; i++){ 
    for(int j = 0; j<= 8; j++){ 
     System.out.println("Position: x:"+i+", y:"+j); 
    } 
} 

Как я могу получить хороший АЛГОРИТМ, чтобы найти все позиции Возможных частей в шахматной доске?

Спасибо.

Answer 1

У вас есть доска 8x8, поэтому общая сумма составляет 64 квадрата.
Заполните список, содержащий эти 64 sqaures [пусть это будет list], и найдите все возможности recursively: каждый шаг «угадает» одну точку и вызовет рекурсивный вызов, чтобы найти другие точки.

Псевдо код:

choose(list,numPieces,sol): 
    if (sol.length == numPieces): //base clause: print the possible solution 
     print sol 
     return 
    for each point in list: 
     sol.append(point) //append the point to the end of sol 
     list.remove(point) 
     choose(list,numPieces,sol) //recursive call 
     list.add(point) //clean up environment before next recursive call 
     sol.removeLast() 

вызова с choose(list,numPieces,[]) где list является предварительно заполняется список с 64 элементов, и numPieces это кусочки вы собираетесь разместить.

Примечание: Это решение предполагает куски не идентичны, поэтому [(1,2),(2,1)] и [(2,1),(1,2)] оба хорошие различные решения.

EDIT:
Просто слово о сложности, так как есть (n^2)!/(n^2-k)! возможные решения вашей проблемы - и вы ищете для всех из них, любой алгоритм будет страдать от экспоненциального времени выполнения, таким образом пытаясь вызвать его всего 10 штук, займет ~ 400 лет
[в приведенных выше обозначениях n ширина и длина доски, и k является количество штук]

Answer 2

Вы можете использовать рекурсивный алгоритм для генерации всех идей!:

void combine(String instr, StringBuffer outstr, int index) 
{ 
    for (int i = index; i < instr.length(); i++) 
    { 
     outstr.append(instr.charAt(i)); 
     System.out.println(outstr); 
     combine(instr, outstr, i + 1); 
     outstr.deleteCharAt(outstr.length() - 1); 
    } 
} 

комбайн ("abc", новый StringBuffer(), 0);

Answer 3

Как я понимаю, вы должны подумать, что может возникнуть какая-то firgure, блокирующая некоторое потенциальное положение для фигур, которые могут дотянуться до них на пустой доске. Думаю, это самая сложная часть. Итак, вы должны построить несколько наборов вершин (множество состояний доски), которые достигаются из некоторой одной вершины (начальное состояние платы).

Первый алгоритм, который приходит на ум:

Предпосылки:

• фигуры Заказ в некотором роде, чтобы сформировать круг.
• Предположим, что начальный набор состояний платы (S0) содержит один элемент, который представляет состояние встроенной платы.

Действия

1. Выбрать следующий рисунок для простираются набор возможных позиций
2. Для каждого состояния платы в S (п) прогулка по глубине первых все возможные движения, новые состояния доски и назвать его F (n) (кадр).
3. Форма S (n + 1) = S (n) ∪ F (n).
4. Повторите шаги, пока все кадры обновлений во время прохождения всего круга не будут пустыми.

Это вид смешивания дыхания первой и поиска в глубину