Gioco delle N lampadine tutte spente (come fare?)

[gimasci99]

Ciao a tutti.
Ripropongo il quesito in oggetto postato nella sezione sbagliata avendo effettivamente un interesse più informatico che orientato al gioco. Di seguito il link del post nella sezione sbagliata.

https://www.matematicamente.it/forum/viewtopic.php?f=12&t=202810

Per comodità ricopio il problema:

Ho N lampadine accese/spente a caso. Ho N interruttori con ciascun interruttore che cambia lo stato di M lampadine predefinite contemporaneamente. Trovare la sequenza del minimo numero di interruttori da premere in modo che tutte le lampadine si spengano.

Facciamo un esempio con N=6:
Sia lo stato iniziale (1=accesa e 0=spenta) delle 6 lampadine (da 1 a 6 da sx verso dx):
1 0 1 0 1 1

Di seguito il comportamento dei 6 interruttori:
1: 1 6 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 1 e 6)
2: 2 5 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 2 e 5)
3: 3 5 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 3 e 5)
4: 3 4 6 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 3, 4 e 6)
5: 2 5 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 2 e 5)
6: 3 4 6 (ossia commuta contemporaneamente da acceso a spento e viceversa lo stato delle lampadine 3, 4 e 6)

Ora ragionandoci un pochino è lampante che per spegnere tutte le lampadine basta premere gli interruttori 1 e 3 perchè:
stato iniziale:
1 0 1 0 1 1
premendo l'interruttore 1 si cambia lo stato delle lampadine 1 e 6 e si passa a:
0 0 1 0 1 0
premendo l'interruttore 3 si cambia lo stato delle lampadine 3 e 5 e si passa a:
0 0 0 0 0 0
portando le lampadine ad essere tutte spente

Ma se abbiamo N lampadine con N interruttori che commutano M lampadine generate casualmente come posso impostare la ricerca della soluzione con un algoritmo?

Voi come impostereste l'algoritmo per la ricerca della soluzione a questo problema?

Grazie,
Giovanni.

[vict85]

Hai provato usando Dijkstra?

[gimasci99]

Hai provato usando Dijkstra?

Grazie per l'interessamento.
Ho risolto elegantemente con il metodo di eliminazione di Gauss.