Форум программистов, компьютерный форум CyberForum.ru

Решение Судоку - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 129, средняя оценка - 4.81
HeddinG
 Аватар для HeddinG
0 / 0 / 0
Регистрация: 23.06.2009
Сообщений: 16
24.06.2009, 23:39     Решение Судоку #1
Здравствуйте!

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

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

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).
Но там англ, для меня это сложновато

Если кто сталкивался - напишите плз хотя-бы алгоритм.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.06.2009, 23:39     Решение Судоку
Посмотрите здесь:

решение судоку C++
почти судоку) C++
проверка судоку C++
C++ Судоку
Судоку C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ISergey
Maniac
Эксперт С++
 Аватар для ISergey
1331 / 864 / 50
Регистрация: 02.01.2009
Сообщений: 2,622
Записей в блоге: 1
25.06.2009, 00:08     Решение Судоку #2
Суть так и не понял, но покоду
это
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
 Аватар для HeddinG
0 / 0 / 0
Регистрация: 23.06.2009
Сообщений: 16
25.06.2009, 09:41  [ТС]     Решение Судоку #3
Спасибо, самому ненравилась эта часть. А что на счет алгоритма, никто так и не знает ?
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 320
Регистрация: 30.03.2009
Сообщений: 14,125
Записей в блоге: 26
25.06.2009, 12:07     Решение Судоку #4
Как-то писал программу. Если интересно - могу кинуть исходник.

Только сразу предупреждаю - работал под gcc, а потом это просто набор исходников, в проект их самом загонять надо будет. Ну и пытался программу сделать универсальной: она сделана как математическая абстракция, т.е. не привязана к квадратной форме поля. А квадратная форма рассматривается как частный случай.
HeddinG
 Аватар для HeddinG
0 / 0 / 0
Регистрация: 23.06.2009
Сообщений: 16
25.06.2009, 14:51  [ТС]     Решение Судоку #5
Интересно! Буду благодарен.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 320
Регистрация: 30.03.2009
Сообщений: 14,125
Записей в блоге: 26
25.06.2009, 14:54     Решение Судоку #6
Вечером тогда скину, а то на работу по ходу я не притаскивал
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 320
Регистрация: 30.03.2009
Сообщений: 14,125
Записей в блоге: 26
25.06.2009, 20:49     Решение Судоку #7
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Выкладываю два архива. sudoku_w.rar - для тебя (в виндовой кодировке), sudoku.rar - для меня (в koi-8) на тот случай, если возникнут вопросы

Вкратце. Программа разбита на две чати. Решалка отдельно, пользовательский интерфейс для ввода и вывода отдельно. Для тебя нужно просто скомпилять все исходники из каталогов solver и ui_example_classic. Решение начинается в rule.c в процедуре rule_make_resolve_task, там последовательно запускаются 4 алгортима разной сложности (когда я писал прогу, в итоге не нашёл ни одной задачи, которой бы этих 4 правил было недостаточно). Если в файле debug.h значение макроса DEBUG выставить в 1, то процесс решения будет печататься на экране
Вложения
Тип файла: rar sudoku.rar (35.8 Кб, 1218 просмотров)
Тип файла: rar sudoku_w.rar (36.1 Кб, 1253 просмотров)
HeddinG
 Аватар для HeddinG
0 / 0 / 0
Регистрация: 23.06.2009
Сообщений: 16
25.06.2009, 21:53  [ТС]     Решение Судоку #8
Большое спасибо.
Volkman
0 / 0 / 0
Регистрация: 26.01.2010
Сообщений: 4
26.01.2010, 22:21     Решение Судоку #9
привет. у меня такой вопрос, скачал то, что ты выложил, но ничего не компилится - gcc выдает до фига ошибок.. можешь описать точно, что нужно сделать? я под линуксом..
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 320
Регистрация: 30.03.2009
Сообщений: 14,125
Записей в блоге: 26
26.01.2010, 22:25     Решение Судоку #10
Так ты хоть покажи, куда ты нажимал и что тебе выдало в ответ
Volkman
0 / 0 / 0
Регистрация: 26.01.2010
Сообщений: 4
26.01.2010, 22:33     Решение Судоку #11
Кликните здесь для просмотра всего текста
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
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 320
Регистрация: 30.03.2009
Сообщений: 14,125
Записей в блоге: 26
26.01.2010, 22:43     Решение Судоку #12
Там есть файл "R", его и надо запускать. ТОлько сделать исполняемым (если через винду разархивировал). В общем-то строка запуска в нём зашита

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

Код
# Выбираем пользовательский модуль
UI=$UI_EXAMPLE_CLASSIC
#UI=$UI_EXAMPLE_JUMPER
#UI=$UI_EXAMPLE_UAREA
#UI=$UI_TEST
Volkman
0 / 0 / 0
Регистрация: 26.01.2010
Сообщений: 4
26.01.2010, 23:30     Решение Судоку #13
Теперь вот:
Кликните здесь для просмотра всего текста
/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
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 320
Регистрация: 30.03.2009
Сообщений: 14,125
Записей в блоге: 26
26.01.2010, 23:41     Решение Судоку #14
> gcc: solver/area.c: Нет такого файла или каталога

Всё же по русски написано. У тебя нормально архив-то распаковался? Если зайти в каталог sudoku и набрать в нём "ls -l ; ls -l *", то что напишет?
Volkman
0 / 0 / 0
Регистрация: 26.01.2010
Сообщений: 4
26.01.2010, 23:47     Решение Судоку #15
Спасибо =) Сам не заметил почему-то - совсем уже после сессии мозги никакие..
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
27.01.2010, 03:18     Решение Судоку #16
вот тут www.deco.tu2.ru есть исходник программы, которая решает судоку, только она на делфи, но думаю переделать не сложно будет
K17
0 / 0 / 0
Регистрация: 07.02.2011
Сообщений: 3
08.02.2011, 00:37     Решение Судоку #17
мое решение на Java: http://sites.google.com/site/sudokujavasolution/
dipic
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 45
27.02.2011, 16:02     Решение Судоку #18
Можете помочь. Я так понимаю у кого то можно взять готовый код? Не поможете??
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 320
Регистрация: 30.03.2009
Сообщений: 14,125
Записей в блоге: 26
27.02.2011, 16:11     Решение Судоку #19
Цитата Сообщение от dipic Посмотреть сообщение
Можете помочь. Я так понимаю у кого то можно взять готовый код? Не поможете??
Если ты задаёшь такой вопрос в теме, где выложено два готовых решения и ссылка, то тебе точно уже ничто не поможет
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.02.2011, 16:17     Решение Судоку
Еще ссылки по теме:

C++ Судоку
C++ Судоку си++
Нужна проверка, имеет ли судоку решение C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
dipic
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 45
27.02.2011, 16:17     Решение Судоку #20
Я с гугла сразу на 2-ю страничку попал %) невнимателен.

Добавлено через 3 минуты
Evg,
А как можно получить код, если у меня Вижуал Студия 2008-я .. ?
Yandex
Объявления
27.02.2011, 16:17     Решение Судоку
Ответ Создать тему
Опции темы

Текущее время: 04:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru