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:
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
[/code]
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
Code:
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.
Code:
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]
