Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
1 / 1 / 0
Регистрация: 13.02.2010
Сообщений: 12
1

Решение судоку методом backtracking(метод перебора с возвратом)

03.05.2010, 15:45. Показов 4249. Ответов 0
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Значится вот как получается. Написал программу для решения судоку методом перебора с возвратом. Согласен, что лучше всего использовать этот метод с помощью рекурсивных функций, но меня на это не хватило. Написал функции проверяющие на доступность вставки выбранного числа и отход назад до предыдущей координаты. Не могу разобраться почему программа виснет намертво. Помогите пожалуйста.

код программы
Pascal
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
program sudoku;
 
 
const datafile='F:\Documents and Settings\Admin\Рабочий стол\SudokuBacktracking\data.txt';
 
type data=integer;
 
type Tmas=array[1..9,1..9] of data;
 
var i,j:data;
    Mas,znach:tmas;
    f:text;
    
function backmove(var a:tmas; var y,x,k:integer):boolean;
         begin
         a[y,x]:=0;
         
         repeat
         dec(x);
         
         if x=0 then begin
                     dec(y);
                     x:=9;
                     end;
 
         if znach[y,x]=0 then begin
                              backmove:=true;
                              k:=a[y,x];
                              a[y,x]:=0;
                              end;
         until backmove=true;
         
         end;
 
function check(var a:tmas; y,x,q:integer):boolean;
         var i1:integer;
         begin
         check:=true;
 
         for i1:=1 to 9 do
             begin
             if x<>i then if q=a[y,i1] then begin
                                            Check:=false;
                                            break;
                                            end;
                                            
             if y<>i1 then if q=a[i1,x] then begin
                                             Check:=false;
                                             break;
                                             end;
             end;
             
         end;
 
procedure main(var a:tmas; y,x:integer);
         var cik:shortint;
             k,q:integer;
         begin
         
         k:=1;
 
         repeat
 
         if a[y,x]=0 then begin
                          cik:=0;
 
                          for q:=k to 9 do
                              if check(a,y,x,q) then begin
                                                     inc(cik);
                                                     a[y,x]:=q;
 
                                                     inc(x);
                                                     if x=10 then begin
                                                                  inc(y);
                                                                  x:=1;
                                                                  end;
                                                     break;
                                                     end;
                                                     
                          if cik=0 then backmove(a,y,x,k);
                          end
                      else begin
                           if x=10 then begin
                                        inc(y);
                                        x:=1;
                                        end;
                           end;
         until y=10;
 
         end;
 
begin
assign(f,datafile);
reset(f);
j:=1; i:=1;
while not eof(f) do
      begin
      while not eoln(f) do
            begin
            read(f,mas[i,j]);
            if mas[i,j]=0 then znach[i,j]:=0
                        else znach[i,j]:=1;
            inc(j);
            end;
      readln(f);
      if j=10 then j:=1;
      if i<=9 then inc(i);
      end;
close(f);
i:=1;
j:=1;
main(mas,i,j);
end.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.05.2010, 15:45
Ответы с готовыми решениями:

Решение уравнения методом перебора и методом деления отрезка пополам
Решите уравнение x^2=5cos(x-1) методом перебора и методом деления отрезка пополам. Сравните кол-во...

Решить задачу методом рекурсивного перебора с возвратом
В Волшебной стране используются монетки достоинством A1, A2,..., AM. Волшебный человечек пришел в...

Обход шахматной доски конём, используя метод перебора с возвратом
На шахматной доске n×m в первой строке в первом столбце находится конь. Составьте план перемещения...

Спуск с горы (перебор с возвратом, backtracking)
Есть такое задание: Решение задачи должно быть представлено в виде функции Matlab (если кто...

0
03.05.2010, 15:45
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.05.2010, 15:45
Помогаю со студенческими работами здесь

Метод перебора для нахождения решения "Судоку"
Всем привет. Люди помогите пожалуйста, у меня курсовая на тему Метод перебора для нахождения...

Решение задачи методом перебора
Уважаемые форумчане, такой к вам вопрос. Как с программной точки зрения реализовать решение задачи...

Решение нелинейного уравнения методом перебора
Решить уравнение sin(1/x)=0 методом перебора на промежутке x = .

Решение уравнения методом перебора (сокращение кода)
A*X3 + B*X2 + C*X + D = 0 нужно решить это уравнение методом перебора корни уравнение целые ....


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru