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

Составить судоку. Разгадать ее и описать алгоритм. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 107, средняя оценка - 4.74
Splatter_Bugs
0 / 0 / 0
Регистрация: 21.01.2009
Сообщений: 3
21.01.2009, 18:15     Составить судоку. Разгадать ее и описать алгоритм. #1
Составить судоку.разгадать ее и описать агларитм.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.01.2009, 18:15     Составить судоку. Разгадать ее и описать алгоритм.
Посмотрите здесь:

C++ составить алгоритм!!!
Составить алгоритм C++
Не могу описать словестно алгоритм работы функции C++
C++ Разгадать мысли Либерти
Разгадать ребус C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
maximus09
32 / 32 / 3
Регистрация: 29.12.2008
Сообщений: 75
21.01.2009, 18:23     Составить судоку. Разгадать ее и описать алгоритм. #2
Об алгоритме составления судоку читай здесь.
Splatter_Bugs
0 / 0 / 0
Регистрация: 21.01.2009
Сообщений: 3
21.01.2009, 18:34  [ТС]     Составить судоку. Разгадать ее и описать алгоритм. #3
а не могли бы вы написать весь код для судоку??
Vourhey
Почетный модератор
6469 / 2244 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
21.01.2009, 18:36     Составить судоку. Разгадать ее и описать алгоритм. #4
Тебе в заказ программ, в таком случае.
maximus09
32 / 32 / 3
Регистрация: 29.12.2008
Сообщений: 75
21.01.2009, 18:37     Составить судоку. Разгадать ее и описать алгоритм. #5
Особо усиленно данной проблемой не занимался, но на форуме на данный момент имеется несколько сообщений с ключевым словом "судоку". Поищи их поиском.
Splatter_Bugs
0 / 0 / 0
Регистрация: 21.01.2009
Сообщений: 3
21.01.2009, 18:41  [ТС]     Составить судоку. Разгадать ее и описать алгоритм. #6
а никто не сможет составить кто сейчас на форуме??
Vourhey
Почетный модератор
6469 / 2244 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
21.01.2009, 18:44     Составить судоку. Разгадать ее и описать алгоритм. #7
Splatter_Bugs, а кому просто так хочется код строчить? Только мазохистам... Лично мне - просто влом.
Ссылки тебе дали. Попробуй реализовать сам. Будут вопросы - пиши.
Cytrus-kun
Сообщений: n/a
13.04.2010, 15:38     Составить судоку. Разгадать ее и описать алгоритм. #8
разгадывание судоку:

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
int testSudoku(int *mas0, int c = 3, bool debug = false, bool write_in_file = true, int max = 0, const char *fn="")
{
    int c2 = c*c, c3 = c*c*c, c4 = c*c*c*c;
    int i, j, k, l, mod, v, col, row, box;
    int *mas = new int[c4];
    int *test = new int[3*c4];
    bool b;
    char *fname;
    FILE *f;
    // заполняем таблицу
    for(i = 0; i < c4; i++)
        mas[i] = ((mas0[i] > 0) || (mas0[i] <= c2))? mas0[i] : 0;
    // имя файла в который идет запись
    if(write_in_file){
        if(fn == ""){
            l = c4 + 6;
            fname = (char*)malloc(l + 1);
            for(i = 0; i < c4; i++)
                fname[i] = '0' + mas[i];
            strcpy(fname + c4, ".table");
            fname[l] = '\0';
        }else{
            l = strlen(fn);
            fname = (char*)malloc(l + 1);
            strcpy(fname, fn);
            fname[l] = '\0';
        }
        f = fopen(fname, "w");
        free(fname);
    }
    // проверка на валидность таблицы
    for(i = 0; i < 3 * c4; i++)
        test[i] = 1;
    for(i = 0; i < c4; i++){
        v = mas[i] - 1;
        if(v >= 0){
            col = i % c2;
            row = int(i / c2);
            box = int(col / c) + int(row / c) * c;
            test[col * c2 + v]--;
            test[c4 + row * c2 + v]--;
            test[2 * c4 + box * c2 + v]--;
        }
    }
    // если таблица невалидна вернуть -1
    for(i = 0; i < 3 * c4; i++)
        if(test[i] < 0)
            return -1;
    // заполняем таблицу неизменными базовыми числами и значениями по умолчанию
    for(i = 0; i < c4; i++)
        mas[i] = (mas0[i] && (mas0[i] >= -c2) && (mas0[i] <= c2))? mas0[i] : -c2;
    // итеративный обход полей таблицы
    // обход происходит в прямом порядке позиций 0,1,2,3,4,...,80
    //                и в прямом порядке чисел -9,-8,-7,-6,-5,...,-1
    for(i = 0, k = 0, mod = 0; i >= 0;){
        if(i == c4){
            // если решение найдено
            k++;
            if(max)
                if(k > max){
                    if(debug)
                        printf("max\n",k);
                    break;
                }
            if(debug)
                printf("%d)\n",k);
            if(write_in_file)
                fprintf(f, "%d)\n", k);
            for(j = 0; j < c4;){
                if(debug)
                    printf("%2d", mas[j]);
                if(write_in_file)
                    fprintf(f, "%2d", mas[j]);
                j++;
                if(!(j % c2)){
                    if(debug)
                        printf("\n");
                    if(write_in_file)
                        fprintf(f, "\n");
                }
            }
            if(debug)
                printf("\n");
            if(write_in_file)
                fprintf(f, "\n");
            i--;
            mod = 1;
        }else if(mas[i] > 0){
            // если текущий элемент на i-ой позиции - неизменный
            if(mod)
                i--;
            else
                i++;
        }else{
            // найти новый подходящий элемент на i-ой позиции
            b = false;
            col = i % c2;
            row = int(i / c2);
            box = int(col / c) + int(row / c) * c;
            v = abs(mas[i]);
            if(mod){
                // если переход в i-ую позицию произошел из i+1-ой, сменить значение элемента на i-ой позиции
                v--;
                // сделать прошлое значение доступным для следующего выбора
                test[col * c2 + v] = test[c4 + row * c2 + v] = test[2 * c4 + box * c2 + v] = 1;
            }
            if(v)
                do{
                    v--;
                    // проверка удовлетворяет ли искомый элемент условия выбора
                    if(test[col * c2 + v])
                        if(test[c4 + row * c2 + v])
                            if(test[2 * c4 + box * c2 + v])
                                b = true;
                }while(!b && (v > 0));
            if(b){
                // удовлетворяет, перейти на i+1-ую позицию
                test[col * c2 + v] = test[c4 + row * c2 + v] = test[2 * c4 + box * c2 + v] = 0;
                mas[i] = -v - 1;
                mod = 0;
                i++;
            }else{
                // не удовлетворяет, откат на i-1-ую позицию
                mod = 1;
                mas[i] = -c2;
                i--;
            }
        }
    }
    if(write_in_file)
        fclose(f);
    delete []mas;
    // вернуть количество результатов
    return k;
}
значения в одержаных таблицах:
1,2,3,4,... - базовые заданные
-1,-2,-3,-4,... - вычисленные розгаданные

