2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 
Сообщение04.03.2007, 20:17 


04/03/07
1
Коллеги, нет ли у вас ссылки на доказательство того, что это NP complete проблема ? По крайней мере в википедии написано что это именно так, но их ссылка на док-во, к сожалению, битая.

 Профиль  
                  
 
 
Сообщение04.03.2007, 23:00 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Здесь ссылки небитые

 Профиль  
                  
 
 
Сообщение07.03.2007, 13:43 
Аватара пользователя


15/11/06
2689
Москва Первомайская
Обычно судоку в метро решают женщины. А сегодня я видел мужчину. Но судоку у него другой формы. Большой квадрат, как обычно, 9х9. В центре - симметричный крест из 9 ячеек, в каждом углу которого - по маленькому квадрату 3х3. Оставшиеся четыре фигуры, каждая в форме С, заполняют четыре угла большого квадрата. В начальной расстановке я насчитал 19 цифр. Мужчина думал-думал, думал-думал и поставил одну цифру. Потом подумал еще немного, бросил и взялся за другую головоломку. Не по зубам орешек оказался. :(

 Профиль  
                  
 
 
Сообщение15.03.2007, 16:38 
Аватара пользователя


15/11/06
2689
Москва Первомайская
Посмотрите, какая идея а-ля судоку-какуро пришла тут мне в голову.

 Профиль  
                  
 
 
Сообщение13.04.2007, 16:47 
Экс-модератор
Аватара пользователя


23/12/05
12046
Сам эту книгу не видел, но наткнулся в анонсах по выходу книг:

Цитата:
"A to Z of SUDOKU"
Narendra Jussein, Ecole des Mines, Nantes, France

The science behind Sudoku...

Sudoku is a logic puzzle that has become a worldwidw phenomenon in the last few years: but where has it come from? How does it work? And what is the science behind sudoku - what are the rules for generating and solving grids?

Answer to all of these questions can be found in the A-Z of Sudoku. As its title suggests, this book provides a "one stop shop" on sudoku, covering the history of the puzzle, izs development and growth in the world's media, before moving on to the mathematics of sudoku and various techniques that can be used to solve grids by hand.

Next, the essentials of software development relating to sudoku are presenred along with the recent branch of computer science devoted to solving such problems: constraint programming, showing how the priniple behind solving sudoku grids can be used in other contexts. Finally, the book concludes with a large number of grids ranging in difficulty from "very easy" to expert which the reader can use to apply the techniques they have acquired from the book in a practical context.

Those interested finding out more about the theory behind sudoku, its origins, it applications in other fields and (of course) how to improve their ability to solve it will find this book is must-read.
...

January 2007 184 pages

 Профиль  
                  
 
 
Сообщение21.04.2007, 21:37 


21/04/07
7
сложность не зависит от количества проставленных цифр.

Добавлено спустя 2 часа 33 минуты 45 секунд:

для Lion: "сложное" судоку вовсе не сложное, я его разгадала за 20 минут без подборов вариантов.Настоящие сложные судоку обязательно содержат "ловушки", когда в нескольких клетках получается несколько вариантов, и тогда нужно идти путем подбора до тупиков.

 Профиль  
                  
 
 
Сообщение21.04.2007, 23:44 
Экс-модератор


12/06/05
1595
MSU
ГБ писал(а):
сложность не зависит от количества проставленных цифр.

Очень спорный тезис. Можно ли назвать сложным судоку, в котором проставлено 80 цифр из 81?

 Профиль  
                  
 
 
Сообщение22.04.2007, 11:15 


21/04/07
7
Спорность тезиса о том, зависит ли сложность судоку от количества проставленных цифр, легко проверить. Попробуйте решить судоку, названный Lion достаточно сложным (в нем проставлено всего 22 цифры) и судоку, названный "наш ответ Чемберлену" (в нем проставлено 27 цифр). Первое решается элементарно, со вторым надо помучиться.

Добавлено спустя 6 минут 52 секунды:

судоку Lion решается без перебора вариантов, без всяких ответвлений.

Добавлено спустя 22 минуты 45 секунд:

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

 Профиль  
                  
 
 
Сообщение22.04.2007, 12:17 
Заслуженный участник
Аватара пользователя


26/11/06
696
мехмат
Ну что ж, ГБ, а вот это тоже решите без перебора вариантов?

$$\begin{array}{ccc|ccc|ccc}
*&*&*&*&*&*&*&2&1\\
4&*&*&6&*&*&*&*&*\\
*&*&*&*&*&*&*&*&*\\
\hline
*&*&*&*&1&2&9&*&*\\
7&*&6&*&*&*&*&*&2\\
*&*&*&*&3&*&*&*&*\\
\hline
5&1&*&*&*&*&*&3&*\\
*&*&*&8&*&7&6&*&*\\
*&2&*&*&*&*&*&*&*\\\end{pmatrix}$$

 Профиль  
                  
 
 
Сообщение22.04.2007, 13:27 


21/04/07
7
[quote="Lion"]Ну что ж, ГБ, а вот это тоже решите без перебора вариантов?

Решили, это не сложно.

 Профиль  
                  
 
 
Сообщение22.04.2007, 21:43 


21/04/07
7
кто-нибудь входит в другие форумы любителей судоку?

 Профиль  
                  
 
 
Сообщение25.04.2007, 02:44 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Lion писал(а):
Ну что ж, ГБ, а вот это тоже решите без перебора вариантов?

Да, это тоже решается. Lion, большое спасибо! Изящная, хотя и не очень сложная судоку. Я уверен, что на ее композицию ушло заметное количество усилий.

P.S. Я готов привести ход решения без перебора, если это интересно кому-либо.

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

 Профиль  
                  
 
 
Сообщение26.04.2007, 19:06 


21/04/07
7
согласна, что лучшие судоку - без явных переборов.

 Профиль  
                  
 
 
Сообщение17.05.2007, 14:52 
Аватара пользователя


15/11/06
2689
Москва Первомайская
Сегодня в метро видел, как судоку разгадывает немолодой мужчина, по виду вполне возможно, что доктор наук. В начальной расстановке у него 24 цифры и, что необычно, два квадрата из девяти - пустые. Не знаю, сложная эта судоку или, наоборот, очень простая, но непохоже, судя по скорости, что он ее разгадает даже за час... И хочу спросить, какое максимальное число пустых квадратов может быть в судоку? Два я вот видел. Три наверное тоже может быть. А больше может быть?

 Профиль  
                  
 
 
Сообщение20.05.2007, 18:45 


21/04/07
7
кто может подсказать, что такое симметрия и ассиметрия в судоку?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 78 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group