Друзья,

Подскажите, пожалуйста, алгоритм заполнения поля судоку. Алгоритмы решения я знаю, а вот про заполнение поля нигде не встречал.
Я сам написал пару вариантов, но один из них генерит не достаточно случайные поля, а другой — случайные, но не всегда решаемые (т.е. иногда остаётся 1-3 ячейки, в которые не вставить никакую цифру).

Спасибо!

Здравствуйте, 0x656b694d, Вы писали:

0>Подскажите, пожалуйста, алгоритм заполнения поля судоку. Алгоритмы решения я знаю, а вот про заполнение поля нигде не встречал.

Сразу два вопроса.
1. Нужно заполнить "поле-ответ" или поле, на котором оставлены только цифры, нужные для отгадывания? В первом случае все существенно проще.
2. Нужно генерировать только классические судоку (9*9) или произвольные? Уже для 16*16 тупой алгоритм генерации (с возвратами) работает довольно долго — приходится возвращаться тысячи раз.

А тупой алгоритм такой: заполняем поле построчно, слева направо. Для каждой клетки генерируем множество кандидатов, которые с учетом уже поставленных чисел можно записать в эту клетку. Наугад выбираем одного, пробуем достроить поле. Если не получилось, берем наугад другого кандидата. Если кандидаты закончились, сообщаем "наверх", что построить не удалось. Продолжаем, пока не заполнится все поле.

C>1. Нужно заполнить "поле-ответ" или поле, на котором оставлены только цифры, нужные для отгадывания? В первом случае все существенно проще.
Да, второе — поле для отгадывания.

C>2. Нужно генерировать только классические судоку (9*9) или произвольные? Уже для 16*16 тупой алгоритм генерации (с возвратами) работает довольно долго — приходится возвращаться тысячи раз.
Хотелось бы произвольные.

C>А тупой алгоритм такой: заполняем поле построчно, слева направо. Для каждой клетки генерируем множество кандидатов, которые с учетом уже поставленных чисел можно записать в эту клетку. Наугад выбираем одного, пробуем достроить поле. Если не получилось, берем наугад другого кандидата. Если кандидаты закончились, сообщаем "наверх", что построить не удалось. Продолжаем, пока не заполнится все поле.

Значит, с возвратами. Это как раз мой второй вариант.
А может есть менее "тупой"?

Спасибо!

Здравствуйте, 0x656b694d, Вы писали:

0>Значит, с возвратами. Это как раз мой второй вариант.
0>А может есть менее "тупой"?

Да вроде бы нету.

Вообще, соображения такие: порождаем "поле-ответ", после чего начинаем случайным образом вычеркивать клетки. После каждого вычеркивания проверяем, решается ли полученная конструкция единственным образом. Кстати, здесь можно добавить интересную штуку: при решении пользоваться либо перебором, либо только логическим выводом — так можно будет управлять сложностью результата.

Между делом нашласьполезная ссылка (раздел "Generating Puzzles")

Товарищ Америки не открыл, все расписано примерно так, как я и предложил. И, сдается мне, что такая конструкция будет тормозить на крупных полях.

Здравствуйте, conraddk, Вы писали:

C>Вообще, соображения такие: порождаем "поле-ответ", после чего начинаем случайным образом вычеркивать клетки. После каждого вычеркивания проверяем, решается ли полученная конструкция единственным образом. Кстати, здесь можно добавить интересную штуку: при решении пользоваться либо перебором, либо только логическим выводом — так можно будет управлять сложностью результата.

ага


C>Между делом нашласьполезная ссылка (раздел "Generating Puzzles")

C>Товарищ Америки не открыл, все расписано примерно так, как я и предложил. И, сдается мне, что такая конструкция будет тормозить на крупных полях.

Класс!

> Подскажите, пожалуйста, алгоритм заполнения поля судоку. Алгоритмы решения
> я знаю, а вот про заполнение поля нигде не встречал.
> Я сам написал пару вариантов, но один из них генерит не достаточно
> случайные поля, а другой — случайные, но не всегда решаемые (т.е. иногда
> остаётся 1-3 ячейки, в которые не вставить никакую цифру).
>

по самой игре на топкодере недавно решалось (соревнования на скорость)
http://www.topcoder.com/longcontest/?module=Static&d1=match_editorials&d2=intel_mtcs_2