/// ************************************************ SuDoKu ************************************************************* ///
function SudokuFeld( parameter ) {
	// Eigenschaften
	var daten = new Array( (9*9) );
	var leeren = function( ) {
		for( var i = 0; i < daten.length; i++ ) daten[i] = 0;
	}
	this.IstSudokuFeld = function( ) {
		return ( daten && daten.length == (9*9) );
	}
	// Methoden
	// SudokuFeld
	this.FeldName = function ( zeilenIndex, spaltenIndex ) {
		return String.fromCharCode( 65 + spaltenIndex ) + String( zeilenIndex + 1 );
	}
	// SudokuFeld
	this.Anzeigen = function( ) {
		alert( daten.toString( ) );
	}
	// SudokuFeld
	this.SetText = function( neuText ) {
		if( neuText.length != 89 || neuText.match( /[^0-9\n]/ ) ) throw( "Fehler - SudokuFeld:SetText parameter '" + neuText + "' ungueltig!" );
		var i = 0;
		for( var z = 0; z < 9; z++ ) {
			for( var s = 0; s < 9; s++ ) {
				daten[z*9+s] = Number( neuText.charAt( i++ ) );
			}
			i++;
		}
	}
	// SudokuFeld
	this.GetText = function( ) {
		var text = "";
		for( var z = 0; z < 9; z++ ) {
			for( var s = 0; s < 9; s++ ) {
				text += daten[z*9+s];
			}
			if( (z+1) < 9 ) text += "\n";
		}
		return text;
	}
	// SudokuFeld
	this.GetHTMLText = function( ) {
		return this.GetText( ).replace( /\n/g, "<BR>"  ) + "<BR>";
	}
	// SudokuFeld
	this.Get = function( z, s ) {
		var index = z * 9 + s;
		if( s >= 9 || 0 > index || index >= daten.length ) throw( "Fehler - SudokuFeld:Get Index [" + z + "," + s + "] ungueltig!" );
		return String( daten[index] );
	}
	// SudokuFeld
	this.Set = function( z, s, wert ) {
		var index = z * 9 + s;
		if( s >= 9 || 0 > index || index >= daten.length ) throw( "Fehler - SudokuFeld:Set Index [" + z + "," + s + "] ungueltig!" );
		if( wert.length != 1 || wert.match( /[^0-9]/ ) ) throw( "Fehler - SudokuFeld:Set Wert[" + z + "," + s + "] '" + wert + "' ungueltig!" );
		daten[index] = Number( wert );
	}
	// SudokuFeld
	this.GetZeile = function( z ) {
		var index = z * 9;
		var text = "";
		if( 0 > z || z >= 9 ) throw( "Fehler - SudokuFeld:GetZeile Zeile " + z + " ungueltig!" );
		for( var s = 0; s < 9; s++ ) {
			text += daten[index+s];
		}
		return text;
	}
	// SudokuFeld
	this.SetZeile = function( z, neuZeile ) {
		var index = z * 9;
		if( 0 > z || z >= 9 ) throw( "Fehler - SudokuFeld:SetZeile Zeile " + z + " ungueltig!" );
		if( neuZeile.length != 9 || neuZeile.match( /[^0-9]/ ) ) throw( "Fehler - SudokuFeld:SetZeile Wert '" + neuZeile + "' ungueltig!" );
		for( var s = 0; s < 9; s++ ) {
			daten[index+s] = Number( neuZeile.charAt( s ) );
		}
	}
	// SudokuFeld
	this.GetSpalte = function( s ) {
		var spalteText = "";
		var text = "";
		if( 0 > s || s >= 9 ) throw( "Fehler - SudokuFeld:GetSpalte Spalte " + s + " ungueltig!" );
		for( var index = s; index < daten.length; index += 9 ) {
			spalteText += daten[index];			
		}
		return spalteText;
	}
	// SudokuFeld
	this.GetUnterfeld = function( z, s ) {
		var unterSpalteVon = 0;
		var unterSpalteBis = 3;
		var unterZeileVon = 0;
		var unterZeileBis = 3;
		var unterfeldText = "";
		if( s == null ) {
			if( 0 > z || z >= 9 ) throw( "Fehler - SudokuFeld:GetUnterfeld Index " + z + " ungueltig!" );
			unterSpalteVon = Math.floor( z % 3 ) * 3;
			unterZeileVon = Math.floor( z / 3 ) * 3;
			unterSpalteBis = unterSpalteVon + 3;
			unterZeileBis = unterZeileVon + 3;
		} else {
			if( 0 > z || z >= 9 || 0 > s || s >= 9 ) throw( "Fehler - SudokuFeld:GetUnterfeld Zeile " + z + " bzw. Spalte " + s + " ungueltig!" );
	//alert( "GetUnterfeld: " + z + "," + s );		
			if( s > 5 ) {
				unterSpalteVon = 6;
				unterSpalteBis = 9;
			} else if( s > 2 ) {
				unterSpalteVon = 3;
				unterSpalteBis = 6;
			}
			if( z > 5 ) {
				unterZeileVon = 6;
				unterZeileBis = 9;
			} else if( z > 2 ) {
				unterZeileVon = 3;
				unterZeileBis = 6;
			}
		}
		for( var zz = unterZeileVon; zz < unterZeileBis; zz++ ) {
			for( var ss = unterSpalteVon; ss < unterSpalteBis; ss++ ) {
				unterfeldText += this.Get( zz, ss );
			}
		}
		return unterfeldText;
	}
	// SudokuFeld
	this.GetSudokuFeldZeilenPermutation = function( zeile ) {
		var nochUebrig =	"123456789";
		var permutation = "";
		var sackgassen =	new Array( 9 ); // Fuer jede Spalte die Zahlen die in eine Sackgasse gefuehrt haben
		sackgassen[0] = "";

		for( var spalte = 0; spalte < 9; spalte++ ) {
			var unterSpalteVon = 0;
			var unterSpalteBis = 3;
			var unterZeileVon = 0;
			var unterZeileBis = 3;
			var j = 0;
			
			var addSackgassen = function( ) {
				if( spalte > 0 ) {
					sackgassen[spalte-1] += permutation.charAt(spalte-1);
					nochUebrig = permutation.charAt(spalte-1);
					permutation = permutation.substr( 0, spalte-1 );
					spalte -= 2;
					return true;
				} else {
					return false;
				}
			}
			
			if( spalte > 5 ) {
				unterSpalteVon = 6;
				unterSpalteBis = 9;
			} else if( spalte > 2 ) {
				unterSpalteVon = 3;
				unterSpalteBis = 6;
			}
			if( zeile && zeile > 5 ) {
				unterZeileVon = 6;
				unterZeileBis = 9;
			} else if( zeile && zeile > 2 ) {
				unterZeileVon = 3;
				unterZeileBis = 6;
			}
			if( (spalte+1) < 9 ) sackgassen[spalte+1] = "";
			
			var spalteNochUebrig = "";
			for( var k = 0; k < nochUebrig.length; k++ ) {
				var istOk = true;
				for( var z = 0; z < 9; z++ ) {
					if( nochUebrig.charAt(k) == this.Get(z,spalte) ) {
						istOk = false;
						break;
					}
				}
				if( istOk ) spalteNochUebrig += nochUebrig.charAt(k);
			}
			if( spalteNochUebrig.length == 0 ) {
				if( addSackgassen( ) ) continue;
				else return null; 
			}

			var feldNochUebrig = "";
			for( var k = 0; k < spalteNochUebrig.length; k++ ) {
				var istOk = true;
				for( var z = unterZeileVon; z < unterZeileBis; z++ ) {
					for( var s = unterSpalteVon; s < unterSpalteBis; s++ ) {
						if( spalteNochUebrig.charAt(k) ==  this.Get(z,s) ) {
							istOk = false;
							break;
						}
					}
				}
				if( istOk ) feldNochUebrig += spalteNochUebrig.charAt(k);
			}
			if( feldNochUebrig.length == 0 ) {
				if( addSackgassen( ) ) continue;
				else return null; 
			}
			var uebrig = new Array( );
			for( var k = 0; k < feldNochUebrig.length; k++ ) {
				var istOk = true;
				for( var z = 0; z < sackgassen[spalte].length; z++ ) {
					if( feldNochUebrig.charAt(k) == sackgassen[spalte].charAt(z) ) {
						istOk = false;
						break;
					}
				}
				if( istOk ) uebrig += feldNochUebrig.charAt(k);
			}
			if( uebrig.length == 0 ) {
				if( addSackgassen( ) ) continue;
				else return null; 
			}
			if( uebrig.length > 1 ) j = Math.floor( Math.random( ) * (uebrig.length - 1) + 0.5 );
			var aktZeichen = uebrig.charAt(j);
			permutation += aktZeichen;
			nochUebrig = nochUebrig.replace( RegExp( aktZeichen ), "" );
		}
		return permutation;
	} // ende GetSudokuFeldZeilenPermutation
	// SudokuFeld
	this.Permutation = function( ) {
		var maxVersuche = 50;
		leeren( );
		for( var z = 0; z < 9; z++ ) {
			var nochVersuche = maxVersuche;
			var istOk = true;
			do {
				var aktZeilenPermutation = this.GetSudokuFeldZeilenPermutation( z );
				if( aktZeilenPermutation == null ) {
					istOk = false;
				} else {
					this.SetZeile( z, aktZeilenPermutation );
//					if( ! istOk ) alert( "Hat doch noch geklapt!!! " + (maxVersuche - nochVersuche) );
					istOk = true;
				}
			} while( ! istOk && nochVersuche-- > 0 );
			if( ! istOk ) {
//				alert( "!!!Fehler!!! - Keine Permutation fuer Zeile" +  z + "moeglich!" );
				leeren( );
				z = -1; // nochmal von Vorne....
			}
		}
		return this;
	} // ende Permutation
	// SudokuFeld
	this.TesteZeile = function( zeile ) {
		var zeileText =  this.GetZeile( zeile );
		for( var zahl = 1; zahl <= 9; zahl++ ) {
			var ergebnis = zeileText.match( RegExp( String( zahl ), "g" ) );
			if( ergebnis && ergebnis.length > 1 ) return false;
		}
		return true;
	}
	// SudokuFeld
	this.TesteSpalte = function( spalte ) {
		var spalteText =  this.GetSpalte( spalte );
		for( var zahl = 1; zahl <= 9; zahl++ ) {
			var ergebnis = spalteText.match( RegExp( String( zahl ), "g" ) );
			if( ergebnis && ergebnis.length > 1 ) return false;
		}
		return true;
	}
	// SudokuFeld
	this.TesteUnterfeld = function( z, s ) {
		var unterfeldText =  this.GetUnterfeld( z, s );
		for( var zahl = 1; zahl <= 9; zahl++ ) {
			var ergebnis = unterfeldText.match( RegExp( String( zahl ), "g" ) );
			if( ergebnis && ergebnis.length > 1 ) return false;
		}
		return true;
	}
	// SudokuFeld
	this.Teste = function( ) {
		for( var n = 0; n < 9; n++ ) {
			if( ! ( this.TesteZeile( n ) && this.TesteSpalte( n ) && this.TesteUnterfeld( n, null ) ) ) return false;
		}
		return true;
	}
	this.AnzahlLeereFelder = function( ) {
		var n = 0;
		for( var i = 0; i < daten.length; i++ ) {
			if( daten[i] == 0 ) n++;
		}
		return n;
	}
	
	this.VorgabeUneindeutigkeiten = function( muster, uneindeutigkeiten ) {
		var anzahl = 0;
		if( uneindeutigkeiten && uneindeutigkeiten.splice ) {
			uneindeutigkeiten.splice( 0, uneindeutigkeiten.length ); // array leeren
		} else {
			uneindeutigkeiten = null; // kein array
		}
		for( var z = 0; z < 9; z += 3 ) {
			for( var s = 0; s < 9; s += 3 ) {
				// Zeilenpaare testen		
				if( (z+3) < 9 ) {
					for( var zz = z; zz < (z+3); zz++ ) {
						for( var zzz = (z+3); zzz < 9; zzz++ ) {
							for( var ss = s; ss < (s+3-1); ss++ ) {
								for( var sss = (ss+1); sss < (s+3); sss++ ) {
									if( 
										this.Get( zz, ss ) == this.Get( zzz, sss ) && 
										this.Get( zz, sss ) == this.Get( zzz, ss ) 
									) {
										if( 
											muster.Get( zz, ss ) == '0' &&
											muster.Get( zz, sss ) == '0' &&
											muster.Get( zzz, ss ) == '0' &&
											muster.Get( zzz, sss ) == '0'
										) {
											if( uneindeutigkeiten ) {
												uneindeutigkeiten[uneindeutigkeiten.length] = new Array( zz * 9 + ss, zz * 9 + sss, zzz * 9 + ss, zzz * 9 + sss );
											}
											anzahl++;
										}
									}
								}
							}
						}		
					}
				}
				if( (s+3) < 9 ) {
					for( var ss = s; ss < (s+3); ss++ ) {
						for( var sss = (s+3); sss < 9; sss++ ) {
							for( var zz = z; zz < (z+3-1); zz++ ) {
								for( var zzz = (zz+1); zzz < (z+3); zzz++ ) {
// document.writeln( "<BR>" + this.FeldName( zz, ss ) + " == " + this.FeldName( zzz, sss ) + " UND<BR>" + this.FeldName( zzz, ss ) + " == " + this.FeldName( zz, sss ) + " ===>");
									if( 
										this.Get( zz, ss ) == this.Get( zzz, sss ) && 
										this.Get( zzz, ss ) == this.Get( zz, sss ) 
									) {
//document.writeln( "JA " );									
										if( 
											muster.Get( zz, ss ) == '0' && muster.Get( zz, sss ) == '0' &&
											muster.Get( zzz, ss ) == '0' && muster.Get( zzz, sss ) == '0'
										) {
//document.writeln( " *<BR>" );									
											if( uneindeutigkeiten ) {
												uneindeutigkeiten[uneindeutigkeiten.length] = new Array( zz * 9 + ss, zz * 9 + sss, zzz * 9 + ss, zzz * 9 + sss );
											}
											anzahl++;
										} else {
//document.writeln( "<BR>" );									
										}
									} else {
//document.writeln( "NEIN " );									
									}
								}
							}
						}		
					}
				}
			} // ende for s
		} // ende for z
		return anzahl;
	} // VorgabeUneindeutigkeiten

	// SudokuFeld Konstruktor
	try {
		leeren( );
		if( typeof( parameter ) == 'string' && parameter.length == 89 ) {
			this.SetText( parameter );
		} else if( typeof( parameter ) == 'object' ) {
			if( parameter.IstSudokuFeld && parameter.IstSudokuFeld( ) ) {
				this.SetText( parameter.GetText( ) );
			}	else if( parameter.length == 9 ) {
				for( var z = 0; z < 9; z++ ) this.SetZeile( z, parameter[z] );
			} else {
				throw( "SudokuFeld-Konstruktor: Fehler Parameter(-Typ)!" );
			}
		}
	} catch( exception ) { throw( "SudokuFeld-Konstruktor: Fehler!\n" + exception ); }
} // ende SudokuFeld


/// ********************************************* Ende SuDoKu *********************************************************** ///