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

[Fireman]

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

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

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

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

 

 

[Рогожников Евгений]

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

 

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

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

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

[Борис Прокофьев]

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

Получил вот такое решение 

 

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

[Fireman]

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

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

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

[Рогожников Евгений]

А а а

[Рогожников Евгений]

Попытка номер 2. На этот раз, вроде, ничего не напутал

 

 

[E.K.]

Победа!

А вторую?

[Fireman]

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

Две IT-фирмы...

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

[E.K.]

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

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

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

 

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

 

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

[Рогожников Евгений]

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

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

 

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

 

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

 

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

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

 

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

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

[E.K.]

А если решений несколько? "По-честному" надо найти ВСЕ решения, если их больше одного..

[Борис Прокофьев]

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

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

 

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

 

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

Изменено 13 июня, 2020 пользователем Борис Прокофьев
ссылки на полноразмерные картинки забыл

[Fireman]

 

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

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

 

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

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

 

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

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

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

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

 

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

 

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

 

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

 

В итоге:

 

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

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

 

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

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

 

требует минимум 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

 

 

Изменено 13 июня, 2020 пользователем Fireman

[Maxim Yurchuk]

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

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

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

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

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

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

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

 

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

 

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

[Fireman]

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

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

 

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

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

 

 

Изменено 13 июня, 2020 пользователем Fireman