# Rekursiver Solver für Sudoku



## merlä (28. Jul 2006)

Hallo Liste,
ich versuche gerade ein Sudoku zu programmieren. Es klappt auch alles ganz gut, bis auf den Solver. 

Das Spiel ist wie folgt aufgebaut:

Klassenübersicht:
- Game -> erstellt ein neues Spielbrett der Dimension x
- Table -> erstellt x mal x Felder des Typs Cell
- Cell -> enthält folgende Variablen: int Wert, boolean isLocked, Color color
- Logic -> kann, wenn man ihr das Spielbrett und die aktuelle Position angibt, berechnen ob auf der Linie der Zeile und im Quadrat (Region) eine doppelte Zahl vorkommt.
- Window -> erstellt das GUI und händelt die EventListener.

Wie ihr seht schiebe ich immer das ganze Spielbrett umher (cellHolder[][]) dort drin sind immer die aktuellen Spieldaten gespeichert.
Ich suche jetzt nach einem Solver, der das ganze Spielfeld (Table) löst und zurückgibt (als cellHolder[][]). Am schönsten wäre eine rekursive Lösung. Am liebsten währe mir jedoch ein Hinweis oder eine Lösung bei der ich auch drauskomme.  :bahnhof: 

Ich hoffe sehr, dass mir jemand helfen kann. Vielen Dank im Voraus
Merlä


Es folgen die beiden Klassen Window und Logic


```
package game;

import java.awt.BorderLayout;
import java.awt.Container;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.GridLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.Color;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;

/** In this Class we handel all graphical Process and able the player to play.
 *  In every process we do, we */
public class Window extends JFrame implements ActionListener
{
    private Cell cellHolder[][];
    private JButton[][] buttons;
    private int menuSize = 8;


    public Window(final Cell cellHolder[][])
    {
        this.cellHolder = cellHolder;
// Frame erstellen
        final JFrame fenster = new JFrame("Sudoku (Grid)");
        // Definiert wo das Fenster auf dem Bildschirn angezeigt wird.
        fenster.setLocation(200, 100);
//        fenster.setSize(300, 400);

// Menü oben erstellen
        // Button erstellen
        JButton neu = new JButton("Neues Spiel");
        neu.setToolTipText("<html>Startet ein neues Spiel 

(Achtung! Alle eingegebenen Daten gehen verloren)</html>");
        fenster.getContentPane().add(neu);
        ActionListener aNeu = new ActionListener() // aNeu = ActionListener für Neu
        {
            public void actionPerformed(ActionEvent e)
            {
                new Thread(new Runnable()
                        {
                            public void run() 
                                { 
                                    System.out.println("ButtonEvent: Button \"neues Spiel\" wurde gedrückt");
                                    for (int i = 0; i < cellHolder.length; i++) 
                                    {
                                        for (int j = 0; j < cellHolder.length; j++) 
                                        {
                                            cellHolder[i][j].setValue(0);
                                            buttons[i][j].setText("0");
                                            cellHolder[i][j].setLocked(false);
                                            buttons[i][j].setForeground(Color.BLACK);
                                            
                                        }
                                    }
                                }
                        }).start();
            }
        };
        neu.addActionListener(aNeu);
        
        JButton neuOfLocked = new JButton("Spiel nochmals starten");
        neuOfLocked.setToolTipText("<html>Startet ein vorher gespeichertes

 Spiel noch einmal</html>");
        fenster.getContentPane().add(neuOfLocked);
        ActionListener aNeuOfLocked = new ActionListener() // aNeuOfLocked = ActionListener für neues Spiel der gelockten Cells
        {
            public void actionPerformed(ActionEvent e)
            {
                System.out.println("ButtonEvent: Button \"Spiel neu starten\" wurde gedrückt");
                new Thread(new Runnable()
                        { 
                            public void run() 
                            { 
                                for (int i = 0; i < cellHolder.length; i++) 
                                {
                                    for (int j = 0; j < cellHolder.length; j++) 
                                    {
                                        if (cellHolder[i][j].isLocked() == false)
                                        {
                                            cellHolder[i][j].setValue(0);
                                            buttons[i][j].setText("0");
                                            buttons[i][j].setForeground(Color.BLACK);
                                        }
                                    }
                                }
                            } 
                        }).start();
            }
        };
        neuOfLocked.addActionListener(aNeuOfLocked);
        
        JButton exit = new JButton("Spiel beenden");
        exit.setToolTipText("Beendet das Spiel");
        fenster.getContentPane().add(exit);
        ActionListener aExit = new ActionListener() // aExit = ActionListener für Exit
        {
            public void actionPerformed(ActionEvent e)
            {
                System.out.println("ButtonEvent: Button \"Spiel beenden\" wurde gedrückt");
                System.exit(1);
            }
        };
        exit.addActionListener(aExit);

        // Panel erstellen
        JPanel menuOben = new JPanel();
        menuOben.setLayout(new GridLayout(0, 3));
        // Buttons auf Panel packen
        menuOben.add(neu);
        menuOben.add(neuOfLocked);
        menuOben.add(exit);

// Menu rechts erstellen
        // Buttons erstellen
        JButton set = new JButton("set");
        set.setToolTipText("speichert das aktuelle Spiel.");
        fenster.getContentPane().add(set);
        ActionListener aSet = new ActionListener() // aSet = ActionListener für Set
        {
            public void actionPerformed(ActionEvent e)
            {
                System.out.println("ButtonEvent: Button Set wurde gedrückt, Cellen mit einem Value werden auf gelockt.");
                new Thread(new Runnable()
                        { 
                            public void run() 
                            { 
                                for (int i = 0; i < cellHolder.length; i++)
                                {
                                    for (int j = 0; j < cellHolder.length; j++)
                                    {
                                        if (cellHolder[i][j].getValue() != 0)
                                        {
                                            cellHolder[i][j].setLocked(true);
                                            buttons[i][j].setForeground(Color.BLUE);
                                        }
                                        else
                                        {
                                            cellHolder[i][j].setLocked(false);
                                            buttons[i][j].setForeground(Color.BLACK);
                                        }
                                    }
                                }
                                System.out.println("ButtonEvent: printout of the Table according to the LockStatus:");
                                for (int i = 0; i < cellHolder.length; i++)
                                {
                                    for (int j = 0; j < cellHolder.length; j++)
                                    {
                                        if (cellHolder[i][j].isLocked() == true)
                                        {
                                            System.out.print(" x");
                                        }
                                        else 
                                        {
                                            System.out.print(" o");
                                        }
                                    }
                                    System.out.println("");
                                }
                            } 
                        }).start();
            }
        };
        set.addActionListener(aSet);
        
        JButton solve = new JButton("solve");
        solve.setToolTipText("Löst das eingegebene Spiel");
        fenster.getContentPane().add(solve);
        ActionListener aSolve = new ActionListener() // aSolve = ActionListener für Solve
        {
            public void actionPerformed(ActionEvent e)
            {
                System.out.println("ButtonEvent: Button Solve wurde gedrückt");
//                for (int i = 0; i < cellHolder.length; i++)
//                {
//                    for (int j = 0; j < cellHolder.length; j++)
//                    {
//                        Logic lg = new Logic(cellHolder, i, j);
//                    }
//                }
            }
        };
        solve.addActionListener(aSolve);

        JButton check = new JButton("check Table");
        check.setToolTipText("<html>Kontrolliert ob im aktuellen Spiel

bereits ein Fehler vorhanden ist.<html>");
        fenster.getContentPane().add(check);
        ActionListener aCheck = new ActionListener() //aCheck = ActionListener für Ckeck
        {
            public void actionPerformed(ActionEvent e)
            {
                for (int i = 0; i < cellHolder.length; i++)
                {
                    for (int j = 0; j < cellHolder.length; j++)
                    {
                        if (cellHolder[i][j].isLocked() != true)
                        {
                            if (cellHolder[i][j].getValue() != 0)
                            {
                                Logic lg = new Logic(cellHolder, i, j);
                                if (lg.checkLine() == false | lg.checkRow() == false | lg.checkRegion() == false)
                                {
                                    buttons[i][j].setForeground(Color.RED);
                                }
                            }
                        }
                    }  
                }
                System.gc();
            }
        };
        check.addActionListener(aCheck);
        
        JButton show = new JButton("show");
        show.setToolTipText("<html>Nur für Programmierer

Gibt das Table auf der Console aus</html>.");
        fenster.getContentPane().add(show);
        ActionListener aShow = new ActionListener() // aShow = ActionListener für Show
        {
            public void actionPerformed(ActionEvent e)
            {
                System.out.println("ButtonEvent: Button Show wurde gedrückt, das grid soeht wie folgt aus:");
                for (int i = 0; i < cellHolder.length; i++)
                {
                    for (int j = 0; j < cellHolder.length; j++)
                    {
                        System.out.print(" "+cellHolder[i][j].getValue());
                    }
                    System.out.println();
                }
            }
        };
        show.addActionListener(aShow);
        
        // Panel erstllen
        JPanel menuRechts = new JPanel();
        menuRechts.setLayout(new GridLayout(menuSize, 0)); //dynamisch, passt sich der Table grösse an.
        // Buttons auf Panel packen
        menuRechts.add(set);
        menuRechts.add(solve);
        menuRechts.add(check);
        menuRechts.add(show);

// Button erstellen und mit den Value der Zelle initialisieren, natürlich Variabel für die grösse des Spiels
        System.out.println("generate Buttons for Field");
        buttons = new JButton[this.cellHolder.length][this.cellHolder.length];
        for (int i = 0; i < buttons.length; i++)
        {
            for (int j = 0; j < buttons.length; j++)
            {
                buttons[i][j] = new JButton("" + this.cellHolder[i][j].getValue());
                buttons[i][j].setPreferredSize(new Dimension(50,50));
                buttons[i][j].setFont(new Font( "Arial", Font.BOLD, 18)); 
                buttons[i][j].setActionCommand("" + i + j);
                buttons[i][j].setToolTipText("<html>Wert erhöhen

durch klicken.</html>");
            }
        }
        
        // Panel Region 1 erstellen
        JPanel grid1 = new JPanel();
        grid1.setLayout(new GridLayout(3, 3));
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                grid1.add(buttons[i][j]);
                buttons[i][j].addActionListener(this);
            }
        }
//      Panel Region 2 erstellen
        JPanel grid2 = new JPanel();
        grid2.setLayout(new GridLayout(3, 3));
        for (int i = 0; i < 3; i++)
        {
            for (int j = 3; j < 6; j++)
            {
                grid2.add(buttons[i][j]);
                buttons[i][j].addActionListener(this);
            }
        }
//      Panel Region 3 erstellen
        JPanel grid3 = new JPanel();
        grid3.setLayout(new GridLayout(3, 3));
        for (int i = 0; i < 3; i++)
        {
            for (int j = 6; j < 9; j++)
            {
                grid3.add(buttons[i][j]);
                buttons[i][j].addActionListener(this);
            }
        }
//      Panel Region 4 erstellen
        JPanel grid4 = new JPanel();
        grid4.setLayout(new GridLayout(3, 3));
        for (int i = 3; i < 6; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                grid4.add(buttons[i][j]);
                buttons[i][j].addActionListener(this);
            }
        }
//      Panel Region 5 erstellen
        JPanel grid5 = new JPanel();
        grid5.setLayout(new GridLayout(3, 3));
        for (int i = 3; i < 6; i++)
        {
            for (int j = 3; j < 6; j++)
            {
                grid5.add(buttons[i][j]);
                buttons[i][j].addActionListener(this);
            }
        }
//      Panel Region 6 erstellen
        JPanel grid6 = new JPanel();
        grid6.setLayout(new GridLayout(3, 3));
        for (int i = 3; i < 6; i++)
        {
            for (int j = 6; j < 9; j++)
            {
                grid6.add(buttons[i][j]);
                buttons[i][j].addActionListener(this);
            }
        }
//      Panel Region 7 erstellen
        JPanel grid7 = new JPanel();
        grid7.setLayout(new GridLayout(3, 3));
        for (int i = 6; i < 9; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                grid7.add(buttons[i][j]);
                buttons[i][j].addActionListener(this);
            }
        }
//      Panel Region 8 erstellen
        JPanel grid8 = new JPanel();
        grid8.setLayout(new GridLayout(3, 3));
        for (int i = 6; i < 9; i++)
        {
            for (int j = 3; j < 6; j++)
            {
                grid8.add(buttons[i][j]);
                buttons[i][j].addActionListener(this);
            }
        }
//      Panel Region 9 erstellen
        JPanel grid9 = new JPanel();
        grid9.setLayout(new GridLayout(3, 3));
        for (int i = 6; i < 9; i++)
        {
            for (int j = 6; j < 9; j++)
            {
                grid9.add(buttons[i][j]);
                buttons[i][j].addActionListener(this);
            }
        }
        JPanel grid = new JPanel();
        grid.setLayout(new GridLayout(3, 3, 8, 8));
        grid.add(grid1);
        grid.add(grid2);
        grid.add(grid3);
        grid.add(grid4);
        grid.add(grid5);
        grid.add(grid6);
        grid.add(grid7);
        grid.add(grid8);
        grid.add(grid9);
        
        
// Container erstellen und alles auf den Container packen
        Container c = fenster.getContentPane();
        c.setLayout(new BorderLayout(5, 5));
        c.add(grid, BorderLayout.CENTER);
        c.add(menuRechts, BorderLayout.EAST);
        c.add(menuOben, BorderLayout.NORTH);

// Alles packen und fertigstellen
        // Beim schliessen des Fensters -> Programm beenden
        fenster.setSize(400, 400);
        fenster.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        fenster.pack();
        fenster.setVisible(true);
    }
    
    public void actionPerformed(final ActionEvent e)
    {
        new Thread(new Runnable()
                { 
                    public void run() 
                    { 
                        for (int i = 0; i < cellHolder.length; i++)
                        {
                            for (int j = 0; j < cellHolder.length; j++)
                            {
                                if(e.getActionCommand().equals(""+i+j))
                                { 
                                    if (cellHolder[i][j].isLocked() != true)
                                    {
                                        if (cellHolder[i][j].getValue() >= cellHolder.length)
                                        {
                                            cellHolder[i][j].setValue(-1);
                                        }
                                        cellHolder[i][j].setValue(cellHolder[i][j].getValue()+1);
                                        System.out.println("GridEvent: increment cell["+i+"]["+j+"] to new value of " + cellHolder[i][j].getValue());
                                        buttons[i][j].setText(""+ cellHolder[i][j].getValue());
                                        buttons[i][j].setForeground(Color.MAGENTA);
                                    }
                                }
                            }
                        }
                        
                    } 
                }).start();
    }    

}

// OK 1. Grundwindow
// OK 2. Layout erstellen
// OK 3. Button erstellen (cellHolder.lenght())
// 4. machen, dass pro klick der wert um eins erhöht wird.
// 5. bei jedem klick autom. Value speichern , Line row und region kontrollieren.
```


