bytes.cat

La wiki d'FP d'informàtica

Eines de l'usuari

Eines del lloc


Barra lateral

ASIX Administració de Sistemes Informàtics i Xarxes
Tots els mòduls del cicle
MP01 Implantació de sistemes operatius
Totes les UFs del modul
MP02 Gestió de bases de dades
Totes les UFs del modul
MP03 Programació bàsica
Totes les UFs del modul
MP04 Llenguatges de marques i sistemes de gestió d'informació
Totes les UFs del modul
MP05 Fonaments de maquinari
Totes les UFs del modul
MP06 Administració de sistemes operatius
Totes les UFs del modul
MP07 Planificació i administració de xarxes
Totes les UFs del modul
MP08 Serveis de xarxa i Internet
Totes les UFs del modul
MP09 Implantació d'aplicacions web
Totes les UFs del modul
MP10 Administració de sistemes gestors de bases de dades
Totes les UFs del modul
MP11 Seguretat i alta disponibilitat
Totes les UFs del modul
MP12 Formació i orientació laboral
Totes les UFs del modul
MP13 Empresa i iniciativa emprenedora
Totes les UFs del modul
MP14 Projecte
Totes les UFs del modul
DAM Desenvolupament d’aplicacions multiplataforma
Tots els mòduls del cicle
MP01 Sistemes informàtics
Totes les UFs del modul
MP02 Bases de dades
Totes les UFs del modul
MP03 Programació bàsica
Totes les UFs del modul
MP04 Llenguatges de marques i sistemes de gestió d'informació
Totes les UFs del modul
MP05 Entorns de desenvolupament
Totes les UFs del modul
MP06 Accés a dades
Totes les UFs del modul
MP07 Desenvolupament d’interfícies
Totes les UFs del modul
MP08 Programació multimèdia i dispositius mòbils
Totes les UFs del modul
MP09 Programació de serveis i processos
Totes les UFs del modul
MP10 Sistemes de gestió empresarial
Totes les UFs del modul
MP11 Formació i orientació laboral
Totes les UFs del modul
MP12 Empresa i iniciativa emprenedora
Totes les UFs del modul
MP13 Projecte de síntesi
Totes les UFs del modul
MPDual Mòdul Dual / Projecte
DAW Desenvolupament d’aplicacions web
Tots els mòduls del cicle
MP01 Sistemes informàtics
Totes les UFs del modul
MP02 Bases de dades
Totes les UFs del modul
MP03 Programació
Totes les UFs del modul
MP04 Llenguatge de marques i sistemes de gestió d’informació
Totes les UFs del modul
MP05 Entorns de desenvolupament
Totes les UFs del modul
MP06 Desenvolupament web en entorn client
Totes les UFs del modul
MP07 Desenvolupament web en entorn servidor
Totes les UFs del modul
MP08 Desplegament d'aplicacions web
Totes les UFs del modul
MP09 Disseny d'interfícies web
Totes les UFs del modul
MP10 Formació i Orientació Laboral
Totes les UFs del modul
MP11 Empresa i iniciativa emprenedora
Totes les UFs del modul
MP12 Projecte de síntesi
Totes les UFs del modul
SMX Sistemes Microinformàtics i Xarxes
Tots els mòduls del cicle
MP01 Muntatge i manteniment d’equips
Totes les UFs del modul
MP02 Sistemes Operatius Monolloc
Totes les UFs del modul
MP03 Aplicacions ofimàtiques
Totes les UFs del modul
MP04 Sistemes operatius en xarxa
Totes les UFs del modul
MP05 Xarxes locals
Totes les UFs del modul
MP06 Seguretat informàtica
Totes les UFs del modul
MP07 Serveis de xarxa
Totes les UFs del modul
MP08 Aplicacions Web
Totes les UFs del modul
MP09 Formació i Orientació Laboral
Totes les UFs del modul
MP10 Empresa i iniciativa emprenedora
Totes les UFs del modul
MP11 Anglès
Totes les UFs del modul
MP12 Síntesi
Totes les UFs del modul
CETI Ciberseguretat en Entorns de les Tecnologies de la Informació
Tots els mòduls del cicle
CiberOT Ciberseguretat en Entorns d'Operació
Tots els mòduls del cicle
sudoku_php

Sudoku en PHP

Guia pràctica per construir un joc de sudoku en PHP.

Iteració 1 : formulari buit jugable

Fer un formulari de Sudoku que ens digui si els números introduïts compleixen les regles del Sudoku.

