|
| View previous topic :: View next topic |
| Author |
Message |
| Auri84
| | Joined: 02 May 2006 | | Posts: 1 | | : | |
Items |
|
 Posted: Tue May 02, 2006 2:51 pm Post subject: Solver cant solve middle sudokus |
 |
|
Hi i have written a Sudoku Solver in Java. Comment are german, sry but my english isnt well and it is my first big java programm.
i have test it with some sudokus an i cant solve heavy und middle sudokus. plz help. what rule i have to implement that it works with middle sudokus.
| Quote: | package Sudoku;
import java.util.*;
import java.lang.Object;
class Sudoku {
/**
* @param feld ist die Klassenvariable
*/
public static int feld[][];
static int unsolved[][];
/**
* Methode die das Integer Feld in ein String Feld umwandelt
* Welches für die Methode JTable erforderlich ist
* @param feld 2 Dimensionales Feld, welche die Sudokuwerte beinhaltet
* @return
*/
public Sudoku(int[][]arg){
feld = arg;
unsolved = copyfeld(arg);
}
public String[][] toStringArray() {
String[][] feldString = new String[9][9];
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++){
String s= "";
s += ""+feld[i][j];
feldString[i][j] = s;
}
return feldString;
}
/**
* Ist eine Methode die als Bedingung genutz wird. M.h. der
* Methode wird festgestellt wann es keine leeren Stellen mehr gibt
* und durch diese Methode terminiert dann auch der Algorithmus
*
* @param feld 2 Dimensionales Feld, welche die Sudokuwerte beinhaltet
* @return
*/
private boolean feldKomplett() {
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (feld[i][j] == 0)
return false;
return true;
}
/**
* In dieser Methode werden Hilfsfelder erstellt in denen sich dann die
* möglichen lösungen für eine Zelle des Sudokus befinden
*
* es wird geprüft ob die zahl in der spalte, reihe oder im black schon vorhanden is
* wenn ja dann wird diese aus dem Hilffeld gelöscht
*
* das Hilfsfeld hat zu anfang alle zahlen von 1 bis 9
*
* und im idealfall nach dem durchlauf der methode für diese eine stelle nur noch einen wert
*
* @param feld 2 Dimensionales Feld, welche die Sudokuwerte beinhaltet
* @return
*/
private Vector[][] auswertenfeld() {
Vector[][] ergebnis = new Vector[9][9];
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (feld[i][j] == 0) {
ergebnis[i][j] = new Vector();
for (int k = 1; k <= 9; k++)
ergebnis[i][j].add(new Integer(k));
}
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (feld[i][j] == 0) {
// nach bekannten Zahlen sehen in der reihe
for (int k = 0; k < 9; k++)
if (feld[i][k] != 0)
ergebnis[i][j].remove(new Integer(feld[i][k]));
// nach bekannten Zahlen sehen in der spalte
for (int k = 0; k < 9; k++)
if (feld[k][j] != 0)
ergebnis[i][j].remove(new Integer(feld[k][j]));
// nach bekannten Zahlen sehen im block3x3
for (int k = 3*(i/3); k < 3*(i/3)+3; k++)
for (int l = 3*(j/3); l < 3*(j/3)+3; l++)
if (feld[k][l] != 0)
ergebnis[i][j].remove(new Integer(feld[k][l]));
}
return ergebnis;
}
private int[][] fuellefeld(Vector[][] werte) {
int[][] ergebnis = copyfeld(feld);
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (feld[i][j] == 0) {
if (werte[i][j].size() == 1) {
ergebnis[i][j] = ((Integer)werte[i][j].get(0)).intValue();
continue;
}
for (int n = 0; n < werte[i][j].size(); n++) {
int num = ((Integer)werte[i][j].get(n)).intValue();
// schaut nach einzel werten in der reihe
boolean einfuegen = true;
for (int k = 0; k < 9; k++)
if ((feld[i][k] == 0) && (k != j) &&
werte[i][k].contains(new Integer(num)))
{
einfuegen = false;
break;
}
if (einfuegen) {
ergebnis[i][j] = num;
break;
}
// schaut nach einzel werten in der spalte
einfuegen = true;
for (int k = 0; k < 9; k++)
if ((feld[k][j] == 0) && (k != i) &&
werte[k][j].contains(new Integer(num)))
{
einfuegen = false;
break;
}
if (einfuegen) {
ergebnis[i][j] = num;
break;
}
// schaut nach bekannten werten im block
einfuegen = true;
boolean continuation = true;
for (int k = 3*(i/3); k < 3*(i/3)+3; k++) {
if (!continuation)
break;
for (int l = 3*(j/3); l < 3*(j/3)+3; l++)
if ((feld[k][l] == 0) &&
!((k == i) && (l == j)) &&
werte[k][l].contains(new Integer(num)))
{
continuation = false;
einfuegen = false;
break;
}
}
if (einfuegen) {
ergebnis[i][j] = num;
break;
}
}
}
return ergebnis;
}
/**
* Methode im das feld/sudoku auszugeben
*
*
* @param feld
*/
public void printfeld() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
if (feld[i][j] != 0)
System.out.print(feld[i][j] + " ");
else
System.out.print(". ");
System.out.println();
}
System.out.println();
}
/**
* Methode um 2 Felder b1 und b2 zu vergleichen
*
* @param b1
* @param feld
* @return
*/
public boolean feldistGleich(int[][] b1) {
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (b1[i][j] != feld[i][j])
return false;
return true;
}
/**
* Methode um ein Feld zu kopieren
*
* @param b
* @return
*/
public int[][] copyfeld(int[][] b) {
int[][] ergebnis = new int[9][9];
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
ergebnis[i][j] = b[i][j];
return ergebnis;
}
/**
* Methode die das Sudoku auflöst
*
* @return
*/
public int[][] loesen(){
Vector[][] werte;
int[][] altesFeld;
//printfeld(feld);
while (!feldKomplett()) {
werte = auswertenfeld();
altesFeld = copyfeld(feld);
feld = fuellefeld(werte);
if (feldistGleich(altesFeld)) {
System.err.println("Das Sudoku ist nicht lösbar.");
System.exit(1);
}
//printfeld(feld);
}return feld;
}
public int[][] getfeld() {
return feld;
}
public void setfeld(int[][] feld) {
this.feld = feld;
}
}
|
|
|
| Back to top |
|
 |