```
package game;

/** The Logic Class treats (behandelt/bearbeitet) all logical problems.


 * We need this for checking the Values of the Cells in the Line, the Row and the Region.


 * When a check failed it returns a false, else it return true for each Method of the Class.

  
 * @param cellHolder[][] All Cellobjects on the Table
 * @param y the y-coordinate on the Table (in cellHolder[][y])
 * @param x the x-coordinate on the Table (in cellHolder[x][] */
public class Logic
{
    private Cell cellHolder[][];
    private int y;
    private int x;
    private int counter = 0;
    
    /**Constructor 


     * @param cellHolder[][] All Cellobjects on the Table
     * @param y the y-coordinate on the Table (in cellHolder[][y])
     * @param x the x-coordinate on the Table (in cellHolder[x][] */
    public Logic(Cell cellHolder[][], int y, int x)
    {
        this.cellHolder = cellHolder;
        this.y = y;
        this.x = x;
    }
    
    /** This Method checks all values in the same Line as the Cell is.
     *  If tere is a equal value in another Cell in this Line it returns
     *  false, else it returns true.
     *  
     *  @return boolean(true) there is no other Cell with the same value as the Cell we are checking. 
     *  @return boolean(false) there is a Cell with the same value as the Cell we are checking  */
    public boolean checkLine()
    {
        for (int i = x+1; i < cellHolder.length; i++)
        {
            if (this.cellHolder[y][x].getValue() == this.cellHolder[y][i].getValue())
            {
                System.out.println("Line   checked for cell["+y+"]"+"["+x+"]"+", Line   has errors : ");
                return false;
            }
        }
        for (int j = x-1; j > 0; j--)
        {
            if (this.cellHolder[y][x] == this.cellHolder[y][j])
            {
                System.out.println("Line   checked for cell["+y+"]"+"["+x+"]"+", Line   has errors : ");
                return false;
            }
        }
        System.out.println("Line   checked for cell["+y+"]"+"["+x+"]"+", Line   has no error  : ");
        return true;
    }
    
    /** This Method checks all values in the same Row as the Cell is.
     *  If tere is a equal value in another Cell in this Row it returns
     *  false, else it returns true.
     *  
     *  @return boolean(true) there is no other Cell with the same value as the Cell we are checking. 
     *  @return boolean(false) there is a Cell with the same value as the Cell we are checking  */
    public boolean checkRow()
    {
        for (int i = y+1; i < cellHolder.length; i++)
        {
            if (this.cellHolder[y][x].getValue() == this.cellHolder[i][x].getValue())
            {
                System.out.println("Row    checked for cell["+y+"]"+"["+x+"]"+", Row    has errors : ");
                return false;
            }
        }
        for (int j = y-1; j > -1 ; j--)
        {
            if (this.cellHolder[y][x].getValue() == this.cellHolder[j][x].getValue())
            {
                System.out.println("Row    checked for cell["+y+"]"+"["+x+"]"+", Row    has errors : ");
                return false;
            }
        }
        System.out.println("Row    checked for cell["+y+"]"+"["+x+"]"+", Row    has no error  : ");
        return true;
    }
   
    /** This Method checks all fields in the Region (with dimension 9x9) of their value equality. 


     *  If there is no other Cell in the Region with the same Value it returns true 


     *  but if there is a Cell with the same value, it will return false. 


     *  


     *   @return boolean(true) there is no Cell in this Region with the same Value
     *   @return boolean(false) there is a Cell in this Region with the same Value */
    public boolean checkRegion()
    {
        // !!! while x is line and y is row !!!
        
        if (this.y == 0 | this.y == 1 | this.y == 2 && this.x == 0 | this.x == 1 | this.x == 2)
        {
            int counter = 0;
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (this.cellHolder[y][x].getValue() == this.cellHolder[i][j].getValue())
                    {
                        counter++;
                    }
                }
            }
            if (counter > 1)
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has errors    : ");
                return false;
            }
            else
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has no error  : ");
                return true;
            }
        }
        if (y == 3 | y == 4 | y == 5 && x == 0 | x == 1 | x == 2)
        {
            int counter = 0;
            for (int i = 3; i < 6; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (this.cellHolder[y][x].getValue() == this.cellHolder[i][j].getValue())
                    {
                        counter++;
                    }
                }
            }
            if (counter > 1)
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has errors    : ");
                return false;
            }
            else
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has no error  : ");
                return true;
            }
        }
        if (y == 6 | y == 7 | y == 8 && x == 0 | x == 1 | x == 2)
        {
            int counter = 0;
            for (int i = 6; i < 9; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (this.cellHolder[y][x].getValue() == this.cellHolder[i][j].getValue())
                    {
                        counter++;
                    }
                }
            }
            if (counter > 1)
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has errors    : ");
                return false;
            }
            else
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has no error  : ");
                return true;
            }
        }
        if (y == 0 | y == 1 | y == 2 && x == 3 | x == 4 | x == 5)
        {
            int counter = 0;
            for (int i = 0; i < 3; i++)
            {
                for (int j = 3; j < 6; j++)
                {
                    if (this.cellHolder[y][x].getValue() == this.cellHolder[i][j].getValue())
                    {
                        counter++;
                    }
                }
            }
            if (counter > 1)
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has errors    : ");
                return false;
            }
            else
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has no error  : ");
                return true;
            }
        }
        if (y == 3 | y == 4 | y == 5 && x == 3 | x == 4 | x == 5)
        {
            int counter = 0;
            for (int i = 3; i < 6; i++)
            {
                for (int j = 3; j < 6; j++)
                {
                    if (this.cellHolder[y][x].getValue() == this.cellHolder[i][j].getValue())
                    {
                        counter++;
                    }
                }
            }
            if (counter > 1)
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has errors    : ");
                return false;
            }
            else
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has no error  : ");
                return true;
            }
        }
        if (y == 6 | y == 7 | y == 8 && x == 3 | x == 4 | x == 5)
        {
            int counter = 0;
            for (int i = 6; i < 9; i++)
            {
                for (int j = 3; j < 6; j++)
                {
                    if (this.cellHolder[y][x].getValue() == this.cellHolder[i][j].getValue())
                    {
                        counter++;
                    }
                }
            }
            if (counter > 1)
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has errors    : ");
                return false;
            }
            else
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has no error  : ");
                return true;
            }
        }
        if (y == 0 | y == 1 | y == 2 && x == 6 | x == 7 | x == 8)
        {
            int counter = 0;
            for (int i = 0; i < 3; i++)
            {
                for (int j = 6; j < 9; j++)
                {
                    if (this.cellHolder[y][x].getValue() == this.cellHolder[i][j].getValue())
                    {
                        counter++;
                    }
                }
            }
            if (counter > 1)
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has errors    : ");
                return false;
            }
            else
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has no error  : ");
                return true;
            }
        }
        if (y == 3 | y == 4 | y == 5 && x == 6 | x == 7 | x == 8)
        {
            int counter = 0;
            for (int i = 3; i < 6; i++)
            {
                for (int j = 6; j < 9; j++)
                {
                    if (this.cellHolder[y][x].getValue() == this.cellHolder[i][j].getValue())
                    {
                        counter++;
                    }
                }
            }
            if (counter > 1)
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has errors    : ");
                return false;
            }
            else
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has no error  : ");
                return true;
            }
        }
        if (y == 6 | y == 7 | y == 8 && x == 6 | x == 7 | x == 8)
        {
            int counter = 0;
            for (int i = 6; i < 9; i++)
            {
                for (int j = 6; j < 9; j++)
                {
                    if (this.cellHolder[y][x].getValue() == this.cellHolder[i][j].getValue())
                    {
                        counter++;
                    }
                }
            }
            if (counter > 1)
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has errors    : ");
                return false;
            }
            else
            {
                System.out.println("Region checked for cell["+y+"]"+"["+x+"]"+", Region has no error  : ");
                return true;
            }
        }
        return true;
    }   
    
    public void Solver(Cell cellHolder[][], int i, int j)
    {
        if (cellHolder[i][j].isLocked() != true)
        {
            cellHolder[i][j].setValue(cellHolder[i][j].getValue() + 1);
            if (checkLine() == false || checkRow() == false || checkRegion() == false)
            {
                if (cellHolder[i][j].getValue() > 9)
                {
                    cellHolder[i][j].setValue(0);
                }
                System.out.println("Neuer Solver wird gestartet.");
                Solver(cellHolder, i, j);
            }
//            System.out.println("Solver für ["+i+"]["+j+"] abgeschlossen.");
            return;
        }          
    }
    
    public boolean Solver2()
    {
     if (checkRegion() == true && checkLine() && checkRow())
     {
      return true;
     }
     else 
     {
      return false;
     }
    }
}
```

