Iniciar sesiónCerrar
Correo:
Contraseña:
Entrar
Recordar sesión en este navegador
Iniciar sesiónIniciar sesiónCrear cuentaCrear cuenta
LWP » Foros » Pascal/Turbo Pascal » tarea sudoku sin terminar

Pascal/Turbo Pascal - tarea sudoku sin terminar

Volver
Nuevo Tema
<<>>
 
Vista:

tarea sudoku sin terminar

Publicado por Monchita (9 intervenciones) el 19/10/2012 20:26:54
Hola soy estudiante de facultad de Quimica y me inscribi en Programacion por creditos y se me complica un poco agarrarle la mano, yo debo entregar un trabajo pa el lunes que conste como de 3 funciones:

function SudokuCorrecto(tablero: TipoTablero) : boolean;
{ retorna true si los valores asignados respetan las reglas de buena formación }

function SudokuResuelto(tablero: TipoTablero) : boolean;
{ retorna true si es correcto y no hay celdas vacías }

procedure CrearCandidatos(tablero: TipoTablero; var candidatos: TipoCandidatos);
{ obtiene el conjunto de candidatos inicial para todas las celdas }


Para el sudoku y en lo que pude hacer me gustaria que m corriguieran si es posible:
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
function verificar_fila(tablero:tipotablero,i1,j1:integer):boolean;
               var
                 valor:digito;
                 i,j:integer;
                 encontre:boolean;
                  begin
                  j:=1;
                  encontre:=false;
 
                  while j<9 and not(encontre) then
                        begin
                        if valor=tablero(i,j) then
                                if i<>i1 or j<>j1 then
                                 encontre:=true
 
                                 j:=j+1;
                       end;
 
                       verifica_fila:=not(encontre);
 
 
                  end.
 
 
 
          begin
 
          i:=1;
          j:=1;
 
          while j < 9 and not(encontre) then
           begin
                while i < 9 and not(encontre) then
                begin
                        if tablero(i,j)<>'0' then
 
                         encontre:=verificar_fila(tablero,i,j);
 
                         if encontre then
 
                        end;
 
                        i:=i+1;
                 end;
 
                j:=j+1;
          end;


Para leer columna tambien lo realize es casi lo mismo, ahora mi problema es q debe me falta la funcion para verificar celdas vacias y posibles candidatos y aca si que me tranque feo jeje, les agradeceria cualquier ayudita. Saludos
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

tarea sudoku sin terminar

Publicado por ramon (2158 intervenciones) el 19/10/2012 21:37:42
Para poder ayudarte mejor pasa todo lo que tienes echo para comprendedlo mejor.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

tarea sudoku sin terminar

Publicado por ramon (2158 intervenciones) el 21/10/2012 17:45:39
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
{Te dejo este programa a ver si te ayuda}
 
