April, 2006

Sudoku

Mittwoch, April 19th, 2006

Drei Tage habe ich gebraucht, dann war die erste Version meines Sudoku löse Programms fertig. Mit meinem Algorithmus ist es in einer wahnsinnigen schnellen Geschwindigkeit möglich auch komplizierteste Sudoku Ränzel innerhalb von Sekunden zulösen.

#include "stdafx.h"
#include 

using namespace std;
/*
int a[9][9] = {
	{0,4,0,0,0,7,0,0,0},
	{0,0,7,0,8,0,0,2,9},
	{0,9,0,1,0,2,7,3,0},
	{0,6,0,0,0,0,0,0,0},
	{1,2,0,4,0,3,0,9,0},
	{0,0,0,0,0,0,0,6,0},
	{0,1,2,5,0,9,0,7,0},
	{9,3,0,0,1,0,5,0,0},
	{0,0,0,3,0,0,0,8,0}
};
*/

int a[9][9] = {
	{0,5,0,1,0,2,0,9,0},
	{1,0,0,6,0,3,0,0,8},
	{0,0,3,0,4,0,2,0,0},
	{6,1,0,0,0,0,8,3,9},
	{7,0,0,0,0,0,0,0,4},
	{9,3,2,0,0,0,0,7,5},
	{0,0,1,0,5,0,9,0,0},
	{2,0,0,9,0,7,0,0,6},
	{0,9,0,8,0,6,0,4,0}
};

int c[9] = {0};
void m(int va[9][9],int x, int y)
{
//	int va[9][9] = {{0}};
//	for(int i=0; i<9; i++)
//		for(int ii=0; ii<9; ii++)
//			va[i][ii] = sa[i][ii];
		
	int b[9] = {0}, x2=(x/3), y2=(y/3);
	for(int i=0,iii=0; i<3; i++)
		for(int ii=0; ii<3; ii++)
			b[iii++] = va[((x2*3)+i)][((y2*3)+ii)];

	//int tmp[9] = {1,2,3,4,5,6,7,8,9};
	for(int i=0;i<9;i++)
		c[i] = i + 1;

	for(int i2=0; i2<9; i2++)
	{
		if(va[x][i2] > 0)
			c[(va[x][i2] - 1)] = 0;
		if(va[i2][y] > 0)
			c[(va[i2][y] - 1)] = 0;
		if(b[i2] > 0 )
			c[(b[i2]    - 1)] = 0;
	}
}

int rz(int sa[9][9])
{
	int n=0;
	int va[9][9];
		
	for(int i=0; i<9; i++)
		for(int ii=0; ii<9; ii++)
		{
			va[i][ii] = sa[i][ii];
			if(va[i][ii] == 0) 
				n++;
		}

	for(int i4=0; 1; i4++)
	{
		n = 0;
		for(int i=0; i<9 && !n; i++)
			for(int ii=0; ii<9 && !n; ii++)
			{
				if(va[i][ii] == 0) 
					n++;
			}

		if(n==0)
		{
			cout << "Fertig\n";
			for(int i=0; i<9 && n==0; i++)
			{
				for(int ii=0; ii<9 && n==0; ii++)
					cout << va[i][ii];
				cout << endl;
			}
			return 1;
		}

		for(int i=0; i<9; i++)
		{
			for(int ii=0; ii<9; ii++)
			{
				if(va[i][ii] == 0)
				{
					//Möglichkeiten für FELD
					m(va,i,ii);

					int tmp = 0;
					for(int iii=0; iii<9; iii++)
						if(c[iii])
							tmp++;
						
					if(tmp==0)
					{
						cout << "  x:" << i << "y:" << ii << " error\n";
						/*
						for(int i=0; i<9; i++)
						{
							for(int ii=0; ii<9; ii++)
								cout << va[i][ii];
							cout << endl;
						}
						*/

						return 0;
					}

					if(tmp==1)
						for(int iii=0; iii<9; iii++)
							if(c[iii])
							{
								va[i][ii] = c[iii];
								i4=0;
								cout << va[i][ii] << " x:" << i << "y:" << ii << "\n";
							}

					//cout << i4 << "\n";
					if(i4>0 && tmp>1) // && tmp < i4)
					{
						for(int iii=0; iii<9; iii++)
							if(c[iii])
							{
								va[i][ii] = c[iii];
								cout << va[i][ii] << " x:" << i << "y:" << ii << " r " << tmp <<"\n";
								if(rz(va))
									return 1;
								i4=0;		
							}
					}			

				}
			}
		}
	}
	return 1;
}

int main()
{
	if(rz(a))
		return 1;
	return 0;
}

Hier gibt es meinen Sudoku Quellcode v 0.3 sodoku3.cpp.