Изо всех сил, чтобы сделать алгоритм для создания доски для головоломки

Question

Я собираюсь сделать головоломку с цифрами.Ради вопроса, скажем, доска является сеткой, состоящей из 4 х 4 квадратов.(В реальной игре-головоломке это число будет 1..15)

Число может встречаться только один раз в каждом столбце и один раз в каждом ряду, немного похоже на судоку, но без «квадратов».

Действительный:

[1, 2, 3, 4
2, 3, 4, 1
3, 4, 1, 2
4, 1, 2, 3]

Я не могу придумать алгоритм, который будет последовательно генерировать правильные, случайные nxn доски.

Я пишу это на C #.

Answer 1

Начните с чтения моей серии по алгоритмам раскраски графа:

http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/

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

---

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

Начните с определения областей вашего графика, которые полностью связаны.

Затем измените алгоритм так, чтобы он пытался найти два решения.

Теперь создайте пустой график и установите случайным цветом одну из областей случайным образом. Попробуйте решить график. Были ли два решения? Затем добавьте еще один случайный цвет. Попробуйте снова. Разве не было решений? Затем сделайте резервную копию шага и добавьте другой случайный цвет.

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

Answer 2

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

Answer 3

Похоже, вы хотите сгенерировать равномерно распределенные латинские квадраты .

В этом pdf есть описание метода Джекобсона и Мэтьюса (который был опубликован в другом месте,ссылку на которую можно найти здесь: http://designtheory.org/library/encyc/latinsq/z/)

Или вы можете предварительно сгенерировать их "много" (перед отправкой :-)), сохранить их в файле и случайным образомвыберите один.

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

Answer 4

Я не говорю на C #, но следующий алгоритм должен быть легко переведен.

Связать набор, состоящий из чисел 1..N, с каждой строкой и столбцом:

for i = 1 to N
  row_set[i] = column_set[i] = Set(1 .. N)

Затем выполните один проход по матрице, выбирая запись для каждой позиции случайным образом из набора элементов, действительных в этой строке и столбце.Удалите число, выбранное из соответствующих наборов строк и столбцов.

for r = 1 to N
  for c = 1 to N
    k = RandomChoice( Intersection( column_set[c], row_set[r] ))
    puzzle_board[r, c] = k
    column_set[c] = column_set[c] - k
    row_set[r] = row_set[r] - k
  next c
next r

Answer 5

Не так много комбинаций, которые вам нужно попробовать. Вы всегда можете переставить допустимую доску, чтобы верхний ряд был 1,2,3,4 (путем переназначения символов), а левый столбец - 1,2,3,4 (путем перестановки строк со 2 по 4). В каждом ряду есть только 6 перестановок оставшихся 3 символов, так что вы можете переключаться между ними, чтобы найти, какая из 216 возможных досок действительна. Вы также можете хранить действительные.

Затем выберите правильную доску случайным образом, случайным образом измените ряды и случайным образом переназначьте символы.

Answer 6

Еще одним решением было бы это. Предположим, у вас есть ряд решений. Для каждого из них вы можете сгенерировать новое решение, просто переставив идентификаторы (1..15). Эти новые решения, конечно, логически одинаковы, но для игрока они будут казаться разными.

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

Answer 7

Используйте ваш первый действительный пример:

1 2 3 4 
2 3 4 1
3 4 1 2
4 1 2 3

Затем создайте случайным образом 2 перестановки {1, 2, 3, 4}.

Используйте первую для перестановки строк, а затем вторую для перестановки столбцов.

Вы можете найти несколько способов создания перестановок в книге Кнута Искусство компьютерного программирования (TAOCP) , том 4, глава 2, Генерация всех кортежей и перестановок (2005), v + 128pp. ISBN 0-201-85393-0.

Если вы не можете найти копию в библиотеке, препринт (той части, которая обсуждает перестановки) доступен на его сайте: asc2b.ps.gz

---

РЕДАКТИРОВАТЬ - ИСПРАВЛЕНИЕ

Приведенное выше решение аналогично 500-Intenral Server Error. Но я думаю, что оба не найдут все действительные меры.

Например, они найдут:

1 3 2 4 
3 1 4 2
2 4 1 3
4 2 3 1

но не этот:

1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

Требуется еще один шаг: после перестановки строк и столбцов (используя метод my или 500) создайте еще одну перестановку (назовем ее s3) и используйте ее для перестановки всех чисел в массиве.

s3 = randomPermutation(1 ... n)
for i=1 to n
  for j=1 to n
    array[i,j] = s3( array[i,j] )

Answer 8

Проверьте http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ - у него есть несколько головоломок, которые имеют именно это ограничение (среди прочих).

Answer 9

Судоку без квадратов звучит немного похоже на судоку.:)

http://www.codeproject.com/KB/game/sudoku.aspx

Существует объяснение кода генератора платы, который они там используют.

Answer 10

Самый простой способ, который я могу придумать, - это создать частичную игру и решить ее. Если это не разрешимо, или если это неправильно, сделайте другое. ; -)