DOCUMENTACIÓ 8-PUZZLE


Descripció

Tenim un puzzle en forma de tauler de 3 files per 3 columnes, on una de les caselles està buida. Donada una situació inicial del puzzle, es pretén arribar a una situació final també donada. Una peça del puzzle només es pot moure cap a la casella buida si és veïna d'aquesta horitzontalment o vertical.

Exemple:

El puzzle A, amb un sol moviment pot generar els puzzles B, C o D.

A

1

2

3

4

5

6

7

8

B

1

2

3

4

6

7

5

8

C

1

2

3

4

5

6

7

8

D

1

2

3

4

5

6

7

8

(Representem les peces com a números (del 1 al 8) i la casella buida com a blanc.)

Per evitar cicles, anem guardant en una llista tots els nodes generats (tractats o pendents de ser tractats). Cada cop que generem els fills del node visitat, eliminem aquells fills que estan a la llista. Aquest procés, pot provocar que l'arbre d'exploració d'un algorisme sigui diferent de l'arbre d'un altre, per als mateixos puzzles inicial i final.

Heurístiques i Cost

- Heurístiques:

- Cost: Nombre de passos per arribar a aquest puzzle des del puzzle inicial.

- Exemples:

Node inicial

1

2

3

4

6

7

8

5

Node solució

1

2

3

4

5

6

7

8

1

2

3

4

6

7

8

5

1

2

3

4

6

7

8

5

1

2

3

4

6

5

7

8

1

2

4

6

3

7

8

5

Primer exemple:

Segon exemple:

Tercer exemple:

Quart exemple:

Inici Anterior