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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Нужна консультация по Visual Studio 6.0 http://www.cyberforum.ru/cpp-beginners/thread21349.html
Я никогда не писал в вижуал студии, и у меня ее нет, чтобы проверить, поэтому прошу консультации. Есть небольшая прога на досовом с++(Борландовский компилятор). Она нормально скомпилируется в качестве консольного приложения на студии или там будут какие-то ньюансы?
C++ Задачи с массивами Задан массив Y(M). Вы числить сумму 2ух наибольших и 2ух наименьших элементов массива.(M>5) ПОМОГИТЕ КТО МОЖЕТ ОЧЕНЬ НАДО!!! http://www.cyberforum.ru/cpp-beginners/thread21342.html
C++ Связь заголовочного файла и файла с описанием класса.
Всем привет! На картинке я выложил код из одной книжки, у меня возникли некоторые вопросы: - Должен ли компилироваться файл TIME1.CPP? - Как связан заголовочный файл с TIME1.CPP, если в заголовочном нет ссылки на второй?(может, они связаны с помощью названия файлов, но спросить не мешает). Если обьявлен указатель int *t; то должна ли быть обьявлена переменная t? Ведь *t хранит адрес...
Расчет по формуле C++
Здравствуйте уважаемые форумчане. Мне мужно вывести на экран значение рассчитанное по формуле, на языке С++ 1511.26 : (1 + 1639.28 * 2.71828 В СТЕПЕНИ -0.00412 * переременная) Проблема в том что я не могу перевести ету формулу в код С++, вернее незнаю как поднести к степени.
C++ Програма которая считутет текст с файла и виводит на екран предложения которая имеет найбольше количество знаков пробелов. http://www.cyberforum.ru/cpp-beginners/thread21327.html
Кто может дописать код дальше у меня что то не выходит буду очень благодарен. Задание: Написать програму которая считутет текст с файла и виводит на екран предложения которая имеет найбольше количество знаков пробелов. #include "iostream.h" #include "fstream.h" #include "string.h"
C++ Найти произведение второго минимума и третьего максимума массива Текст задачи: Задан вещественный массив размера N. Найти произведение второго минимума и третьего максимума массива. Все элементы, расположенные между ними, заменить нулями. Пример: 0 8 6 4 7 2 1 4 9 3 → 7, 0 8 6 4 7 0 1 4 9 3 #include <stdio.h> void sort(double array, int num) { //В переменной last на каждой итерации по массиву //содержится позиция последнего элемента, который... подробнее

Показать сообщение отдельно
Cytrus-kun
Сообщений: n/a
13.04.2010, 15:38     Составить судоку. Разгадать ее и описать алгоритм.
разгадывание судоку:

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
Пользуйтесь на здоровье.
А как сгенерировать судоку пока не знаю, уж извините.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru