Coder Forum

C Quellcode

// Copyright Christoph Egger
//Berechnet eine Mögliche Lösung für das Sudoku
//Als eingabe wird eine Textdatei mit 9 Zeilen zu je 9 Zahlen mit ' ' als
//Abstand angenommen, 0 steht für ein Leeres Feld
#include <stdio.h>
 
 
 
 
 
bool step(int feld[9][9], int filled, int searchdepth, char* filename);
inline void get_next_empty(int* posx, int* posy, int feld[9][9]);
void print_solution(int feld[9][9]);
inline bool test_feld(int feld[9][9]);
void save_solution(int feld[9][9], char* filename);
 
int main()
{
	char buffer[255];
	int feld[9][9];
	int filled = 0;
	int searchdepth = 0;
	printf("Dateiname des zu lösenden Sudokus eingeben!\n");
	scanf("%s", buffer);
	printf("\n\n");
 
	searchdepth = 10000;
 
	FILE* theFile = fopen(buffer,"r");
	if(theFile == NULL)
	{
		return -1;
	}
 
	for (int z = 0; z < 9; z++)
	{
		for(int s = 0; s < 9; s++)
		{
			fscanf(theFile, "%d", &feld[z][s]);
			if (feld[z][s] != 0) filled++;
		}
	}	
	fclose(theFile);
 
	return step(feld, filled, searchdepth, buffer);
}
 
bool step(int feld[9][9], int filled, int searchdepth, char* filename)
{
	static int iteration = 0;
	static bool printed = false;
	if(++iteration > searchdepth)
	{
		print_solution(feld);
		printf("Zu viele Durchläufe nötig!\n");
		return false;
	}
 
	int posx;
	int posy;
 
 
	get_next_empty(&posx, &posy, feld);
 
	if (posx == -1 || posy == -1) 
	{
		printf("SuDoKu nach %d durchläufen gelöst:\n\n", iteration);
		print_solution(feld);
		save_solution(feld, filename);
		return true;
	}
 
 
	filled++;
 
	for (int i = 1; i < 10; i++)
	{
		feld[posx][posy] = i;
		if (test_feld(feld))
		{
			if (step(feld, filled, searchdepth, filename))
				return true;
			else
			{
 
			}
		}
	}
 
	feld[posx][posy] = 0;
 
	if (!printed)
	{
		print_solution(feld);
		printed = true;
	}
 
	return false;
}
 
inline void get_next_empty(int* posx, int* posy, int feld[9][9])
{
	*posx = -1;
	*posy = -1;
 
	for (int x = 0; x < 9; x++)
	{
		for (int y = 0; y < 9; y++)
		{
			if (feld[x][y] == 0)
			{
				*posx = x;
				*posy = y;
				break;
			}
		}
		if(*posx != -1) break;
	}
}
 
inline bool test_feld(int feld[9][9])
{
	bool first = true;
	int zff;
	int x;
	int y;
 
 
	//Zeilen
	for (zff = 1; zff < 10; zff++)
	{
		for (y = 0; y < 9; y++)
		{
			for (x = 0; x < 9; x++)
			{
				if (feld[x][y]==zff)
				{
					if (first)
					{
						first = false;
					}
					else
					{
						return false;
					}
				}
			}
			first = true;
		}
	}
 
	first = true;
 
	//Spalten
	for (zff = 1; zff < 10; zff++)
	{
		for (x = 0; x < 9; x++)
		{
			for (y = 0; y < 9; y++)
			{
				if (feld[x][y]==zff)
				{
					if (first)
					{
						first = false;
					}
					else
					{
						return false;
					}
				}
			}
			first = true;
		}
	}
 
	//Quadrate
	int x2, y2;
 
	for (zff = 1; zff < 10; zff++)
	{
		for (x2 = 0; x2 < 3; x2++)
		{
			for (y2 = 0; y2 < 3; y2++)
			{
				first = true;
				for (x = 0; x < 3; x++)
				{
					for (y = 0; y < 3; y++)
					{
						if (feld[x + (x2 * 3)][y + (y2 * 3)]==zff)
						{
							if (first)
							{
								first = false;
							}
							else
							{
								return false;
							}
						}
					}
				}
			}
		}
	}
	return true;
}
 
void print_solution(int feld[9][9])
{
	for (int i = 0; i < 9; i++)
	{
		printf("%d %d %d %d %d %d %d %d %d\n", feld[i][0], feld[i][1], feld[i][2], feld[i][3], feld[i][4], feld[i][5], feld[i][6], feld[i][7], feld[i][8]);
	}
	printf("\n\n");
}
 
void save_solution(int feld[9][9], char* filename)
{
	char newFilename[255];
	sprintf(newFilename, "%s.solution", filename);
	FILE* theFile = fopen(newFilename,"w");
	if(theFile == NULL)
	{
		printf("Fehler beim Speichern!");
	}
	for (int i = 0; i < 9; i++)
	{
		fprintf(theFile, "%d %d %d %d %d %d %d %d %d\n", feld[i][0], feld[i][1], feld[i][2], feld[i][3], feld[i][4], feld[i][5], feld[i][6], feld[i][7], feld[i][8]);
	}
	fprintf(theFile, "\n\n");
}