Вопрос по судоку

[arseniiv]

У меня есть процедура, генерирующая решённый квадрат судоку. Чтобы сделать головоломку, можно "вынимать" числа из сетки как попало, или всё же придётся проверять? (Т.е. нет ли такого свойства у таблицы судоку, что при любом извлечении некоторого кол-ва чисел она останется решаемой?). Конечно, я собираюсь не как попало убирать числа, а так, чтобы их соотношение было близко к 1:1:1:...:1 (например, если убирать 9 цифр, то так, чтобы все были разные).

[EtCetera]

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

[arseniiv]

Могу предоставить некоторые данные ещё: программа на телефоне, которая аозволяла самому задавать сложность с помощью кол-ва оставляемых чисел, позволяла ввести минимум 10. (Там оставались 9 разных чисел, и одно повторялось.)
Но вроде ещё сложность зависит не только от оставшихся в сетке цифр, а ещё от "геометрии". Недавно решал вполне "приличное" судоку, было дано много чисел, но решалось очень трудно, да ещё и неоднозначность была. Вот так!

-- Вс июн 21, 2009 21:11:50 --

Странный результат получился - я провёл опыт - убрал последовательно из квадрата 4x4 все числа, кроме четырёх 1, 2, 3 и 4. И всё равно смог восстановить обратно тот самый квадрат, притом даже не возникало неоднозначностей. С квадратом 9x9 проделать это мне было бы слишком трудно - может, кто-нибудь, если захочет, и сумеет

[Yuri Gendelman]

arseniiv в сообщении #223728 писал(а):

У меня есть процедура, генерирующая решённый квадрат судоку...

Есть книга на английском, посвященная программированию судоку:
Wei-Meng Lee. Programming Sudoku. // Apress. 2006
Возможно, в ней есть то, что Вы ищете.

Чтобы скачать что-нибудь с сайта gigapedia.com/, на нем нужно зарегистрироваться.

[arseniiv]

А так никак?

[Yuri Gendelman]

arseniiv в сообщении #223782 писал(а):

А так никак?

Регистрация - это быстро, бесплатно и не больно.

[arseniiv]

Цитата:

вы можете зарегистрироваться только указав google-аккаунт почты! (мы боремся со спамом)

Это мне не нравится - у меня нету google-почты
Да и книга на английском, смогу осилить только куски... Нет, подожду, может, кто-нибудь ещё что-то скажет

[Nerazumovskiy]

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

-- Пн июн 22, 2009 21:13:23 --

кстати забыл сказать вы вкурсе что есть нерешаемое судоку(неоднозначно)
в котором удалено всего 2 цыфры?

[venco]

Nerazumovskiy в сообщении #224089 писал(а):

кстати забыл сказать вы вкурсе что есть нерешаемое судоку(неоднозначно)
в котором удалено всего 2 цыфры?

Неужели?

[arseniiv]

Да нет такого судоку

-- Ср июн 24, 2009 23:08:52 --

Кстати, зачем решать после каждого выкидывания? Намного умнее просто выкинуть случайным образом сразу нужное кол-во цифр. И повторить, если не решается...

[PAV]

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

[arseniiv]

Ну, это тоже важно, если нужно сделать качественное судоку (я видел с расположением цифр симметрично, например, интересно ), но меня конечно интересовал просто вопрос однозначности. Видимо, "автоматическим решением" придётся делать - может, так все и делают.

Большое спасибо, что сменили букву в названии темы, а то потом уже было никак.

[iig]

По моему, это напрямую относится к восстановлению латинских квадратов,
точнее, к генерации квазигрупп.

[arseniiv]

Да, вроде именно так. Но с квазигруппами у меня никак, да я так сильно судоку и не занимаюсь...

[iig]

Как ни странно, но дискретные квазигруппы, как и латинские квадраты, вполне доступны даже школьникам начальных классов.
Сюда можно добавить и магические квадраты, но это не мое.
Мне было интересно классифицировать лупы - это квазигруппы с единицей, и обнаруживать у них новые свойства по мере повышения порядка.
О собенно интересовали отклонения от ассоциативности.
Это на школьном уровне, только их трудно заинтересовать, зачем это надо,
я знал и было интересно.
Другое дело, что тут слишком заумная терминология, вроде шаманы на своем языке объясняются.
Может, соберусь написать попроще, чтобы любой склонный понял.
Вот Я, к примеру, стоял перед доской - два одинаковых треугольника доказать, что равны - а я дуб дубом.
Затем пошла алгебра, тут врубился, стал корифеем - незабываемое чувство, решил себе и соседям и гордо сдать тетрадь.
У меня похожая проблема - некоторые простые вопросы так опутаны терминологией, почти как идиш изучай, славо богу хоть пишут в нашу сторону.
Для примера по поводу приведу ссылку ниже, как можно закрутить - математики страдают излишними подробностями, а я могу просраться быстрее, суки, пока понял, год прошел. Так что не ссы, главное их язык понять, а там можно по-ихней фене ботать.
Желаю не слишком многомерного пространства и иметь базис.

Пример как можно простые вещи замутить, хотя все правильно
ЗЫ Это не для школьников, даже профи могут каждый по своему
Кобаяси Ш., Номидзу к. Основы дифференциальной геометрии т.1 М.: Наука 1981
- приложение Сабинина стр 293.
PPS: А вот генерация (полный перебор) луп меня и сейчас интересует.