Как лучше всего положить 20 фигур на шахматной доске в случайных местах?

Question

Идея, которую мне нужно было решить, это создать буфер размером 8x8, заполнить его указателями на мои шашки (все 20 из них), а остальные оставить 0 (ноль), затем запустить алгоритм перетасовки в буфере, и это все (просто прочитайте его как массив 8x8)

1. Мне было интересно, есть ли лучший способ сделать это.
2. Мне нужно написать это на C #, и мое предложение не будет работать так, как я его описал

кто-нибудь?

Answer 1

В дополнение к идее Борцио, когда вы приближаетесь к двадцатой части, есть шанс 1 в 3, что вам придется заново сгенерировать случайное число и попробовать еще раз. С 20 фигурами вы, вероятно, все еще в безопасности, но если бы у вас было, скажем, 40 штук, был бы лучший шанс, чем 1 к 2, и вы могли бы застрять в ожидании.

1. Создайте массив плат, все пустые.
2. Скопировать ссылку на каждый квадрат доски в список (emptySquareList).
3. Петля для каждой фигуры, которую вы хотите добавить:
   1. Генерирует случайное число между 0 и emptySquareList.Length-1.
   2. Поместите фигуру в этот квадрат
   3. Уберите квадрат из emptySquareList.

Таким образом, вы всегда ведете список пустых квадратов и выбираете из них. Обратите внимание, что массив индексов в массиве вашей доски работает так же хорошо и может быть быстрее (Enumerable.Range(0,64)).

Я рекомендую вам поэкспериментировать с алгоритмом случайного выбора и проверки, а также с этим; посмотрите, какой из них более эффективен.

Answer 2

Чтобы ответить на поставленный вопрос:

1. Поместите первую шахматную фигуру в случайное место, которое еще не занято
2. Повторите для остальных 19 штук

Серьезно, вы не дали нам достаточно информации, чтобы вообще ответить на этот вопрос. Вот несколько вопросов:

• Какие шахматные фигуры?
• Какие цвета (их по 16) и имеет ли значение цвет? Должны ли белые быть в плену у черных и наоборот?

При условии, что нет никаких правил, за исключением того, что вам нужно разместить все 20 на доске, т.е. без столкновений, это будет делать то, что вы хотите:

Piece[] pieces = ... your 20 pieces here
Piece[] board = new Piece[8 * 8];
Random r = new Random();
foreach (Piece piece in pieces)
{
    while (true)
    {
        Int32 location = r.Next(board.Length);
        if (board[location] == null)
        {
            board[location] = piece;
            break;
        }
    }
}

Более простое решение, при условии, что у вас уже есть вспомогательные подпрограммы, заключалось бы в том, чтобы просто поместить их в начало массива из 64 элементов, а затем перемешать весь массив. Это перетасует эти 20 частей и 44 пустых квадрата вокруг, и эффективно разместит их в случайных местах.

Answer 3

Если вам нужно следовать правилам размещения, учитывая ваш пример матрицы 8x8, я бы также счел это массивом 1d, как указал Эван - (см. Его математику для определения x & y) -

Черные и белые квадраты являются нечетными и четными значениями индекса; Но, эй, вы никогда не говорили, что вам нужны правила размещения - я также предполагаю, что вы ищете не код на C #, а больше идей на «логическом» уровне ...

Если вы пытаетесь найти решение Linq-Challenged, учтите следующее:

1. Создайте массив "board", все пустые; (64 элемента)
2. Создайте массив "игровых фигур", состоящий из ваших фигур
3. Создать цикл от 1 до # штук
4. Генерация случайного числа от 1 до # пробелов на доске (64)
5. Если пространство на доске, на которое указывает # 4, равно! 0, повторите шаг 4 (или вы можете «пока»! 0)
6. Поместите кусок (# из цикла в шаге 3) в квадрат X из шага 4

Только одна идея, которой наверняка будет много -

Надеюсь, это поможет ...

Answer 4

Матрица 8x8, которая содержит либо указатели (c ++) для разбиения объектов, либо ссылки (c # / java), выглядит очень разумным дизайном.

Вы можете использовать одномерный массив размером 64 элемента (вы можете легко отобразить двумерные индексы в одномерный массив) и использовать что-то вроде этого:

using System;
using System.Linq;

Piece[] board = whatever();

// New random number generator.
Random random = new Random();

// LINQ query orders each element by the next random number.
Piece[] randomBoard = (from piece in board
    orderby random.Next()
    select piece).ToArray();

ПРИМЕЧАНИЕ: я не программист на c #, но это кажется разумным.

Чтобы преобразовать пару x, y в индекс массива, используйте этот алгоритм:

int index = (y * 8) + x;

ПРИМЕЧАНИЕ2: Я не знаю, нужно ли вам соблюдать правила размещения шашек или нет, если вам нужно, нужно сделать что-то более умное. Вы могли бы иметь массив размером 32 элемента (представляющий все черные квадраты). Перемешайте в этом, затем назначьте каждый элемент в большом 32 массиве каждому «черному» квадрату реального массива из 64 элементов.