# Sudoku update und solve methode

Hi Leute,

ich hab ein kleines Problem bei dem ich nicht weiter komme und zwar weiss ich nicht wie ich die update und solve methode aus der Klasse sudoku programmieren soll. Also ich steh am schlauch und weiß nicht wie ich da ran gehen soll.

Klasse Cell

``````public class Cell {

public int value;
public int[] options;

/**
* Constructs a cell for a Sudoku of given size.
*
* @param size
*            the size n of the Sudoku
* @param value
*            the value of the cell, may be EMPTY
*
*/
public Cell(int size, int value) {
this.value = value;
this.options = new int[size];
for(int i = 0; i < options.length; i++) {
options** = i + 1;
}
}

/**
* Returns the value of this cell.
*
* @return the value
*
*/
public int getValue() {
return this.value;
}

/**
* Indicates if cell is empty, i.e., has no value.
*
* @return true, if empty
*
*/
public boolean isEmpty() {
return this.value == 0;
}

/**
* Erases the given value from options and returns changes.
*
* @return true, if erase action changed options
*
*/
public boolean erase(int value) {

for (int i = 0; i < this.options.length; i++) {
if (value == options** && this.value == 0) {
options** = 0;
return true;
}
}

return false;
}

/**
* Returns the current number of possible values of this cell.
*
* @return the number of possible values, 0, if the cell has a value
*
*/
public int getOptionCount() {

int count = 0;

if(!this.isEmpty()) {
return 0;
} else {
for(int i = 0; i < options.length; i++) {
if(options** != 0) {
count++;
}
}
}
return count;
}

/**
* Checks options to give this cell a value and returns changes.
*
* @return true, if cell state changed from empty to not empty
*
*/
public boolean update() {
if (this.getOptionCount() == 1) {
for (int i = 0; i < this.options.length; i++) {
if (this.options** != 0) {
this.value = options**;
return true;
}
}
}
return false;
}
}
``````

Klasse Sudoku:

``````public class Sudoku {

Cell[][] s;
int[][] values;
/**
* Constructs the Sudoku.
*
* @param values
*            the unsolved Sudoku (empty cells are 0)
*
*/
public Sudoku(int[][] values) {
this.values = values;
this.s = new Cell[values.length][values.length];
for(int i = 0; i < values.length; i++) {
for(int j = 0; j < values**.length; j++) {
s**[j] = new Cell(values.length, values**[j]);
}
}
}

/**
* Updates a logical part of the Sudoku by erasing known values and updating
* cells.
*
* @return true, if any cell in the part changed (including cell options)
*
*/
public boolean update(Cell[] part) {

int test = 0;
for(int i = 0; i < part.length; i++) {
for(int j = 0; j < this.values.length; j++) {
for(int k = 0; k < this.values[j].length; k++) {
test = values[j][k];
part**.erase(test);
}
}
}

if(test != 0) {
return true;
}

return false;
}

/**
* Returns the string representation of this Sudoku.
*
* @return the Sudoku string
*
*/
public String toString() {
String matrix = "";
for (int i = 0; i < this.s.length; i++) {
for (int j = 0; j < this.s**.length; j++) {
matrix = matrix + " " + this.s**[j].getValue();
}
matrix = matrix + "
";
}
return matrix;
}

/** Solves the Sudoku by updating rows, columns, and sub-grids
* as long as there is no more change. */
public void solve() {
//    	update(s);
}
}
``````

Wäre nett wenn ihr mir da helfen könnt

lg

Angabe:

*** Edit ***

Keiner einen Tipp für mich?

allgemein: Sudoko in Programmierung, Java oder anderers, gibt es zum Umfallen,
falls du fertiges suchst, dann mit Suchmaschine sicher jede Menge zu finden,

zu deinem Programm scheinst du noch nicht wirklich durchdrungen zu haben, worum es geht,
wozu über Code nachdenken/ fragen wenn du nicht weiß was das Programm oder alternativ du als denkender Kopf überhaupt tun sollst?
freilich kann genau das auch die Frage sein:

in deiner Aufgabe steht ein Beispiel
3 0 4 0
2 0 0 0
0 3 0 0
0 0 0 3

kannst du das als Mensch lösen, hast du ein Verfahren was du ungefähr beschreiben kannst?
blind wird das Programm nicht von selber entstehen…

in der Aufgabe ist von Cell[] als ‘part’ des Sudokus die Rede, dazu hast du bisher wenig,
deine update-Methode macht nichts sinnvolles, oder was genau stellst du dir unter deinem Code vor,
kannst du ihn in Worten beschreiben? aber ok, hast du ja auch selber in Frage gestellt,
nur was hattest du mit dem bisherigen Code vor, welche Ideen, welche Aufgaben schon bekannt?

'part’s sind:
jede Zeile, etwa die obere `3 0 4 0`, jede Spalte, etwa die linke `3 2 0 0`
und auch jede Ecke, etwa oben links `3 0` + `2 0` darunter bilden für sich einer 4er-Menge,
unabhängig von ihrer globalen Position

wenn man `3 0 4 0` betrachtet, dann kann man für die beiden noch nicht bestimmten Zellen die 3 und die 4 als Option löschen,
andere ‘part’ ergeben andere Löschmöglichkeiten, die idealerweise mit der Zeit eine Zelle oft genug treffen bis dort nur noch eine Möglichkeit über bleibt

->
erstelle eine update()-Methode, die die Zellen eines ‘part’ sinnvoll betrachtet: wenn schon irgendwo ein Wert gesetzt ist, dann bei den anderen Zellen löschen,
dazu natürlich noch Aufruf der update()-Methode jeder Zelle am Ende,
Rückgabe true/ false je nachdem ob sich was getan hat, dazu auch die Rückgabe von erase() berücksichtigen, läßt du bisher verfallen

solve() wiederholt dann solange update() zu allen ‘part’ bis sich in einer kompletten Runde nix mehr tut

Hallo danke für deine Antwort also ich stell mir das so vor.

``````/**
* Updates a logical part of the Sudoku by erasing known values and updating
* cells.
*
* @return true, if any cell in the part changed (including cell options)
*
*/
public boolean update(Cell[] part) {

for(int i = 0; i < part.length; i++) { // ich geh das part array durch
if(!part**.isEmpty()) {           //wenn nicht 0 dann lösche den wert aus jeder Cell option richtig?
for(){                           // nur ich weiß nicht wie ich das programmiere..?

}
}
}

}
``````

lg

detaillierter Punkt, für dich selber auch der richtige Schritt, gute Überlegung hin zu einer klaren Aktion,
aber warum dann Frage, das ist unverständlich

du kannst den Wert aus part** herausholen (idealerweise diese wichtige aktuelle Cell sofort erstmal in einer Variablen wie Cell c = … ablegen)

nun hast du einen int-Wert und sollst den in allen anderen Cell des Arrays per erase() löschen,
zur Not schadet es auch nicht, falls die aktuelle Cell c dabei ebenso drankommt
-> eine simple Schleife über das Array (natürlich nun nicht mehr Index i möglich) und bei jeder Cell erase() aufrufen?

Ok dann war ich doch nicht so falsch in meinen überlegungen Danke
Ich hab das jetzt so geschrieben.

``````/**
* Updates a logical part of the Sudoku by erasing known values and updating
* cells.
*
* @return true, if any cell in the part changed (including cell options)
*
*/
public boolean update(Cell[] part) {

for(int i = 0; i < part.length; i++) {
if(!part**.isEmpty()) {
int c = part**.getValue();
for(int j = 0; j < part.length; j++){
part[j].erase(c);
}
for(int k = 0; k < part.length; k++) {
if(part[k].getValue() == 0) {
part[k].update();
}
}
return true;
}
}
return false;
}
``````

Jetzt ist für mich noch die frage wie du das gemeint hast in Cell c abspeichern wenn ich mir den wert raushole bracuhe ich doch eine int variable? Bin jetzt verwirrt.

Edit:

``````public boolean update(Cell[] part) {

for(int i = 0; i < part.length; i++) {
if(!part**.isEmpty()) {
int c = part**.getValue();
for(int j = 0; j < part.length; j++){
part[j].erase(c);
}
}
if(part**.isEmpty()){
for(int k = 0; k < part.length; k++) {
if(part[k].getValue() == 0) {
part[k].update();
}
}
}
}
return true;
}
``````

oberer code würde bei jedem schleifendurchlauf true zurück geben, daher falsch hab ich ausgebessert! sry

das mit Cell c habe ich unten beispielhaft eingebaut, neben anderen Alternativen,
musst du nicht alle kennen/ mögen

continue ist früher Schleifensprung, erspart if/ else,
eine for-Schleife auch ohne Index ist möglich

fachlich bei dir noch:
ob direkt nach einem erase() schon update(), das ist fraglich,
ich habe mal eine Variante erst nach allen erase() gebaut, aber hat alles Vor und Nachteile

mit dem boolean bist du aber noch gar nicht weit,
nur weil eine Cell nicht empty ist gibt es auf keinen Fall return true; , das ist ja im ganzen Sudoko von Anfang an der Fall,
das boolean misst ob sich eine Änderung ergibt

du musst darauf achten ob das erase() oder update() der Cell-Objekte ein true liefert, wenn dann merken und später zurückgeben,
in der Hoffnung dass nicht gleich ‘ja und wie mach ich das?’ kommt belasse ich es bei diesem Hinweis…

``````	public boolean update(Cell[] part) {

for(int i = 0; i < part.length; i++) {
Cell c = part**; // das unhandliche part** nur genau einmal gebraucht, die Variable c mindestens 2x
if(c.isEmpty()) continue;
int v = c.getValue();
for(Cell p : part) { // Index unnötig
p.erase(v); // hier evtl. prüfen ob p != c ist
}
}

for(Cell p : part) { // Index unnötig
p.update();
}

}
``````

sehr spätes edit: die Hauptschleife braucht freilich genausowenig den Index i, könnte zu `for(Cell c : part) {` werden,
dann die lokale Variable c umso natürlicher gewonnen

Hab meine update methode nun angepasst sieht wie folgt aus:

``````public boolean update(Cell[] part) {

boolean check = false;
for (Cell c : part) {
if (c.isEmpty())
continue;
int v = c.getValue();
for (Cell p : part) { // Index unnötig
p.erase(v); // hier evtl. prüfen ob p != c ist
check = true;
}
}

for (Cell p : part) { // Index unnötig
if (p.update()) {
check = true;
}
}
return check;
}
``````

Das hier ist meine solve methode nur stimmt das sudoku immer noch nicht hab ich noch irgendetwas übersehen?

``````public void solve() {

Cell[] all = new Cell[s.length * s.length];
int counter = 0;

for (int i = 0; i < s.length; i++) {
for (int j = 0; j < s**.length; j++) {
all[counter] = s**[j];
counter++;
}
}
update(all);
}
``````

alte Kommentare lieber nicht ewig mitschleppen, ‚// Index unnötig‘ usw. war nur einmalig zum Verständnis

der Rückgabewert von update soll feststellen ob sich was getan hat,
nur eine Zelle mit Wert, für die bei anderen erase() aufgerufen wird ist keine Änderung, vielleicht war der Wert dort ja schon gelöscht,
wenn dann wieder mit if wie beim update später

im Moment führst du update mit dem gesamten Array aus, eine 3 irgendwo im Beispiel
3 0 4 0
2 0 0 0
0 3 0 0
0 0 0 3
führt zur Verhindung der 3 bei ALLEN anderen Zellen im Sudoku

kennst du Sudoku überhaupt? weißt du dass es darum geht einzelne Zeilen usw. zu betrachten?
ich habe das ja auch schon geschrieben, wenn du willst kannst du es weiter oben nachlesen,

wie würdest du das Beispiel-Sudoku per Hand bzw. Kopf lösen? diese Schritte kommen in etwa auch im Programm vor,
vielleicht woanders eine Beschreibung des Spiels usw. nachlesen?

Ok danke für deine Tipps hab die solve methode jetzt so geschrieben das er zeilen und spalten an die update methode übergibt aber es verändert sich immer noch nichts? Und wie ich die blöcke prüfen kann hab ich auch noch nicht ganz verstanden.

``````public void solve() {

Cell[] zeile = new Cell[s.length];
Cell[] spalte = new Cell[s.length];
Cell[] block = new Cell[s.length];

int step = 0;

boolean check = false;

do {
if(step == 4) {
step = 0;
}

for (int i = 0; i < s.length; i++) {
zeile** = s[step]**;
}

for (int i = 0; i < s.length; i++) {
spalte** = s**[step];
}

check = update(zeile);
check = update(spalte);

step++;
} while (check == true);
}
``````

Normalerweiße müssten sich wenigsten schon ein paar zahlen verändern da ja zeilen und spalten geprüft werden aber das geht auch nicht. Bin jetzt echt schon ein bisschen am verzweifeln… ;(

lg

das ist ja schon ein großer Schritt, jetzt auf einmal eine ganze while-Schleife in solve(), bin positiv überrascht

du musst noch check zu Beginn jeder Runde auf false setzen, sonst einmal true, immer true

bisher hast du auch noch eine 4er-Schleife drin, ok, etwas kompliziert, wenn dann auch nur alle 4 Runden check wieder auf false setzen,
besser aber einmalig die Arrays zusammenstellen und die dann erst in der Schleife alle durchlaufen,

ein Array von 12 Cell[] zusammenstellen, 4 Zeilen, 4 Spalten, 4 Blöcke, bisher hast du die Blöcke gar nicht

mit

``````            check = update(spalte);
``````

überschreibst du auch die Rückgabe des ersten update() völlig, wenn das true liefert, das zweite aber false, dann ist check false, Schleife endet, die Änderung nicht berücksichtigt

check = true; in der update(Cell[]) Methode nur bei if (p.erase(v)), nur wenn wirklich aktuell noch etwas passiert,
sonst wird das ja in jeder Runde auf true gesetzt, weil immer irgendein Wert schon gesetzt ist (von Anfang an), immer das erase() vielfach drankommt,
nur wenn das erase() auch noch was bewirkt mit der Arbeit insgesamt fortfahren

hast du überhaupt auch schon Startwerte eingepflegt, etwa die 3 in Zelle[0][0] aus dem Beispiel?
wenn du ganzes Programm postest kann ich mal reinschauen

ansonsten auch ideale Möglichkeit für dich, Analyse der Programme zu lernen:
was erwartest du auf dem Papier als ersten Schritt, welche Zelle sollte gefüllt, welcher update-Aufruf dann welche Aktionen ausführen?

überprüfe ob das Programm das genauso macht, logge jeden update(Cell[])-Aufruf mit System.out.println(), gib die 4 beteiligten Zellen mit ihren Werten aus,
werden die richtigen 4 geprüft?, wenn nicht schaue dir die Zusammenstellung der Cell[]-parts an,
wenn es die richtigen 4 sind, dann schaue genauer wie sie verarbeitet werden, kommt die erase()-Schleife dann? usw., einfach Schritt für Schritt so genau wie nötig nachschauen,

jede einzelne Aktion kann vorausbedacht und nachgeprüft werden, oder umgekehrt anschauen was das Programm macht und dann beurteilen ob jeweils richtig,
Ausgabe überall der Schlüssel dazu, nur kontrollieren dass nicht unlesbar viel Ausgabe, Endlosschleifen ärgern schnell

Danke das du dir die zeit nimmst ist für mich sehr wichtig das ich das verstehe brauch das ganz dringend.

Cell Klasse:

``````public class Cell {

public int value;
public int[] options;

/**
* Constructs a cell for a Sudoku of given size.
*
* @param size
*            the size n of the Sudoku
* @param value
*            the value of the cell, may be EMPTY
*
*/
public Cell(int size, int value) {
this.value = value;
this.options = new int[size];
for(int i = 0; i < options.length; i++) {
options** = i + 1;
}
}

/**
* Returns the value of this cell.
*
* @return the value
*
*/
public int getValue() {
return this.value;
}

/**
* Indicates if cell is empty, i.e., has no value.
*
* @return true, if empty
*
*/
public boolean isEmpty() {
return this.value == 0;
}

/**
* Erases the given value from options and returns changes.
*
* @return true, if erase action changed options
*
*/
public boolean erase(int value) {

for (int i = 0; i < this.options.length; i++) {
if (value == options** && this.value == 0) {
options** = 0;
return true;
}
}

return false;
}

/**
* Returns the current number of possible values of this cell.
*
* @return the number of possible values, 0, if the cell has a value
*
*/
public int getOptionCount() {

int count = 0;

if(!this.isEmpty()) {
return 0;
} else {
for(int i = 0; i < options.length; i++) {
if(options** != 0) {
count++;
}
}
}
return count;
}

/**
* Checks options to give this cell a value and returns changes.
*
* @return true, if cell state changed from empty to not empty
*
*/
public boolean update() {
if (this.getOptionCount() == 1) {
for (int i = 0; i < this.options.length; i++) {
if (this.options** != 0) {
this.value = options**;
return true;
}
}
}
return false;
}
}
``````

Sudoku Klasse:

``````public class Sudoku {

public Cell[][] s;

/**
* Constructs the Sudoku.
*
* @param values
*            the unsolved Sudoku (empty cells are 0)
*
*/
public Sudoku(int[][] values) {
this.s = new Cell[values.length][values.length];
for (int i = 0; i < values.length; i++) {
for (int j = 0; j < values**.length; j++) {
s**[j] = new Cell(values.length, values**[j]);
}
}
}

/**
* Updates a logical part of the Sudoku by erasing known values and updating
* cells.
*
* @return true, if any cell in the part changed (including cell options)
*
*/
public boolean update(Cell[] part) {

boolean check = false;
for (Cell c : part) {
if (c.isEmpty())
continue;
int v = c.getValue();
for (Cell p : part) {
if (p.erase(v)) {
check = true;
}
}
}

for (Cell p : part) {
if (p.update()) {
check = true;
}
}
return check;
}

/**
* Returns the string representation of this Sudoku.
*
* @return the Sudoku string
*
*/
public String toString() {
String matrix = "";
for (int i = 0; i < this.s.length; i++) {
for (int j = 0; j < this.s**.length; j++) {
matrix = matrix + " " + this.s**[j].getValue();
}
matrix = matrix + "
";
}
return matrix;
}

/**
* Solves the Sudoku by updating rows, columns, and sub-grids as long as
* there is no more change.
*/
public void solve() {

Cell[] zeile = new Cell[s.length];
Cell[] spalte = new Cell[s.length];
Cell[] block = new Cell[s.length];

int step = 0;
boolean check = false;

do {
check = false;
if(step == 4) {
step = 0;
}

for (int i = 0; i < s.length; i++) {
zeile** = s[step]**;
}

for (int i = 0; i < s.length; i++) {
spalte** = s**[step];
}

check = update(zeile);
check = update(spalte);

step++;
} while (check == true);
}
}
``````

Sry hab vergessen zu erwähnen das die werte in einer anderen KLasse gesetzt werden.

``````public static void main(String[] args) {

Sudoku a = new Sudoku(new int[][] { { 3,0,4,0},  { 2,0,0,0},  { 0,3,0,0},  { 0,0,0,3}});

a.solve();

System.out.print(a.toString());

}
``````

lg und danke nochmal vielmals

wie schon geraten: wenn alles auf 0 steht, keine Anfangswerte gesetzt, dann wird auch nichts passieren,
kein erase(), kein update(), Schleife schnell zu Ende
(edit: oder was ist der Konstruktor-Aufruf, das values[][]? ohne main-Methode kein vollständiges Programm…)

im übrigen genug anderes genannt was du wieder zu tun hast
ok, bisschen schon umgesetzt, aber ohne Blöcke wird es wohl nichts, und anderes mehr

dass mit dem step ist weiter schlimm
evtl. noch als innere Schleife

``````            check = false;

// 4er-Schleife durchlaufen, for-Schleife reicht dann auch wieder

} while (check == true);
``````

aber besser ganz raus,
erstelle zunächst 12 Cell[] mit passenden Inhalt, das ist eine klar definierte Aufgabe

``````/**
* Solves the Sudoku by updating rows, columns, and sub-grids as long as
* there is no more change.
*/
public void solve() {

Cell[] all = new Cell[s.length * 3];

int step = 0;
boolean check = false;

do {

check = false;

for (int i = 0; i < s.length; i++) {
all** = s[step]**;
all[i + s.length] = s**[step];
// Blöcke übersteigt meine vorstellungskraft wie ich das umsetzen könnte ?
// dass mit dem step ist weiter schlimm
// evtl. noch als innere Schleife  wie ist das gemeint ?
}

check = update(all);

step++;

} while (check == true);
}
``````

Jetzt bekomm ich noch dazu eine exception:
at Sudoku.update(Sudoku.java:37)
at Sudoku.solve(Sudoku.java:90)
at Bsp10.main(Bsp10.java:8)

eine innere Schleife von 0 bis 4 zum Zusammenbau der jeweiligen Zeilen und Spalten, aber schön ist das eh nicht

update(all) aktuell auf ein Array was mehr als 4 Zellen hat ist doch wieder gleich illusorisch…

`Cell[][] parts = new Cell[12][4];` steht für 12 Arrays (4 Zeilen, 4 Spalten, 4 Blöcke) der Länge 4 ,
jedes dieser 12 Arrays ist in einem Durchlauf der do-while-Schleife zu updaten, mit einer Schleife über diese 12

befüllen magst du die 12 Arrays intelligent wenn es dir einfällt oder notfalls manuell mit 12 x 4 Befehlen:
parts[0][0] = s[0][0];

dieses Befüllen EINMALIG vor der do-while-Schleife

``````public void solve() {

Cell[][] parts = new Cell[s.length * 3][s.length];
boolean check;

// Zeilen
for (int i = 0; i < s.length; i++) {
for (int j = 0; j < s.length; j++) {
parts**[j] = s**[j];
}
}
// Spalten
for (int i = 0; i < s.length; i++) {
for (int j = 0; j < s.length; j++) {
parts[i + s.length][j] = s[j]**;
}
}
// Blöcke

//Weiß ich nicht wie ich das umsetzen kann finde dazu auch nichts

do {

check = false;

for(int i = 0; i < parts.length; i++) {
//update(); Kann hier kein 2 dim array übergeben? Oder gibts da eine andere möglichkeit ? Sry aber hab ich noch nicht gemacht
}

} while (check == true);
}
``````

für Blöcke tun es wie gesagt notfalls auch manuelle Befehle
parts[8][0] = s[0][0];
8 1 = 0 1
8 2 = 1 0
8 3 = 1 1 oder ähnlich

in Zeile 29 sollst du doch mit den 12 4er-Arrays arbeiten, die Schleife ist schon richtig, nicht zu sehen?
`check |= update(parts**);`
|= ist Abkürzung für check = check || …
ein if tuts auch, das hier ist etwas kürzer, sieht aber wie manches vielleicht nach fremder Hilfe aus

die alternative Schleife ohne Index wäre hier wieder denkbar

Hallo danke für die Antwort die manuelle befüllung funktioniert glaube ich nicht da das testprogramm mehrere eingaben tätigt.

Edit habs jetzt so geschrieben und es kommt in jeder spalte 10 heraus.

``````
public void solve() {

Cell[][] parts = new Cell[s.length * 3][s.length];
boolean check;

// Zeilen
for (int i = 0; i < s.length; i++) {
for (int j = 0; j < s.length; j++) {
parts**[j] = s**[j];
}
}
// Spalten
for (int i = 0; i < s.length; i++) {
for (int j = 0; j < s.length; j++) {
parts[i + s.length][j] = s[j]**;
}
}

// Blöcke
parts[8][0] = s[0][0];
parts[8][1] = s[0][1];
parts[8][2] = s[1][0];
parts[8][3] = s[1][1];

parts[9][0] = s[0][2];
parts[9][1] = s[0][3];
parts[9][2] = s[1][2];
parts[9][3] = s[1][3];

parts[10][0] = s[2][0];
parts[10][1] = s[2][1];
parts[10][2] = s[3][0];
parts[10][3] = s[3][1];

parts[11][0] = s[2][2];
parts[11][1] = s[2][3];
parts[11][2] = s[3][2];
parts[11][3] = s[3][3];

do {

check = false;

for(int i = 0; i < parts.length; i++) {
if(update(parts**)){
check = true;
}
}

} while (check == true);
}

``````

Bin froh das sich überhaupt was tut

lg