[/code]


----------



## Leroy42 (28. Jul 2006)

:shock: 

Bevor du einen rekursiven Solver wagst und sich jemand in deinen Code reintraut,
würde ich diesen erst mal entkrampfen.

200 deiner 340 Zeilen kannst du mit Sicherheit kürzen; dann wird's auch verständlicher.


BTW: Bist du dir sicher, daß du bei Ausdrücken wie


```
if (this.y == 0 | this.y == 1 | this.y == 2 && this.x == 0 | this.x == 1 | this.x == 2)
```

wirklich keine Klammern brauchst?


----------



## merlä (28. Jul 2006)

Ich habe noch vergessen zu sagen, dass nur die Zellen (Cell) überprüft werden sollen, die nicht "gelockt" sind.



> cellHolder_[j].isLocked() == false _


----------



## Leroy42 (28. Jul 2006)

Ich will dich ja nicht entmutigen, aber aus genau diesem Grund
möchte ich dich darauf vorbereiten, daß sich wohl kaum jemand
durch diesen Code durcharbeiten und dann ad hoc einen Solver(ansatz)
aus den Ärmeln schütteln wird.


----------



## muckelzwerg (28. Jul 2006)

Wie genau funzt denn ein "rekursiver Solver" ?

Anregung :
1) Funktion bauen, die mit den Logic Funktionen ein Brett komplett
testet.

