Arraycopy kopiert nur die Referenz?!

[BruteForce]

Hallo zusammen,

ich schreibe derzeit an einem Sudoku-Löser, der mithilfe von BruteForce das Sudoku löst. Wenn ein Thread sich damit beschäftigt, läuft alles rund. Nun wollte ich das ganze beschleunigen und wollte dazu einen zweiten Thread in die entgegengesetzte Richtung bruteforcen lasse. Dieser Thread darf natürlich nicht das gleiche int[][]-Array wie der erste bekommen, sonst kommt keiner zum richtigen Ergebnis.

Das Array-Kopieren hab ich zunächst mit .clone() versucht, aber auch mit System.arraycopy() klappt es nicht

Hier mal ein bisschen Code:

Thread-Ersteller-Klasse:

//Im Kunstruktor wird das Feld "mySudoku" korrekt in das Objekt kopiert.

@Override public void run()
{
System.arraycopy(mySudoku, 0, copy, 0, mySudoku.length);
System.arraycopy(mySudoku, 0, copy2,0, mySudoku.length);
			
firstCore = new SudokuBruter(copy, 0, this);
secondCore= new SudokuBruter(copy2, 1, this);
// [...]
secondCore.start();
firstCore.start();
}

Der SudokuBruter:

public SudokuBruter(int[][] gotSudoku, int Tmode, SudokuBruteForce mum) {
	OwnSudoku = gotSudoku;
	mode = Tmode;
	parent = mum;
}

@Override public void run()
{  
System.out.println("Mode " + mode + " got started");
printSudoku(OwnSudoku);  //Sudoku ausgeben ---> Hier entstehen seltsame Ausgaben
if(nextfield(OwnSudoku, mode)){ //Rekursiv das Sudoku bruteforcen (klappt auch wunderbar)
	parent.finishSudoku(mode, OwnSudoku);  //gelöstes Sudoku an die Oberklasse reichen und drucken lassen (+ ggf. den anderen Thread interrupten)
} else {
System.out.println("Mode " + mode + " finished");
}
 }

In der Konsole entstehen dann folgende Ausgaben:
Bei einem Thread:

Start solving the Sudoku...
Mode 0 got started
 9       1   4       2  
   8       6       7    
                        

 4                   1  
   7               3    
 3                   7  

                        
   3       7       8    
 1       2   9       4  

Solved Sudoku:

 9 5 7   1 8 4   3 6 2  
 2 8 1   9 6 3   4 7 5  
 6 4 3   7 2 5   1 9 8  

 4 9 6   3 5 7   8 2 1  
 8 7 5   4 1 2   9 3 6  
 3 1 2   8 9 6   5 4 7  

 7 2 9   5 4 8   6 1 3  
 5 3 4   6 7 1   2 8 9  
 1 6 8   2 3 9   7 5 4  

Solved Sudoku was printed.

Alles wunderbar... Aber bei zwei Threads:

Start solving the Sudoku...
Mode 1 got started
 9       1   4       2  
   8       6       7    
                        

 4                   1  
   7               3    
 3                   7  

                        
   3       7       8    
 1       2   9       4  

Mode 0 got started
 9       1   4       2  
   8       6       7    
                        

 4                   1  
   7               3    
 3                   7  

                        
 9 3 2   4 7 5   1 8 6  // <--- Wo kommen diese zusätzlichen Zahlen her?! 
 1 6 7   2 8 9   3 5 4  // Hab ich das Array nur flach kopiert?
Mode 0 finished //Schon fertig? Achja, mit dem Array konnte man ja auch nichts weiter anfangen -.-

Reached iteration 18021344. 2% of worst case scenario.  //Diese Ausgaben mach ein anderer Thread (jede 1.5 Sekunden)
Reached iteration 32115093. 5% of worst case scenario.

Mode 1 finished
Solved Sudoku:

[...] <-- Sudoku wird ordentlich gelöst ausgegeben (siehe oben)

Das Problem beim zweiten Versuch ist, dass Mode 0 eigentlich als erster ein Ergebnis finden würde (statt nach 3 Sekunden, in 0.05 Sekunden). Aber warum bekommt Mode 0 so ein merkwürdiges Array

Vielleicht kann mir jemand helfen und sagen, wo eventuell mein Fehler liegt, und wie ich nun in beide Threads ein autonomes Array reinschaufeln kann.

Schönen Tag euch noch

 

[faetzminator]

Wenn beide Threads wild durcheinander schreiben, ist es klar, dass da die Ausgaben irgendwie wie zusammengewürfelt aussehen.

 

[codechaos]

Be zweidimensionalen Arrays, wird nur eine Kopie des Äußeren erstellt. Du hast also zwei verschiedene Arrays, die wiederum die selben Arrays enthalten.

        int[][] k = new int[][] {{1,2},{3,4}};
        int[][] w = Arrays.copyOf(k, k.length);
        
        w[1][0] = 5;
        w[0] = new int[] {8,9};

        System.out.println(Arrays.deepToString(k));
        System.out.println(Arrays.deepToString(w));

 

[BruteForce]

Ok
Dass beim "tiefen" Arraykopieren nur das äußere Feld kopiert wird, hätte man auch früher vermuten können

Mein Code sieht jetzt so aus:

//Deep-Array-Copy:
			
for(int i = 0; i < 9; i++){
	copy[i] = Arrays.copyOf(mySudoku[i], 9);
}

Und siehe da: alles flink und elegant Danke

Jetzt lässt sich auch dieser Worst-Case-Fall ( Sudoku algorithms - Wikipedia, the free encyclopedia ) innerhalb von 0.05 Sekunden lösen :lol: *so viel zum Thema worst-case*