?

Log in

No account? Create an account

Предыдущий пост Поделиться Следующий пост
Ферзи и множества
lex_kravetski


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

Иными словами, никакие два ферзя не должны находиться на одной горизонтали, вертикали или диагонали — именно так ведь ходит ферзь.

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

Но и с перебором тоже не всё так очевидно. Особенно если обобщить задачу до «найти все способы размещения любого количества ферзей на доске» — ну, так, чтобы размещения одного ферзя, двух ферзей и даже ста ферзей, если такое каким-то чудом получится, тоже вошло бы в ответ.

Казалось бы, а чего тут такого? 1 — есть на этом поле ферзь, 0 — нет ферзя. Переберём все варианты, для каждого проверим, не бьют ли какие-то ферзи друг друга…


Читать целиком



  • 1
В линейной алгебре такая задача эквивалентна тому, чтобы найти такой вид неособой матрицы размера 8х8, в которой все индескы элементов не равны и не кратны(т.е. не находятся на диагоналях). Только зачем?

Мне нужно было, чтобы придумать, как плитку уложить.

в некоторый момент момент Остапа понесло

В некоторый момент (ну примерно когда ты начинаешь говорить о бОльшей общности или большей эффективности data-flow (aka functional programming) реализации) ты начинаешь воевать с соломенным чучелом.

1.
>> Вдобавок данная реализация подходит для любых фигур, а не только для ферзей — надо только лишь при запуске процесса передать в него другую функцию фильтрации полей.
Извини, но это просто очень близко к явному надувательству людей, которые не зная программирования могут читать твою статью. Любая боле-менее нормальная реализация также будет предполагать "исключение неправильных точек" (т.е. тех, которые фигура бьёт)


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

В большинстве "классических" реализаций будет делаться ровно то же самое:
1. перебираться все свободные клетки.
2. Ставиться фигура
3. Исключаться клетка с фигурой и все клетки, которые она бьёт
4. Переход к постановке следующей фигуры.

Другое дело, что в языке без замыканий (например pure C -- у нас что-нибудь есть без замыканий ещё?) это будет делаться не очень красиво, через рекурсию и указатель на функцию.

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

Re: в некоторый момент момент Остапа понесло

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

У Вирта, видимо, ненормальная реализация.

Или ты не понимаешь смысл мной сказанного.


> В большинстве "классических" реализаций будет делаться ровно то же самое:

Да, не понимаешь.

>> Или ты не понимаешь смысл мной сказанного.
>> Да, не понимаешь.
Лекс ты бронзоветь начинаешь ))
Сам спросил, сам ответил (только вот аргументы привести забыл).

Решение Вирта 1976го года, по современным меркам действительно безобразное (что тому причиной: нехватка времени, не очень подходящий инструмент или неразвитость самого переборного метода -- я не знаю, наверное всё одновременно).

И лучше всего подходит для того, чтобы использовать его как "чучело для битья".




Re: в некоторый момент момент Остапа понесло

С-шник для доски 8х8 взял бы битовые маски для отображения поля побития фигуры и их комбинаций.
Так же легко проверяются пересечения оных.
Конечно, нужно что-то вроде эффективного map для кеширования комбинаций расстановок и их полей покрытия для сокращения переборов.

Re: в некоторый момент момент Остапа понесло

> С-шник для доски 8х8 взял бы битовые маски для отображения поля побития фигуры и их комбинаций.

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

Что называется стоя на одной ноге подведу итог нашей беседы с Лексом с формальной стороны (* а было бы интереснее с содержательной). Т.к. на мой взгляд в каждой из значимых подветок диалога я получил в итоге некорректное требование или утверждение.


В начале мне резануло глаз, что берётся решение 1976 года Вирта и используется как "соломенное чучело".
Собственно говоря сегодня "любой нормальный мат-школьник" взяв эту задачу с нуля начнёт писать что-то похожее на решение Лекса -- заводим доску, ставим в свободную клетку ферзя, запрещаем его клетку и всё что он бьёт -> го в рекурсию
Перейдёт ли он к "частностям" и решению Вирта или "к общностям" и решению Лекса -- я не знаю. Но "общее" правило таково -- заведи правильную структуру данных и решение у тебя в кармане.

Лекс: >> Парадокс в том, что эта реализация, внезапно, быстрее, чем большинство простых «классических».
Я: >> Извини, но это просто очень близко к явному надувательству людей, которые не зная программирования могут читать твою статью. Любая боле-менее нормальная реализация также будет предполагать "исключение неправильных точек" (т.е. тех, которые фигура бьёт)
Я написал, возможно не расставив все реверансы что это не так. Но я действительно считаю что содержательная сторона вопроса (особенно в местах которые могут почитать плохо разбирающие люди со стороны ! ) куда важнее формы с которой указывается на такого рода неточности.

В ответ получил желание разговаривать "по форме", а также что должен привести:
а) Это самое "лучше" решение
б) Статистику распространённости разных видов решений.

Собственно с точки зрения "формальности":
- Решение Вирта идет единственный ответ.
- Существует решение, ищущее единственный ответ за линейное время (кроме размерностей доски 2*2 и 3*3 где решений нет) расставив 2 "лесенки" из ферзей-- это ответ на вопрос "а".
- Сам Лекс задаёт уровень строгости в своей статье, без статистики просто из головы пишет "большинство решений" -- это значит что он не имеет права требовать от других более формального подхода.

