Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

RESOLVIENDO SUDOKU POR BACKTRACKING

Solución del pasatiempo SUDOKU por la técnica de backtracking
by

Robert Smith

on 29 November 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of RESOLVIENDO SUDOKU POR BACKTRACKING

RESOLVIENDO SUDOKU POR BACKTRACKING BACKTRACKING (vuelta atrás o retroceso)

Es una técnica de programación para hacer búsqueda sistemática a través de todas las configuraciones posibles dentro de un espacio de búsqueda. SUDOKU (palabra de origen japones -
su, "número" y doku, "único")

El objetivo del sudoku es rellenar una cuadrícula
de 9 × 9 celdas (81 casillas) dividida en cuadrícula 3 × 3 (también llamadas "cajas" o "regiones") con las cifras del 1 al 9 partiendo con varias celdas con un valor inicial, de modo que debemos empezar a resolver el problema a partir de esta solución
parcial sin modificar ninguna de las celdas
iniciales. SOLUCION DE SUDOKU POR BACKTRACKING Restricciones explícitas (indican qué valores pueden adoptar las componentes de la solución ):
sudoku[i; j] [0..9]:
- Si sudoku[i; j] = 0 -> La casilla está vacía.
- Si sudoku[i; j] [1..9] -> La casilla has sido rellenada con un valor válido hasta el momento. Restricciones implícitas (indican qué conjuntos de valores para el Sudoku determinan soluciones validas):
los valores de cada fila deben ser distintos entre sí.
Para todo i; j1, j2 [1..9] (j1 <> j2 ) à sudoku[i, j1] <> sudoku[i, j2])
los valores de cada columna deben ser distintos entre sí.
Para todo i1, i2, j 2 [1..9] (i1 <> i2 ) -> sudoku[i1, j] <> sudoku[i2, j])
los valores de cada sector (subgrupo de 9) deben ser distintos entre sí.
Para todo (i1, j1), (i2, j2) [1..9, 1..9] ((((i1, j1) <> (i2, j2)) ^ (Sector(i1, j1) = Sector(i2, j2))) )
-> sudoku[i1, j1] <> sudoku[i2, j2]) Ingrid Julieth Martinez
Jair Guerrero
Jorge A. Perdomo
Full transcript