int *mas0 - базовый массив
int с = 3 - размер массива, например при с=2 массив 4х4, при с=3 - 9х9, при с=4 - 16х16
bool debug = false - выводить ли результат в консольной программе
bool write_in_file = true - записывать ли результат в файл
int max = 0 - максимальное искомое количество результатов
const char *fn="" - имя файла для записи

Добавлено через 1 час 51 минуту
немного изменю код для решения судоку с цепочками, так программа будет более универсальной

int *mask = NULL - массив цепочок в таблице судоку (по умолчанию - квадраты)

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
int testSudoku(int *mas0, int *mask = NULL, int c = 3, bool debug = true, bool write_in_file = true, int max = 0, int step = 0, const char *fn="")
{
    int c2 = c*c, c4 = c*c*c*c;
    int i, j, k, l, mod, v, col, row, box;
    int *mas = new int[c4];
    int *test = new int[3*c4];
    bool b;
    char *fname;
    FILE *f;
    // заполняем таблицу
    for(i = 0; i < c4; i++)
        mas[i] = ((mas0[i] > 0) || (mas0[i] <= c2))? mas0[i] : 0;
    if(mask == NULL){
        mask = new int[c4];
        for(i = 0; i < c4; i++){
            col = i % c2;
            row = int(i / c2);
            mask[i] = int(col / c) + int(row / c) * c;
        }
    }
    // имя файла в который идет запись
    if(write_in_file){
        if(fn == ""){
            l = c4 + 6;
            fname = (char*)malloc(l + 1);
            for(i = 0; i < c4; i++)
                fname[i] = '0' + mas[i];
            strcpy(fname + c4, ".table");
            fname[l] = '\0';
        }else{
            l = strlen(fn);
            fname = (char*)malloc(l + 1);
            strcpy(fname, fn);
            fname[l] = '\0';
        }
        f = fopen(fname, "w");
        free(fname);
    }
    // проверка на валидность таблицы
    for(i = 0; i < 3 * c4; i++)
        test[i] = 1;
    for(i = 0; i < c4; i++){
        v = mas[i] - 1;
        if(v >= 0){
            col = i % c2;
            row = int(i / c2);
            box = mask[i];
            test[col * c2 + v]--;
            test[c4 + row * c2 + v]--;
            test[2 * c4 + box * c2 + v]--;
        }
    }
    // если таблица невалидна вернуть -1
    for(i = 0; i < 3 * c4; i++)
        if(test[i] < 0){
            delete []mas;
            if(gen_mask)
                delete []mask;
            return -1;
        }
    // заполняем таблицу неизменными базовыми числами и значениями по умолчанию
    for(i = 0; i < c4; i++)
        mas[i] = (mas0[i] && (mas0[i] >= -c2) && (mas0[i] <= c2))? mas0[i] : -c2;
    // итеративный обход полей таблицы
    // обход происходит в прямом порядке позиций 0,1,2,3,4,...,80
    //                и в прямом порядке чисел -9,-8,-7,-6,-5,...,-1
    for(i = 0, k = 0, mod = 0; i >= 0;){
        if(i == c4){
            // если решение найдено
            k++;
            if(max)
                if(k > max){
                    if(debug)
                        printf("max\n",k);
                    break;
                }
            if(debug)
                printf("%d)\n",k);
            if(write_in_file)
                fprintf(f, "%d)\n", k);
            for(j = 0; j < c4;){
                if(debug)
                    printf("%2d", mas[j]);
                if(write_in_file)
                    fprintf(f, "%2d", mas[j]);
                j++;
                if(!(j % c2)){
                    if(debug)
                        printf("\n");
                    if(write_in_file)
                        fprintf(f, "\n");
                }
            }
            if(debug)
                printf("\n");
            if(write_in_file)
                fprintf(f, "\n");
            if(step)
                if(!(k % step))
                    pause();
            i--;
            mod = 1;
        }else if(mas[i] > 0){
            // если текущий элемент на i-ой позиции - неизменный
            if(mod)
                i--;
            else
                i++;
        }else{
            // найти новый подходящий элемент на i-ой позиции
            b = false;
            col = i % c2;
            row = int(i / c2);
            box = mask[i];
            v = abs(mas[i]);
            if(mod){
                // если переход в i-ую позицию произошел из i+1-ой, сменить значение элемента на i-ой позиции
                v--;
                // сделать прошлое значение доступнім для следующего выбора
                test[col * c2 + v] = test[c4 + row * c2 + v] = test[2 * c4 + box * c2 + v] = 1;
            }
            if(v)
                do{
                    v--;
                    // проверка удовлетворяет ли искомый элемент условия выбора
                    if(test[col * c2 + v])
                        if(test[c4 + row * c2 + v])
                            if(test[2 * c4 + box * c2 + v])
                                b = true;
                }while(!b && (v > 0));
            if(b){
                // удовлетворяет, перейти на i+1-ую позицию
                test[col * c2 + v] = test[c4 + row * c2 + v] = test[2 * c4 + box * c2 + v] = 0;
                mas[i] = -v - 1;
                mod = 0;
                i++;
            }else{
                // не удовлетворяет, откат на i-1-ую позицию
                mod = 1;
                mas[i] = -c2;
                i--;
            }
        }
    }
    if(write_in_file)
        fclose(f);
    delete []mas;
    if(gen_mask)
        delete []mask;
    // вернуть количество результатов
    return k;
}
Пример 1:
C++
1
2
3
4
5
int mas[] = {  4,3,2,1,
                    0,0,0,0,
                    0,0,0,0,
                    3,4,1,2};
