powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничная задачка для ума за 1 миллион $
25 сообщений из 491, страница 8 из 20
Пятничная задачка для ума за 1 миллион $
    #39518275
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tip78кстати, зеркалирование доски рассматривали? оно теоретически ускоряет в 4 раза скорость перебора
т.е. каждая доска это 4 разных доски, где паттерн зеркалится во все стороны

нечистые доски не зеркалятся
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518280
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahovtip78кстати, зеркалирование доски рассматривали? оно теоретически ускоряет в 4 раза скорость перебора
т.е. каждая доска это 4 разных доски, где паттерн зеркалится во все стороны

нечистые доски не зеркалятся
чавойта?
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518302
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tip78,

если на доски уже стоят несколько ферзей,
зеркало не поможет, сколько перед ним ни ходи.
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518331
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahovtip78,

если на доски уже стоят несколько ферзей,
зеркало не поможет, сколько перед ним ни ходи.
кстати, вместе с зеркалированием ещё и вращание доски можно устроить... 4 раза
я не понял, почему не поможет, ну стоит там хоть 7 ферзей, разверните доску на 180 по горизонтали и перенесите на новую доску
и по вертикали/диагоналям тоже
потом каждый ход на исходной доске зеркалируется также на остальные 3
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518334
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
по сути надо просто положения ферзей исходные запоминать, от которых идут все остальные ходы
и НЕ делать их же в других зеркальных вариациях
но это всё не избавляет нас от перебора...
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518339
jbond
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
tip78,
у тебя УЖЕ стоят 2 ферзя. они БУДУТ в решении. те перестановки, которые ты будешь генерировать уже должны включать этих ферзей. смысла вращать и зеркалить нет, потому что сдвинешь заданных ферзей
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518448
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Несколько мыслей.

1) Итеративный рекурсивный поиск (ИРП). (та ботва что опубликована в Вики) Работает долго.
Очень долго. Очень-очень. Зато перебирает все варианты. Варианты уникальны.
Никакой доп-проверки не нужно. Рекурсия гарантирует. O(a^x). Экспонента
предположительно.

Плюсы. Гарантировано выдаст все решения.
Минусы. Выдает медленно. Не дождемся в обозримом будущем.

2) Случайный выбор (СВ). Полиномиален по отношению к одной комбинации. Генерирует
неуникальную расстановку. Требуется доп-проверка уникальности. А здесь подвох.
Британские ботаны обещали стартовую расстановку для 1000х1000. Условий больше
нет. Это значит что имеют право поставить 1 ферзя и это будет тоже стартовые условия.
Далее. Алгоритм генерит случайные расстановки. Их надо ГДЕ-ТО хранить. Учитывая
факториальные оценки. Вангую что не хватит никаких баз. Сколько надо места? Петабайт?
Эксабайт? Столько места нет у гугла и амазона. Это первое.

Второе. Даже если мы найдем столько места. Купим хостинг у инопланетян на альфа-центавре.
У них - молекулярные 3д SSD диски.
Тогда нас ждет еще один сюрприз. Тот-же что и постиг копателей биткоинов. Будет замедление
нахождения новых решений. Мы будем делать промахи и попадать в существующие решения.
И наконец когда будет найдено 99.999% последнее решение мы не найдем никогда. В обозримом
будущем. O(x^n). Полином. На старте полином. На финише - тормоз.

Итак.

Плюсы. Со старта начинает выдавать какие-то решения.
Минусы. Хаотичный порядок. Нет системы. Скорость выдачи решения со временем падает.
Требуется платить за хостинг гуманоидам с Центавры. А хостинг у них дорогой.

В обоих случаях у нас нет progress-bar. Тоесть точно не знаем сколько уже накопали а сколько еще впереди.
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518456
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tip78кстати, зеркалирование доски рассматривали? оно теоретически ускоряет в 4 раза скорость перебора
т.е. каждая доска это 4 разных доски, где паттерн зеркалится во все стороны
Да. Давайте 1 раз прокашляем этот вопрос в топике. Чтоб больше к нему не возвращаться.

