[Stiller Leser]

Das Schieberätsel fand bisher nicht so die Resonanz. Aber vielleicht klappt es ja, mit Sudoku.

Das Spiel ist bekannt?

Eine 9x9 Matrix muss derart mit den Zahlen 1-9 gefüllt werden, dass:

• Zeilen die Zahlen 1 bis 9 haben müssen
• Spalten die Zahlen 1 bis 9 haben müssen
• wenn man die große Matrix aufteilt in 9 3x3 Matrizen, auch diese die Zahlen 1 bis 9 haben müssen.

Es gibt jeweils nur eine Lösung.

Auf Zeitonline gibt es diese Rubrik https://www.zeit.de/spiele/index

Dort findet man Sudokurätsel von der Schwierigkeit leicht bis sehr schwer. Letzteres wollen wir angehen. Macht man das per Hand, kann das durchaus recht lange dauern. Sie sind aber durch reine Logik lösbar.

Interessant wird das mit dem Rechner. Man kann sich vorstellen, dass das Lösen durch schieres probieren ewig lange dauert. Ist also nur eine Möglichkeit für Leute mit sehr viel Zeit oder einem superschnellen Rechner.

Aber Rechner haben es ja auch mit der Logik. Ich habe jetzt so ein Mittelding programmiert. Es wird teils mit Probieren gearbeitet und teils mit Logik. Für die Logik habe ich 5 Regeln benutzt. (Vermutlich wird er umso schneller, je mehr Regeln man eingibt). Jedenfalls füllt sich die 9x9 Matrix dann schon ein bisschen und ab dann wird probiert und wieder mit der Logik weitergearbeitet. Dazu nutze ich beides: Rekursion und Iteration. Für die Logik zweites, fürs Probieren erstes.

Benutzt habe ich Java. Fürs heutige sehr schwere Rätsel hat das Programm 27 Sekunden gebraucht. Aber die Zeit variiert sehr stark mit dem Rätsel. Das gestrige sehr schwere Rätsel benötigte immerhin über 200 Sekunden.

Also: Mal ran an die Bouletten. Vielleicht findet ihr ja einen supertollen Code. Stelle meinen natürlich gerne zur Verfügung, wenn erstmal was hier steht.

EDIT:
Hatte ein bisschen was übersehen. Das geht jetzt bedeutend schneller. Jetzt sind es lediglich Bruchteile einer Sekunde bis hin zu ein paar Sekunden, je nach Problem.

[Multithread]

Auf die schnelle komme Ich auf 2 Regeln.
Welche jeweils für alle Dimensionen angewandt werden müssen

[Stiller Leser]

Auf 2 Regeln kommst Du auf die schnelle?

Drei habe ich oben schon genannt. Das sind die grundsätzlichen Regeln und diese zeigen auch, ob die Lösung richtig ist, wenn die Matrix erstmal komplett gefüllt ist. Ist die Lösung richtig, dann haben alle 9 kleinen Matrizen, sowie alle Spalten und alle Zeilen die Zahlen 1-9.
Ich habe dazu noch zwei weitere Regeln festgelegt, die man herleiten kann, wenn man die Hauptregeln beachtet. Bzw. eigentlich sind da noch mehr Regeln drin, die ich aber gleich zusammengefasst habe.

Nennen wir sie mal Regel 4:

010000000
000000000 betrachten wir die kleine Matrix oben links. Derzeit ist nur die 1 vorhanden.
000500000 Wir sehen in der ersten und dritten Spalte eine 5. Also kann die kleine Matrix in der ersten und dritten Spalte keine 5 haben.
005000000 Wir sehen in der dritten Zeile eine 5. Also verbietet sich auch diese Zeile.
000000000 Es bleiben zwei mögliche Standorte übrig: (0,1) und (1,1). Da in (0,1) schon die 1 vorhanden ist, bleibt als einziger möglicher Standort
000000000 (1,1) übrig. Diese wird dann auf 5 gesetzt, weil es die einzige Möglichkeit für die 5 in der kleinen Matrix oben links ist.
000000000
500000000
000000000

und hier wäre meine Regel 5:

Xxxxxxxxx Vom Zelle oben links ausgehen (0,0) dürfen alle x nur je einmal die Zahlen von 1 bis 9 haben. Wenn noch nicht besetzt. Das dicke X muss natürlich für eine Betrachtung noch leer sein
xxx000000
xxx000000 Ist beispielsweise (0,8)=9 kann (0,0) unmöglich 9 sein. ist (2,2) = 9, ebenso nicht. Die beiden beispiele sind kursiv in der Matrix dargestellt.
x00000000
x00000000
x00000000
x00000000
x00000000
x00000000


Man kann noch etliche weitere aufstellen. Aber diese 5 Regeln reichen schon aus, um auch sehr schwere Sudokurätsel per Programm zu lösen, wobei teils mit Logik und teils mit Versuch gearbeitet wird und die Berechnungszeit dafür relativ klein ist.

[Whiz-zarD]

Es gibt jeweils nur eine Lösung.

Das ist nicht richtig. Je nach dem, wie das Feld gefüllt ist, kann es auch mehrere Lösungen geben.
Ich habe schon einen Sodoku-Löser geschrieben und der hat etliche Lösungen ermitteln können.

Im Grunde besteht Sudoku nur aus einer einzigen Regel, dessen Eingangsparameter aber auf drei unterschiedliche Arten bestimmt werden.

Du brauchst also nichts weiter, als eine Funktion/Methode, die eine Liste (z.B. als Array) von Zahlen entgegennimmt und überprüft, ob dort keine Zahl doppelt vorkommt. Die Zahl 0 repräsentiert ein leeres Feld und soll nicht beachtet werden.

Also brauchen wir jeweils eine Funktion/Methode, die aus der 9x9 Matrix eine Zeile, eine Spaltenreihe und ein Block ermittelt.

Dann braucht man doch nur noch per Bruteforce-Verfahren die Zahlen eintragen:
Wir springen in das linke, obere leere Feld und füllen es mit 1. Dann überprüfen wir, ob die Regeln eingehalten werden.
Wenn die Regeln eingehalten werden, springen wir zum nächsten Feld und füllen es mit 1 und überprüfen wieder die Regeln.
Wenn die Regeln nicht eingehalten werden, dann erhöhen wir die Zahl um 1.
Wenn wir bei 9 angekommen sind und die Regeln weiterhin nicht eingehalten werden, tragen wir da wieder eine 0 ein und gehen ein Feld zurück und erhöhen dieses um 1.

usw.

Das Traversieren der Felder lässt sich per Rekursion lösen und das Inkrementieren über eine Schleife.

Dieser Algorithmus ist trotz Bruteforce sehr schnell und löst ein Rätsel unter einer Sekunde.

[Stiller Leser]

Ist das so? Ich habe nun noch nicht so viele Rätsel gemacht. Aber letztendlich waren dann alle so, wie die vorgegebene Lösung war. Das eine zweite oder gar dritte Möglichkeit bestand, hatte ich nie. Das sagt natürlich nichts aus über alle Rätsel.

Neben den Hauptregeln nur Brute Force zu nehmen, hatte ich eigentlich getestet. Aber ich hatte da schnell einen StackOverFlow. Aber vielleicht war da auch was fehlerhaft.
Aber gut. Stell mal vor.

[Whiz-zarD]

Aber gut. Stell mal vor.

Ich glaube nicht, dass ich den Code dazu noch habe. Ich kann aber mal nachschauen.
Ich hab das damals in meiner Ausbildung mit Pascal gebastelt und ein paar Jahre später mal für Android 4.0, um mich mal Android zu beschäftigen (mit Oberfläche, etc.)

Ich kann aber mal vielleicht mal versuchen, es nachzubauen. Kompliziert war es ja nicht.

[Stiller Leser]

Da bin ich ja mal gespannt. Ich hab meins mal gerade etwas umgebaut, um es nach der Methode zu versuchen. Und die Zeilen sind sogar so sortiert, dass er mit den Zeilen anfängt, die die wenigsten fehlenden Elemente haben und es dauert trotzdem sehr lange.
Das Problem ist, dass 79 Elemente richtig sein können und erst das 80. und 81 Element ist doppelt. Das sind also sehr tiefe Rekursionen.

EDIT:
Dank dir konnte ich noch einiges optimieren und einen schweren Fehler hab ich auch noch gefunden.
Jetzt schafft er die in Sekundenbruchteilen. Aber eben mit den 5 Regeln und der Verbindung rekursiv und iterativ.

[Multithread]

Was die Geschwindigkeit angeht: Für ein Schweres Rätsel (nur mit Regeln beachten, kein Raten), tippe ich aktuell auf maximal 150ms, selbst bei schlecht Optimiertem Code.

Ich bin inzwischen auch bei 3 Regeln

Meine Regeln:
1. Jede Zahl darf nur einmal vorkommen, Ich streiche also aus jedem Feld die Zahlen, welche in einer Spalte/Zeile/Quadrat bereits vorkommen
2. Wenn eine Zahl in einer Spalte/Zeile in einem anderen Quadrat sein muss (weil es daneben keinen Platz gibt), streiche Ich diese. (Muss Ich noch Implementieren)
3. Jede Zahl muss einmal vorkommen, Ich akzeptiere Jede Zahl, welche die einzige Möglichkeit innerhalb einer Spalte/Zeile/Quadrat ist.

ev. braucht es noch mehr, bisher sieht es aber danach aus, als ob Ich damit alle Sudoki lösen kann.

[Stiller Leser]

Ja, mit dem Link oben kann man das ganz gut testen. Da gibt es auch die leichten Rätsel bis hin zu sehr schwer. Ob es grundsätzlich funktioniert, kann man dann schon mal mit den leichten Rätseln testen. Fehler haben bei mir sehr viel Zeit gekostet, also Laufzeit. Mich wundert fast, dass es trotzdem funktioniert hat. Aber ich habe gut mögliche Fehler abgefangen.

Und es kommt sehr entscheidend darauf an, wie das schwere Rätsel angeordnet ist. Jetzt scheinen bei mir alle sehr schnell zu funktionieren. Aber auf dem Weg dorthin war eine ganz schöne Spannweite. Von wenigen Sekunden bis etliche Sekunden.

[Stiller Leser]

package Fenster;

import java.awt.Color;
import java.awt.Font;
import java.awt.Toolkit;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;


import javax.swing.BorderFactory;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;




public class Fenster implements MouseListener{
	
	//globale Konstanten
		final static int FENSTERBREITE=600;
		final static int FENSTERHOEHE=490;
		
		JFrame jframe;
		JPanel jp=new JPanel();
		JPanel jp_hauptpanel=new JPanel();
		JPanel[] jp_unterpanel=new JPanel[9];
		JButton[][] zahlen =new JButton[9][9];
		JButton jb_ok=new JButton("Ok");
		JButton jb_laden=new JButton("Laden");
		
		int[][][] matrix = new int[9][3][3];
		int [][]hauptmatrix=new int[9][9];
		
		boolean fertig=false;
		boolean laden=false;
		
		public	Fenster(){
	
		for(int i=0;i<9;i++)
			for(int j=0;j<3;j++)
				for(int k=0;k<3;k++)
				matrix[i][j][k]=0;
		
		jframe=new JFrame("Sudoko");
    	JFrame.setDefaultLookAndFeelDecorated(true);


    	jframe.pack();
    	
    	jframe.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
    	


    	jframe.setBounds(Toolkit.getDefaultToolkit().getScreenSize().width/2 - FENSTERBREITE/2, 
    							Toolkit.getDefaultToolkit().getScreenSize().height/2-FENSTERHOEHE/2, 
    							FENSTERBREITE, 
    							FENSTERHOEHE);
    	
    	jframe.setResizable(false);
    	
	    //Listener fuer Window- und key_events hinzufuegen
	    jframe.addWindowListener(new WindowClosingAdapter());
	    
	    jframe.setLayout(new java.awt.GridLayout(1, 1));
	    Font font=new Font("Arial",Font.BOLD,20);
	    
	    
	    for(int i=0;i<9;i++)
	    	for(int j=0;j<9;j++){
	    		zahlen[i][j]=new JButton();
	    		zahlen[i][j].setFont(font);
	    		zahlen[i][j].addMouseListener(this);
	    		zahlen[i][j].setFocusable(false);
	    	}
	    
	    for(int i=0;i<9;i++){
	    	jp_unterpanel[i]=new JPanel();
	    	jp_unterpanel[i].setLayout(new java.awt.GridLayout(3, 3));
	    	jp_unterpanel[i].setBorder(BorderFactory.createLineBorder( Color.black ));
	    }
	    
	    for(int i=0;i<9;i++)
    		for(int k=0;k<9;k++){
    			jp_unterpanel[i].add(zahlen[i][k]);
    		}
	    
    	jp_hauptpanel.setLayout(new java.awt.GridLayout(3, 3));
    	jp_hauptpanel.setBounds(5, 5,450,450);
    	for(int i=0;i<9;i++){
	    	jp_hauptpanel.add(jp_unterpanel[i]);
	    }
    	
    	jb_ok.setBounds(480, 100,95,25);
    	jb_ok.setFont(font);
    	jb_ok.addMouseListener(this);


    	jb_laden.setBounds(480, 130,95,25);
    	jb_laden.setFont(font);
    	jb_laden.addMouseListener(this);
    	
    	
	    jp.setLayout(null);
	    jp.add(jp_hauptpanel);
	    jp.add(jb_ok);
	    jp.add(jb_laden);
	    jp.setBounds(0, 0, 590, 590);
	    
	    jframe.add(jp);
	    
	    
	    jframe.setVisible(true);
	}