testSudoku(mas, NULL, 2);
вернет количество результатов = 4
при этом в файле будут результаты:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
1)
 4 3 2 1
-2-1-4-3
-1-2-3-4
 3 4 1 2
 
2)
 4 3 2 1
-2-1-3-4
-1-2-4-3
 3 4 1 2
 
3)
 4 3 2 1
-1-2-4-3
-2-1-3-4
 3 4 1 2
 
4)
 4 3 2 1
-1-2-3-4
-2-1-4-3
 3 4 1 2
Пример 2:
C++
1
2
3
4
5
6
7
8
9
int mas[] = {  4,3,2,1,
                    0,0,0,0,
                    0,0,0,0,
                    0,0,0,0};
int mask[] = {  4,4,1,1,
                    4,1,3,1,
                    2,4,2,3,
                    2,2,3,3};
testSudoku(mas, mask, 2);
вернет количество результатов = 1
C++
1
2
3
4
5
1)
 4 3 2 1
-2-4-1-3
-3-1-4-2
-1-2-3-4
Пользуйтесь на здоровье.
А как сгенерировать судоку пока не знаю, уж извините.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16828 / 5249 / 321
Регистрация: 30.03.2009
Сообщений: 14,134
Записей в блоге: 26
13.04.2010, 20:11     Составить судоку. Разгадать ее и описать алгоритм. #9
Цитата Сообщение от Splatter_Bugs Посмотреть сообщение
Составить судоку.разгадать ее и описать агларитм.
Решение Судоку
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2010, 00:09     Составить судоку. Разгадать ее и описать алгоритм.
Еще ссылки по теме:

C++ Как написать фразу I Love You, что б интересно было её разгадать
Составить алгоритм C++
C++ Может кто словами описать алгоритм многопутевого слияния?

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

Или воспользуйтесь поиском по форуму:
proverka
Сообщений: n/a
13.05.2010, 00:09     Составить судоку. Разгадать ее и описать алгоритм. #10
Если кому не сложно, тестируем алгоритм решения. bars1602_awardspace_biz/start.php
Алгоритм составления в процессе.
Yandex
Объявления
13.05.2010, 00:09     Составить судоку. Разгадать ее и описать алгоритм.
Ответ Создать тему
Опции темы

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