Con una scelta, si seleziona un valore per una variabile . Una buona strategia è selezionare una variabile con una piccola quantità di valori possibili rimasti. Poi ti propaghi di nuovo e possibilmente fai un'altra scelta e così via.
È possibile che il programma scopra che una scelta è sbagliata: rende vuoto il dominio di una o più variabili. In tal caso, è backtrack: si annulla una scelta effettuata in precedenza (oltre alla propagazione effettuata dopo quella scelta) e si seleziona un altro valore.
Questa risposta evidentemente non mira a fornire una panoramica approfondita dell'argomento, ma lo Wikipedia page può fornire una panoramica migliore e indicazioni per ulteriori informazioni.
ci sono vincolo programmazione risolutori come Eclipse (non l'IDE), MiniZinc, ecc dove si può semplicemente definire le variabili, i domini e vincoli.
Risolvere il problema con Eclipse
Sul sito di Eclipse, è possibile trovare a model for sudoku. Dato che leggi alcuni documenti su ECLiPSe, puoi trasformare questo file in un modello per multi-sudoku. Ho fatto alcune piccole modifiche risultanti nella soluzione quick-and-dirty seguente:
% credits to Joachim Schimpf for his model of sudoku
% http://eclipseclp.org/examples/sudoku.ecl.txt
:- lib(ic).
:- import alldifferent/1 from ic_global.
solve(ProblemName) :-
problem(ProblemName,BA,BB),
multi_sudoku(3,BA,BB),
print_board(BA),
print_board(BB).
multi_sudoku(N,BA,BB) :-
sudoku(N,BA,VA),
sudoku(N,BB,VB),
N2 is N*N,
Inc is N2-N,
(multifor([I,J],1,N,1),param(BA,BB,Inc) do
BA[I+Inc,J+Inc] #= BB[I,J]
),
append(VA,VB,Vars),
labeling(Vars).
sudoku(N,Board,Vars) :-
N2 is N*N,
dim(Board,[N2,N2]),
Board[1..N2,1..N2] :: 1..N2,
(for(I,1,N2), param(Board,N2) do
Row is Board[I,1..N2],
alldifferent(Row),
Col is Board[1..N2,I],
alldifferent(Col)
),
(multifor([I,J],1,N2,N), param(Board,N) do
(multifor([K,L],0,N-1), param(Board,I,J), foreach(X,SubSquare) do
X is Board[I+K,J+L]
),
alldifferent(SubSquare)
),
term_variables(Board, Vars).
print_board(Board) :-
dim(Board, [N,N]),
(for(I,1,N), param(Board,N) do
(for(J,1,N), param(Board,I) do
X is Board[I,J],
(var(X) -> write(" _") ; printf(" %2d", [X]))
), nl
), nl.
%----------------------------------------------------------------------
% Sample data
%----------------------------------------------------------------------
problem(1, [](
[](_, _, _, _, 6, _, _, _, _),
[](_, _, _, 4, _, 9, _, _, _),
[](_, _, 9, 7, _, 5, 1, _, _),
[](_, 5, 2, _, 7, _, 8, 9, _),
[](9, _, _, 5, _, 2, _, _, 4),
[](_, 8, 3, _, 4, _, 7, 2, _),
[](_, _, _, 2, _, 8, _, _, _),
[](_, _, _, 6, _, 4, _, _, _),
[](_, _, _, _, 5, _, _, _, _)
),
[](
[](_, _, _, _, 3, _, _, _, _),
[](_, _, _, 8, _, 7, _, _, _),
[](_, _, _, 1, _, 6, 3, _, _),
[](_, 9, 8, _, _, _, 1, 2, _),
[](2, _, _, _, _, _, _, _, 3),
[](_, 4, 3, _, _, _, 6, 5, _),
[](_, _, 7, 3, _, 5, 9, _, _),
[](_, _, _, 4, _, 2, _, _, _),
[](_, _, _, _, 6, _, _, _, _)
)
).
I "preso in prestito" il modello del sudoku da Joachim Schimpf, quindi i crediti a lui.Si noti inoltre che questa risposta non consiglia di utilizzare ECLiPSe su un altro strumento. Ho semplicemente più familiarità con la toolchain Prolog quando si tratta di programmazione dei vincoli. Ma se sei più interessato al C++, il metodo Gecode farà il trucco con circa le stesse (o anche migliori) prestazioni.
che genera l'output:
ECLiPSe Constraint Logic Programming System [kernel]
Kernel and basic libraries copyright Cisco Systems, Inc.
and subject to the Cisco-style Mozilla Public Licence 1.1
(see legal/cmpl.txt or http://eclipseclp.org/licence)
Source available at www.sourceforge.org/projects/eclipse-clp
GMP library copyright Free Software Foundation, see legal/lgpl.txt
For other libraries see their individual copyright notices
Version 6.1 #199 (x86_64_linux), Sun Mar 22 09:34 2015
[eclipse 1]: solve(1).
lists.eco loaded in 0.00 seconds
WARNING: module 'ic_global' does not exist, loading library...
queues.eco loaded in 0.00 seconds
ordset.eco loaded in 0.01 seconds
heap_array.eco loaded in 0.00 seconds
graph_algorithms.eco loaded in 0.03 seconds
max_flow.eco loaded in 0.00 seconds
flow_constraints_support.eco loaded in 0.00 seconds
ic_sequence.eco loaded in 0.01 seconds
ic_global.eco loaded in 0.07 seconds
2 1 4 8 6 3 9 5 7
8 7 5 4 1 9 2 6 3
6 3 9 7 2 5 1 4 8
4 5 2 3 7 1 8 9 6
9 6 7 5 8 2 3 1 4
1 8 3 9 4 6 7 2 5
5 4 1 2 3 8 6 7 9
7 2 8 6 9 4 5 3 1
3 9 6 1 5 7 4 8 2
6 7 9 5 3 4 2 8 1
5 3 1 8 2 7 4 6 9
4 8 2 1 9 6 3 7 5
7 9 8 6 5 3 1 2 4
2 6 5 7 4 1 8 9 3
1 4 3 2 8 9 6 5 7
8 2 7 3 1 5 9 4 6
9 1 6 4 7 2 5 3 8
3 5 4 9 6 8 7 1 2
Ha preso la mia macchina di circa 0,11 secondi. Inoltre ci sono 60 soluzioni valide in totale.
Le ultime due "matrici" mostrano la soluzione per i due Sudoku. Come puoi vedere (non l'ho verificato completamente), condividono un blocco (lo stesso output) e tutti i vincoli di sudoku sono validi. Una rappresentazione più conveniente della soluzione è la seguente:
+-----+-----+-----+
|2 1 4|8 6 3|9 5 7|
|8 7 5|4 1 9|2 6 3|
|6 3 9|7 2 5|1 4 8|
+-----+-----+-----+
|4 5 2|3 7 1|8 9 6|
|9 6 7|5 8 2|3 1 4|
|1 8 3|9 4 6|7 2 5|
+-----+-----+-----+-----+-----+
|5 4 1|2 3 8|6 7 9|5 3 4|2 8 1|
|7 2 8|6 9 4|5 3 1|8 2 7|4 6 9|
|3 9 6|1 5 7|4 8 2|1 9 6|3 7 5|
+-----+-----+-----+-----+-----+
|7 9 8|6 5 3|1 2 4|
|2 6 5|7 4 1|8 9 3|
|1 4 3|2 8 9|6 5 7|
+-----+-----+-----+
|8 2 7|3 1 5|9 4 6|
|9 1 6|4 7 2|5 3 8|
|3 5 4|9 6 8|7 1 2|
+-----+-----+-----+
Non so di una libreria di programmazione in Python vincolo, né so di un porto di Eclipse a Python. Ma la mia esperienza è che tutti i moderni linguaggi di programmazione hanno questo strumento.
Il vantaggio di utilizzare uno strumento di programmazione a vincoli come Eclipse, Gecode, ... è prima di tutto quello che devi solo specificare il problema, come si è risolto è qualcosa che si don' devo preoccuparmi Inoltre, tali librerie implementano 30 anni di ricerca sulla programmazione di vincoli: sono estremamente ottimizzati, sfruttano vincoli e strutture in un modo in cui la maggior parte delle persone non può immaginare e hanno meno probabilità di contenere bug (rispetto a un algoritmo personalizzato). Inoltre, se vengono trovate nuove strategie, algoritmi, ... un aggiornamento di ECLiPSe comporterà un'elaborazione più veloce del modello.
Un svantaggio è che alcuni problemi difficili non possono ancora essere risolti utilizzando la programmazione a vincoli: lo spazio di ricerca è semplicemente troppo grande, i vincoli sono quel complesso che i domini non sono ridotti a piccoli insiemi, e non c'è abbastanza potenza di elaborazione per fare abbastanza scelte al fine di trovare una soluzione valida. Un altro svantaggio è che non è sempre facile specificare un problema: sebbene i programmatori mirino a progettare buoni vincoli, ci sono sempre problemi complessi in cui non sono definiti vincoli facili da usare.
Altre tecniche
Evidentemente ci sono altre tecniche di intelligenza artificiale per risolvere i problemi. Una tecnica che viene comunemente utilizzata per affrontare i problemi di ricerca e ottimizzazione è calcolo evolutivo: si inizia col riempire il sudoku permettendo che alcuni valori siano errati, quindi ad ogni passo temporale mirano a correggere uno o più campi. A volte introducono nuovi errori al fine di trovare una soluzione valida alla fine.
Hai un'idea di come risolvere un sudoku in generale? Una volta capito, il passo verso un multi-sudoku non è difficile. –
Bene, ci sono diverse soluzioni intuitive quando ci penso in termini di un singolo gioco di sudoku. Ma volevo sapere cosa pensavano gli altri per vedere se c'erano soluzioni più eleganti/meno intuitive/non sembravano un'estensione hacky della singola soluzione di sudoku. –
Ah, deve essere stato un refuso inconscio; Lo sto codificando in python. Lo modificherò ora. –