Risolvere Sudoku in C++?

Samueleex

Dopo aver imparato a giocare come si fa a non creare una logica in C++ che ti permette di risolverli automaticamente?
Nel complesso tutto il codice si divide in due parti. Una che grazie ad un loop crea le possibili soluzioni, continuando fino a quando il gioco non viene arrestato, significa che continuerà all'infinito fino al completamento con Brute Force tramite ricorsione!

La struttura cell_structrappresenta una cella sul Sudoku ed è composta da:

rowe col: le coordinate della cella nella griglia del Sudoku.
cell: l'indice della macrocella a cui appartiene la cella.
size: il numero di possibili valori per la cella.
notes: un array booleano che tiene traccia dei possibili valori per la cella.
Si può dire sicuramente che la classe SudokuSolver è il cuore del programma.

Il builder inizializza la griglia di gioco con tutti i valori iniziali a 0.

Il metodo set_rowsconsente di impostare i valori della griglia di gioco.
Il metodo get_rowsconsente di ottenere i valori attuali della griglia di gioco.
Il metodo load_filecarica una configurazione di gioco da un file specificato.
Il metodo write_filesalva la configurazione corrente della griglia di gioco su un file specificato inclusi eventuali appunti (notes) sulle celle.
solverisolve il Sudoku utilizzando un algoritmo di backtracking.
Altre funzioni usate: make_notes, check, to_full, join_sugge get_macro

#include <iostream>
#include <math.h>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

struct cell_struct {
	int row, col, cell, size;
	bool notes[10];

	bool operator<(const cell_struct &b) const
	{
		return this->size < b.size;
	};
};

class SudokuSolver
{
	public:
		SudokuSolver();

		void set_rows(int rows[][10]);
		void get_rows(int rows[][10]);

		bool load_file(string filename);
		bool write_file(string filename, bool print_notes = true);

		bool solve();

	private:
		void make_notes();

		bool check();

		int to_full(bool complete[], bool the_set[]);
		int join_sugg(bool joint[], bool a[], bool b[]);

		int get_macro(int row, int column);

		int rows[10][10];
		vector<cell_struct> notes;
};

SudokuSolver::SudokuSolver()
{

	int i, j;
	for(i = 1; i < 10; i++)
	{
		for(j = 1; j < 10; j++)
		{
			this->rows[i][j] = 0;
		}
	}
}

void SudokuSolver::set_rows(int rows[][10])
{
	int i, j;
	for(i = 1; i < 10; i++) {
		for(j = 1; j < 10; j++) {
			this->rows[i][j] = rows[i][j];
		}
	}
}


void SudokuSolver::get_rows(int rows[][10])
{
	int i, j;
	for(i = 1; i < 10; i++) {
		for(j = 1; j < 10; j++) {
			rows[i][j] = this->rows[i][j];
		}
	}
}


bool SudokuSolver::load_file(string filename)
{
	int num;
	int i, j;


	ifstream in;
	in.open(filename.c_str());


	if(!in.is_open()) {
		return false;
	}


	for(i = 1; i < 10; i++) {
		for(j = 1; j < 10; j++) {
			in >> num;
			num = (num < 10 && num > 0) ? num : 0;
			this->rows[i][j] = num;
		}
	}


	in.close();

	return true;
}


bool SudokuSolver::write_file(string filename, bool print_notes)
{
	ofstream out;
	out.open(filename.c_str());


	if(!out.is_open()) {
		return false;
	}


	int i, j;
	for(i = 1; i < 10; i++) {
		for(j = 1; j < 10; j++) {
			out << this->rows[i][j] << " ";
		}
		out.seekp(-1, ios_base::cur);
		out << endl;
	}


	if(print_notes) {
		out << endl << endl << "NOTES" << endl << endl;
		vector<cell_struct>::iterator it;
		for(it=this->notes.begin(); it!=this->notes.end(); ++it) {
			out << "Cell " << it->row << "x" << it->col << " " <<  it->size << ":";
			
			for(i = 1; i < 10; i++) {
				if(it->notes[i])
					out << " " << i;
			}
			out << endl;
		}
	}


	out.close();

	return true;
}


bool SudokuSolver::solve()
{



	vector<cell_struct>::iterator it;


	int to_solve = 90;


	bool changed = true;
	while(changed) {

		changed = false;


		this->make_notes();


		sort(this->notes.begin(), this->notes.end());
		for(it=this->notes.begin(); it!=this->notes.end(); ++it) {
			if(this->rows[it->row][it->col] != 0) {
			} else if(it->size == 1) {
				int i;
				for(i = 1; i < 10; i++) {
					if(it->notes[i]) {
						this->rows[it->row][it->col] = i;
						changed = true;
						break;
					}
				}
			}
		}


		to_solve = this->notes.size();
	}

	if(to_solve == 0)
		return this->check();


	SudokuSolver * bruteforcer = new SudokuSolver();
	int i;
	it = this->notes.begin();
	for(i = 1; i < 10; i++) {

		if(!it->notes[i])
			continue;
		this->rows[it->row][it->col] = i;

    
		bruteforcer->set_rows(this->rows);
		if(bruteforcer->solve()) {
			bruteforcer->get_rows(this->rows);
			return true;
		}


		this->rows[it->row][it->col] = 0;
	}

	return false;
}


void SudokuSolver::make_notes()
{
	int num;
	int i, j, k, size;

	bool row[10][10], col[10][10], cell[10][10], already[10];
	cell_struct the_cell;


	this->notes.erase(this->notes.begin(), this->notes.end());


	for(i = 1; i < 10; i++) {
		for(j = 1; j < 10; j++) {
			row[i][j] = false;
			col[i][j] = false;
			cell[i][j] = false;
		}
	}

	for(i = 1; i < 10; i++) {
		for(j = 1; j < 10; j++) {
			num = this->rows[i][j];

			if(num == 0)
				continue;

			row[i][num] = true;
			col[j][num] = true;
			cell[this->get_macro(i, j)][num] = true;
		}
	}

	for(i = 1; i < 10; i++) {
		for(j = 1; j < 10; j++) {
			num = this->rows[i][j];

			if(num != 0)
				continue;

			k = this->get_macro(i, j);

			this->join_sugg(already, row[i], col[j]);
			this->join_sugg(already, already, cell[k]);
			size = this->to_full(the_cell.notes, already);

			the_cell.row = i;
			the_cell.col = j;
			the_cell.cell = k;
			the_cell.size = size;
			this->notes.push_back(the_cell);
		}
	}
}


bool SudokuSolver::check()
{
	bool row[10][10], col[10][10];
	int i, j;


	for(i = 1; i < 10; i++) {
		for(j = 0; j < 10; j++) {
			row[i][j] = false;
			col[i][j] = false;
		}
	}


	for(i = 1; i < 10; i++) {
		for(j = 1; j <10; j++) {
			if(row[j][this->rows[i][j]] || col[i][this->rows[i][j]]) {
				return false;
			} else {
				row[j][this->rows[i][j]] = true;
				col[i][this->rows[i][j]] = true;
			}
		}
	}

	return true;
}

int SudokuSolver::to_full(bool complete[], bool the_set[])
{
	int size = 0;
	int i;
	for(i = 1; i < 10; i++) {
		complete[i] = !the_set[i];
		size += complete[i] ? 1 : 0;
	}

	return size;
}


int SudokuSolver::join_sugg(bool joint[], bool a[], bool b[])
{
	int ret = 0, i;
	for(i = 1; i < 10; i++) {
		joint[i] = a[i] || b[i];
		ret += joint[i] ? 1 : 0;
	}

	return ret;
}


int SudokuSolver::get_macro(int row, int column)
{
	int urow, ucol;

	row--;
	column--;

	urow = floor(row / 3) * 3;
	ucol = floor(column / 3);

	return urow + ucol + 1;
}


int main(int argc, char *argv[])
{
	SudokuSolver * s = new SudokuSolver();

	s->load_file("input.txt");

	bool ok = s->solve();
	if(ok)
		cout << "Risolto!" << endl;
	else
		cout << "Qualcosa non va!" << endl;

	s->write_file("output.txt", !ok);
}

Giulio_M

Samueleex interessante, merita di essere commentato per bene (personalmente cercavo anche una soluzione di altro genere tramite equazioni matematiche, magari questa idea riuscirò a completarla in un'altra vita 😊).

Preciso come prima cosa un dettaglio per la compilazione (usando gcc da terminale, programmando in C, qui ho dovuto fare invece qualche modifica): consiglio quindi di compilare tramite il comando: g++ nomefile.c -o nomefile.
La compilazione è diretta, altrimenti tramite gcc occorre specificare in input l'inclusione delle varie librerie (es. aggiungendo il parametro -lm per <math.h>, ecc).

Partendo da un file iniziale chiamato input.txt dove consiglio di inserire un carattere (es. "x") al posto dei numeri a noi sconosciuti, se avviamo il programma prende in input questo e stampa il risultato, completato, nel file output.txt. Altrimenti il programma genera un file di output.txt di default.

Volendo potremmo fare una modifica di questa parte, ovvero mostrare errore se non esiste il file input.txt (ad esempio il messaggio "Qualcosa non va!"), anziché generare un output.txt di default, casuale. Il codice in tal caso si modifica come segue (ho anche aggiunto i commenti):

SudokuSolver * s = new SudokuSolver();

if(s->load_file("input.txt")){ //verifica se esiste il file input.txt, se non esiste dà errore
bool ok = s->solve();
	if(ok)
		cout << "Risolto!" << endl;
	else
		cout << "Qualcosa non va!" << endl;

	s->write_file("output.txt", !ok);
}else{
cout << "Qualcosa non va!" << endl;
	
}

Altre piccole precisazioni, ma sono solo "sottigliezze", dal punto di vista dell'ottimizzazione del codice, trattandosi di una griglia piccola (9x9) dove abbiamo variabili di tipo int, esse potrebbero essere semplicemente unsigned char; così come un'altra sottigliezza, dichiarando ad esempio int i,j; queste variabili vengono memorizzate nella memoria centrale (RAM), per gli indici di un ciclo, che possono comportare un numero elevato di operazioni, un'ulteriore sottigliezza è quello di memorizzarle nel registro della CPU dato che l'accesso a tale area di memoria è più rapido (zona di memoria più piccola, ma memorizziamo solo poche variabili, quelle più significative ovvero gli indici di un ciclo), quindi ad esempio scrivendo register int i,j;. In questo caso la differenza non è così impattante.

Fondatori