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

Cудоку перебор - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Что не так? Дан текстовый файл F. Переписать в другой файл G все строки, содержащие цифры. http://www.cyberforum.ru/cpp-beginners/thread447582.html
#include <iostream> #include <math.h> using std::cin; using std::cout; using std::endl; int main (int argc, char** argv){ std::cout << "my_cat: Usage : ./my_cat input_file output_file " << std::endl; return (EXIT_SUCCESS);
C++ Не получается работать с cout в MS Visual C++ 2010 Express в общем берем даже обычную программу: # include <stdio.h> # include <conio.h> int main() { printf ("Privet!\n"); getch(); } http://www.cyberforum.ru/cpp-beginners/thread447581.html
C++ Если сpеднее аpифметическое элементов массива больше 0, то отpицательные элементы массива заменить на него
собственно полдела сделано, нужно немного доделать. но мне уже не под силу( задача: Даны целые массивы А, B, C. Каждый массив пpеобpазовать по пpавилу: если сpеднее аpифметическое значение элементов массива больше 0, то отpицательные элементы массива заменить на это сpеднее аpифметическое значение. В пpотивном случае массив оставить без изменений. вот что у меня получилось. среднее...
C++ Движок Irrlicht и текстуры формата png
Помогите мне загрузить текстуру формата png в игру, в туториалах на офф. сайте про это не написано, там написано о md2 текстуры.
C++ Легкая программа на СИ++ строки http://www.cyberforum.ru/cpp-beginners/thread447564.html
В текстовом файле находятся записи о номерах телефонов.В каждой строке записана информация об одном абоненте:№ телефона,ФИО,адрес. Програма выводит диапазоны свободных номеров телефонов для каждой АТС в консоль. Ввод информации осуществляется с файла input.txt. Желательно с использованием процедур и функций.
C++ передача парамеров разными способами есть программа которая проветяет какой ряд чисел я задаю-арифметическую,геометрическую последовательность или просто строку: #include <iostream.h> #include <stdlib.h> #include <conio.h> void fun1(int n) { int mas ; int b=1; double q=0; cout<<"Vvedite elementi posledovatel'nosti"<<endl; подробнее

Показать сообщение отдельно
ShmidT333
0 / 0 / 0
Регистрация: 16.02.2012
Сообщений: 3
16.02.2012, 23:55     Cудоку перебор
Здравствуйте,мы с товарищем решили написать решалку для судоку,но появилась проблемма,которая как оказалось поставила нас в тупик.

Введение:
Сам судоку у нас хранится в структуре sudoky,где "x" само значение судоку(равен 0 если точка неизвесна), "y" количество вариантов для точки(равен 0 если точка проставлена), дальше массив "c[10]" в массиве хранятся варианты которые подходят для этой точки), и массив "ind[10]" вспомогательный массив для функций.Принимаем мы из файла,точки пришутся через пробел и неопределённые точки пишутся 0.
C++
1
2
3
4
5
6
7
8
9
struct sudoky{
    int x,y;
    int c[10];
    int ind[10];
    sudoky()
    {x=y=0;for(int i=0;i<10;i++){
        c[i]=i;ind[i]=0;}
    }
};
Я думаю, что все из вас знают, как решается эта головоломка(судоку).
Как правило сложные судоку решаются различными методами, но самая простая часть(расстановка вариантов для точек, запись однозначный вариантов) приводит судоку к неопределённости, в том смысле, что нет однозначных вариантов расположения точек. Мы написали 4 разных метода, которые
позволяют раскрывать эту неопределённость.Я думаю эти 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
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
void doneopr(void){
    
 
for(i=0;i<9;i++){
    
        for(j=0;j<9;j++)
        if(a[i][j].x==0)
            {for(k=1;k<10;k++){
                for(q=0;q<9;q++)
                    if(a[i][q].x==k){
                        a[i][j].c[k]=0;
                    }
            
                for(q=0;q<9;q++)
                    if(a[q][j].x==k){
                        a[i][j].c[k]=0;
                    }
 
            }
 
        }
    }
 
//end proverka!!!
 
 
//proverka 2
 
for(i=0;i<9;i++)
        for(j=0;j<9;j++)
        if(a[i][j].x==0)
            {for(k=1;k<10;k++){
                if(i%3==2){
                    if(j%3==2){for(q=i-2;q<=i;q++)
                    for(t=j-2;t<=j;t++)
                        if(a[q][t].x==k){
                            a[i][j].c[k]=0;}}
                else { if(j%3==1){for(q=i-2;q<=i;q++)
                            for(t=j-1;t<=j+1;t++)
                            if(a[q][t].x==k){
                            a[i][j].c[k]=0;}}
                        else{ if(j%3==0){for(q=i-2;q<=i;q++)
                                for(t=j;t<=j+2;t++)
                                if(a[q][t].x==k){
                                    a[i][j].c[k]=0;}}
                                            }
                                    }
                }
                else { if(i%3==1){if(j%3==2){for(q=i-1;q<=i+1;q++)
                    for(t=j-2;t<=j;t++)
                        if(a[q][t].x==k){
                            a[i][j].c[k]=0;}}
                    else { if(j%3==1){for(q=i-1;q<=i+1;q++)
                            for(t=j-1;t<=j+1;t++)
                                if(a[q][t].x==k){
                                    a[i][j].c[k]=0;}}
                        else{ if(j%3==0){for(q=i-1;q<=i+1;q++)
                                    for(t=j;t<=j+2;t++)
                                    if(a[q][t].x==k){
                                a[i][j].c[k]=0;}}
                                            }
                                    }}
                else {if(i%3==0){if(j%3==2){for(q=i;q<i+3;q++)
                        for(t=j-2;t<=j;t++)
                        if(a[q][t].x==k){
                            a[i][j].c[k]=0;}}
                        else { if(j%3==1){for(q=i;q<=i+2;q++)
                                for(t=j-1;t<=j+1;t++)
                                if(a[q][t].x==k){
                                    a[i][j].c[k]=0;}}
                        else{ if(j%3==0){for(q=i;q<=i+2;q++)
                                    for(t=j;t<=j+2;t++)
                                    if(a[q][t].x==k){
                                        a[i][j].c[k]=0;}}
                                            }
                                    }
                }
                }
                }
        }
        }
//search!
for(i=0;i<9;i++){
        for(j=0;j<9;j++)
        if(!a[i][j].x){p=0;
            for(k=1;k<10;k++)
                if(a[i][j].c[k])p++;
            a[i][j].y=p;
        }
}
//zamena
r=r1=0;
for(i=0;i<9;i++)
 
 for(j=0;j<9;j++){
 if(a[i][j].y==1){r++;
  for(k=1;k<10;k++)
   if(a[i][j].c[k]!=0){
    a[i][j].x=a[i][j].c[k];
    a[i][j].y=0;
//  for(q=0;q<10;q++)
    //  a[i][j].c[q]=0;
   
   }
 
 
 
} if(a[i][j].y==0)r1++;
}
if(r!=0&&r1!=0)doneopr();  // r - это количество 1 в судоку, r1 количество 0
}
Проблемма:
Наши 4 метода о которых я говорил выше, упрощают судоку, а бывает и решают её=), но на самых сложных они тоже становятся бесполезными. И тут мы думаем сделать перебор, но как его реализовать мы не знаем=( Перебор должен перебирать значения из точек у которых нет однозначного значения из массива с.

вот пример такого судоку:
C++
1
2
3
4
5
6
7
8
9
2 0 0 8 6 0 0 9 7
0 5 4 0 0 2 0 0 3
0 0 0 0 0 0 0 5 2
0 0 0 3 8 0 0 0 9
0 0 0 0 0 0 0 0 0
6 4 1 0 0 0 0 0 5
5 9 0 0 0 0 0 0 0
0 0 2 9 3 0 0 0 0
0 0 0 1 0 0 0 0 0
вот что выводит программа:
C++
1
2
3
4
5
6
7
8
9
2 1 3 8 6 5 4 9 7 
0 5 4 7 0 2 0 0 3 
0 0 0 4 0 3 0 5 2 
7 2 5 3 8 0 0 0 9 
0 0 0 5 0 0 0 0 0 
6 4 1 2 0 0 0 0 5 
5 9 0 6 0 0 0 0 0 
1 0 2 9 3 0 5 0 0 
4 0 0 1 5 0 9 2 0
и вот на этих точках надо сделать перебор.
Жду советов и предложений.
Заранее спасибо.
Вроде всё=)

Добавлено через 4 минуты
Формально, перебрать весь массив с, и после каждого перебора делать проверку на решенность судоку.Проверка написана.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 13:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru