Перейти к содержанию

Математическое и загадочное


E.K.

Рекомендуемые сообщения

5 минут назад, Рогожников Евгений сказал:

На второе судоку уже сил нет. Пойду пиво пить. 

https://www.youtube.com/watch?v=bEPwwwTRWTw :)

Вторая/ое/ой судоку кстати проще первых двух - на 1 выбор меньше делать надо

 

 

Ссылка на комментарий
Поделиться на другие сайты

Ну и, пользуясь случаем, что Евгений Валентинович разрешил давать здесь задачи и посетителям, хочу предложить следующую на IT-тему

 

Две IT-фирмы по очереди нанимают программистов, среди которых есть N гениев. 
Первого программиста каждая фирма выбирает произвольно, а каждый следующий должен быть
знаком с кем-то из ранее нанятых данной фирмой. Если фирма не может нанять програм-
миста по этим правилам, она прекращает прием, а другая может продолжать. Список
программистов и их знакомств заранее известен, включая информацию о том, кто гении.
Могут ли знакомства быть устроены так, что фирма, вступающая в игру второй, сможет
нанять (N-1) гения, как бы ни действовала первая фирма?

Ну и подслучаи:

1) N = 3  (легкий вариант)
2) N = 4   ( вариант  посложнее)
3) N = 11  или произвольно   (сложный вариант. )

  • Спасибо (+1) 1
Ссылка на комментарий
Поделиться на другие сайты

15 минут назад, Борис Прокофьев сказал:

К сожалению...

Кстати в таком исполнении судоку становится гораздо халявнее - в лучшем случае надо всего лишь 2 раза угадать ветку

Ссылка на комментарий
Поделиться на другие сайты

7 минут назад, Fireman сказал:

а выбирать надо начиная с гениев или брать любого программиста?

По условиям - с любого. То есть, надо подобрать такое расположение "гениев" в топологии знакомств, что 2я фирма хапает их всех вне зависимости от укуса шоколада от первого найма первой фирмой. Надо брать бумажку и рисовать. Например, начиная с лёгких случаев.

 

// кстати, требуется уточнение очевидного вроде факта, что "знакомство" есть симметричное свойство. То есть, я, например, знаком с сэром Ричардом Брэнсоном. И я про это помню. А вот что сэр Ричард Брэнсон помнит, что он со мной знаком - это может оказаться сомнительным фактом :) Хотя, наверное, вроде бы должен помнить..

 

Короче, надо брать листок бумаги в клеточку - и рисовать картинки.

Ссылка на комментарий
Поделиться на другие сайты

1 час назад, E.K. сказал:

кстати, требуется уточнение очевидного вроде факта, что "знакомство" есть симметричное свойство.

 

Да, конечно,симметричное свойство.

 

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

IMG_20200613_190401.jpg.80d97849e238385ed5a798a8c9513ed9.jpg

 

Кстати, вопрос к Fireman. Как вам удается оценивать сложность судоку? Чуть выше вы писали, что во втором судоку придется перебирать меньше вариантов, чем в первом.

Т.е получается, что у вас есть некий алгоритм, который быстро позволяет оценить такую сложность?

 

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

Таким образом, решением будет только доказательство данного факта. Я не знаю, как решают судоку метры, но если решать так как я - путем "блуждающего" перебора, то я бы и за неделю не решил.

Ссылка на комментарий
Поделиться на другие сайты

1 час назад, Рогожников Евгений сказал:

но если решать так как я - путем "блуждающего" перебора, то я бы и за неделю не решил.

 

Ну... до Вас тут такую судоку три недели решали... Но со всеми выкладками ;)  

 

Задача:                                                                                 Ответ:

432253891_Sudoku0603.thumb.jpg.a70566dc2329179a086b3a2ce70da9d3.jpg373309394_Sudoku2703.thumb.jpg.a0e95307fd47201645ad0b6cfae18435.jpg

Изменено пользователем Борис Прокофьев
ссылки на полноразмерные картинки забыл
Ссылка на комментарий
Поделиться на другие сайты

 

2 часа назад, Рогожников Евгений сказал:

Кстати, вопрос к Fireman. Как вам удается оценивать сложность судоку?

 

После решения таких судоку недавно задался вопросом - а какая судока сложнее.

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

 

Написал программу для решения судоку, перебора всех вариантов решения (т.е. все вариантов выбора) и поиска самого короткого.

На питоне решение подобных судоку занимало 15 секунд, поиск кратчайшего решения - 2-3 часа.

Переписал на c++ (обожаю возиться с оптимизациями) - решение стало занимать 4мсек, поиск кратчайшего решения - 200мсек.