Собственно всё. Все претензии "по форме" (и исключительно по форме, по содержанию там на самом деле есть что обсуждать) выполнены: существует более быстрое решение чем Вирта за линейное время; комментатору надо подтверждать слово "большинство" статистикой тогда и только тогда, когда в самой статье автор делает то же самое.



*) А вот по содержанию там есть о чём поговорить (что изначально я и собирался сделать): как бы писали такую задачу олимпиадники (субьективно с моей точки зрения) 20 и 10 лет назад и почему от решения 10 летней давности до его решения ровно один шаг, но тем не менее шаг весьма значительный.
В чём существенное преимущество (и я бы даже сказал новаторство) его подхода, в чём -- некоторые проблемы
Какие есть задачи, которые хуже ложатся на data-flow (declarative / functional programing elements) подход -- причём тоже с моей стороны, примере двух последних решённых мною "для разминки мозгов" задачек и т.д.
.......
Собственно тема существенно интереснее, чем "ловить друг-друга на слове".

> Сам Лекс задаёт уровень строгости в своей статье, без статистики просто из головы пишет "большинство решений" -- это значит что он не имеет права требовать от других более формального подхода.

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

> Собственно говоря сегодня "любой нормальный мат-школьник" взяв эту задачу с нуля начнёт писать что-то похожее на решение Лекса -- заводим доску, ставим в свободную клетку ферзя, запрещаем его клетку и всё что он бьёт -> го в рекурсию

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

P.S. Не претендуя на "сбор статистики", вот первая ссылка из гугла про восемь ферзей на Питоне: https://solarianprogrammer.com/2017/11/20/eight-queens-puzzle-python/
Вроде те же циклы, за которые нормальные мат. школьники обоссут. Я еще три рез-та по Питону глянул и один на Java. Даже если там укрылось решение идентичное приведенному Лексом в статье, оно так люто просасывает по читаемости, что я приписал его к плохим.

Это всё не катит. Ты говоришь по-существу, а Лекс прежде чем говорить по-существу выдвинул условия.
Как оказалось первое условие он в дальнейшем поменял, второму (по уровню строгости) не соответствует его собственная статья.

ПС
Но делать второй заход на обсуждение по форме я не хочу, если интересно "по делу", то давай (но видимо уже не раньше чем завтра, сегодня ещё пара дел есть).

Прочитал начало статьи и попробовал решить на Скале задачу расстановки n ферзей — так, чтобы без счётчиков циклов и без рекурсий.
Получилось вот что:

object Queens {
  val board = for(x <- 1 to 8; y <- 1 to 8) yield (x, y)
 
  // Все варианты расстановки нуля ферзей.
  val zeroQueens = Set((Set.empty[(Int, Int)], board.toSet))
 
  def placeQueens(numberOfQueens: Int) = (1 to numberOfQueens).foldLeft(zeroQueens) {
    (variants, _=>
      variants.flatMap { case(queens, freeCells) => oneMoreQueen(queens, freeCells) }
  }.map(_._1)
 
  // queens — вариант расстановки ферзей
  // freeCells — клетки, которые не атакуются этими ферзями
  // результат функции — все варианты добавления ещё одного ферзя к указанным (точнее, все пары <возможный вариант; клетки, не атакуемые этим вариантом> )
  def oneMoreQueen(queens: Set[(Int, Int)], freeCells: Set[(Int, Int)]) = freeCells.map {
    newQueen => (
      queens + newQueen,
      freeCells filterNot (isAttacked(_, newQueen))
    )
  }
 
  def isAttacked(cell: (Int, Int), queen: (Int, Int)) = (cell, queen) match {
    case((x, y), (i, j)) => i == x || j == y || i + j == x + y || i - j == x - y
  }
 
  def main(args: Array[String]): Unit = {
    placeQueens(8) foreach println
  }
}

В целом почти верно, но есть нюансы:

1. В решении захардкожен размер доски. Впрочем, это легко исправляется.

2. (1 to numberOfQueens) предполагает, что именно такое количество ферзей обязательно может быть расставлено на доске. Однако с ним вполне можно не угадать. Особенно на неквадратных досках.

Я не программист и большую часть статьи, к сожалению, не понял. Однако, в шахматы играю с детства и головоломку эту решал ещё в 80-х, без компьютера. Перебор был оптимизирован следующим образом: задача решалась для доски 4 на 4, затем следовало безуспешно попытаться расставить ещё четырёх ферзей на оставшихся небитыми полях. Это позволяло понять, какой из первых четырёх ферзей мешает больше всего и передвинуть его. Сейчас я нашёл решение минут за 10, в уме, на доске только проверил; школьником, помнится, потратил пару часов, рисуя точки на тетрадных клетках. И да, повороты и зеркальные отражения, за счёт которых можно найти максимум решений. Наверное, этот алгоритм можно изложить языком программирования, хотя, формализовать понятие "мешает", конечно, не так просто...

По мне, так сразу очевидно, что у нас ферзи должны быть по одной штуке в каждой строке и каждом столбце. Для 8 ферзей и стандартной доски 8 на входе имеем 8 строк, в каждой из которых ферзи стоят в разных клетках от 1-й до 8-й. Наша задача — расположить эти строки по вертикали, это число перестановок 8 элементов, 8!, всего лишь 40320 случаев.

  • 1