SUDOKU
4596
11
Picaro
гундос
Есть такая игруха sudoku. Да знаете, в газетах в кроссвордах часто стали печатать: есть поле 9*9, разделенное на квадраты 3*3, надо расставить цифры от 1 до 9 так, чтобы в квадрате 3*3, на горизонтали и вертикали не было повторяющихся цифр.
Вот задумал нарисовать для себя такую на компе (в газете скучно). Алгоритм генерации карты сделал, ничего сложного в нем нет. А вот теперь стоит задача закрыть (или открыть) цифры, чтобы был единственный путь решения. Словами коряво получается объяснить... Попробую... Надо закрыть ячейки так, чтобы "вычислялась" однозначно лишь пара-тройка, а при открытии одной "вычислялась" другая, то есть выстраивалась последовательная цепочка ходов, приводящая к решению.
Простым рандомом открывать ячейки хреново - возникает масса неоднозначностей, что половину поля можно тупо открыть от фанаря, а судока все равно складывается, не интересно получается.
Мож, кто сталкивался или сам делал подобное?
Вот задумал нарисовать для себя такую на компе (в газете скучно). Алгоритм генерации карты сделал, ничего сложного в нем нет. А вот теперь стоит задача закрыть (или открыть) цифры, чтобы был единственный путь решения. Словами коряво получается объяснить... Попробую... Надо закрыть ячейки так, чтобы "вычислялась" однозначно лишь пара-тройка, а при открытии одной "вычислялась" другая, то есть выстраивалась последовательная цепочка ходов, приводящая к решению.
Простым рандомом открывать ячейки хреново - возникает масса неоднозначностей, что половину поля можно тупо открыть от фанаря, а судока все равно складывается, не интересно получается.
Мож, кто сталкивался или сам делал подобное?
задача нетривиальная, требует знания предмета 
пытался разгадать судоку однажны - пришел к выводу, что разгадывать её нужно именно методом перебора - по всем линиям выходило не менее трех-четырех вариантов в каждой клетке, соответственно решать её можно было только прямым перебором (в процессе которого количество вариантов не уменьшалось, как требовал интеллект, а тупо росло в геометрической прогресии)... м.б. судока некачественная попалась...
м.б. обсуждению поможет пример качественной (красивой) судоки ?
пытался разгадать судоку однажны - пришел к выводу, что разгадывать её нужно именно методом перебора - по всем линиям выходило не менее трех-четырех вариантов в каждой клетке, соответственно решать её можно было только прямым перебором (в процессе которого количество вариантов не уменьшалось, как требовал интеллект, а тупо росло в геометрической прогресии)... м.б. судока некачественная попалась...
м.б. обсуждению поможет пример качественной (красивой) судоки ?
Красивую судоку надо? Пожалуйте /нули - пустые клетки/:
130 070 000
000 000 008
000 009 405
800 000 000
000 060 100
004 000 029
008 310 000
400 000 000
007 000 604
Эта судока решается очень красиво за... у меня ушло 2 минуты 49 секунд
130 070 000
000 000 008
000 009 405
800 000 000
000 060 100
004 000 029
008 310 000
400 000 000
007 000 604
Эта судока решается очень красиво за... у меня ушло 2 минуты 49 секунд
Логически эта судока решается так:
1. однозначно открываются последовательно четверки в клетках (строка/столбец): 2/2, 7/6, 4/5, 1/4, 5/8
2. единицы: 8/9, 9/2, 4/3
3. восьмерки: 1/6, 3/2
4. пятерка: 1/3
И так делее...
Как видно из примера, каждый ход приводит к возможности однозначного открытия одной или нескольких клеток, в которых до этого была неоднозначность.
Так вот задача ставится в поиске такого алгоритма закрытия или открытия ячеек сгенерированной карты, чтобы изначально было пара-тройка однозначных вариантов, и каждый из них приводил бы к появлению следующего однозначного варианта. Простой рандом, как я говорил, дает такие судоки, где можно от фанаря открыть кучу ячеек, прежде чем появится такая однозначная цепочка ходов.
зы определение: однозначный вариант - либо в клетке может стоять только одна единственная некоторая цифра, либо в квадрате-вертикали-горизонтали некоторая цифра может стоять только в одном месте
1. однозначно открываются последовательно четверки в клетках (строка/столбец): 2/2, 7/6, 4/5, 1/4, 5/8
2. единицы: 8/9, 9/2, 4/3
3. восьмерки: 1/6, 3/2
4. пятерка: 1/3
И так делее...
Как видно из примера, каждый ход приводит к возможности однозначного открытия одной или нескольких клеток, в которых до этого была неоднозначность.
Так вот задача ставится в поиске такого алгоритма закрытия или открытия ячеек сгенерированной карты, чтобы изначально было пара-тройка однозначных вариантов, и каждый из них приводил бы к появлению следующего однозначного варианта. Простой рандом, как я говорил, дает такие судоки, где можно от фанаря открыть кучу ячеек, прежде чем появится такая однозначная цепочка ходов.
зы определение: однозначный вариант - либо в клетке может стоять только одна единственная некоторая цифра, либо в квадрате-вертикали-горизонтали некоторая цифра может стоять только в одном месте
пришел к выводу, что разгадывать её нужно именно методом перебора - по всем линиям выходило не менее трех-четырех вариантов в каждой клетке, соответственно решать её можно было только прямым перебором (в процессе которого количество вариантов не уменьшалось, как требовал интеллект, а тупо росло в геометрической прогресии)... м.б. судока некачественная попалась...Т.е., по Вашему, качественно и красиво - это когда тупо и быстро просчитываются все варианты?
Вообще-то, в Судоку, насколько я припоминаю, есть много уровней сложности.
На простейшем уровне, можно решить за пару остановок, пока едешь в метро. На самых сложных - у меня интеллекта не хватало...
Как в любой игре - соперник должен быть ненамного лучше, ненамного хуже, иначе будет неинтересно. И уровень интеллекта у всех разный.
Мне за 2 мин. - неинтересно и некрасиво
Подбирайте себе Судоку по Вашему уровню
В судоку есть очень красивые способы решения.. Нифига на первый взгляд непонятные.Сам люблю залипать на самой высокой сложности, пусть долго, зато интереснее, чем тупо смотреть в каких рядах/строках есть одна и та же цифра.
по всем линиям выходило не менее трех-четырех вариантов в каждой клеткеВот это я называю интересной задачей.
Вариант решения судоку может быть не единственным... я сама наталкивалась несколько раз, когда можно было поставить в клетку одну цифру из возможных двух, а можно и другую, и сойдётся.
Причём, от сложности это не сильно зависело.
На мой взгляд, интереснее задача составлять правильную судоку, а не решать её.
Но могу ошибаться...
Причём, от сложности это не сильно зависело.
На мой взгляд, интереснее задача составлять правильную судоку, а не решать её.
Но могу ошибаться...
Сейчас читают
ФОТОБАРАХОЛКА (часть 2)
505578
1000
Дозор гостевой
105061
1000
Красивые и счастливые мамочки форева! )) (часть 44)
227876
1000
Да, это тоже любопытно
Тут чистым рандомом не отделаешься имхо.
Тут чистым рандомом не отделаешься имхо.На последнего.
Эта задача как раз из области искусственного интеллекта. Что касается решения, то прямой перебор вариантов тут крайне неэффективен особенно если изначально заполнено мало клеточек. Чтобы отсекать лишние вариантынеобходимы эвристики. Откуда их взять - ну, порешать довольно много самому, и тогда можно что-то сформулировать. Лично я для себя придумал несколько таких, которыми пользуюсь при ручном решении.
Что же касается составления задач, то, возможно, лучший подход - сначала попытаться вручную составлять задачи (и, к примеру, предлагать их для решения окружающим). После сотни-другой задач у Вас уже сформируются какие-то типовые подходы, где как можно поступить. Пробуйте.
Эта задача как раз из области искусственного интеллекта. Что касается решения, то прямой перебор вариантов тут крайне неэффективен особенно если изначально заполнено мало клеточек. Чтобы отсекать лишние вариантынеобходимы эвристики. Откуда их взять - ну, порешать довольно много самому, и тогда можно что-то сформулировать. Лично я для себя придумал несколько таких, которыми пользуюсь при ручном решении.
Что же касается составления задач, то, возможно, лучший подход - сначала попытаться вручную составлять задачи (и, к примеру, предлагать их для решения окружающим). После сотни-другой задач у Вас уже сформируются какие-то типовые подходы, где как можно поступить. Пробуйте.
3-4 года назад делал программку для нахождения решения судоку 9x9. Решение было основано на рекурсии. С её помощью решение "газетной" судоку не занимало более секунды. А вот с определением минимального набора чисел на поле, для которого существует однозначное решение - задача сложнее.
Допустим, есть поле, с начальным набором цифр. Начальное поле можно задать случайным образом, избегая нарушений правил. Далее производить проверку всех клеток поля на количество возможных вариантов. Проверку осуществлять по формализованным правилам. Клетку, где вариант единственный - оставить скрытой, где вариантов несколько - определить случайным числом из возможных. После каждой итерации - находить решение.
Допустим, есть поле, с начальным набором цифр. Начальное поле можно задать случайным образом, избегая нарушений правил. Далее производить проверку всех клеток поля на количество возможных вариантов. Проверку осуществлять по формализованным правилам. Клетку, где вариант единственный - оставить скрытой, где вариантов несколько - определить случайным числом из возможных. После каждой итерации - находить решение.