program aasudoku;
 uses
    crt;
  type
     sudoku_reg = record
          dificultac : string[15];
          matriz : array[1..9,1..9]of char;
           guego :  array[1..9,1..9]of char;
         partida : array[1..9,1..9]of char;
       end;
 
  var
     ds, sap ,rs : array [1..9,1..9] of integer;
     init : array [1..9,1..9] of boolean;
     ok, nok : boolean;
     d, u : string;
     x, y, i, j, pt : integer;
     crear : integer;
     sudoku : sudoku_reg;
 
 
  function comprueva_la_linea(li : integer) : boolean;
   var
      lin : array [0..9] of integer;
      jl : integer;
   begin
      for jl := 1 to 9 do
      lin[jl] := 0;
        for jl := 1 to 9 do
        lin[ds[li,jl]] := lin[ds[li,jl]] + 1;
        comprueva_la_linea := true;
       for jl := 1 to 9 do
        if lin[jl] > 1 then
        comprueva_la_linea := false;
      end;
 
  function comprueva_la_columna(co : integer) : boolean;
  var
  t : array [0..9] of integer;
  j : integer;
  begin
     for j := 1 to 9 do
     t[j] := 0;
      for j := 1 to 9 do
      t[ds[j,co]] := t[ds[j,co]] + 1;
      comprueva_la_columna := true;
     for j := 1 to 9 do
      if t[j] > 1 then
       comprueva_la_columna := false;
   end;
 
  function comprueva_la_linea_y_columna(li, co : integer) : boolean;
  var
     t : array [0..9] of integer;
     ch, cv, j  : integer;
    begin
    cv := (li - 1) div 3;
    ch := (co - 1) div 3;
    for j := 1 to 9 do
    t[j] := 0;
    for co := 1 to 3 do
     for li := 1 to 3 do
     t[ds[li + cv * 3,co + ch * 3]] := t[ds[li + cv * 3,co + ch * 3]] + 1;
     comprueva_la_linea_y_columna := true;
    for j := 1 to 9 do
     if t[j] > 1 then
     comprueva_la_linea_y_columna := false;
  end;
 
   function adelante : boolean;
   var
      av : boolean;
    begin
       if y = 9 then
       begin
         x := x + 1;
         y := 1;
    end
  else
     y := y + 1;
     if x = 10 then
     av := false
   else
     av := true;
     adelante := av;
   if init[x,y] and av then
   adelante := adelante;
 end;
 
  function atras : boolean;
  var
     at : boolean;
     begin
      if y = 1 then
      begin
         x := x - 1;
         y := 9;
     end
   else
      y := y - 1;
      if x = 0 then
      begin
         at := false;
    end
  else
     at := true;
     atras := at;
     if init[x,y] and at then
     atras := atras;
  end;
 
  function datos_son_correctos : boolean;
  begin
      ok := false;
      nok := false;
	while not ok and not nok do
        begin
         if ds[x,y] < 9 then
        begin
    repeat
        ds[x,y] := ds[x,y] + 1;
    until (comprueva_la_linea(x) and comprueva_la_columna(y)
     and comprueva_la_linea_y_columna(x,y)) or (ds[x,y] = 10);
       if ds[x,y] < 10 then
       ok := not adelante;
     end
   else
      begin
         ds[x,y] := 0;
         nok := not atras;
    end;
  end;
    if ok then
    datos_son_correctos := true;
     if nok then
     datos_son_correctos := false;
  end;
 
  function correcto : boolean;
   var
     cor : boolean;
  begin
      cor := true;
      for x := 1 to 9 do
        for y := 1 to 9 do
        begin
          cor := cor and comprueva_la_linea(x);
          cor := cor and comprueva_la_columna(y);
          cor := cor and comprueva_la_linea_y_columna(x,y);
     end;
       correcto := cor;
  end;
 
  procedure genera_sudoku(dific : integer);
   var
    dificultad : integer;
   begin
      randomize;
      dificultad := 30;
   case dific of
  1 : dificultad := 30;
  2 : dificultad := 35;
  3 : dificultad := 40;
   end;
   repeat
       repeat
        for x := 1 to 9 do
           for y := 1 to 9 do
           begin
              ds[x,y] := 0;
              init[x,y] := false;
           end;
        for i := 1 to 10 do
        begin
          x := random(9) + 1;
          y := random(9) + 1;
          ds[x,y] := random(9) + 1;
          init[x,y] := true;
       end;
   until (correcto) or (keypressed);
   x := 0;
   y := 9;
   adelante;
   until datos_son_correctos;
   for i := 1 to 9 do
      for j := 1 to 9 do
      begin
          sap[i,j] := ds[i,j];
          init[i,j] := true;
    end;
     for i := 1 to 9 do
       for j := 1 to 9 do
    begin
       str(ds[i,j],u);
       sudoku.matriz[i][j] := u[1];
       sudoku.guego[i][j] := u[1];
    end;
	pt := 0;
    while pt < dificultad do
    begin
       i := random(9) + 1;
       j := random(9) + 1;
       if ds[i,j] <> 0 then
       begin
          ds[i,j] := 0;
          init[i,j] := false;
          pt := pt + 1;
          ds[10 - i,10 - j] := 0;
          init[10 - i,10 - j] := false;
          str(ds[i,j],d);
          if d[1] = '0' then
          sudoku.guego[i][j] := ' ';
     end;
   end;
      for i := 1 to 9 do
       for j := 1 to 9 do
        if ds[i,j] = 0 then
         rs[i,j] := sap[i,j]
   else
       rs[i,j] := 0;
  end;
 
  procedure cuadriculado;
  var
    a, x, y : integer;
  begin
      x := 30;
      y := 2;
      textcolor(15);
          gotoxy(x,y);write('ÃÄÄÄÂÄÄÄÂÄÄÄÅÄÄÄÂÄÄÄÂÄÄÄÅÄÄÄÂÄÄÄÂÄÄÄ´');
      gotoxy(x,y + 1);write('³   ³   ³   ³   ³   ³   ³   ³   ³   ³');
      gotoxy(x,y + 2);write('ÃÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄ´');
      gotoxy(x,y + 3);write('³   ³   ³   ³   ³   ³   ³   ³   ³   ³');
      gotoxy(x,y + 4);write('ÃÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄ´');
      gotoxy(x,y + 5);write('³   ³   ³   ³   ³   ³   ³   ³   ³   ³');
      gotoxy(x,y + 6);write('ÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅ');
      gotoxy(x,y + 7);write('³   ³   ³   ³   ³   ³   ³   ³   ³   ³');
      gotoxy(x,y + 8);write('ÃÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄ´');
      gotoxy(x,y + 9);write('³   ³   ³   ³   ³   ³   ³   ³   ³   ³');
     gotoxy(x,y + 10);write('ÃÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄ´');
     gotoxy(x,y + 11);write('³   ³   ³   ³   ³   ³   ³   ³   ³   ³');
     gotoxy(x,y + 12);write('ÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅ');
     gotoxy(x,y + 13);write('³   ³   ³   ³   ³   ³   ³   ³   ³   ³');
     gotoxy(x,y + 14);write('ÃÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄ´');
     gotoxy(x,y + 15);write('³   ³   ³   ³   ³   ³   ³   ³   ³   ³');
     gotoxy(x,y + 16);write('ÃÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄÅÄÄÄ´');
     gotoxy(x,y + 17);write('³   ³   ³   ³   ³   ³   ³   ³   ³   ³');
     gotoxy(x,y + 18);write('ÅÄÄÄÁÄÄÄÁÄÄÄÅÄÄÄÁÄÄÄÁÄÄÄÅÄÄÄÁÄÄÄÁÄÄÄÅ');
     for x := 1 to 9 do
      for y := 1 to 9 do
      begin
      gotoxy(28 + (x * 4),1 + (y * 2));write(sudoku.guego[x,y]);
      end;
  end;
 
   procedure solucion;
   var
     i,j : integer;
    begin
       for i := 1 to 9 do
       begin
         for j := 1 to 9 do
         begin
             str(sap[i,j],u);
             textcolor(14);
             gotoxy(3 + (i * 2),3 + (j + 2));write(u);
         end;
      end;
   end;
 
 
   begin
       clrscr;
       genera_sudoku(1);
       cuadriculado;
       solucion;
       readkey;
   end.
 
