Hm, es läuft bei mir immer noch nicht. Selbst wenn ich das rausnehme, werden Errors angezeigt? Mir noch nicht ganz klar, warum er es nicht macht.
Dafür hab ich auch was neues. Auf deine Zeit komme ich zwar nicht, was mir ein Rätsel ist, weil ich immerhin einen i7 drin habe. Aber ich komme jetzt auf 1.4 Sekunden. Und zwar wird jetzt nur noch der Zug gespeichert. Dazu braucht es nur drei Werte, die gespeichert werden müssen: Die Position, also x und y und die Richtung. Alles weitere ergibt sich ja aus der Regel. Beim Zeichnen später dann wird einmal die Grundstellung gezeichnet und dann nur noch die einzelnen Züge.
Bei deinem Code muss ich noch ein wenig nachdenken. So richtig verstehe ich ihn noch nicht. Mag an den englischen Bezeichnern liegen Aber da komme ich noch durch, wenn ich ihn erst mal zum laufen bekomme.
Code:
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import javax.swing.JFrame;
public class Solit extends JFrame
{
/**
*
*/
private static final long serialVersionUID = -4382011225551225106L;
final static int OBEN=1;
final static int UNTEN=2;
final static int LINKS=3;
final static int RECHTS=4;
static short [][][] loesung= new short[1][7][7];
static Zug [] zug=new Zug[32];
static int currentStep=0;
static boolean zeichnen=false;
static boolean zugzeichnen=false;
public Solit()
{
super();
setDefaultCloseOperation(EXIT_ON_CLOSE);
for (int i=0;i<32;i++)
{
zug[i]= new Zug();
}
}
public void paint(Graphics gs)
{ // @Override ermöglicht dem Compiler die Kontrolle
Graphics2D g=(Graphics2D)gs;
int x,y;
short inhalt;
if(zeichnen)
{
g.setColor(Color.lightGray);
g.fillRect(0, 0, getWidth(), getHeight());
{
for (y=0;y<7;y++)
{
for (x=0;x<7;x++)
{
inhalt=loesung[currentStep-1][x][y];
if (inhalt == 0)
{
g.setColor(Color.WHITE);
g.fillOval(x*100+150, y*100+150, 30, 30);
g.setColor(Color.BLACK);
g.drawOval(x*100+150, y*100+150, 28, 28);
}
else if(inhalt == 1)
{
g.setColor(Color.GREEN);
g.fillOval(x*100+150, y*100+150, 30, 30);
}
}
}
}
}
if(zugzeichnen)
{
switch (zug[currentStep-1].richtung)
{
case OBEN:
g.setColor(Color.WHITE);
g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y-1)*100+150, 30, 30);
g.setColor(Color.BLACK);
g.setColor(Color.lightGray);
g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.drawOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y-1)*100+150, 30, 30);
g.setColor(Color.GREEN);
g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y-2)*100+150, 30, 30);
break;
case UNTEN:
g.setColor(Color.WHITE);
g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y+1)*100+150, 30, 30);
g.setColor(Color.BLACK);
g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.drawOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y+1)*100+150, 30, 30);
g.setColor(Color.GREEN);
g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y+2)*100+150, 30, 30);
break;
case LINKS:
g.setColor(Color.WHITE);
g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.fillOval((zug[currentStep-1].x-1)*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.setColor(Color.BLACK);
g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.drawOval((zug[currentStep-1].x-1)*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.setColor(Color.GREEN);
g.fillOval((zug[currentStep-1].x-2)*100+150, zug[currentStep-1].y*100+150, 30, 30);
break;
case RECHTS:
g.setColor(Color.WHITE);
g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.fillOval((zug[currentStep-1].x+1)*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.setColor(Color.BLACK);
g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.drawOval((zug[currentStep-1].x+1)*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.setColor(Color.GREEN);
g.fillOval((zug[currentStep-1].x+2)*100+150, zug[currentStep-1].y*100+150, 30, 30);
break;
default:
}
}
}
static boolean oben(short A[][], short x, short y)
{
if(y>1 && A[x][y]==1 && A[x][y-1]==1 && A[x][y-2]==0) return true;
return false;
}
static boolean unten(short A[][], short x, short y)
{
if(y<5 && A[x][y]==1 && A[x][y+1]==1 && A[x][y+2]==0) return true;
return false;
}
static boolean links(short A[][], short x, short y)
{
if(x>1 && A[x][y]==1 && A[x-1][y]==1 && A[x-2][y]==0) return true;
return false;
}
static boolean rechts(short A[][], short x, short y)
{
if(x<5 && A[x][y]==1 && A[x+1][y]==1 && A[x+2][y]==0) return true;
return false;
}
static void speichern(short A[][], int i)
{
for(int y=0;y<7;y++)
{
for(int x=0;x<7;x++)
{
loesung[i][x][y]=A[x][y];
}
}
}
static void zug_speichern(int x, int y, int richtung, int zug)
{
Solit.zug[zug].x=x;
Solit.zug[zug].y=y;
Solit.zug[zug].richtung=richtung;
}
static boolean soli (short A[][], int i)
{
boolean inhalt;
if (i<31)
{
i++;
for (short y=0;y<7;y++)
{
for (short x=0;x<7;x++)
{
if(oben(A,x,y))
{
A[x][y]=0; A[x][y-1]=0; A[x][y-2]=1;
inhalt=soli(A,i);
if(inhalt) {
zug_speichern(x,y,OBEN,i);
return true;
}
else {A[x][y]=1; A[x][y-1]=1; A[x][y-2]=0;}
}
if(unten(A,x,y))
{
A[x][y]=0; A[x][y+1]=0; A[x][y+2]=1;
inhalt=soli(A,i);
if(inhalt) {
zug_speichern(x,y,UNTEN,i);
return true;
}
else {A[x][y]=1; A[x][y+1]=1; A[x][y+2]=0;}
}
if(links(A,x,y))
{
A[x][y]=0; A[x-1][y]=0; A[x-2][y]=1;
inhalt=soli(A,i);
if(inhalt) {
zug_speichern(x,y,LINKS,i);
return true;
}
else {A[x][y]=1; A[x-1][y]=1; A[x-2][y]=0;}
}
if(rechts(A,x,y))
{
A[x][y]=0; A[x+1][y]=0; A[x+2][y]=1;
inhalt=soli(A,i);
if(inhalt) {
zug_speichern(x,y,RECHTS,i);
return true;
}
else {A[x][y]=1; A[x+1][y]=1; A[x+2][y]=0;}
}
}
}
i--;
return false;
}
else
{
return true;
}
}
public static void main(String[] args)
{
Solit f= new Solit();
f.setSize(1000, 1000);
f.setVisible(true);
short [][] A = new short [][]{
{ 9,9,1,1,1,9,9 },
{ 9,9,1,1,1,9,9 },
{ 1,1,1,1,1,1,1 },
{ 1,1,1,0,1,1,1 },
{ 1,1,1,1,1,1,1 },
{ 9,9,1,1,1,9,9 },
{ 9,9,1,1,1,9,9 }
};
speichern(A,0);
Zeitmesser.startZeitmessung(1);
soli(A,0);
System.out.println(Zeitmesser.getZeitmessung(1)/1000.0);
Zeitmesser.stopZeitmessung(1);
zeichnen=true;
currentStep++;
f.repaint();
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
zeichnen=false;
zugzeichnen=true;
for (int i=1;i<32;i++)
{
currentStep++;
f.repaint();
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
class Zug
{
int x,y;
int richtung;
public Zug()
{
x=0;
y=0;
richtung=0;
}
}
}
EDIT:
Hab deine Idee mal übernommen, statt immer sofort zu speichern, nur einmal auf dem Rückweg zu speichern. Unglaublich. Obwohl es nur noch drei Werte waren, die gespeichert werden, ist er von 1.4etwas auf 1.1 etwas schneller geworden. dreizehntel Sekunden. Der Hammer. Natürlich noch sehr weit weg von 72 milisekunden. Aber wenn Du nur noch einen Jumpaufruf brauchst, leuchtet das schon irgendwie ein. Nur hab ich noch nicht genau verstanden, wie Du das gemacht hast.
EDIT2:
Ich glaube, deine Zeitmessung stimmt nicht. Habe das auch mal mit 100 mal gemacht und hatte auf einmal die gleiche Zeit, war sogar noch etwas schneller, als bei dir. Das kam mir sehr spanisch vor.
Das Problem ist, dass das ursprüngliche Array nicht mehr passt. Man übergibt zwar das Array, aber es wird mit Aufruf trotzdem alle Änderungen haben, die die Methode ermittelt hat. Am Ende ist also im Array A nur noch ein Stein vorhanden. Und dieses Array mit dem einen Stein wird dann über die Zeit Ermittlungsschleife gejagt. Da es da aber keinen Zug mehr gibt, wird Soli sofort beendet. Weiß nicht mehr genau, wie das heißt, wenn ein Array übergeben wird. Da wird quasi nicht ein neues Array aufgemacht, sondern es wird nur die Adresse übergeben. Ein Point war das nicht, das war noch ein anderer Begriff. EDIT3: Referenzen war das Wort, welches ich suchte. Ich habe das jetzt jedenfalls mal probiert, in dem ich jedes Mal das Array wieder neu erstellt habe auf die Ausgangsstellung und dann passt es auch. 117,455 Sekunden /100 ergibt 1,17455 Sekunden pro Versuch.
EDIT3:
Was da noch alles möglich ist...
Habe jetzt in der Methode soli bevor es zum Prüfen geht, noch eine Vorabprüfung eingebaut. Eigentlich braucht man ja nur prüfen, wenn x,y überhaupt ein Stein ist. Erst dann macht es Sinn. Dazu wird einfach noch eine If-Abfrage mit if (A[x][y]==1) eingeführt.
Das hat die Zeit drastisch gesenkt. Jetzt komme ich auf 0.6 Sekunden. Also fast die Zeit zum Lösung halbiert. Wahnsinn.
Code:
static boolean soli (short A[][], int i)
{
boolean inhalt;
if (i<31)
{
i++;
for (short y=0;y<7;y++)
{
for (short x=0;x<7;x++)
{
if(A[x][y]==1)
{
if(oben(A,x,y))
{
A[x][y]=0; A[x][y-1]=0; A[x][y-2]=1;
inhalt=soli(A,i);
if(inhalt) {
zug_speichern(x,y,OBEN,i);
return true;
}
else {A[x][y]=1; A[x][y-1]=1; A[x][y-2]=0;}
}
if(unten(A,x,y))
{
A[x][y]=0; A[x][y+1]=0; A[x][y+2]=1;
inhalt=soli(A,i);
if(inhalt) {
zug_speichern(x,y,UNTEN,i);
return true;
}
else {A[x][y]=1; A[x][y+1]=1; A[x][y+2]=0;}
}
if(links(A,x,y))
{
A[x][y]=0; A[x-1][y]=0; A[x-2][y]=1;
inhalt=soli(A,i);
if(inhalt) {
zug_speichern(x,y,LINKS,i);
return true;
}
else {A[x][y]=1; A[x-1][y]=1; A[x-2][y]=0;}
}
if(rechts(A,x,y))
{
A[x][y]=0; A[x+1][y]=0; A[x+2][y]=1;
inhalt=soli(A,i);
if(inhalt) {
zug_speichern(x,y,RECHTS,i);
return true;
}
else {A[x][y]=1; A[x+1][y]=1; A[x+2][y]=0;}
}
}
}
}
i--;
return false;
}
else
{
return true;
}
}
Das ganze also jetzt:
Code:
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import javax.swing.JFrame;
public class Solit extends JFrame
{
/**
*
*/
private static final long serialVersionUID = -4382011225551225106L;
final static int OBEN=1;
final static int UNTEN=2;
final static int LINKS=3;
final static int RECHTS=4;
final static int STEIN=1;
static short [][][] loesung= new short[1][7][7];
static Zug [] zug=new Zug[32];
static int currentStep=0;
static boolean zeichnen=false;
static boolean zugzeichnen=false;
static long zaehler=0;
public Solit()
{
super();
setDefaultCloseOperation(EXIT_ON_CLOSE);
for (int i=0;i<32;i++)
{
zug[i]= new Zug();
}
}
public void paint(Graphics gs)
{ // @Override ermöglicht dem Compiler die Kontrolle
Graphics2D g=(Graphics2D)gs;
int x,y;
short inhalt;
if(zeichnen)
{
g.setColor(Color.lightGray);
g.fillRect(0, 0, getWidth(), getHeight());
{
for (y=0;y<7;y++)
{
for (x=0;x<7;x++)
{
inhalt=loesung[currentStep-1][x][y];
if (inhalt == 0)
{
g.setColor(Color.WHITE);
g.fillOval(x*100+150, y*100+150, 30, 30);
g.setColor(Color.BLACK);
g.drawOval(x*100+150, y*100+150, 28, 28);
}
else if(inhalt == 1)
{
g.setColor(Color.GREEN);
g.fillOval(x*100+150, y*100+150, 30, 30);
}
}
}
}
}
if(zugzeichnen)
{
switch (zug[currentStep-1].richtung)
{
case OBEN:
g.setColor(Color.WHITE);
g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y-1)*100+150, 30, 30);
g.setColor(Color.BLACK);
g.setColor(Color.lightGray);
g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.drawOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y-1)*100+150, 30, 30);
g.setColor(Color.GREEN);
g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y-2)*100+150, 30, 30);
break;
case UNTEN:
g.setColor(Color.WHITE);
g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y+1)*100+150, 30, 30);
g.setColor(Color.BLACK);
g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.drawOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y+1)*100+150, 30, 30);
g.setColor(Color.GREEN);
g.fillOval(zug[currentStep-1].x*100+150, (zug[currentStep-1].y+2)*100+150, 30, 30);
break;
case LINKS:
g.setColor(Color.WHITE);
g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.fillOval((zug[currentStep-1].x-1)*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.setColor(Color.BLACK);
g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.drawOval((zug[currentStep-1].x-1)*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.setColor(Color.GREEN);
g.fillOval((zug[currentStep-1].x-2)*100+150, zug[currentStep-1].y*100+150, 30, 30);
break;
case RECHTS:
g.setColor(Color.WHITE);
g.fillOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.fillOval((zug[currentStep-1].x+1)*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.setColor(Color.BLACK);
g.drawOval(zug[currentStep-1].x*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.drawOval((zug[currentStep-1].x+1)*100+150, zug[currentStep-1].y*100+150, 30, 30);
g.setColor(Color.GREEN);
g.fillOval((zug[currentStep-1].x+2)*100+150, zug[currentStep-1].y*100+150, 30, 30);
break;
default:
}
}
}
static boolean oben(short A[][], short x, short y)
{
if(y>1 && A[x][y]==1 && A[x][y-1]==1 && A[x][y-2]==0) return true;
return false;
}
static boolean unten(short A[][], short x, short y)
{
if(y<5 && A[x][y]==1 && A[x][y+1]==1 && A[x][y+2]==0) return true;
return false;
}
static boolean links(short A[][], short x, short y)
{
if(x>1 && A[x][y]==1 && A[x-1][y]==1 && A[x-2][y]==0) return true;
return false;
}
static boolean rechts(short A[][], short x, short y)
{
if(x<5 && A[x][y]==1 && A[x+1][y]==1 && A[x+2][y]==0) return true;
return false;
}
static void speichern(short A[][], int i)
{
for(int y=0;y<7;y++)
{
for(int x=0;x<7;x++)
{
loesung[i][x][y]=A[x][y];
}
}
}
static void zug_speichern(int x, int y, int richtung, int zug)
{
Solit.zug[zug].x=x;
Solit.zug[zug].y=y;
Solit.zug[zug].richtung=richtung;
}
static boolean soli (short A[][], int i)
{
boolean inhalt;
zaehler++;
if (i<31)
{
i++;
for (short y=0;y<7;y++)
{
for (short x=0;x<7;x++)
{
if(A[x][y]==STEIN)
{
if(oben(A,x,y))
{
A[x][y]=0; A[x][y-1]=0; A[x][y-2]=1;
inhalt=soli(A,i);
if(inhalt) {
zug_speichern(x,y,OBEN,i);
return true;
}
else {A[x][y]=1; A[x][y-1]=1; A[x][y-2]=0;}
}
if(unten(A,x,y))
{
A[x][y]=0; A[x][y+1]=0; A[x][y+2]=1;
inhalt=soli(A,i);
if(inhalt) {
zug_speichern(x,y,UNTEN,i);
return true;
}
else {A[x][y]=1; A[x][y+1]=1; A[x][y+2]=0;}
}
if(links(A,x,y))
{
A[x][y]=0; A[x-1][y]=0; A[x-2][y]=1;
inhalt=soli(A,i);
if(inhalt) {
zug_speichern(x,y,LINKS,i);
return true;
}
else {A[x][y]=1; A[x-1][y]=1; A[x-2][y]=0;}
}
if(rechts(A,x,y))
{
A[x][y]=0; A[x+1][y]=0; A[x+2][y]=1;
inhalt=soli(A,i);
if(inhalt) {
zug_speichern(x,y,RECHTS,i);
return true;
}
else {A[x][y]=1; A[x+1][y]=1; A[x+2][y]=0;}
}
}
}
}
i--;
return false;
}
else
{
return true;
}
}
public static void main(String[] args)
{
Solit f= new Solit();
f.setSize(1000, 1000);
f.setVisible(true);
short [][] A = new short [][]{
{ 9,9,1,1,1,9,9 },
{ 9,9,1,1,1,9,9 },
{ 1,1,1,1,1,1,1 },
{ 1,1,1,0,1,1,1 },
{ 1,1,1,1,1,1,1 },
{ 9,9,1,1,1,9,9 },
{ 9,9,1,1,1,9,9 }
};
speichern(A,0);
Zeitmesser.startZeitmessung(1);
soli(A,0);
System.out.println(Zeitmesser.getZeitmessung(1)/1000.0);
Zeitmesser.stopZeitmessung(1);
System.out.println();
System.out.println(zaehler);
zeichnen=true;
currentStep++;
f.repaint();
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
zeichnen=false;
zugzeichnen=true;
for (int i=1;i<32;i++)
{
currentStep++;
f.repaint();
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
class Zug
{
int x,y;
int richtung;
public Zug()
{
x=0;
y=0;
richtung=0;
}
}
}