Для для доски 8х8 существуют только 12 уникальных расстановок. 92 получаются путем
- поворота уникальной доски на 90 градусов.
- отражения горизонтально или вертикально или от диагонали.

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

Зависит от алгоритма. Для рекурсивного - скорее всего не нужно он и так их всех переберет.

Для начальной расстановки - надо проверить что повороты и отражения не нарушают этой расстановки.
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518468
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

зачем вообще возиться с зеркалированием?

Ведь в нашем случае:
1. при поиске всех перестановок зеркалирование не дает выигрыша по времени,
2. никто не спрашивает, сколько уникальных решений было найдено.
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518556
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahov, мы так запутаемся. В топике есть минимум два алгоритма.

О каком алгоритме вы сейчас говорите?
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518578
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonAleksandr Sharahov, мы так запутаемся. В топике есть минимум два алгоритма.

О каком алгоритме вы сейчас говорите?

Мы решаем задачу завершения расстановки ферзей.

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

Даже если окажется, что у полученного решения есть зеркальное, которое тоже нам подходит, совершенно бессмысленно его выдавать, потому что потом еще придется отсеивать его среди найденных. И генерация зеркального решения, и отсев только увеличат общие временные затраты.
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518605
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr SharahovmaytonAleksandr Sharahov, мы так запутаемся. В топике есть минимум два алгоритма.

О каком алгоритме вы сейчас говорите?

Мы решаем задачу завершения расстановки ферзей.

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

Даже если окажется, что у полученного решения есть зеркальное, которое тоже нам подходит, совершенно бессмысленно его выдавать, потому что потом еще придется отсеивать его среди найденных. И генерация зеркального решения, и отсев только увеличат общие временные затраты.
да нет же, если сразу самого первого ферзя из этого патnерна зафиксировать и далее этот паттерн не рассматривать, так как ВСЕ ферзи из него уже рассмотрены
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518609
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tip78да нет же, если сразу самого первого ферзя из этого патnерна зафиксировать и далее этот паттерн не рассматривать, так как ВСЕ ферзи из него уже рассмотрены

И...?
Продолжай, расскажи, как мы будем использовать зеркалирование и чем нам это поможет.
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518612
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr SharahovВ общем случае начальная позиция не переходит в себя при поворотах и отражениях.
Давай раскроем суть этой твоей фразы.

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

...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518614
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

значит, вас двое )
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518641
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Но не для рекурсии.
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518660
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahovtip78да нет же, если сразу самого первого ферзя из этого патnерна зафиксировать и далее этот паттерн не рассматривать, так как ВСЕ ферзи из него уже рассмотрены

И...?
Продолжай, расскажи, как мы будем использовать зеркалирование и чем нам это поможет.
если фигуры заранее фиксировать, то никак не поможет
а так сократит в несколько раз объём перебора, потому что не надо будет делать тоже самое, но с другой стороны (сторон)
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518664
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tip78Aleksandr Sharahovпропущено...


И...?
Продолжай, расскажи, как мы будем использовать зеркалирование и чем нам это поможет.
если фигуры заранее фиксировать, то никак не поможет
а так сократит в несколько раз объём перебора, потому что не надо будет делать тоже самое, но с другой стороны (сторон)

Хорошо, но мало )
Продолжай, расскажи, как мы будем использовать зеркалирование и чем нам это поможет с другой стороны.
Как именно это будет выглядеть в твоем алгоритме?
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518684
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahovtip78пропущено...

если фигуры заранее фиксировать, то никак не поможет
а так сократит в несколько раз объём перебора, потому что не надо будет делать тоже самое, но с другой стороны (сторон)

Хорошо, но мало )
Продолжай, расскажи, как мы будем использовать зеркалирование и чем нам это поможет с другой стороны.
Как именно это будет выглядеть в твоем алгоритме?
спасибо за предоставленную возможность (с)
но волшебные слова никто не отменял.

