Решение Судоку

@HeddinG · Регистрация: 23.06.2009

Студворк — интернет-сервис помощи студентам

Здравствуйте!

Заранее извеняюсь за повтор, писал такую тему в алгоритмах, но там глухо

Интересует алгоритм для программы, которая решает Судоку. Те, что обсуждались тут - не подходят. Мне ненравиться программа которая вылетает если однозначных вариантов подстановки нет.
Знаю, что нужна рекурсия, попытался написать, но мало что получилось (С++):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
bool Sudoku::Anser ()
{
        if (
                Calculation(0,0) && Calculation(0,1) && Calculation(0,2) && Calculation(0,3) && Calculation(0,4) && Calculation(0,5) && Calculation(0,6) && Calculation(0,7) && Calculation(0,8) &&
                Calculation(1,0) && Calculation(1,1) && Calculation(1,2) && Calculation(1,3) && Calculation(1,4) && Calculation(1,5) && Calculation(1,6) && Calculation(1,7) && Calculation(1,8) &&
                Calculation(2,0) && Calculation(2,1) && Calculation(2,2) && Calculation(2,3) && Calculation(2,4) && Calculation(2,5) && Calculation(2,6) && Calculation(2,7) && Calculation(2,8) &&
                Calculation(3,0) && Calculation(3,1) && Calculation(3,2) && Calculation(3,3) && Calculation(3,4) && Calculation(3,5) && Calculation(3,6) && Calculation(3,7) && Calculation(3,8) &&
                Calculation(4,0) && Calculation(4,1) && Calculation(4,2) && Calculation(4,3) && Calculation(4,4) && Calculation(4,5) && Calculation(4,6) && Calculation(4,7) && Calculation(4,8) &&
                Calculation(5,0) && Calculation(5,1) && Calculation(5,2) && Calculation(5,3) && Calculation(5,4) && Calculation(5,5) && Calculation(5,6) && Calculation(5,7) && Calculation(5,8) &&
                Calculation(6,0) && Calculation(6,1) && Calculation(6,2) && Calculation(6,3) && Calculation(6,4) && Calculation(6,5) && Calculation(6,6) && Calculation(6,7) && Calculation(6,8) &&
                Calculation(7,0) && Calculation(7,1) && Calculation(7,2) && Calculation(7,3) && Calculation(7,4) && Calculation(7,5) && Calculation(7,6) && Calculation(7,7) && Calculation(7,8) &&
                Calculation(8,0) && Calculation(8,1) && Calculation(8,2) && Calculation(8,3) && Calculation(8,4) && Calculation(8,5) && Calculation(8,6) && Calculation(8,7) && Calculation(8,8)
                )
                return true;
//      Add (pole_tmp);
        return false;
}
bool Sudoku::Calculation (int I, int K, int C)
{
        if (pole_tmp[i][K])
                return true;
        if (!Verification(I,K,C))       // Перебераються возможные цифры для поля
        {
                if (C<9)
                        Calculation (I,K,C+1);
                else
                        return false;
        }
        else
        {
                pole[i][K]=C;
                return true;
        }
}
bool Sudoku::Verification(int I, int K, int C)
{
        //----------------------- проверка совпадений по вертикали
        for (int i=I+1;i<9;i++)
        {
                if (pole[i][K]==C)
                        return false;
        }
        for (int ii=I-1;ii>=0;ii--)
        {
                if (pole[ii][K]==C)
                        return false;
        }
        //----------------------- проверка совпадений по горизонтали
        for (int k=K+1;k<9;k++)
        {
                if (pole[i][k]==C)
                        return false;
        }
        for (int kk=K-1;kk>=0;kk--)
        {
                if (pole[i][kk]==C)
                        return false;
        }
        return true;
}

Нашел кое-что у Д.Кнута - Dancing Links (http://www.sudopedia.org/wiki/Dancing_Links).
Но там англ, для меня это сложновато

Если кто сталкивался - напишите плз хотя-бы алгоритм.

@ISergey · 25.06.2009, 00:08

Суть так и не понял, но покоду
это

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool Sudoku::Anser ()
{
        if (
                Calculation(0,0) && Calculation(0,1) && Calculation(0,2) && Calculation(0,3) && Calculation(0,4) && Calculation(0,5) && Calculation(0,6) && Calculation(0,7) && Calculation(0,8) &&
                Calculation(1,0) && Calculation(1,1) && Calculation(1,2) && Calculation(1,3) && Calculation(1,4) && Calculation(1,5) && Calculation(1,6) && Calculation(1,7) && Calculation(1,8) &&
                Calculation(2,0) && Calculation(2,1) && Calculation(2,2) && Calculation(2,3) && Calculation(2,4) && Calculation(2,5) && Calculation(2,6) && Calculation(2,7) && Calculation(2,8) &&
                Calculation(3,0) && Calculation(3,1) && Calculation(3,2) && Calculation(3,3) && Calculation(3,4) && Calculation(3,5) && Calculation(3,6) && Calculation(3,7) && Calculation(3,8) &&
                Calculation(4,0) && Calculation(4,1) && Calculation(4,2) && Calculation(4,3) && Calculation(4,4) && Calculation(4,5) && Calculation(4,6) && Calculation(4,7) && Calculation(4,8) &&
                Calculation(5,0) && Calculation(5,1) && Calculation(5,2) && Calculation(5,3) && Calculation(5,4) && Calculation(5,5) && Calculation(5,6) && Calculation(5,7) && Calculation(5,8) &&
                Calculation(6,0) && Calculation(6,1) && Calculation(6,2) && Calculation(6,3) && Calculation(6,4) && Calculation(6,5) && Calculation(6,6) && Calculation(6,7) && Calculation(6,8) &&
                Calculation(7,0) && Calculation(7,1) && Calculation(7,2) && Calculation(7,3) && Calculation(7,4) && Calculation(7,5) && Calculation(7,6) && Calculation(7,7) && Calculation(7,8) &&
                Calculation(8,0) && Calculation(8,1) && Calculation(8,2) && Calculation(8,3) && Calculation(8,4) && Calculation(8,5) && Calculation(8,6) && Calculation(8,7) && Calculation(8,8)
                )
                return true;
//      Add (pole_tmp);
        return false;
}

лучше заменить на вот это

C++
1
2
3
4
5
6
7
8
bool Sudoku::Anser ()
{
    for(int i = 0; i < 9; ++i)
        for(int j = 0; j < 9; ++j)
            if(! Calculation(i,j) )
                return false;
    return true;
}

@HeddinG · 25.06.2009, 09:41 **[ТС]**

Спасибо, самому ненравилась эта часть. А что на счет алгоритма, никто так и не знает ?

Evg · 25.06.2009, 12:07

Как-то писал программу. Если интересно - могу кинуть исходник.

Только сразу предупреждаю - работал под gcc, а потом это просто набор исходников, в проект их самом загонять надо будет. Ну и пытался программу сделать универсальной: она сделана как математическая абстракция, т.е. не привязана к квадратной форме поля. А квадратная форма рассматривается как частный случай.

@HeddinG · 25.06.2009, 14:51 **[ТС]**

Интересно! Буду благодарен.

Evg · 25.06.2009, 14:54

Вечером тогда скину, а то на работу по ходу я не притаскивал

Evg · 25.06.2009, 20:49

Выкладываю два архива. sudoku_w.rar - для тебя (в виндовой кодировке), sudoku.rar - для меня (в koi-8) на тот случай, если возникнут вопросы

Вкратце. Программа разбита на две чати. Решалка отдельно, пользовательский интерфейс для ввода и вывода отдельно. Для тебя нужно просто скомпилять все исходники из каталогов solver и ui_example_classic. Решение начинается в rule.c в процедуре rule_make_resolve_task, там последовательно запускаются 4 алгортима разной сложности (когда я писал прогу, в итоге не нашёл ни одной задачи, которой бы этих 4 правил было недостаточно). Если в файле debug.h значение макроса DEBUG выставить в 1, то процесс решения будет печататься на экране

@HeddinG · 25.06.2009, 21:53 **[ТС]**

Большое спасибо.

@Volkman · 26.01.2010, 22:21

привет. у меня такой вопрос, скачал то, что ты выложил, но ничего не компилится - gcc выдает до фига ошибок.. можешь описать точно, что нужно сделать? я под линуксом..

Evg · 26.01.2010, 22:25

Так ты хоть покажи, куда ты нажимал и что тебе выдало в ответ

@Volkman · 26.01.2010, 22:33

Кликните здесь для просмотра всего текста

Volkman:~/Programs/C/sudoku/solver> gcc *.c
/usr/lib64/gcc/x86_64-suse-linux/4.4/../../../../lib64/crt1.o: In function `_start':
/usr/src/packages/BUILD/glibc-2.10.1/csu/../sysdeps/x86_64/elf/start.S:109: undefined reference to `main'
/tmp/cc8m9VEu.o: In function `process_areas_after_resolve':
resolve.c:(.text+0x92): undefined reference to `area_get_area'
resolve.c:(.text+0xa9): undefined reference to `area_is_field_in_area'
resolve.c:(.text+0xf4): undefined reference to `area_num_areas'
/tmp/ccqGmy02.o: In function `rule_make_resolve_task':
rule.c:(.text+0x14b): undefined reference to `area_check_all_areas'
/tmp/cckLQjOD.o: In function `rule_exclude':
rule_exclude.c:(.text+0x1fa): undefined reference to `area_get_area'
rule_exclude.c:(.text+0x22d): undefined reference to `area_num_areas'
/tmp/cciaMMxx.o: In function `mark_fields_by_locale_set':
rule_overlap.c:(.text+0xb3): undefined reference to `area_get_area'
rule_overlap.c:(.text+0xca): undefined reference to `area_is_set_in_area'
rule_overlap.c:(.text+0x134): undefined reference to `area_num_areas'
/tmp/cciaMMxx.o: In function `rule_overlap':
rule_overlap.c:(.text+0x169): undefined reference to `area_get_area'
rule_overlap.c:(.text+0x1aa): undefined reference to `area_num_areas'
/tmp/ccya0lLd.o: In function `rule_single':
rule_single.c:(.text+0x87): undefined reference to `area_get_area'
rule_single.c:(.text+0xba): undefined reference to `area_num_areas'
/tmp/cc48AHcy.o: In function `task_init_task':
task.c:(.text+0x14): undefined reference to `area_init'
/tmp/cc48AHcy.o: In function `task_finish_task':
task.c:(.text+0x29): undefined reference to `area_finish'
/tmp/ccMrjTOo.o: In function `user_create_area':
user.c:(.text+0x5b6): undefined reference to `area_new_area'
/tmp/ccMrjTOo.o: In function `user_add_area_field':
user.c:(.text+0x5fa): undefined reference to `area_num_areas'
user.c:(.text+0x693): undefined reference to `area_get_area'
user.c:(.text+0x69e): undefined reference to `area_add_field'
collect2: ld returned 1 exit status

я видимо просто не понимаю, что значит " просто скомпилять все исходники из каталогов solver и ui_example_classic." или не знаю, какие библиотеки нужно еще подключать к gcc..

Evg · 26.01.2010, 22:43

Там есть файл "R", его и надо запускать. ТОлько сделать исполняемым (если через винду разархивировал). В общем-то строка запуска в нём зашита

Code
1
2
$ chmod +x R
$ ./R

Только отредактируй файл R, чтобы там был вариант классического судоку. Фрагмент кода должен выглядеть так:

Code
1
2
3
4
5
# Выбираем пользовательский модуль
UI=$UI_EXAMPLE_CLASSIC
#UI=$UI_EXAMPLE_JUMPER
#UI=$UI_EXAMPLE_UAREA
#UI=$UI_TEST

@Volkman · 26.01.2010, 23:30

Теперь вот:

Кликните здесь для просмотра всего текста

/Programs/C/sudoku> ./R
+ gcc -O3 -Wall -Werror -I. solver/task.c solver/field.c solver/set.c solver/area.c solver/jumper.c solver/resolve.c solver/maybe.c solver/rule.c solver/rule_one.c solver/rule_single.c solver/rule_overlap.c solver/rule_exclude.c solver/rule_jumper.c solver/stub.c solver/user.c solver/debug.c ui_example_uarea/ui_example_uarea.c
gcc: solver/area.c: Нет такого файла или каталога
Volkman@linux-wu9u:~/Programs/C/sudoku> chmod +x R
Volkman@linux-wu9u:~/Programs/C/sudoku> ./R
+ gcc -O3 -Wall -Werror -I. solver/task.c solver/field.c solver/set.c solver/area.c solver/jumper.c solver/resolve.c solver/maybe.c solver/rule.c solver/rule_one.c solver/rule_single.c solver/rule_overlap.c solver/rule_exclude.c solver/rule_jumper.c solver/stub.c solver/user.c solver/debug.c ui_example_classic/ui_example_classic.c
gcc: solver/area.c: Нет такого файла или каталога

Evg · 26.01.2010, 23:41

> gcc: solver/area.c: Нет такого файла или каталога

Всё же по русски написано. У тебя нормально архив-то распаковался? Если зайти в каталог sudoku и набрать в нём "ls -l ; ls -l *", то что напишет?

@Volkman · 26.01.2010, 23:47

Спасибо =) Сам не заметил почему-то - совсем уже после сессии мозги никакие..

@PointsEqual · 27.01.2010, 03:18

вот тут www.deco.tu2.ru есть исходник программы, которая решает судоку, только она на делфи, но думаю переделать не сложно будет

@K17 · 08.02.2011, 00:37

мое решение на Java: http://sites.google.com/site/sudokujavasolution/

@dipic · 27.02.2011, 16:02

Можете помочь. Я так понимаю у кого то можно взять готовый код? Не поможете??

Evg · 27.02.2011, 16:11

Сообщение от dipic

Можете помочь. Я так понимаю у кого то можно взять готовый код? Не поможете??

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

@dipic · 27.02.2011, 16:17

Я с гугла сразу на 2-ю страничку попал %) невнимателен.

Добавлено через 3 минуты
Evg,
А как можно получить код, если у меня Вижуал Студия 2008-я .. ?

Новые блоги и статьи Все статьи Все блоги /
Видеокарта простаивает ночами? Вот 4 проекта, которые загрузят её наукой Programma_Boinc 10.04.2026 Видеокарта простаивает ночами? Вот 4 проекта, которые загрузят её наукой Если на Windows стоит дискретная NVIDIA или AMD — можно отдать её вычислительную мощность реальным исследованиям. . . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .

@HeddinG 0 / 0 / 0 Регистрация: 23.06.2009 Сообщений: 16
	25.06.2009, 09:41 [ТС]
	Спасибо, самому ненравилась эта часть. А что на счет алгоритма, никто так и не знает ? 0

Evg 21281 / 8305 / 637 Регистрация: 30.03.2009 Сообщений: 22,660 Записей в блоге: 30
	25.06.2009, 12:07
	Как-то писал программу. Если интересно - могу кинуть исходник. Только сразу предупреждаю - работал под gcc, а потом это просто набор исходников, в проект их самом загонять надо будет. Ну и пытался программу сделать универсальной: она сделана как математическая абстракция, т.е. не привязана к квадратной форме поля. А квадратная форма рассматривается как частный случай. 0

@HeddinG 0 / 0 / 0 Регистрация: 23.06.2009 Сообщений: 16
	25.06.2009, 14:51 [ТС]
	Интересно! Буду благодарен. 0

Evg 21281 / 8305 / 637 Регистрация: 30.03.2009 Сообщений: 22,660 Записей в блоге: 30
	25.06.2009, 14:54
	Вечером тогда скину, а то на работу по ходу я не притаскивал 0

@HeddinG 0 / 0 / 0 Регистрация: 23.06.2009 Сообщений: 16
	25.06.2009, 21:53 [ТС]
	Большое спасибо. 0

@Volkman 0 / 0 / 0 Регистрация: 26.01.2010 Сообщений: 4
	26.01.2010, 22:21
	привет. у меня такой вопрос, скачал то, что ты выложил, но ничего не компилится - gcc выдает до фига ошибок.. можешь описать точно, что нужно сделать? я под линуксом.. 0

Evg 21281 / 8305 / 637 Регистрация: 30.03.2009 Сообщений: 22,660 Записей в блоге: 30
	26.01.2010, 22:25
	Так ты хоть покажи, куда ты нажимал и что тебе выдало в ответ 0

@Volkman 0 / 0 / 0 Регистрация: 26.01.2010 Сообщений: 4
	26.01.2010, 22:33
	Кликните здесь для просмотра всего текста Volkman:~/Programs/C/sudoku/solver> gcc *.c /usr/lib64/gcc/x86_64-suse-linux/4.4/../../../../lib64/crt1.o: In function `_start': /usr/src/packages/BUILD/glibc-2.10.1/csu/../sysdeps/x86_64/elf/start.S:109: undefined reference to `main' /tmp/cc8m9VEu.o: In function `process_areas_after_resolve': resolve.c:(.text+0x92): undefined reference to `area_get_area' resolve.c:(.text+0xa9): undefined reference to `area_is_field_in_area' resolve.c:(.text+0xf4): undefined reference to `area_num_areas' /tmp/ccqGmy02.o: In function `rule_make_resolve_task': rule.c:(.text+0x14b): undefined reference to `area_check_all_areas' /tmp/cckLQjOD.o: In function `rule_exclude': rule_exclude.c:(.text+0x1fa): undefined reference to `area_get_area' rule_exclude.c:(.text+0x22d): undefined reference to `area_num_areas' /tmp/cciaMMxx.o: In function `mark_fields_by_locale_set': rule_overlap.c:(.text+0xb3): undefined reference to `area_get_area' rule_overlap.c:(.text+0xca): undefined reference to `area_is_set_in_area' rule_overlap.c:(.text+0x134): undefined reference to `area_num_areas' /tmp/cciaMMxx.o: In function `rule_overlap': rule_overlap.c:(.text+0x169): undefined reference to `area_get_area' rule_overlap.c:(.text+0x1aa): undefined reference to `area_num_areas' /tmp/ccya0lLd.o: In function `rule_single': rule_single.c:(.text+0x87): undefined reference to `area_get_area' rule_single.c:(.text+0xba): undefined reference to `area_num_areas' /tmp/cc48AHcy.o: In function `task_init_task': task.c:(.text+0x14): undefined reference to `area_init' /tmp/cc48AHcy.o: In function `task_finish_task': task.c:(.text+0x29): undefined reference to `area_finish' /tmp/ccMrjTOo.o: In function `user_create_area': user.c:(.text+0x5b6): undefined reference to `area_new_area' /tmp/ccMrjTOo.o: In function `user_add_area_field': user.c:(.text+0x5fa): undefined reference to `area_num_areas' user.c:(.text+0x693): undefined reference to `area_get_area' user.c:(.text+0x69e): undefined reference to `area_add_field' collect2: ld returned 1 exit status я видимо просто не понимаю, что значит " просто скомпилять все исходники из каталогов solver и ui_example_classic." или не знаю, какие библиотеки нужно еще подключать к gcc.. 0

@Volkman 0 / 0 / 0 Регистрация: 26.01.2010 Сообщений: 4
	26.01.2010, 23:30
	Теперь вот: Кликните здесь для просмотра всего текста /Programs/C/sudoku> ./R + gcc -O3 -Wall -Werror -I. solver/task.c solver/field.c solver/set.c solver/area.c solver/jumper.c solver/resolve.c solver/maybe.c solver/rule.c solver/rule_one.c solver/rule_single.c solver/rule_overlap.c solver/rule_exclude.c solver/rule_jumper.c solver/stub.c solver/user.c solver/debug.c ui_example_uarea/ui_example_uarea.c gcc: solver/area.c: Нет такого файла или каталога Volkman@linux-wu9u:~/Programs/C/sudoku> chmod +x R Volkman@linux-wu9u:~/Programs/C/sudoku> ./R + gcc -O3 -Wall -Werror -I. solver/task.c solver/field.c solver/set.c solver/area.c solver/jumper.c solver/resolve.c solver/maybe.c solver/rule.c solver/rule_one.c solver/rule_single.c solver/rule_overlap.c solver/rule_exclude.c solver/rule_jumper.c solver/stub.c solver/user.c solver/debug.c ui_example_classic/ui_example_classic.c gcc: solver/area.c: Нет такого файла или каталога 0

Evg 21281 / 8305 / 637 Регистрация: 30.03.2009 Сообщений: 22,660 Записей в блоге: 30
	26.01.2010, 23:41
	> gcc: solver/area.c: Нет такого файла или каталога Всё же по русски написано. У тебя нормально архив-то распаковался? Если зайти в каталог sudoku и набрать в нём "ls -l ; ls -l *", то что напишет? 0

@Volkman 0 / 0 / 0 Регистрация: 26.01.2010 Сообщений: 4
	26.01.2010, 23:47
	Спасибо =) Сам не заметил почему-то - совсем уже после сессии мозги никакие.. 0

@PointsEqual ниначмуроФ 851 / 535 / 110 Регистрация: 12.10.2009 Сообщений: 1,913
	27.01.2010, 03:18
	вот тут www.deco.tu2.ru есть исходник программы, которая решает судоку, только она на делфи, но думаю переделать не сложно будет 0

@K17 0 / 0 / 0 Регистрация: 07.02.2011 Сообщений: 3
	08.02.2011, 00:37
	мое решение на Java: http://sites.google.com/site/sudokujavasolution/ 0

@dipic 2 / 2 / 0 Регистрация: 09.12.2010 Сообщений: 45
	27.02.2011, 16:02
	Можете помочь. Я так понимаю у кого то можно взять готовый код? Не поможете?? 0

@dipic 2 / 2 / 0 Регистрация: 09.12.2010 Сообщений: 45
	27.02.2011, 16:17
	Я с гугла сразу на 2-ю страничку попал %) невнимателен. Добавлено через 3 минуты Evg, А как можно получить код, если у меня Вижуал Студия 2008-я .. ? 0