Guia per realitzar l'exercici:

  1. Fer una taula de 9×9 amb marques adequades per indicar els quadrants del Sudoku.
  2. Afegir menús desplegables per cada casella.
  3. Aconseguir que el formulari s'envii i que es mantinguin els números que l'usuari ha seleccionat.
  4. Elaborar funcions de comprovació. Es recomana posar-les en un arxiu apart i fer-hi un include:
    • comprova_fila($fila)
    • comprova_columna($columna)
    • comprova_quadrant($quadrant)
  5. Comprovar que el que envia l'usuari compleix les regles del Sudoku.


Iteració 2: crear partida

Farem unes passes per generar una partida amb cel·les predefinides. Guia:

  1. Crear un nombre N de números aleatoris (de l'1 al 9) i distribuir-los per la quadrícula. Inicialment provem amb N=15.
  2. Guardar els nombres generats a la variable $_SESSION. Assegura't que si fas F5 (recàrrega de pàgina) els nombres no es tornen a generar (partida activa).
  3. A les caselles on hi ha un número fix, no s'ha de posar el SELECT (o dropdown menu) i pintarem el número assignat (només lectura).
  4. Assegurar-se que els nombres generats compleixen les normes del Sudoku que hem implementat amb les funcions de la iteració 1.


Iteració 3: jugar partida

Abans que res caldrà que modifiquis les funcions comprova_fila($fila), comprova_columna($columna) i comprova_quadrant($quadrant), per tal que no només miri les dades enviades per $_POST (formulari) sinó que també tingui en compte les cel·les fixes guardades a la variable $_SESSION.

Amb el què tenim el jugador pot avançar en jugar una partida, però cal un pas important: determinar el final de partida.

Quan detectis que el taulell del Sudoku està resolt correctament, dóna un missatge de felicitació.

NOTA: la partida finalitza quan es passa positivament els tests de totes les files, columnes i quadrants, i a més s'han omplert totes les cel·les.


Iteració 4: solver amb backtrack

Secció només per a les més agosarades!

Si has resolt fins aquí i ets dels més agosarats, voldràs provar de trobar solució a la partida que has generat de forma automàtica. Això es pot fer amb un clàssic algorisme de backtracking. En el fons, aquest el què fa és provar sistemàticament totes les combinacions possibles fins que troba una de vàlida, similarment al que coneixem per un «atac de força bruta».

Aquí tens una breu explicació i psuedo-codi de l'algorisme de backtrack recursiu per al Sudoku.

helloacm.com_wp-content_uploads_2020_08_sudoku-solver.jpg

Hi ha moltes tècniques de resolució de sudokus com joc (X-wing, Y-wing, etc). Aquestes són «fàcils» d'utilitzar per persones, però no son fàcils d'implementar en un programa.

En canvi, el backtrack seria una tècnica molt difícil que segueixi una persona, però més fàcil d'implementar en un programa. No és un algorisme òptim, en el sentit en què triga molt i consumeix CPU i memòria, però funciona.

Una optimització senzilla del backtrack que pot disminuir molt el temps de computació seria disposar d'una matriu extra on posaríem els valors vàlids per a cada cel·la, descartant valors impossibles (els que hi hagi a la fila, columna i quadrant de la cel·la). Llavors el bucle que fem pels possibles valors de la cel·la dins elbacktrack es redueix i el temps de càlcul es redueix considerablement.

Implementar el backtrack del Sudoku.

Fes-ho en una pàgina específica, per exemple solver.php, on pots agafar la partida emmagatzemada a la variable de sessió i resoldre-la.


Iteració 5: check partida resoluble

Quan inicialitzem una partida aleatòriament, encara que els nombres que posem compleixin les regles del Sudoku (no repetir números en files, columnes ni quadrants) això no assegura que aquesta partida sigui resoluble.

Per assegurar-nos, quan creem una partida, abans de passar-la a l'usuari, li aplicarem el Solver que hem realitzat a la iteració anterior, el qual ens dirà si té solució o no (i en un temps raonable, pel què ha d'estar optimitzat).

A més, les regles del Sudoku inclouen un altre requisit: que la partida no tingui vàries solucions, sinó només una de sola. Per tant, haurem de modificar el nostre solver perquè també ens determini si té més d'una solució. Si ens dona una 2a solució, tornarem a descartar la partida.


sudoku_php.txt · Darrera modificació: 2022/10/17 18:41 per enrique_mieza_sanchez