Sudoku

[moog]

Возможно ли решение основываясь исключительно на вычислениях, то есть без угадывания? Навеяно игрой на уровне hardest в ksudoku.

[nerezus]

Хм. имхо рекурсивно только...

[moog]

Так там практически всегда несколько вариантов, как же быть?)

[moog]

Эх, а ведь хорошая игра-то...)

[VoidExp]

Так там практически всегда несколько вариантов, как же быть?)

А вы попробуйте версию для портативной плэйстэйшн от сони (Go Sudoku), там можно добавить временно какие-нибудь числа, типа если вы не уверены между 1 и 9, кнопкой O нажимаете соответственно на 1 и на 9, они добавляются как маленькие числа в квадратике... Потом когда находите другие числа ряда, и когда становится видно что это точно не 1 или не 9, то тогда кнопкой X выбираете нужное число... Что-то похожее есть??

[Linston]

А вы попробуйте версию для портативной плэйстэйшн от сони (Go Sudoku), там можно добавить временно какие-нибудь числа, типа если вы не уверены между 1 и 9, кнопкой O нажимаете соответственно на 1 и на 9, они добавляются как маленькие числа в квадратике... Потом когда находите другие числа ряда, и когда становится видно что это точно не 1 или не 9, то тогда кнопкой X выбираете нужное число... Что-то похожее есть??

Так вроде бы такое есть в Sudoku, который в составе gnome-games 2.18.*

[broom]

В LinuxFormate когда-то был конкурс программ для решения судоку. Там, собственно, решение находилось программой методом вычислений.

[moog]

Спасибо, а номер не подскажешь?

[broom]

Спасибо, а номер не подскажешь?

результаты вот в этом - http://linuxformat.ru/anons76.phtml
там на диске программы лежат.

[moog]

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

[Michael]

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

Что-то типа такого:
1) Перебираем подряд все цифры.
2) Для каждого положения выбранной цифры на доске вычеркиваем клетки горизонтальной и вертикальной линий, на которых находится наша цифра, а также клетки квадрата с ней.
3) Поле шага 2 проверяем, нет ли на доске линий или квадратов с одной невычеркнутой позицией. Если есть, ставим туда нашу цифру и повторяем шаг 2. Если нет, берём следующую цифру и опять делаем пункт 2.
4) Перебрав все цифры, начинаем сначала.

Тупо, но действенно. Пользовался ksudoku, там клёвый интерфейс для шага 2.

[moog]

Спасибо).

[MrSinister]

Это баг? Когда неправильно, подсвечивает красным, но тут уже 3 шестёрки. Я правила то читал давно и не помню, чтобы была такая особенность.
версия 2.28.2

[MrSinister]

GNOME Sudoku 2.30.1
Видимо, пофиксили. тестил тестил, шестёрки не реплицируются больше, подствечиваются красным. это так, может пригодится :D