| lawrence
| | Joined: 18 Apr 2006 | | Posts: 3 | | : | |
Items |
|
| Posted: Tue May 09, 2006 3:05 pm Post subject: |
|
|
Hi Auri84,
Can you give me some unsolved sudokus that your program cannot solve? I'd like to test my solver program.
Anyway, have you implemented Dancing Links algorithm? My first solver mimics human way in solving and got stucked (i.e. took a way long time to solve) some sudokus, but when I switch to dancing links, it churns sudokus in under 1 or 2 seconds, and I'm only using VBA.
regards,
eka |
|
| Back to top |
|
|
| Volker1953_Hamburg
| | Joined: 23 May 2006 | | Posts: 4 | | : | |
Items |
|
| Posted: Tue May 23, 2006 11:11 pm Post subject: |
|
|
Ich bin kein JAVA-Programmierer und kann das Programm bzw. die "Methoden" daher nur ungefähr verfolgen.
Mir scheint, daß dort lediglich das Verfahren: "Absolute Singles" bzw. "Naked Singles" angewandt wird.
Es sollte mindestens das Verfahren: "Hidden Singles" zusätzlich angewandt werden. HiddenSingles sind solche, die je in einer BOX, ROW oder COLUMN nur einmal gesetzt werden können.
Die Methode: "Feldkomplett" sollte ggf. nicht (nur) einen booleschen Wert liefern, sondern die konkrete Zahl der Leerstellen. Auch mit ganzen Zahlen können meist problemlos Bedingungen abgefragt werden. In den meisten Systemen ist
FALSE == 0 und
TRUE jeder Wert ungleich 0.
Es könnte damit eine Methode: "Findfirstmoves" nach folgendem Muster (Pseudo-Code!) geschrieben werden:
Methode Findfirstmoves
{ FindNakedSingles
Feldkomplett(alt)
SOLANGE ( Feldkomplett(alt) ungleich 0 ?)
FindHiddensingles
SOLANGE ( Feldkomplett(alt) > Feldkomplett(neu) ? )
FindNakedSingles
-> zum SCHLEIFENENDE
SCHLEIFENENDE
}
Nach den FindFirstMoves, (die die Felder nicht nur finden, sondern auch füllen), muß sich ggf. das Verfahren: "Trial and Error" anschließen.
p.s.:
1. Evtl. ist es insbesondere bei den Schleifen einfacher und schneller, das Sudoku-Feld nicht als 9 mal 9 Felder ( i von 1 bis 9; j von 1 bis 9 ), sondern als 81 Felder zu beschreiben ( i von 0 bis 80 bzw. von 1 bis 81 ).
2. Was man BERECHNEN kann, sollte man nicht als BEDINGUNG formulieren, hier z.B. in feldkomplett:
Nicht:
{ ...
if (feld[i][j] == 0)
return false;
return true;
}
(Mangels JAVA-Kenntniossen bei mir:
Was wird da eigentlich als "letzter" Wert geliefert?
Ist sichergestellt, daß FALSE geliefert wird, wenn nur ein einziges Feld in der Mitte frei ist?)
Sondern in etwa:
{ ...
return (feld[i][j] == 0);
return true;
}
bzw. sogar noch kürzer:
{ ...
return (feld[i][j]);
}
Ich weiß allerdings leider nicht, ob eine derart "schlanke" Lösung in JAVE möglich ist.
Ich selbst benutze Forth (WinForth32). |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