на доске 64 варианта первого ферзя
каждый одинокий ферзь на доске это некое дерево остальных ферзей до упора, где ВСЕ варианты заполнения опробованы
т.е. всё что надо это разбить доску на 4 квадрата и заполнить стартовыми ходами только 1 из них
поворачивание тут, кстати, уже и не нужно
просто есть квадраты по 16 клеток, как бы не начал на любом из них, на остальных будет зеркально тоже самое дерево и результаты
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518689
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tip78просто есть квадраты по 16 клеток, как бы не начал на любом из них, на остальных будет зеркально тоже самое дерево и результаты

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

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

Основная проблема здесь в том, что для отсева решения надо знать,
уникальное ли оно, а для этого его придется сначала получить.
Т.е. придется получить *ВСЕ* решения.
А если решение уже получено, то его проще показать,
чем возиться с отсевом и ведением списка уникальных решений,
которые еще надо отзеркалить во все стороны.
Зеркалирование ровным счетом ничего не дает, кроме лишней работы.
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518692
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
т.е. непонятно, что надо будет начинать только в 1м квадрате 16x16, а не в 4х?
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518694
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tip78т.е. непонятно, что надо будет начинать только в 1м квадрате 16x16, а не в 4х?

непонятно, что это дает.

Лучшим доказательством того, что идея зеркалирования работает,
будет реализация этого замечательного алгоритма, а не слова.

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

Реализуйте, например, поиск с возвратом двумя способами )
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518733
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Все самому приходится делать.

Алгоритм:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
procedure BackTrackingSymmetric;
var
  Queen, Col, Row: integer;
begin;
  for Queen:=0 to QueenCount-2 do QueenColRow[Queen].QueenRow:=Queen+1;   //symmetric
  QueenColRow[QueenCount-1].QueenRow:=0;                                  //symmetric

  Queen:=QueenCount-1;
  with QueenColRow[Queen] do begin;
    Col:=BoardSize-1;
    Row:=QueenRow;
    end;
  while true do begin;
    while Col>=0 do begin;
      if CountCol[Col] or CountDiagP[Col+Row] or CountDiagM[Col-Row]=0 then begin;
        CountCol[Col]:=1;
        CountDiagP[Col+Row]:=1;
        CountDiagM[Col-Row]:=1;
        QueenColRow[Queen].QueenCol:=Col;
        if Queen>0 then begin;
          dec(Queen);
          if Row=0 then begin;
            Row:=BoardSize-1-Col; if Col>Row then Col:=Row else dec(Col); //symmetric
            end
          else Col:=BoardSize-1;
          Row:=QueenColRow[Queen].QueenRow;
          continue;
          end;
        CountSymmetricSolution;                                           //symmetric
        //exit; //comment this statement to calculate all solutions
        CountCol[Col]:=0;
        CountDiagP[Col+Row]:=0;
        CountDiagM[Col-Row]:=0;
        end;
      dec(Col);
      end;
    inc(Queen);
    if Queen>=QueenCount then break;
    with QueenColRow[Queen] do begin;
      Col:=QueenCol;
      Row:=QueenRow;
      end;
    CountCol[Col]:=0;
    CountDiagP[Col+Row]:=0;
    CountDiagM[Col-Row]:=0;
    dec(Col);
    end;
  end;



Вывод с учетом симметрии:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
procedure CountSymmetricSolution;
var
  i, SymCount: integer;
begin;
  if SolutionCount=0 then ShowFirstSolution;
  if BoardSize>1
  then if QueenColRow[BoardSize-1].QueenCol
        + QueenColRow[BoardSize-2].QueenCol
        <>BoardSize-1
       then SymCount:=4
       else SymCount:=2
  else SymCount:=1;
  inc(SolutionCount, SymCount);
  for i:=0 to BoardSize-2 do //excluding big digonals
    if (CountDiagP[i]=CountDiagP[i+BoardSize])
    or (CountDiagM[i+1]=CountDiagM[i+1-BoardSize]) then exit;
  if ModularCount=0 then ShowFirstSolution;
  inc(ModularCount, SymCount);
  end;



Итого получилось быстрее несимметричного варианта почти в 2 раза.

