Tl;dr version: ho provato a fare un algoritmo per risolvere sudoku ma con quelli più diffici sbaglia. Voi che algorimo usereste?
__________________________________________________________________________________
Long version:
Sto provando a fare un risolutore di sudoku 4x4 ma l'algoritmo che ho fatto ogni tanto sballa(quando ci sono troppe celle vuote per riga o colonna)
Io l'avevo pensato così:
metto il sudoku in una matrice (lo 0 al posto delle celle vuote), poi per ogni cella faccio queste operazioni:
-ho un vettore di supporto grande 4 che contiene solo 0
-se la cella che sto esaminando è vuota controllo sulla riga, sulla colonna e nella "zona" 2x2 dove si trova la cella che sto esaminando e metto a 1 i valori corrispondenti che trovo. (Per esempio se sulla riga e sulla colonna trovo i valori 2 4 3 il mio vettore si supporto sarà 0 1 1 1)
-trovo quale valore dei vettori è a 0 e lo metto nella matrice
Ho appurato che questo algoritmo non funziona quando nel vettore di supporto ho più di uno zero.
Ho pensato di mettere un altro if che controlli se c'è più di uno 0 nel vettore di supporto ed in tal caso non scrive niente, e poi faccio ri-eseguire l'algoritmo per cercare di rimpire i buchi che ho lasciato.
Questa soluzione però non mi soddisfa. Sapete consigliarmi qualche algoritmo migliore?
Questo è quello che ho descritto:
*/
/*sudoku di esempio:
4 0 0 1
2 0 4 0
0 0 0 0
0 2 0 0
*/
//sudoku versione 4x4
#include <iostream>
#include <fstream>
using namespace std;
int main() {
fstream in,out;
in.open("insu.txt",ios::in); //file dov ho il sudoku
int rig=4, col= 4, i,k,crig,ccol,cquad,tmp,reset=0;
int matrix[rig][col];
int ck[4]= {0,0,0,0};
int inrig,incol;
//prendo i numeri dal file insu.txt
for (i=0; i<rig; i++) {
for (k=0;k<col; k++) {
in>>matrix[i][k];
}
}
in.close();
//qua inizia il bello
for (i=0; i<rig; i++) {
for (k=0;k<col; k++) {
if(matrix[i][k]==0) {
for (crig=0; crig<rig; crig++) {
if(matrix[crig][k]!=0)
ck[matrix[crig][k]-1]=1;
}
for (ccol=0; ccol<col; ccol++) {
if(matrix[i][ccol]!=0)
ck[matrix[i][ccol]-1]=1;
}
if(i<2 && k<2) {
//cicla nella 1,1
for (inrig=0; inrig<2; inrig++) {
for (incol=0; incol<2; incol++) {
if(matrix[inrig][incol]!=0)
ck[matrix[inrig][incol]-1]=1;
}
}
}
if(i<2 && k>2) {
//cicla nella 1,2
for (inrig=2; inrig<4; inrig++) {
for (incol=0; incol<2; incol++) {
if(matrix[inrig][incol]!=0)
ck[matrix[inrig][incol]-1]=1;
}
}
}
if(i>2 && k<2) {
//cicla nella 2,1
for (inrig=0; inrig<2; inrig++) {
for (incol=2; incol<4; incol++) {
if(matrix[inrig][incol]!=0)
ck[matrix[inrig][incol]-1]=1;
}
}
}
if(i>2 && k>2) {
//cicla nella 2,2
for (inrig=2; inrig<4; inrig++) {
for (incol=2; incol<4; incol++) {
if(matrix[inrig][incol]!=0)
ck[matrix[inrig][incol]-1]=1;
}
}
}
///controlli finiti
for (tmp=0; tmp<4; tmp++) {
if(ck[tmp]==0) {
matrix[i][k]=tmp+1;
}
}
}
//riazzero il vettore
for (tmp=0; tmp<4; tmp++) {
ck[tmp]=0;
}
//fin???
}
}
//fin prendo num
for (i=0; i<rig; i++) {
for (k=0;k<col; k++) {
cout<<matrix[i][k]<<" ";
}
cout<<endl;
}
}