Переписал оптимизированный вариант на питон - решение вместо 16 сек стало занимать 2 сек (это по поводу насколько быстрый язык :))))

 

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

 

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

 

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

 

В итоге:

 

image.png.d1be9b1bde753f36818ea65c5010974b.png

требует минимум 4 раза выбрать один из двух вариантов (хода):  (3,8) = 3, (3,5) = 4, (3,1) = 9, (7,1) = 7

но если использовать клетки с 2, 3 и 4 вариантами - то требуется всего 2 хода: (7,1) = 7, (3,2) = 6

 

image.png.039a5e93289c7cd681657c93a263f3bd.png

требует минимум 3 хода: (3,2) = 4, (8,2) = 7, (1,5) = 9

но если использовать клетки с 2 и 3 вариантами - то требуется всего 2 хода: (7,1) = 4, (9,4) = 6

 

image.png.442f29b4e1850c1784516486e4eab08a.png

требует минимум 5 ходов!!!: (7,8) = 9, (7,7) = 3, (2,7) = 2, (3,1) = 2, (3,9) = 6

но если использовать клетки с 2 и 3 вариантами - то требуется всего 3 хода: (2,2) = 4, (6,2) = 2, (7,7) = 3

если использовать клетки с любым кол-вом вариантов - то требуется всего 2 хода: (3,1) = 2, (2,5) = 6

 

 

Изменено пользователем Fireman
Ссылка на комментарий
Поделиться на другие сайты

12.06.2020 в 18:16, Рогожников Евгений сказал:

Две IT-фирмы по очереди нанимают программистов, среди которых есть N гениев. 
...

Я возможно как-то не так понял условие, но кажется, если взять следующую схему знакомств, то ответ найден: 

- есть N "гениев"

- есть N "обычных"

- все имеют номера от 1 до 2N, причем нечетные это "гении", а четные "обычные"

- каждый знаком с соседними номерами (причем 1 и 2N тоже знакомы)

 

Т.е. получается такой цикл из 2N вершин, где чередуются "гении" и "обычные". 

 

Первая контора выбирает любого назовем его 'A', вторая выбирает любого знакомого 'A' назовем его 'B'. После этого, первая контора может выбрать только единственного знакомого 'A' (второй знакомый уже занят), назовем его 'C'. После этого вторая выбирает не нанятого знакомого 'C'. Получается, что первая контора уже не может нанять никого, т.к. больше не осталось не нанятых знакомых программистов. И среди них только один "гений", т.к. в графе знакомств они чередуются. Вторая контора нанимает всех остальных, т.е. N-1 всех "гениев"

Ссылка на комментарий
Поделиться на другие сайты

11 минут назад, Maxim Yurchuk сказал:

то ответ найден: 

image.png.6cf9c2c752afeafa6def44f7289aca4f.png

 

Зеленым показан последовательный выбор фирмы №1

Фирма №2 никак не сможет помешать, чтобы у фирмы №1 было 2 гения - если попробует помешать взять соседнего гения справа, то фирма №1 возьмет соседнего гения слева

 

 

Изменено пользователем Fireman
Ссылка на комментарий
Поделиться на другие сайты

Пожалуйста, войдите, чтобы комментировать

Вы сможете оставить комментарий после входа в



Войти
  • Похожий контент

    • E.K.
      От E.K.
      Всем привет!
       
      По ходу жизни мы все иногда сталкиваемся с разными визуальными несуразностями, которые можно сфотографировать - или которые уже существуют в виде фоток. Например, однажды в небольшом магазинчике на Гавайях я обнаружил... водку Камчатка!

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

       
      Или меня постоянно удивляет кофе "Georgia" в японских уличных магазинах и вендинговых автоматах:

       
      Процитирую себя
      "Каждый раз в Японии меня умиляет кофейный бренд "GEORGIA" со снежными вершинами на картинке.
      Никак не могу понять - если это американская Джорджия - то при чём здесь горы? Если же это Грузия - то при чём здесь кофе? Но в Японии эти несовместимые несовместимости вполне себя неплохо чувствуют в повсеместно расставленных вендинговых машинках. Хотя... Если посмотреть по сторонам.. Например, "Спартак" и "Динамо".. ... - какое отношение эти бренды имеют к футболу?"
       
      Кстати, а почему он на картинке в каске? Зачем это кофе надо пить в каске?..

       
      Так вот, картинок таких наверняка не только у меня достаточно - посему эта тема будет как раз посвящена разным фоткам с несуразностями, загадками - и разными прочими подобными тоже. Спасибо Борису за подсказку!
       
       
      Ну, можно начинать.
×
×
  • Создать...