Внутренние структуры алгоритма уже раньше были изменены под градиентный спуск и в данном случае это позволило добиться ускорения. Хитрость состоит в порядке перебора, чтобы обеспечить получение алгоритмом только уникальных решений:
1. Порядок перебора для строк: 0, N-1, ... 1.
2. Порядок перебора для столбцов строки N-1: Min(Col-1,BoardSize-1-Col), ... 0, где Col - текущий столбец строки 0.
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518736
tip78
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Aleksandr Sharahovtip78т.е. непонятно, что надо будет начинать только в 1м квадрате 16x16, а не в 4х?

непонятно, что это дает.

Лучшим доказательством того, что идея зеркалирования работает,
будет реализация этого замечательного алгоритма, а не слова.

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

Реализуйте, например, поиск с возвратом двумя способами )
чё-то мне влом
да и денег у вас не хватит моё время оплачивать.
в чём тут сложность понимания то?
весь алгоритм в том, что первый ферзь ставится только в 16 клеток, а не в 64
как 64 может быть быстрее 16 для меня загадка. алгоритм в помойку.

первый ферзь ставится в любую точку на доске
после этого пошёл поиск места для следующего
у каждого ферзя есть своё дерево ходов до полного исчезновения свободных клеток (ходов будут миллионы-миллиарды, но они конечны и ограничены)
8й ферзь отработает все свободные клетки
после чего 7й ферзь сдвинется на следующую свободную клетку и снова 8й ферзь будет пробивать все свободные
когда у 7го закончатся клетки, сдвинется 6й итд
и вот ровно такие же действия (зеркально) для каждого ферзя, но на другой стороне поля, будут происходить, если поставить первого ферзя в другой противоположный квадрат.
это же перебор. ВСЕ свободные клетки на доске будут задействованы для каждого ферзя.
В одном квадрате 1й ферзь встаёт на 3:4, 2й на 1:1, в противоположном они же займут 6:5 и 8:8, после чего ровно также 2й пойдёт пробивать все клетки, получая ровно те же (зеркальные) результаты
я хз, как ещё понятнее объяснить, вроде элементарно.
...
Рейтинг: 0 / 0
Пятничная задачка для ума за 1 миллион $
    #39518742
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tip78чё-то мне влом
да и денег у вас не хватит моё время оплачивать.

С чего вы взяли, что тут вас кто-то наймет? Для поиска работы есть другой форум.

tip78в чём тут сложность понимания то?
весь алгоритм в том, что первый ферзь ставится только в 16 клеток, а не в 64
как 64 может быть быстрее 16 для меня загадка. алгоритм в помойку.

Да запросто: алгоритм-64 есть и у него есть время работы,
а алгоритм-16 пока только у вас в голове и его время работы там же.

tip78первый ферзь ставится в любую точку на доске
после этого пошёл поиск места для следующего
у каждого ферзя есть своё дерево ходов до полного исчезновения свободных клеток (ходов будут миллионы-миллиарды, но они конечны и ограничены)
8й ферзь отработает все свободные клетки
после чего 7й ферзь сдвинется на следующую свободную клетку и снова 8й ферзь будет пробивать все свободные
когда у 7го закончатся клетки, сдвинется 6й итд
и вот ровно такие же действия (зеркально) для каждого ферзя, но на другой стороне поля, будут происходить, если поставить первого ферзя в другой противоположный квадрат.
это же перебор. ВСЕ свободные клетки на доске будут задействованы для каждого ферзя.
В одном квадрате 1й ферзь встаёт на 3:4, 2й на 1:1, в противоположном они же займут 6:5 и 8:8, после чего ровно также 2й пойдёт пробивать все клетки, получая ровно те же (зеркальные) результаты
я хз, как ещё понятнее объяснить, вроде элементарно.

Да всем это понятно. Не это надо объяснять.

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

А то что вы рассказываете уже в который раз - не алгоритм.
...
Рейтинг: 0 / 0
25 сообщений из 491, страница 8 из 20
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пятничная задачка для ума за 1 миллион $
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]