{Fíjate que el soudoku no esta  solo de ayuda}
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
1
Comentar

tarea sudoku sin terminar

Publicado por Monchita (9 intervenciones) el 23/10/2012 20:25:41
Muchas gracias por el sudoku que pasaste, algo m guia pero el esta medio complikado en unas partes para que yo lo entienda debido aque estoy en el primer semestre de programacion 1 y vi funciones que aun ni eh tocado en clases, lo q yo entiendo en pascal es lo mas basico de lo basico jeje, pero ta. gracias igual
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

tarea sudoku sin terminar

Publicado por ramon (2158 intervenciones) el 23/10/2012 21:27:12
Es para que observes las lineas columna y lineas y columna paro si pasas el anunciado que
te andado y sabiendo tu nivel te podre ayudar mas.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

tarea sudoku sin terminar

Publicado por Monchita (9 intervenciones) el 24/10/2012 00:51:05
Ya termine las 2 primeras funciones, ahora necesitaria ayuda en la 3ra

procedure CrearCandidatos(tablero: TipoTablero; var candidatos: TipoCandidatos);
{ obtiene el conjunto de candidatos inicial para todas las celdas } te paso el enunciado:

Candidato de una celda

Dado un sudoku, un número d &#8712; {1,2,3,4,5,6,7,8,9} es un candidato para la celda (i,j) vacía, si se cumple que d no aparece en la fila i, ni en la columna j , ni en la región que contiene a la celda (i,j).

Notar que candidato sólo se define para las celdas vacías.

C(S,i,j) representa el conjunto de candidatos de la celda (i,j) en el sudoku S.

Así por ejemplo, si llamamos S1 al sudoku de la primera figura, tendremos:

C(S1,0,0) = { 2, 8, 9}
C(S1,8,8) = { 9 }
El conjunto de candidatos definido aquí es en realidad lo que llamamos conjunto inicial de candidatos ya que luego veremos, que este conjunto puede reducirse aplicando tácticas apropiadas.


