Судоку и отношение порядка.

[Nemiroff]

Собственно, судоку. Отношение порядка присутствует.

[arseniiv]

(Оффтоп)

Великолепно! (Но решать не буду.)

[gris]

Я бы начал с претендентов на 1 и 9.

Видно, что некоторые цифры отсеиваются.
Да многие!
Если за ночь не будет опубликовано решение, то утром попробую погадать, а пока согласен с arseniiv

[Tall]

(Оффтоп)

Где-то я уже видел эту задачку. Nemiroff колесо вращается быстрей?

[hippie]

834 967 251
915 238 764
276 451 839

657 329 148
489 175 623
321 846 597

743 582 916
162 793 485
598 614 372

gris в сообщении #960153 писал(а):

Я бы начал с претендентов на 1 и 9.

Только с девяток. И дальше сверху вниз (8, 7, 6, ...).

[Nemiroff]

hippie, это верно.

Tall в сообщении #960162 писал(а):

Nemiroff колесо вращается быстрей?

Так точно.
Для непосвящённых, задачку я спёр отсюда: http://avva.livejournal.com/2832977.html Комментарии огорчают.

[Yadryara]

Nemiroff в сообщении #960174 писал(а):

Комментарии огорчают.

Отчего же? Среди комментариев есть вполне логичное упоминание об избыточности решения. Только нет конкретики.

В самом деле, ведь достаточно не $108$, а, например, $98$ символов "<" и ">" для нахождения того самого единственного решения. Например, можно убрать $10$ символов из правого нижнего угла и получить то же самое решение:

$\tikz[scale=.06]{ \draw [ultra thick] (0,0)--(0,90)--(90,90)--(90,0)--(0,0); \draw(0,10)--(90,10); \draw(0,20)--(90,20); \draw [very thick](0,30)--(90,30); \draw(0,40)--(90,40); \draw(0,50)--(90,50); \draw [very thick](0,60)--(90,60); \draw(0,70)--(90,70); \draw(0,80)--(90,80); \draw(10,0)--(10,90); \draw(20,0)--(20,90); \draw [very thick](30,0)--(30,90); \draw(40,0)--(40,90); \draw(50,0)--(50,90); \draw [very thick](60,0)--(60,90); \draw(70,0)--(70,90); \draw(80,0)--(80,90); \draw[thick](22,83.4)--(18,85)--(22,86.6); \draw[thick](52,83.4)--(48,85)--(52,86.6); \draw[thick](72,83.4)--(68,85)--(72,86.6); \draw[thick](8,83.4)--(12,85)--(8,86.6); \draw[thick](38,83.4)--(42,85)--(38,86.6); \draw[thick](78,83.4)--(82,85)--(78,86.6); \draw[thick](22,73.4)--(18,75)--(22,76.6); \draw[thick](42,73.4)--(38,75)--(42,76.6); \draw[thick](52,73.4)--(48,75)--(52,76.6); \draw[thick](8,73.4)--(12,75)--(8,76.6); \draw[thick](68,73.4)--(72,75)--(68,76.6); \draw[thick](78,73.4)--(82,75)--(78,76.6); \draw[thick](12,63.4)--(8,65)--(12,66.6); \draw[thick](42,63.4)--(38,65)--(42,66.6); \draw[thick](82,63.4)--(78,65)--(82,66.6); \draw[thick](18,63.4)--(22,65)--(18,66.6); \draw[thick](48,63.4)--(52,65)--(48,66.6); \draw[thick](68,63.4)--(72,65)--(68,66.6); \draw[thick](22,53.4)--(18,55)--(22,56.6); \draw[thick](52,53.4)--(48,55)--(52,56.6); \draw[thick](72,53.4)--(68,55)--(72,56.6); \draw[thick](82,53.4)--(78,55)--(82,56.6); \draw[thick](8,53.4)--(12,55)--(8,56.6); \draw[thick](38,53.4)--(42,55)--(38,56.6); \draw[thick](12,43.4)--(8,45)--(12,46.6); \draw[thick](22,43.4)--(18,45)--(22,46.6); \draw[thick](42,43.4)--(38,45)--(42,46.6); \draw[thick](82,43.4)--(78,45)--(82,46.6); \draw[thick](48,43.4)--(52,45)--(48,46.6); \draw[thick](68,43.4)--(72,45)--(68,46.6); \draw[thick](52,33.4)--(48,35)--(52,36.6); \draw[thick](72,33.4)--(68,35)--(72,36.6); \draw[thick](8,33.4)--(12,35)--(8,36.6); \draw[thick](18,33.4)--(22,35)--(18,36.6); \draw[thick](38,33.4)--(42,35)--(38,36.6); \draw[thick](78,33.4)--(82,35)--(78,36.6); \draw[thick](42,23.4)--(38,25)--(42,26.6); \draw[thick](82,23.4)--(78,25)--(82,26.6); \draw[thick](8,23.4)--(12,25)--(8,26.6); \draw[thick](18,23.4)--(22,25)--(18,26.6); \draw[thick](48,23.4)--(52,25)--(48,26.6); \draw[thick](68,23.4)--(72,25)--(68,26.6); \draw[thick](12,13.4)--(8,15)--(12,16.6); \draw[thick](42,13.4)--(38,15)--(42,16.6); \draw[thick](18,13.4)--(22,15)--(18,16.6); \draw[thick](48,13.4)--(52,15)--(48,16.6); \draw[thick](12,3.4)--(8,5)--(12,6.6); \draw[thick](52,3.4)--(48,5)--(52,6.6); \draw[thick](18,3.4)--(22,5)--(18,6.6); \draw[thick](38,3.4)--(42,5)--(38,6.6); \draw[thick](13.4,82)--(15,78)--(16.6,82); \draw[thick](33.4,82)--(35,78)--(36.6,82); \draw[thick](43.4,82)--(45,78)--(46.6,82); \draw[thick](3.4,78)--(5,82)--(6.6,78); \draw[thick](23.4,78)--(25,82)--(26.6,78); \draw[thick](53.4,78)--(55,82)--(56.6,78); \draw[thick](63.4,78)--(65,82)--(66.6,78); \draw[thick](73.4,78)--(75,82)--(76.6,78); \draw[thick](83.4,78)--(85,82)--(86.6,78); \draw[thick](3.4,72)--(5,68)--(6.6,72); \draw[thick](53.4,72)--(55,68)--(56.6,72); \draw[thick](73.4,72)--(75,68)--(76.6,72); \draw[thick](13.4,68)--(15,72)--(16.6,68); \draw[thick](23.4,68)--(25,72)--(26.6,68); \draw[thick](33.4,68)--(35,72)--(36.6,68); \draw[thick](43.4,68)--(45,72)--(46.6,68); \draw[thick](63.4,68)--(65,72)--(66.6,68); \draw[thick](83.4,68)--(85,72)--(86.6,68); \draw[thick](3.4,52)--(5,48)--(6.6,52); \draw[thick](33.4,52)--(35,48)--(36.6,52); \draw[thick](53.4,52)--(55,48)--(56.6,52); \draw[thick](73.4,52)--(75,48)--(76.6,52); \draw[thick](83.4,52)--(85,48)--(86.6,52); \draw[thick](13.4,48)--(15,52)--(16.6,48); \draw[thick](23.4,48)--(25,52)--(26.6,48); \draw[thick](43.4,48)--(45,52)--(46.6,48); \draw[thick](63.4,48)--(65,52)--(66.6,48); \draw[thick](3.4,42)--(5,38)--(6.6,42); \draw[thick](13.4,42)--(15,38)--(16.6,42); \draw[thick](23.4,42)--(25,38)--(26.6,42); \draw[thick](43.4,42)--(45,38)--(46.6,42); \draw[thick](63.4,42)--(65,38)--(66.6,42); \draw[thick](33.4,38)--(35,42)--(36.6,38); \draw[thick](53.4,38)--(55,42)--(56.6,38); \draw[thick](73.4,38)--(75,42)--(76.6,38); \draw[thick](83.4,38)--(85,42)--(86.6,38); \draw[thick](3.4,22)--(5,18)--(6.6,22); \draw[thick](23.4,22)--(25,18)--(26.6,22); \draw[thick](13.4,18)--(15,22)--(16.6,18); \draw[thick](33.4,18)--(35,22)--(36.6,18); \draw[thick](43.4,18)--(45,22)--(46.6,18); \draw[thick](53.4,18)--(55,22)--(56.6,18); \draw[thick](33.4,12)--(35,8)--(36.6,12); \draw[thick](43.4,12)--(45,8)--(46.6,12); \draw[thick](3.4,8)--(5,12)--(6.6,8); \draw[thick](13.4,8)--(15,12)--(16.6,8); \draw[thick](23.4,8)--(25,12)--(26.6,8); \draw[thick](53.4,8)--(55,12)--(56.6,8); }$

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

Определил, что для судоку 4-го порядка минимальное количество символов сравнения — $5$. Вот пример:

$\tikz[scale=.06]{ \draw [ultra thick] (0,0)--(0,40)--(40,40)--(40,0)--(0,0); \draw(0,10)--(40,10); \draw [very thick](0,20)--(40,20); \draw(0,30)--(40,30); \draw(10,0)--(10,40); \draw [very thick](20,0)--(20,40); \draw(30,0)--(30,40); \draw[thick](12,33.4)--(8,35)--(12,36.6); \draw[thick](3.4,32)--(5,28)--(6.6,32); \draw[thick](13.4,28)--(15,32)--(16.6,28); \draw[thick](32,33.4)--(28,35)--(32,36.6); \draw[thick](32,13.4)--(28,15)--(32,16.6); \fill[green](55,22)--(75,22)--(75,25)--(85,20)--(75,15)--(75,18)--(55,18)--(55,22); \draw [ultra thick] (100,0)--(100,40)--(140,40)--(140,0)--(100,0); \draw(100,10)--(140,10); \draw [very thick](100,20)--(140,20); \draw(100,30)--(140,30); \draw(110,0)--(110,40); \draw [very thick](120,0)--(120,40); \draw(130,0)--(130,40); \draw[thick](112,33.4)--(108,35)--(112,36.6); \draw[thick](103.5,31.8)--(105,28.2)--(106.5,31.8); \draw[thick](113.5,28.2)--(115,31.8)--(116.5,28.2); \draw[thick](132,33.4)--(128,35)--(132,36.6); \draw[thick](132,13.4)--(128,15)--(132,16.6); \node at (105,35){\large \textbf{2}}; \node at (115,35){\large \textbf{3}}; \node at (105,25){\large \textbf{1}}; \node at (115,25){\large \textbf{4}}; \node at (125,35){\large \textbf{1}}; \node at (135,35){\large \textbf{4}}; \node at (125,15){\large \textbf{2}}; \node at (135,15){\large \textbf{3}}; \node at (125,25){\large \text{3}}; \node at (135,25){\large \text{2}}; \node at (105,15){\large \text{4}}; \node at (115,15){\large \text{1}}; \node at (105,5){\large \text{3}}; \node at (115,5){\large \text{2}}; \node at (125,5){\large \text{4}}; \node at (135,5){\large \text{1}}; }$

Найти такой минимум для 9-го порядка пока представляется очень сложной задачей.

[hippie]

Yadryara в сообщении #962011 писал(а):

В самом деле, ведь достаточно не $108$, а, например, $98$ символов "<" и ">" для нахождения того самого единственного решения. Например, можно убрать $10$ символов из правого нижнего угла и получить то же самое решение:

При этом важно чтобы решение находилось логическим путём, без большого перебора (тем более без компьютерного перебора).
В исходной задаче пришлось только раз рассмотреть два варианта. (Когда были выставлены все девятки, восьмёрки, семёрки, шестёрки и 5 пятёрок. Оставшиеся 4 пятёрки можно было выставить двумя способами, один из которых быстро привёл в тупик.)
А Вы проверяли свою расстановку знаков на наличие логического решения? Или проверили единственность на компьютере? (Я поищу её логическое решение несколько позже.)

Yadryara в сообщении #962011 писал(а):

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

Легко построить расстановку 48 знаков. Только решать такое "судоку" будет совсем неинтересно.

[hippie]

Похоже, что логическое решение есть!

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

При первоначальной расстановке знаков возникает такая позиция:




При расстановке, предложенной Yadryara, на этой же стадии возникает такая позиция:

[Yadryara]

hippie в сообщении #962554 писал(а):

Похоже, что логическое решение есть!

Ура!

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

Так что поставленная задача минимизации подсказок, это задача в духе конкурсов Al Zimmerman и, пожалуй, больше подходит для раздела «Олимпиадные задачи (CS)» и я, возможно, создам там отдельную тему, чтобы с постановкой могли ознакомиться многие сильные программисты, которые в головоломный раздел, возможно, даже и не заглядывают.

Подобный вопрос предельного решения для классического судоку был закрыт сравнительно недавно, только 3 года назад. Искали расстановку 16-ти чисел, дающую единственное решение. Так и не нашли. Установленный минимум — 17 чисел. Полагаю, Вы в курсе этой работы, но ссылку даю.

http://www.math.ie/McGuire_V1.pdf

Я предполагаю, что вопрос расстановки минимального количества символов "<"и ">" ещё не ставился. Пока будем ориентироваться на Ваш прекрасный результат в 48 знаков.

hippie в сообщении #962499 писал(а):

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

Да, для нынешнего раздела, конечно же, важно.

hippie в сообщении #962499 писал(а):

Легко построить расстановку 48 знаков. Только решать такое "судоку" будет совсем неинтересно.

Всё равно порешаем на досуге

[hippie]

hippie в сообщении #962554 писал(а):

Похоже, что логическое решение есть!

Действительно есть!

В приведённой выше позиции

так же, как и при решении исходной задачи, нужно рассмотреть две возможных расстановки пятёрок.

hippie в сообщении #962499 писал(а):

Легко построить расстановку 48 знаков.

И убрать 6 знаков, оставляя только 42.

Yadryara в сообщении #962564 писал(а):

Всё равно порешаем на досуге

Наверно досуга очень мало . Вряд ли решение займёт больше пяти минут.

Yadryara в сообщении #962564 писал(а):

Подобный вопрос предельного решения для классического судоку был закрыт сравнительно недавно, только 3 года назад. Искали расстановку 16-ти чисел, дающую единственное решение. Так и не нашли. Установленный минимум — 17 чисел. Полагаю, Вы в курсе этой работы, но ссылку даю.

Большое спасибо за ссылку! Не знал, не только о работе, но и о текущем минимуме определяющих цифр.



Вспомнил задачу (ОЧЕНЬ ПРОСТУЮ), предлагавшуюся несколько лет назад на одном из соревнований по решению головоломок:
Разбить квадрат $9\times 9$ на 9 нонамино (связных фигур, состоящих из девяти клеток). Квадрат заполняется цифрами от 1 до 9 по правилам: в каждой горизонтали, в каждой вертикали и в каждом из нонамино должны встречаться все цифры.
Требуется найти разбиение, при котором можно расставить как можно меньше цифр, таким образом, чтобы полученное "судоку" имело единственное решение.

[venco]

hippie в сообщении #962692 писал(а):

Требуется найти разбиение, при котором можно расставить как можно меньше цифр, таким образом, чтобы полученное "судоку" имело единственное решение.

8?

[Nemiroff]

Если что, на буржуйском задачи типа стартовой называются Greater than Sudoku.

[venco]

venco в сообщении #962704 писал(а):

hippie в сообщении #962692 писал(а):

Требуется найти разбиение, при котором можно расставить как можно меньше цифр, таким образом, чтобы полученное "судоку" имело единственное решение.

8?

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

[hippie]

hippie в сообщении #962692 писал(а):

Вспомнил задачу (ОЧЕНЬ ПРОСТУЮ), предлагавшуюся несколько лет назад на одном из соревнований по решению головоломок:
Разбить квадрат $9\times 9$ на 9 нонамино (связных фигур, состоящих из девяти клеток). Квадрат заполняется цифрами от 1 до 9 по правилам: в каждой горизонтали, в каждой вертикали и в каждом из нонамино должны встречаться все цифры.
Требуется найти разбиение, при котором можно расставить как можно меньше цифр, таким образом, чтобы полученное "судоку" имело единственное решение.

venco в сообщении #962738 писал(а):

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

Правильно!
Если при том же разбиении на нонамино вместо определяющих цифр расставлять знаки, то их так же потребуется 8.
Очевидно, что меньше чем восемью определяющими цифрами обойтись нельзя. Похоже, что так же, как и для цифр, меньше чем восемью знаками обойтись невозможно (ни при каком разбиении квадрата на нонамино). А есть ли простое доказательство этого?