Дано:


Нужно расставить цифры от 1 до 9 в ячейках так, что бы в каждом ряду и каждой строке присутствовала каждая цифра (от 1 до 9) + в каждом из 9 квадратиков по-меньше присутствовали тоже все цифры (от 1 до 9)
Подскажите, какой путь решения для подобных задач. Хочу прогу написать.

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

G>Дано:
G>

G>Нужно расставить цифры от 1 до 9 в ячейках так, что бы в каждом ряду и каждой строке присутствовала каждая цифра (от 1 до 9) + в каждом из 9 квадратиков по-меньше присутствовали тоже все цифры (от 1 до 9)
G>Подскажите, какой путь решения для подобных задач. Хочу прогу написать.
Эта игра называется СУДОКУ (SUDOKU). Поиск рулит. А способ решения — backtracking, IMHO.

Простейший brute force прекрасно решает задачу. Выбираем
строку/столбец/клетку с минимальным количеством незаполненных квадратов и в
первую попавшуюся клетку подставляем все числа от 1 до 9 по порядку,
проверяем на валидность строку, столбец и клетку и уходим в рекурсию. Даже
debug версия решает сложную задачу за пренебрежимо малое время.

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

G>Подскажите, какой путь решения для подобных задач. Хочу прогу написать.

Решение почти "в лоб" (совсем в лоб — это перебором).

Кодируем числа от 1 до 9 разными простыми числами. Например так:
1 -> 1
2 -> 2
3 -> 3
4 -> 5
5 -> 7
6 -> 11
7 -> 13
8 -> 17
9 -> 19

Обозначаем клетки в ячейках как Xij, где i — строка, j — столбец. Значения некоторых известны, некоторые надо найти.

Сумма (закодированных) чисел от 1 до 9 = 78.

Записываем задачу линейного программирования с 27-ю уравнениями вида:
Xi1+Xi2+...+Xi9 = 78 — для строк
...
X1j+X2j+...+X9j = 78 — для столбцов
...
X11+X12+X13+X21+X22+X23+X31+X32+X33 = 78 — для "субквадратиков"
...

и с неравенствами вида
Xij <= 19.

Дальше решаем задачу линейного программирования — как раз один из способов эффективно засрать ресурсы процессора, там все методы решения итеративные.

Есть доп. условия — все числа простые, но средствами линейного программирования это задать, придётся проверять получаемые решения и выкидывать неподходящие.

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

Есть решение проще. Я верю в это.

Ох, позор на мою седую голову, совсем забыл что задачи ЛП — на минимизацию целевой функции и что тут она не в тему. Каких-то шесть лет не трогаешь знания — и всё, прощай.

Ну так или иначе 27 уравнений, кучка неравенств — вся мощь математики к твоим услугам.

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

Интересное предложение =)

Только вот как именно это и решать: ?

T>Дальше решаем задачу линейного программирования — как раз один из способов эффективно засрать ресурсы процессора, там все методы решения итеративные.

Вот нарисовал...
вроде даже работает =)

http://grog.homeip.net/sudoku.exe [23kB]
или тут
http://kyra.spb.ru/sudoku.exe [23kb]

P.S. Вообще мое первое приложение на .NET