2) Klasse "Step" bauen :
enthält eine Liste für weitere Step Objekte.
Attribut "Parent" (Step)
Attribut "Position" (Cell) (gibt das Feld an)
Attribut "Value" (int) (Wert des Feldes)
Attribut "Valid" (boolean)
Funktion "addStep(Step)" (fügt in die Liste ein)
+ getter und setter gesocks und anderer kleinkram,
der evtl nötig wird.

3) Feld und Wert Menge :
Stellt alle möglichen Züge dar.
Getter und Setter um einen Zug (Feld und Wert) auf "used" oder "unused" zusetzen.
Getter für einen Container mit allen noch ungenutzten Zügen.

4) Zufallsfunktion :
ermittelt ein zufälliges Feld aus der Menge der verfügbaren Felder,
und einen zufälligen Wert aus der Menge der ungenutzten Werte.
Die Menge wird der Funktion z.B. in einem 3D Array übergeben,
oder einer Liste, um die Suche einfacher zu machen.


5) Feld nehmen und vorne anfangen :

```
Step RootStep = new Step();
boolean invalid = true;
while(invalid){
Step erzeugen, mit "zufälligem Feld" und "zufälligem Wert";
invalid = Step validieren;
}
// erster valider schritt ermittelt

Feld aktualisieren;

Weitere Steps erzeugen, und an den jeweils
letzten Step anfügen, wenn sie valide sind.
Lassen sich aus der Menge der restlichen Züge keine Validen mehr
bilden, wird der ganze Step auf "broken" gesetzt.
"stepBack()" zum parent des jetzt kautten Steps,
und den nächsten validen Step suchen und anfügen.
Die "broken" Steps dienen dazu, die Restzüge weiter einzuschränken.
Alternativ kann man auch sodurch die Restzüge durchgehen,
dass man sich die dead ends nicht merken muss.

Zwischendurch immer mal checken ob das Brett voll ist ;)
(dann wenn kein valider Zug mehr möglich ist, oder einfach mitzählen)
```

Das wäre mal so spontan Backtracking aus dem Ärmel.
So wie ich das denke, sollte es gehen. Fehler liegen dann auschließlich an der unsauberen Beschreibung 

Alternative :
Eleganter und evlt. performanter;
Alle verfügbaren Züge in ein 3D Array packen, und Schritt für Schritt
verknüpfen.DeadEnds werden dann durch die Verbindungen gekennzeichnet (dead Link) oder über einen schlauen Algorithmus übergangen.
Aber das ist alles schon Sudoku-Forschung. 
Und die macht man nunmal selbst, oder man lässt es ganz.

  --  --  muckelzwerg


----------



## merlä (28. Jul 2006)

Hallo Leroy42,
du hast völlig recht, aber ich habe keine einfachere Lösung für das Logic.checkRegion Problem finden können. Vielleicht bin ich das ganze falsch angegangen aber es funktioniert, und das ist für als Anfänger das Wichtigste. 

Natürlich ist es einwenig Krass wenn ich 600 Zeilen poste und dann nach einem Solver frage, aber ich kann die Frage fast nicht anderst stellen. Oder?


----------



## merlä (28. Jul 2006)

Hallo muckelzwerg,

deine Beschreibungen sind zwar sehr ausfühlich, jedoch einwenig zu komplex für mich. Ich verstehe erhlich gesagt nur Bahnhof.

Sei mir bitte nicht böse, aber ich bin hald ein Anfänger. 

Es scheint mir, als sei diese rekursive Sache einwenig kompliziert.
Kann man es auch anders (einfacher) lösen?


----------



## muckelzwerg (30. Jul 2006)

Das ist schon so ziemlich die simpelste Methode.
Die Grundidee davon ist nämlich :
"Fülle das Feld solange mit zufälligen Werten, bis Du die richtige Lösung hast."
Dabei ist halt zu beachten, dass man sich falsche Wege merkt, um dann andere zu gehen.
Einfachstes Backtracking für Sudoku ist, immer eine neue Zufallszahl aufs Brett setzen,
bis kein Zug mehr möglich ist.
Ist das Brett voll, hat man gelöst, ist es nicht voll, hat man mindestens einen falschen Zug gemacht.
Also macht man den letzten Zug rückgängig und nimmt einen anderen.
Hat man alle möglichen Züge für das letzte Feld probiert, und es gab keinen richtigen darunter, muss der Fehler schon vorher passiert sein.
Also macht man den Zug davor rückgängig und versucht andere Züge.
Das muss man dann nur noch einigermaßen schick verpacken.

  --  --  muckelzwerg


----------



## Gast (31. Jul 2006)

Ein Beispiel für einen Solver in Java findet sich auch hier:
http://www.javaspecialists.co.za/archive/newsletter.do?issue=128&locale=en_US


----------



## KSG9|sebastian (31. Jul 2006)

> /** In this Class we handel all graphical Process and able the player to play.
> *  In every process we do, we */


 :bahnhof:


----------