5.&#8194; Métodos de resolución
El sudoku puede resolverse fácilmente por métodos computacionales conocidos como ensayo y error. A grandes rasgos en estos métodos se elige para una celda aún vacía, uno cualquiera de sus candidatos y se continúa con las restantes celdas. Si en algún momento se llega a una configuración que no tiene solución, se deshace la última elección y se elige otro candidato para esa celda. Se continúa así hasta agotar todas las posibilidades o encontrar alguna solución.

En esta tarea no aplicaremos métodos de ensayo y error sino que nos limitaremos a las tácticas que se describen a continuación. Existen muchos textos y sitios web que explican las tácticas más usadas en la resolución de sudokus. Las que usamos aquí han sido tomadas de el sitio:

Solving Sudoku. Angus Johnson. http://www.angusj.com/sudoku/hints.php

5.1&#8194; Candidato único

Decimos que un dígito d es candidato único para una celda (i,j) en un sudoku S si se cumple que:

C(S,i,j) = { d }
Cuando esto se cumple podemos asegurar que la celda (i,j) debe ser ocupada por el dígito d.

En el sukoku de la figura, la posición (8,8) tiene como candidato único el 9.

Esta táctica es denominada single en el sitio Solving Sudoku


5.2&#8194; Candidato exclusivo

Decimos que un dígito d es un candidato exclusivo de una celda (i,j), si d es candidato para esa celda y además se cumple al menos una de las siguientes condiciones:

d no es candidato de ninguna otra celda en la fila i (exclusivo en fila).
d no es candidato de ninguna otra celda en la columna j (exclusivo en columna).
d no es candidato de ninguna otra celda en la region que contiene a la celda (i,j) (exclusivo en región).
Cuando esto se cumple podemos asegurar que la celda (i,j) debe ser ocupada por el dígito d.

En el sudoku de la figura, la posición (0,4) tiene como candidato exclusivo al 1, puesto que es un candidato de esa celda y no es candidato de ninguna otra celda dentro de la misma fila.

Esta táctica es denominada hidden single en el sitio Solving Sudoku

5.3&#8194; Tácticas de reducción de candidatos

Las dos tácticas anteriores permiten identificar de manera inequívoca cuál es el valor que debe asignarse a una celda. La aplicación de ambas tácticas permite resulver un número importante de sudokus calificados como de nivel fácil pero no son suficientes para resolver muchos sudokus (nivel medio, difícil, extremo, etcétera).

Cuando no se detecta ninguna celda que cumpla con las condiciones de candidato único o exclusivo, surge la aplicación de tácticas que permiten descartar ciertos candidatos de una o más celdas y por eso se denominan de reducción de candidatos. La aplicación de una o más de estas tácticas dará lugar a la aparición de nuevos candidatos únicos y exclusivos y así se continuará alternando ambas familias de tácticas hasta resolver todas las celdas.

Existen muchas tácticas de reducción de candidatos de diferentes niveles de complejidad. Se recomienda consultar el sitio Solving Sudoku para ver una explicación completa de estas tácticas.

6.&#8194; Estructuras de datos
6.1&#8194; El tablero

Se define la siguiente estructura para representar el tablero de un sudoku:

type
Rango9 = 0..8;
Digito = '0'..'9';
TipoTablero = array [Rango9,Rango9] of Digito;
Si tenemos una variable S de tipo tablero entonces S[i,j] contiene el valor asignado a la celda ubicada en la fila i, columna j El carácter ‘0&#8242; se utiliza para representar una celda vacía.

Candidatos

En todas las estrategias de resolución resulta fundamental llevar registro de los candidatos de las celdas aún por completar. Se propone la siguiente estructura de datos:

type
ConjuntoDigito = set of Digito;
TipoCandidatos = array [Rango9,Rango9] of ConjuntoDigito;
El tipo set de Pascal es utilizado para representar el conjunto de candidatos de una celda libre.

Para las celdas ocupadas el conjunto de candidatos es irrelevante por lo que lo tomaremos como el conjunto vacío.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

tarea sudoku sin terminar

Publicado por ramon (2158 intervenciones) el 24/10/2012 18:27:01
Como te mencione antes te pase lo del sudoku, y en [genera_sudoku] se encuentra CrearCandidatos ya que crea el sudoku total fíjate que cada celda toma un valor con
las condiciones que rigen el el sudoku.
No octante te mirare a ver si puedo pasarlo a un nivel mas sencillo.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

tarea sudoku sin terminar

Publicado por Monchita (9 intervenciones) el 24/10/2012 19:37:15
Ok muchas gracias
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar