Methoden Zelle updaten bei Sudoku

Loddakwin

Aktives Mitglied
Hi Leute,

ich hab ein kleines Problem, weiß nicht wie ich bei einem Sudoku die einzelnen Zellen updaten soll.

Was ich bis jetzt hab:
Java:
public class Cell {

    public int size;
    public int value;
    public int[] options = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    /**
     * 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.size = size;
        this.value = value;
    }

    /**
     * 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 (this.value == options[i]) {
                options[i] = 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() {

        if (this.isEmpty()) {

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

        return 0;
    }

    /**
     * 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.isEmpty()) {
            for (int i = 0; i < this.options.length; i++) {
                if (this.options[i] != 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

Kann mir nicht vorstellen das ich hier am richtigen weg bin wäre nett wenn ihr mir vielleicht einen tipp geben könnt.

Angabe:
sudoku.PNG


lg
 

Flown

Administrator
Mitarbeiter
Sind das wirklich alle Angaben zu dieser Übung? (Möchte aus Jucks mal selber nachprogrammieren :))

Du bist schon auf dem richtigem Weg, bis auf die update-Methode. Da würde ich wirklich nur den Wert zuweisen, wenn dieser eindeutig ist (alles andere wäre dann geraten). Sonst sieht das gut aus.
 

Loddakwin

Aktives Mitglied
Hi danke für deine Antwort! Und genau das verstehe ich nicht alle werte die im Options array vorhanden sind wären dann ja geraten weil ich nicht weiss welchen wert ich zuweisen kann bzw darf?

Edit: ja das sind alle Angaben zum ersten Teil es gibt dann noch eine zweiten möchte aber erst diesen hier zu ende bringen :)

lg
 

Flown

Administrator
Mitarbeiter
Jap ich hab das jetzt nicht mit Arrays sondern einem BitSet gelöst und update nur, wenn es genau nur EINE Option gibt:
Java:
class Cell {
	public static final int EMPTY = 0;
	
	private int value;
	private BitSet 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;
		options = new BitSet(size);
		if (value == EMPTY) {
			options.set(0, size, true);
		}
	}
	
	/**
	 * Returns the value of this cell.
	 * 
	 * @return the value
	 */
	public int getValue() {
		return value;
	}
	
	/**
	 * Indicates if cell is empty, i.e., has no value.
	 * 
	 * @return <code>true</code>, if empty
	 */
	public boolean isEmpty() {
		return value == EMPTY;
	}
	
	/**
	 * Erases the given value from options and returns changes.
	 * 
	 * @param value
	 *          value to be erased
	 * @return <code>true</code>, if erase action changed options, else
	 *         <code>false</code>
	 */
	
	public boolean erase(int value) {
		if (options.get(value - 1)) {
			options.clear(value - 1);
			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() {
		return options.cardinality();
	}
	
	/**
	 * Checks options to give this cell a value and returns changes.
	 * 
	 * @return <code>true</code>, if cell state changed from empty to not empty
	 */
	public boolean update() {
		if (getOptionCount() == 1) {
			value = options.nextSetBit(0) + 1;
			options.clear(value - 1);
			return true;
		}
		return false;
	}
}
 

Loddakwin

Aktives Mitglied
Hi danke für deinen Code bei mir funktioniert die getOptionCount Methode nicht.
Exception:
Created object: new Cell(3, 0)
Called methods (in this order): getOptionCount()
>> Expected result: 3
>> Your result: 9

Verstehe ich aber nicht dachte das es bei einem value von 0, 9 Optionen gibt.

lg
 

Flown

Administrator
Mitarbeiter
Zeig mal deinen ganzen Cell Code her, bei mir kommt das richtige raus!

Nein die size gibt die Anzahl der Optionen.
 

Loddakwin

Aktives Mitglied
Hi danke ich habs umgeschrieben das stimmt jetzt auch :) hier der code:
Java:
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] = 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[i] && this.value == 0) {
                options[i] = 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[i] != 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[i] != 0) {
                    this.value = options[i];
                    return true;
                }
            }
        }
        return false;
    }
}

hast du die klasse sudoku auch geschrieben bzw die update methode in sudoku?
Achja und der 2 Teile der aufgabe ist einfach noch eine solve methode der Sudokuklasse hinzuzufügen.

Java:
public class Sudoku {

    private int[][] s;

    /**
     * Constructs the Sudoku.
     *
     * @param values
     *            the unsolved Sudoku (empty cells are 0)
     *
     */
    public Sudoku(int[][] values) {
        s = values;
    }

    /**
     * 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) {
        return false;
    }

    /**
     * Returns the string representation of this Sudoku.
     *
     * @return the Sudoku string
     *
     */
    public String toString() {
        String matrix = "";
        for (int i = 0; i < s.length; i++) {
            for (int j = 0; j < s[i].length; j++) {
                matrix = matrix + " " + s[i][j];
            }
            matrix = matrix + "\n";
        }
        return matrix;
    }
   
    /** Solves the Sudoku by updating rows, columns, and sub-grids
     * as long as there is no more change. */
     public void solve() {
        
     }
}

lg und danke nochmal
 

Flown

Administrator
Mitarbeiter
Das ist wirklich nur ein simples Sudoku Lösungskonstrukt, dass nur Möglichkeiten durch auftreten lösen kann. Man bräuchte einige Constraints, die man mit Constraint Programming lösen könnte (so könnte man logische Schritte wie auch der Mensch spielt machen). Oder natürlich einen Backtracking Algorithmus um alle Felder auszufüllen. Kommt drauf an wie man das machen möchte.

HIER gibt es ein paar Möglichkeiten wie man weitermachen kann.
 

nobody76

Mitglied
Von Backtracking habe ich schon öfters gehört. Kann mir das ja auch irgendwie vorstellen, aber nicht wie ich das in Java umsetzen könnte...
 

JStein52

Top Contributor
z.B. so:
Java:
    private boolean check_zeile(int ypos, int wert, int matrix[][]){ 
        for (int i=0; i<9; i++)
            if( matrix[ypos][i] == wert)
                return false;
        return true;
    }
    private boolean check_spalte(int xpos, int wert, int matrix[][]){
        for (int i=0; i<9; i++)
            if( matrix[i][xpos] == wert)
                return false;
        return true;
    }
    private boolean check_quadrant(int ypos, int xpos, int wert, int matrix[][]){
        int xposneu=0;
        int yposneu=0;
        xposneu=xpos%3;
        yposneu=ypos%3;     
        for (int i=(xpos-xposneu);i<(xpos-xposneu+3);i++)
            for (int j=(ypos-yposneu);j<(ypos-yposneu+3);j++)
                if(matrix[j][i]==wert)
                    return false;
        return true;
    }
    private boolean solve_matrix(int matrix[][]){
        int myMatrix[][] = new int[9][9];
        for (int i=0;i<9;i++){
            for (int j=0;j<9;j++){
                myMatrix[i][j]=matrix[i][j];
            }
        }
        for(int k=0;k<9;k++){
            for(int l=0;l<9;l++){
                if(myMatrix[k][l]==0){
                    for(int m=1;m<10;m++){
                        if(check_zeile(k,m,myMatrix)==true
                         &&check_spalte(l,m,myMatrix)==true
                         &&check_quadrant(k,l,m,myMatrix)==true){
                            myMatrix[k][l]=m;
                            if(solve_matrix(myMatrix)==true){
                                for(int i=0;i<9;i++){
                                    for(int j=0;j<9;j++){
                                        matrix[i][j]=myMatrix[i][j];
                                    }
                                }
                                return true;
                            }
                        }
                    }
                    return false;
                }
            }
        }     
        return true;
    }

Der Ausgangspunkt ist solve_matrix, die übergebene Matrix ist das Spielfeld mit beliebig vorgegebenen Werten. Wenn es überhaupt eine Lösung gibt findest du die mit diesem Verfahren.

Edit: Noch eine Anmerkung, du findest mit diesem Verfahren nicht alle möglichen Lösungen sondern nur die erste passende !!
 
Zuletzt bearbeitet:

Neue Themen


Oben