	public void set_button(int matrix, int index, String text){
		zahlen[matrix][index].setText(text);
		
	}
	
	public void set_fertig(boolean fertig){
		int zahl=0;
		this.fertig=fertig;
		
		for(int i=0;i<9;i++){
			for(int j=0;j<3;j++){
				for(int k=0;k<3;k++){
					if(this.zahlen[i][zahl].getText().equals(""))zahl++;
					else matrix[i][j][k]=Integer.parseInt(zahlen[i][zahl++].getText());
				}
			}
		zahl=0;
		}
	}
	
	public void set_laden(boolean laden){
		this.laden=laden;
	}


	public boolean get_fertig(){
		return fertig;
	}


	public boolean get_laden(){
		return laden;
	}


	
	public int get_matrix(int i, int zeile, int spalte){
		return matrix[i][zeile][spalte];
	}
	
	public void set_text(){
		for(int i=0;i<9;i++)
			for(int j=0;j<9;j++)
				zahlen[i][j].setText("");
	}


	
  	private void beenden()	{	
		jframe.setVisible(false);
		jframe.dispose();
		
		System.exit(0);
	}


	/*Wenn Window schließen durch X erfolgt, wird
	 * Fenster mit beenden() geschlossen
	 */	
	class WindowClosingAdapter 	extends WindowAdapter
	{
	   public void windowClosing(WindowEvent event)
	   	{beenden();}
	}


	@Override
	public void mouseClicked(MouseEvent arg0){
		int zahl=0;
		int button=arg0.getButton();
		
		if(arg0.getSource() == this.jb_ok){
			set_fertig(true);
		}
		
		if(arg0.getSource() == this.jb_laden){
			set_laden(true);
		}




		switch(button){
			case 1:
				for(int i=0;i<9;i++)
					for(int j=0;j<9;j++){
						if(arg0.getSource() == this.zahlen[i][j]){
							if(this.zahlen[i][j].getText().equals(""))zahl=0;
							else zahl=Integer.parseInt(this.zahlen[i][j].getText());
							zahl++;
							if(zahl==10)zahl=0;
							this.zahlen[i][j].setText(Integer.toString(zahl));
						}
					}
			break;
			case 3:
				for(int i=0;i<9;i++)
					for(int j=0;j<9;j++){
						if(arg0.getSource() == this.zahlen[i][j]){
							if(this.zahlen[i][j].getText().equals(""))zahl=0;
							else zahl=Integer.parseInt(this.zahlen[i][j].getText());
							zahl--;
							if(zahl==-1)zahl=9;
							this.zahlen[i][j].setText(Integer.toString(zahl));
						}
					}
			break;
			
		}
		
		
		
	}


	@Override
	public void mouseEntered(MouseEvent arg0) {
		// TODO Auto-generated method stub
		
	}


	@Override
	public void mouseExited(MouseEvent arg0) {
		// TODO Auto-generated method stub
		
	}


	@Override
	public void mousePressed(MouseEvent arg0) {
		// TODO Auto-generated method stub
		
	}


	@Override
	public void mouseReleased(MouseEvent arg0) {


}
}

Da es ja um das Lösen des Rätsels geht und nicht um das Eingeben der Zahlen, wer will eine einfache Eingabemaske für Java.
Mit der Linken Maustaste lassen sich die Zahlen von 0 bis 9 durchklicken, beginnt danach wieder mit der null. Mit der rechten von 9 bis 0 und beginnt danach wieder mit der 9.
Nullstellen müssen natürlich nicht belegt werden. Ist sehr einfach, aber auch sehr funktionell.

		Fenster b=new Fenster();		
		boolean initialisiert=false, laden=false, gelöst=false;
		int x=0, y=0, y1=0;
		
		b.set_text();
		
		while(!initialisiert&&!laden){
			initialisiert=b.get_fertig();
			laden=b.get_laden();
			try {
				TimeUnit.SECONDS.sleep(1);
			} catch (InterruptedException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		
		if(initialisiert){
		for(int i=0;i<9;i++){
			switch(i){
			case 0:case 1:case 2:
				switch(i){
					case 0:
						x=0;y=0;y1=y;
						break;
					case 1:
						x=0;
						y=3;y1=y;
						break;
					case 2:
						x=0;
						y=6;y1=y;
						break;
				}
			break;
			case 3:case 4: case 5:
				switch(i){
				case 3:
					x=3;
					y=0;y1=y;
					break;
				case 4:
					x=3;
					y=3;y1=y;
					break;
				case 5:
					x=3;
					y=6;y1=y;
					break;
				}


				break;
			case 6: case 7: case 8:
				switch(i){
				case 6:
					x=6;
					y=0;y1=y;
					break;
				case 7:
					x=6;
					y=3;y1=y;
					break;
				case 8:
					x=6;
					y=6;y1=y;
					break;
				}
				break;
		}
			for(int j=0;j<3;j++){
				for (int k=0;k<3;k++){
					matrix[x][y1++]=b.get_matrix(i, j, k);
				}
				x++;y1=y;
			}
		}
		
		FileWriter writer;
		File datei=new File("Sodoku.txt");
		
		try {
			writer=new FileWriter(datei);
			
			for(int i=0;i<9;i++){
				for(int j=0;j<9;j++){
					writer.write(Integer.toString(matrix[i][j]));
				}
				writer.write(System.getProperty("line.separator"));
			}
			
			writer.flush();
			writer.close();
			
			
		} catch (IOException e) {
			e.printStackTrace();
			System.out.println("Fehler beim Speichern");
		}
	}//end initialisiert -> Zahlen vom Eingabefenster
		
		if(laden){
				System.out.println("Versuche zu laden");
		FileReader reader;
		File datei=new File("Sodoku.txt");
		int zahl;
		int i=0;int j=0;
		
		
		try {
			  reader=new FileReader(datei);
			  
			  try {
				while( (zahl=reader.read()) != -1 ){
					if((char)zahl!=13 &&(char)zahl!=10){//13=return 10=neue Zeile
						matrix[i][j++]=Character.getNumericValue((char)zahl);
						if(j==9){
							i++;
							j=0;
						}
						if(i==9)i=0;
					}
				}	
				reader.close();
				System.out.println("Laden ok");
			} catch (IOException e) {
				e.printStackTrace();
				System.out.println("Fehler beim Datei auslesen");
			}
			  
			  
			} catch (FileNotFoundException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
				System.out.println("Datei nicht gefunden.");
			}
		}//end laden -> Zahlen aus Datei

Das muss in die main. Kann sein, dass ihr da noch ein paar Variablen deklarieren müsst. Ist ja nur ein Ausschnitt. Zur Erklärung: Bei ok werden die Zahlen aus dem Fenster übernommen. Gleichzeitig wird eine Datei sudoku.txt angelegt und die Zahlen werden in die matrix[9][9] gespeichert. Die fehlt hier glaube ich noch in der Deklaration.

Beim nächsten Start kann man dann ganz einfach laden und mit der gewählten Vorgabe rechnen lassen. Das spart viel Zeit. Ist wie gesagt sehr einfach gehalten und eigentlich hat das in der main alles nichts zu suchen. Aber es geht ja wie gesagt um die Lösung des Rätsels. Das ist nur, damit man Zeit sparend testen kann.

[jabu]

@Stiller Leser
Danke für deinen Java-Code. Weil ich mit C++ angefangen habe, kann ich ihn jetzt nicht verwenden, vielleicht später mal.

Zuerst hatte ich mir überlegt, das auf der Basis von Mengen zu {1...9} je einzelnem Feld zu lösen, aus denen zuerst die unmöglichen Kandidaten naiv ausgeschlossen und dann nötigenfalls recht komplexe Regeln angewendet werden sollten, evtl. auch unter Berücksichtigung von Wahrscheinlichkeiten. Ein Durchprobieren sollte nachrangig stattfinden.

Um die Mengen performant zu behandeln, hatte ich mir dafür (in C++) eine Klasse erstellt, welche mit Bitmasken arbeitet, mit einem Bit je Kandidat, was also mindestens neun Bit erfordert und was noch Platz für weitere Informationen ließe. Eine zusätzliche Bit-Operation ist nämlich sehr viel schneller als die sonst nötigen zusätzlichen Lade- oder Speicheroperationen.

Dann ist mir aber der Aufwand schon beim bloßen Gedanken zu groß geworden, was mir eigentlich von vornherein klar war, aber ich ließ mich ein wenig verführen, was auch mit daran lag, dass hier noch anfänglich von einer ziemlich langen Zeit zum Lösen die Rede war, was einen komplexeren Wurf evtl. hätte rechtfertigen können.

Als ich von dem Ansatz von Whiz-zarD las, dachte ich mir, dass man damit bei nicht allzu schweren Sudokus zu genügend kurzen Zeiten gelangen müsste, weil man nämlich wegen der geringen Komplexität relativ wenige Speicherzugriffe braucht. Dann kann man im Gegenzug durchaus viele erfolglose rekursive Aufrufe in Kauf nehmen. Die "dummen" Lösungen sind auf einer PC-CPU manchmal die schnellsten. Man denkt als Mensch zu komplex (wobei das bei größeren Problemen (vielleicht auch schon bei extremen Sudokus) irgendwann nützt).

Also dachte ich mir, dass das ein realistischer Aufwand ist, um es nebenbei hinzubekommen. Ich zeige euch mal Zeiten, die sich bei mir ergeben haben. Zu berücksichtigen wäre, dass das Kompilat auf nur einem Core2Duo T6600 mit konstant 1,8 GHz (und DDR2-Speicher (PC2-5300)) läuft. Es handelt sich um ein 32-Bit-Programm.

//Zahlen von zeit.de ("SEHR-SCHWER")
const int templBoard[81]{
    0, 5, 0,   0, 0, 2,   0, 0, 9,
    1, 0, 2,   0, 0, 0,   0, 8, 0,
    6, 0, 0,   3, 0, 0,   4, 0, 0,

    0, 0, 0,   0, 2, 3,   0, 0, 0,
    0, 8, 5,   0, 0, 9,   7, 0, 0,
    0, 6, 3,   0, 7, 0,   0, 0, 2,

    8, 0, 7,   0, 0, 0,   0, 5, 0,
    0, 2, 0,   8, 0, 4,   1, 3, 0,
    4, 0, 0,   0, 0, 0,   0, 0, 0
};

Dauer je Durchgang: 25,7 µs
Anzahl rekursiver Aufrufe: 527

//Zahlen von zeit.de ("SEHR-SCHWER")
const int templBoard[81]{
    0, 1, 3,   8, 7, 6,   5, 0, 0,
    0, 0, 0,   0, 0, 0,   8, 0, 0,
    0, 0, 2,   9, 5, 4,   0, 0, 0,

    0, 7, 1,   0, 0, 0,   0, 0, 0,
    9, 0, 0,   0, 0, 3,   6, 2, 0,
    0, 0, 0,   7, 0, 5,   0, 1, 0,

    0, 0, 4,   0, 0, 0,   0, 0, 1,
    0, 0, 0,   5, 0, 0,   7, 4, 0,
    0, 6, 0,   0, 2, 0,   0, 8, 0
};

Dauer je Durchgang: 239 µs
Anzahl rekursiver Aufrufe: 3111

//Zahlen von 123sudoku.de ("Teuflisch (extrem)")
const int templBoard[81]{
    0, 0, 0,   0, 0, 0,   0, 0, 0,
    9, 0, 0,   1, 5, 4,   0, 0, 0,
    7, 0, 4,   0, 9, 0,   1, 0, 0,
 
    0, 3, 0,   4, 1, 6,   0, 0, 0,
    1, 0, 0,   0, 0, 0,   0, 0, 0,
    8, 0, 0,   3, 0, 0,   0, 0, 0,

    3, 0, 0,   0, 0, 7,   0, 0, 8,
    0, 0, 7,   8, 0, 0,   9, 0, 3,
    0, 5, 0,   0, 0, 9,   4, 0, 0
};

Dauer je Durchgang: 3770 µs
Anzahl rekursiver Aufrufe: 47333

Es wurde jeweils inklusive der Initialisierung des Boards sowie der Zählung der rekursiven Aufrufe gemessen. Die Werte sind aus Summen von hunderten bis hunderttausenden Durchgängen gemittelt, weil einzelne Durchgänge bei den kurzen Zeiten etwas sprunghaft sind. Eine große Diskrepanz zwischen den Zeiten von Einzeldurchgängen und mehreren gibt es im Gegensatz zu Java nicht, weil nicht zur Laufzeit optimiert wird. Vielleicht kann die CPU bei Wiederholung Cache Misses vermeiden, sodass weniger Ausreißer drin sind. Grundsätzlich ändert sich aber nichts.

Wie sehen eure Zeiten aus? Bei Interesse zeige ich gerne, was ich gemacht habe, um meine zu erreichen (es wurde nicht mit Bitoperationen getrickst). Wenn eure (unter Berücksichtigung der Hardware) viel besser sind, kann ich mir das natürlich sparen.

Ihr könnt natürlich aus dem JIT-Compiler die bestmögliche Optimierung herausholen, wenn ihr Java verwendet - vorausgesetzt, jeder Durchgang wird dabei immer noch einzeln berechnet (nicht wegoptimiert). Dass nichts weggemogelt wird, sollte sich befördern lassen, indem die rekursiven Aufrufe über alle Durchgänge hinweg gezählt und ausgegeben werden. Zur Korrektur teilt man natürlich vor der Ausgabe den Zählerstand durch die Anzahl der Durchgänge. Vermutlich ist der Compiler nicht so clever, aber sicher weiß man das nicht.

[Stiller Leser]

Ist also komplett mit Gewalt berechnet?

Also das sieht sehr schnell aus. Ich muss die Beispiele von dir testen, um einen Vergleich zu haben. Ist doch sehr unterschiedlich von Problem zu Problem.
Rekursionsaufrufe brauch ich in der Regel zwischen 0 und 7 bei den sehr schweren. Da kann man mal sehen, was da für Bandbreiten sind.

Für die Zeitermittlung muss ich aber dann erst mal die ganzen Fehlerausgaben rausnehmen. Jedesmal, wenn ein Lösungsversuch ein Fehler ergibt, wird bei mir ja ausgegeben wo der Fehler ist und wer verantwortlich ist.

[jabu]

Ist also komplett mit Gewalt berechnet?

Nach dem rekursiven Ansatz, den Whiz-zarD hier erklärt hat. Es wird also jeder Feldwert, welcher mit 0 vorbelegt ist, versuchsweise von 1 bis 9 durchprobiert, wobei die drei Regeln (Zeile, Spalte, Quadrat) angewendet werden. Wenn die 9 nicht überschritten wird (es wurde der erste erlaubte Wert gefunden), geht es in die nächste Rekursion. Andernfalls wird mit Rückgabe von false abgestiegen und die nächsthöhere Zahl probiert.

Also das sieht sehr schnell aus.

Bei denen von zeit.de hat sich bisher immer deutlich weniger als 1 ms ergeben (womit ich nichts behaupten will, denn ich müsste noch mehr probieren). Das letzte Beispiel ist tatsächlich komplexer (nicht mit den anderen gleichzusetzen), schon weil es weniger Vorgaben hat (was aber nicht immer was heißen muss).

Ich muss die Beispiele von dir testen, um einen Vergleich zu haben. Ist doch sehr unterschiedlich von Problem zu Problem.

Jepp. Bei diesem Algorithmus spielt Zufall eine große Rolle.

Rekursionsaufrufe brauch ich in der Regel zwischen 0 und 7 bei den sehr schweren. Da kann man mal sehen, was da für Bandbreiten sind.

Vielleicht spielt Zufall bei dir eine nicht ganz so große Rolle.

Für die Zeitermittlung muss ich aber dann erst mal die ganzen Fehlerausgaben rausnehmen. Jedesmal, wenn ein Lösungsversuch ein Fehler ergibt, wird bei mir ja ausgegeben wo der Fehler ist und wer verantwortlich ist.

Ja, das kann laufzeitmäßig teuer werden.

[Stiller Leser]

Also dein Code ist bedeutend schneller. Besonders beim letzten Teil. Hätte ich echt nicht erwartet, da ich ja nun vorsortiere und mit 5 Regeln arbeite. Beim letzten weiß ich noch nicht mal, ob er es gelöst bekommt. Da ist er immer noch dabei.

[jabu]

Also dein Code ist bedeutend schneller. Besonders beim letzten Teil. Hätte ich echt nicht erwartet, da ich ja nun vorsortiere und mit 5 Regeln arbeite. Beim letzten weiß ich noch nicht mal, ob er es gelöst bekommt. Da ist er immer noch dabei.

Bei Gelegenheit zeige ich meinen Code mal. Aber vorschnell möchte ich ihn auch nicht zeigen, denn der ist so schmerzhaft einfach, wenn man ihn sieht, dass es ein Spoiler wäre, der den Knobelspaß verderben könnte. Trotzdem ist es nicht ganz leicht, darauf zu kommen.

Weil man skeptisch sein soll, habe ich vorhin
...das Ergebnis des letzten Beispiels durchgeguckt, scheint alles zu stimmen, auch die festgelegten Werte:
513 728 694
962 154 837
784 693 125

235 416 789
176 985 342
849 372 516

391 547 268
427 861 953
658 239 471

...die Anzahl der Durchgänge auf 1000 festgelegt und mit einer stinknormalen Uhr die Zeit genommen:
knapp 4 s / 1000 Durchgänge = knapp 4 ms / Durchgang

Es hat sich also nichts geändert.

[Stiller Leser]

Ich habe jetzt auch mal den Algorithmus genommen. Also der ist tatsächlich sehr schnell. Bin zwar von deiner Geschwindigkeit weit weg (ca. 190 ms), aber da denke ich, dass ich da noch einiges schneller werden kann. Ich hab das jetzt halt ins bestehende übernommen samt aller Methoden, die ich schon hatte. Habe vermutlich viel zu viel in die Sicherheit gesteckt. Das Prüfen dauert sehr lange, weil ich tausend Sicherheiten eingebaut habe.

Ich denke, es ist besser, dass nochmal komplett neu zu schreiben.

Hier die Methode.
Zum Verständnis: Ich habe vorher die Nullstellen alle in einer Liste gespeichert.
Die Nullstellen sind dergestalt sortiert, dass diejenigen Zellen mit den meisten vorhandenen Zahlen vorne sind.

class Koordinaten{int x=0;
int y=0;


Koordinaten(int x, int y){
	set_Koordinaten(x,y);
}


int get_x() {
	return x;
}


int get_y() {
	return y;
}


void set_Koordinaten(int x, int y) {
	this.x=x;
	this.y=y;
}


}

boolean primus(int aktuelle_zahl, int pos) {	boolean fertig=false;


	aufrufe++;
	do {
			do {
				if(this.matrix[nullstellen.get(pos).get_x()][nullstellen.get(pos).get_y()]>=10) {
					this.matrix[nullstellen.get(pos).get_x()][nullstellen.get(pos).get_y()]=0;
					aktualisieren_neu(nullstellen.get(pos).x,nullstellen.get(pos).y,get_matrix(nullstellen.get(pos).x,nullstellen.get(pos).y));
					keine_zahl_passt=true;
					return false;
					
				}
				if(keine_zahl_passt) {
					pos--;
					keine_zahl_passt=false;
				}
				
				
				this.matrix[nullstellen.get(pos).get_x()][nullstellen.get(pos).get_y()]++;
				aktualisieren_neu(nullstellen.get(pos).x,nullstellen.get(pos).y,get_matrix(nullstellen.get(pos).x,nullstellen.get(pos).y));
			}while(prüfen()!=0);
			
					if(pos==nullstellen.size()-1) {
						for(int i=0;i<zeilen;i++) {
							if(this.zeile[i].reihe.contains(0)||
							   this.spalte[i].reihe.contains(0)||
							   kl_matrix[i].fehlen.contains(0)) {
								fertig=false;
							}
							   else {
								   return true;
							   }
							}
					}
					fertig=primus(0,++pos);
	}while(!fertig);
	
	return fertig;
	
}

[jabu]

Ich habe jetzt auch mal den Algorithmus genommen. Also der ist tatsächlich sehr schnell. Bin zwar von deiner Geschwindigkeit weit weg (ca. 190 ms), aber da denke ich, dass ich da noch einiges schneller werden kann.

Es ist noch reichlich Overhead drin. Nur vorsichtshalber angemerkt: In der Größenordnung, wo sich Gedanken lohnen, ob es an Java liegen könnte, sind die Zeiten bei weitem nicht.

Ich hab das jetzt halt ins bestehende übernommen samt aller Methoden, die ich schon hatte. Habe vermutlich viel zu viel in die Sicherheit gesteckt. Das Prüfen dauert sehr lange, weil ich tausend Sicherheiten eingebaut habe.

Wenn der Algorithmus korrekt ist, dann gelten natürlich die kürzeren Zeiten, ohne die Prüfungen.

Zum Verständnis: Ich habe vorher die Nullstellen alle in einer Liste gespeichert.
Die Nullstellen sind dergestalt sortiert, dass diejenigen Zellen mit den meisten vorhandenen Zahlen vorne sind.

Bei mir gibt es solche Optimierungen nicht, weswegen die Spreizung zwischen unterschiedlichen Sudokus mit demselben Schwierigkeitsgrad sehr groß ist, je nachdem, was zufällig am Anfang kommt (im weitesten Sinne der Grund für deine Maßnahme (die noch mehr leistet)).

Auch bei meiner Lösung könnte noch optimiert werden (eine Liste (sogar ein Array) hätte einiges an Overhead, also anders):
Wenn ich bloß das Brett drehen, spiegeln oder bei diesem die äußeren drei Zeilen oder Spalten zusammen vertauschen und das nachher wieder umstellen würde, dann sollte aus dem letzten Sudoku schon ein schnelleres werden, mit nur wenig (unvermeidbarer) Verschlechterung bei den einfachen.
Damit könnte mein Code so dumm und effizient bleiben, wie er ist und trotzdem bei den schweren Sudokus in vielen Fällen - wie diesem, wo die Nullen am Anfang stehen - schneller werden. Dann müssten wir bei diesem noch über ganz andere Zeiten (schätze ca. 400...600 µs anstatt 3770 µs) sprechen (bin mir ziemlich sicher, dass das geht (und bedenke den ollen untertakteten Core2Duo))...

Bei deinem Code sehe ich mehrere Effizienzprobleme, wobei dieses eines der größeren sein sollte:
Jeder auszuprobierende Wert wird zunächst per
this.matrix[nullstellen.get(pos).get_x()][nullstellen.get(pos).get_y()]++;
ins temporäre Ziel geschrieben. Warum?
Es sollte genügen, ihn zu laden, vorzuhalten und ohne diesen Umweg zu prüfen (wobei der Test gegen das eigene Feld nicht stört, wenn es auf 0 bleibt). Der Erfolg ist nicht so wahrscheinlich, dass es sich lohnen würde, auch bei Misserfolg zu speichern (hinzu kommt, dass der Vorgang rückgängig gemacht werden muss). Und es ist in jedem Fall unglücklich, dass der Wert zum Überprüfen noch einmal geladen werden muss, anstatt dass er immer noch im Register läge.

Falls deine "Liste" nicht als Array implementiert ist, ein weiteres (großes) Effizienzproblem:
Was die Zeiten für den Lookup in einer Liste (sollte schnelles Ein- und Aushängen (kein Umsortieren beim Einfügen bzw. Entfernen nötig) unterstützen, was Verpointerung bedeutet) angeht, bin ich skeptisch. Sogar wenn sie optimalerweise indiziert ist (um das Verfolgen zahlreicher Pointer, die Liste hinab bis zum Ziel, zu vermeiden), wird sie zwar viel schneller (endlich mit konstanter Zugriffszeit), aber nicht schnell genug, weil eine weitere Indirektion, eben über den Index zum Pointer und erst über diesen zum Ziel, unvermeidbar ist. Und wenn du mehrmals zugreifst (wie in deinem Code) und der Compiler nicht weiß, dass die Liste sich zwischenzeitlich nicht ändern kann, dann schlägt die Zeit gleich mehrmals zu Buche, sodass du den Wert zwischenspeichern solltest, wenn du ihn nicht wenigstens rasant hervorkramen kannst. Ein echtes Array, wo die Elemente direkt aufeinanderfolgend gespeichert sind und das natürlich ohne dazwischengefummeltes Bounds Checking, sollte den Anforderungen schon einigermaßen entgegenkommen. Ob dann zusätzliches Zwischenspeichern bei Mehrfachzugriff noch was bringt, müsstest du ausprobieren. Manchmal bringt es was, manchmal ist es kontraproduktiv. Die entsprechenden Zweige werden ja nicht immer durchlaufen.

Die Chancen, dass du deinen Code noch schneller hinbekommst, stehen also gut!

[Stiller Leser]

Es ist noch reichlich Overhead drin. Nur vorsichtshalber angemerkt: In der Größenordnung, wo sich Gedanken lohnen, ob es an Java liegen könnte, sind die Zeiten bei weitem nicht.

Ja. Bin aber eh gerade dabei, dass ganze neu zu schreiben. Das Problem ist halt, dass mein alter Code von vorne bis hinten auf die logische Rangehensweise geeicht ist. Hab zwar noch was an Zeit rausholen können. Aber letztendlich merkt man es halt. Da ist es besser, neu ranzugehen.

Wenn der Algorithmus korrekt ist, dann gelten natürlich die kürzeren Zeiten, ohne die Prüfungen.

Yep. Aber bei meinem Weg war das unerlässlich und entsprechend auch komplex.

Bei mir gibt es solche Optimierungen nicht, weswegen die Spreizung zwischen unterschiedlichen Sudokus mit demselben Schwierigkeitsgrad sehr groß ist, je nachdem, was zufällig am Anfang kommt (im weitesten Sinne der Grund für deine Maßnahme (die noch mehr leistet)).

Das ging halt, weil alles schon da war. Alles in der Klasse kl_matrix und reihen gespeichert. Da brauchte ich nur auf die Information zugreifen. Aber das braucht natürlich auch seine Zeit. Beispielsweise ist es nur suboptimal sortiert. Sortierung nach Spalten brachte die beste Geschwindigkeit. Wenn ich hingegen nach allen sortiere, habe ich zwar die besten Felder vorne, aber es dauert insgesamt länger, weil die Sortierung auch Zeit braucht.

Bei deinem Code sehe ich mehrere Effizienzprobleme, wobei dieses eines der größeren sein sollte:
Jeder auszuprobierende Wert wird zunächst per
this.matrix[nullstellen.get(pos).get_x()][nullstellen.get(pos).get_y()]++;
ins temporäre Ziel geschrieben. Warum?
Es sollte genügen, ihn zu laden, vorzuhalten und ohne diesen Umweg zu prüfen (wobei der Test gegen das eigene Feld nicht stört, wenn es auf 0 bleibt). Der Erfolg ist nicht so wahrscheinlich, dass es sich lohnen würde, auch bei Misserfolg zu speichern (hinzu kommt, dass der Vorgang rückgängig gemacht werden muss). Und es ist in jedem Fall unglücklich, dass der Wert zum Überprüfen noch einmal geladen werden muss, anstatt dass er immer noch im Register läge.

Das ist dem vorherigen Code geschuldet. Aktualisieren holt seine Werte aus der Matrix. Damit werden die Zeilen, Spalten und kleinen Matrizen hergestellt. Zudem habe ich ja auch probiert. Nur eben mit mehr Regeln. Für das Probieren habe ich dann die ganze Matrix übergeben. Wie gesagt, es ist besser, alles neu zu schreiben.

Falls deine "Liste" nicht als Array implementiert ist, ein weiteres (großes) Effizienzproblem:
Was die Zeiten für den Lookup in einer Liste (sollte schnelles Ein- und Aushängen (kein Umsortieren beim Einfügen bzw. Entfernen nötig) unterstützen, was Verpointerung bedeutet) angeht, bin ich skeptisch. Sogar wenn sie optimalerweise indiziert ist (um das Verfolgen zahlreicher Pointer, die Liste hinab bis zum Ziel, zu vermeiden), wird sie zwar viel schneller (endlich mit konstanter Zugriffszeit), aber nicht schnell genug, weil eine weitere Indirektion, eben über den Index zum Pointer und erst über diesen zum Ziel, unvermeidbar ist. Und wenn du mehrmals zugreifst (wie in deinem Code) und der Compiler nicht weiß, dass die Liste sich zwischenzeitlich nicht ändern kann, dann schlägt die Zeit gleich mehrmals zu Buche, sodass du den Wert zwischenspeichern solltest, wenn du ihn nicht wenigstens rasant hervorkramen kannst. Ein echtes Array, wo die Elemente direkt aufeinanderfolgend gespeichert sind und das natürlich ohne dazwischengefummeltes Bounds Checking, sollte den Anforderungen schon einigermaßen entgegenkommen. Ob dann zusätzliches Zwischenspeichern bei Mehrfachzugriff noch was bringt, müsstest du ausprobieren. Manchmal bringt es was, manchmal ist es kontraproduktiv. Die entsprechenden Zweige werden ja nicht immer durchlaufen.

Das habe ich nicht ganz verstanden. Also die Matrix ist natürlich ein Array. Auch die kleinen Matrizen sind Arrays. Nur die Zeilen und Spalten sind Listen.

[jabu]

[...]

Danke für die weiteren Erläuterungen, erscheint mit alles schlüssig.
Ja, man kann es neu schreiben. Oder man hält es lauffähig und wandelt es schrittweise ab.

Das habe ich nicht ganz verstanden. Also die Matrix ist natürlich ein Array. Auch die kleinen Matrizen sind Arrays. Nur die Zeilen und Spalten sind Listen.

Dass die Matrizen Arrays sind, habe ich naheliegenderweise angenommen.
Wie deine Zeilen und Spalten zum Prüfen repräsentiert sind, wusste ich nicht. Ich hatte nur eine dahingehende Vermutung, was mir für den Anfang zu vage war, weswegen ich mich erst mal auf gesichertere Erkenntnisse konzentriert hatte.

Ich meinte dieses:

Zum Verständnis: Ich habe vorher die Nullstellen alle in einer Liste gespeichert.

Das Nachgucken in einer Liste (was du doch immer wieder machst, um die Array-Indizes zu ermitteln) geht nicht gerade schnell.

Ich habe mal kurz und übersichtlich zusammengefasst, was dein Code im Wesentlichen tut. Wegen der Übersichtlichkeit habe ich den Zugriff auf die Matrixwerte symbolisch ersetzt (zugleich ein Wink mit dem Zaunpfahl auf ein alternatives Konzept, aber darum geht es jetzt noch nicht):

boolean primus(int pos) {
    do { // pos ändert sich nach Misserfolg nicht, weswegen...
        do {          
            if (Nullen[pos].wert > 9) { // (derselbe Test noch einmal erfolgt, nun gegen 0 statt 10)
                Nullen[pos].wert = 0;
                keine_zahl_passt = true; // ...diese unnütze Variable gebraucht wird...
                return false; 
            }  
            if(keine_zahl_passt) { // ...und dieser unnütze Fall behandelt wird.
                pos--;
                keine_zahl_passt = false;
            }               
        } while (!Prüferfolg(++Nullen[pos].wert));      
        
        // NichtsFalschesGefunden() ist bei korrektem Code überflüssig
        // und könnte andernfalls zu einer Endlosschleife führen,
        // also besser nachher prüfen!
        if (pos == MAX_POS && NichtsFalschesGefunden())
            return true;
         
    } while (!primus(++pos)); // pos bleibt auch nach Misserfolg um 1 erhöht!
       
    return true;
}

Somit reduziert sich das Gehörn zu dieser gleichwertigen Lösung:

boolean primus(int pos) {
    do {
        do {
            if (Nullen[pos].wert > 9) {
                Nullen[pos].wert = 0;
                return false;
            }                
        } while (!Prüferfolg(++Nullen[pos].wert));
              
        if (pos == MAX_POS)
            return true;
         
    } while (!primus(pos+1));
       
    return true;    
}

Auf deinen Code übertragen:

boolean primus(int pos) { 
  
    aufrufe++;
    
    // Muss nur noch beim rekursiven Aufstieg geprüft werden.
    if (pos == nullstellen.size()) {
        return true; // fertig!
    }
    // Werte zwischenspeichern, wenn sie mehrmals gebraucht werden,
    // ob das später irgendwann mal entfallen kann, wird man sehen.
    final int x = nullstellen.get(pos).get_x();
    final int y = nullstellen.get(pos).get_y();

    do {
        do {
            if (this.matrix[x][y] > 9) {         
                this.matrix[x][y] = 0; // Darf doch 0 anstatt get_matrix(x, y) zugewiesen werden?
                aktualisieren_neu(x, y, 0); // Ist das nicht unnötig?
                return false;           
            }        
            this.matrix[x][y]++; // Lahm (ändern): Es wird auch mit (this.matrix[x][y] == 10) geprüft!
            aktualisieren_neu(x, y, get_matrix(x, y)); // TODO: kann später entfallen, s.u.
        } while (prüfen() != 0); // TODO: Umgestalten in: while (prüfen(x, y, get_matrix(x, y))) 
        // TODO:
        // Ab hier gibt es die temporäre Erfolgsgarantie!
        // Daher genügt es, hier den passenden Wert in die Matrix zu schreiben,
        // also z.B. per this.matrix[x][y] = i; 
        // get_matrix wird durch die Iterationsvariable i ersetzt
    } while (!primus(pos+1)); // nicht: ++pos, denn so entfällt das Gehörn rund um pos--
    return true; // Bei Austritt aus der Schleife herrscht immer Erfolg!
}

Man kann also schrittweise den Code hin zu schnellerem abwandeln. Der Vorteil besteht darin, immer etwas Lauffähiges zu behalten und sich schrittweise dem Problem in seiner reinen Gestalt anzunähern. Nebenbei kann man ziemlich frustarm eine Menge lernen.

[Stiller Leser]

Danke für die weiteren Erläuterungen, erscheint mit alles schlüssig.
Ja, man kann es neu schreiben. Oder man hält es lauffähig und wandelt es schrittweise ab.

Ich mach das neu. Dieses abwandeln, würde nur dazu führen, dass das andere nicht mehr läuft. Das wäre zwar nicht mehr notwendig. Aber es ist ja auch ein lauffähiger Algorithmus, den ich eigentlich erhalten will.

Ich meinte dieses:
Das Nachgucken in einer Liste (was du doch immer wieder machst, um die Array-Indizes zu ermitteln) geht nicht gerade schnell.

Naja, er schaut ja nicht wirklich nach. Ich hole da nur die x,y werte. Das die Stellen 0 sind, ist ja klar. Das wird ja vorher einmal ermittelt.
Aber es ist klar, dass es besser ist, x und y einmal abzuspeichern, als ständig die Methode zu bemühen.

Das meiste von deinen Vorschlägen konnte ich umsetzen und es wird nachvollziehbar schneller. Und der Code wird sogar deutlicher.
Lediglich das Prüfen läuft so nicht. Für die andere Methode brauche ich ein anderes prüfen.

boolean primus(int aktuelle_zahl, int pos) {    final int x=nullstellen.get(pos).get_x(),y=nullstellen.get(pos).get_y();


    aufrufe++;
    do {
            do {
                if(this.matrix[x][y]>9) {
                    this.matrix[x][y]=0;
                    aktualisieren_neu(x,y,get_matrix(x,y));
                    return false;
                    
                }
                
                this.matrix[x][y]++;
                aktualisieren_neu(x,y,get_matrix(x,y));
            }while(prüfen()!=0);
            
                    if(pos==nullstellen.size()-1) {
                        return true;
                    }
    }while(!primus(0,pos+1));
    
    return true;
}

Aber mal sehen, wie es funktioniert im reinen Brute Force bei mir. Hab schon was entwickelt, was die Prüfzeiten deutlich reduzieren wird. Mal sehen, was bei rauskommt.

matrix[x][y]=0;
aktualisieren_neu(x,y,get_matrix(x,y));

Ist leider bei mir notwendig.
Das Problem ist halt, dass er die Spalten, Zeilen und Matrizen aus der großen Matrix zieht und anschließend wird geprüft. Das geht sicherlich viel besser. Aber wenn ich das hier ändere, läuft der ganze Rest nicht mehr. Deshalb mache ich das komplett neu und brauch mich nicht mehr um andere Zöpfe zu kümmern.