C++ Rössel schachbrett problem
-
ja also ich bin noch totaler c++ neuling (in der schule angefangen mit c++)
und wir sind jetzt an einem gröberen problem angelangt-> das rössel program
für alle die s noch nicht kennen.
man soll ein pferd auf ein schachbrett legen und es soll dann alle felder einmal besuchen (und nicht mehr).soweit so gut hier ist mein programm, das nicht funktioniert, habs mir schon 2 stunden angeschaut und nix gefunden
hab mir gedacht vielleicht können ein paar profis von hier mit bisschen weiter helfen also hir mal mein programm :
aja c kanns complieren aber der scheint in ner endlos schleife zu hängen.
und das ganze sollen wir nur mit den hilfe von arrays (feldern),if, case, anweisungen machen, da wir ja sonst nix gelernt haben ^^#include<iostream.h> #include<conio.h> #include<fstream.h> #include<Math.h> #include<stdlib.h> void main(){ int Hilfsfeld [3][65]; int Schachbrett[8][8]; int Zugtyp=1,a=0,b=0,Reihe1=4,Reihe2=4,Flag=0; Schachbrett[Reihe1][Reihe2]=1; for (int i=0;i<8;i++){ // sämtliche Felder mit 0 initialisieren. for (int j=0;j<8;j++){ Schachbrett[i][j]=0; } } // for (int i=2;i<65;i++){ Zugtyp=1; Flag=0; switch(Zugtyp){ case 1: a=1;b=2;break; // Sprungmöglichkeiten eines pferdes (max 8 möglichkeiten) case 2: a=1;b=-2;break; case 3: a=-1;b=2;break; // dies ist der normal ablauf, falls keine sackgasse etc erfolgt case 4: a=-1;b=-2;break; case 5: b=1;a=2;break; case 6: b=-1;a=2;break; case 7: b=1;a=-2;break; case 8: b=-1;a=-2;break; // } while ((Schachbrett[Reihe1+a][Reihe2+b]!=0)||Reihe1+a>7||Reihe1+a<0||Reihe2+b>7||Reihe2+b<0){ // falls das pferd über den rand hinausspringen würde bzw. ein feld besuchen sollte das bereits schon mal besucht war Zugtyp++; while (Zugtyp>8){ Reihe1=Hilfsfeld[0][i-1]; Reihe2=Hilfsfeld[1][i-1]; Schachbrett[Reihe1][Reihe2]=0; Reihe1=Hilfsfeld[0][i-1]=0; Reihe2=Hilfsfeld[1][i-1]=0; Reihe1=Hilfsfeld[0][i-2]; Reihe2=Hilfsfeld[1][i-2]; Zugtyp=Hilfsfeld[2][i-2]; i--; Flag=1; Zugtyp++; } switch(Zugtyp){ // auswahl eines neuen sprungtypes case 1: a=1;b=2;break; case 2: a=1;b=-2;break; case 3: a=-1;b=2;break; case 4: a=-1;b=-2;break; case 5: b=1;a=2;break; case 6: b=-1;a=2;break; case 7: b=1;a=-2;break; case 8: b=-1;a=-2;break; // } } if (Flag ==1) Schachbrett[Reihe1+a][Reihe2+b]=i; if (Flag ==0) Schachbrett[Reihe1+a][Reihe2+b]=i; Hilfsfeld[0][i]=Reihe1+a; // buchführung : einschreibung der x,y koordinaten und sprungtypes Hilfsfeld[1][i]=Reihe2+b; Hilfsfeld[2][i]=Zugtyp; // } for (int i=1;i<65;i++){ cout<<Hilfsfeld[0][i]<<" "<<Hilfsfeld[1][i]<<" "<<Hilfsfeld[2][i]<<" "<<endl; } getch(); }
-
while (Zugtyp>8){ Reihe1=Hilfsfeld[0][i-1]; Reihe2=Hilfsfeld[1][i-1]; Schachbrett[Reihe1][Reihe2]=0; Reihe1=Hilfsfeld[0][i-1]=0; Reihe2=Hilfsfeld[1][i-1]=0; Reihe1=Hilfsfeld[0][i-2]; Reihe2=Hilfsfeld[1][i-2]; Zugtyp=Hilfsfeld[2][i-2]; i--; Flag=1; Zugtyp++; }Falls Zugtyp wirklich grösser als 8 ist, kommst du nicht mehr aus der Schleife raus.
Aber ich würde dir anraten das ganze Rekursiv zu programmieren, das ist wahrscheinlich einfacher.Edit: void main(), hattet ihr das so gelernt? Das sollte heissen int main(), ausserdem solltest du besser schreiben #include <iostream> anstatt <iostream.h>
Wenn du einfach alle möglichkeiten ausprobierst, kann es übrigens relativ lange dauern, bis die lösung auf einem 8x8 Feld errechnet wird, eine Verbesserungsmöglichkeit wäre, immer zuerst zu versuchen, in die Ecken zu springen. Dann geht es schneller.
-
wieso?
falls zugtyp grösser als 8 ist dann übernimmt zugtyp den wert eine runde davor (den ich ja in der buchführung geschrieben habe) und wird um eins erhöht, falls diese wieder grösser als acht ist übernimmt sie wieder den wert von zugtyp noch ne runde davor.bsp: zug 8 buchführung alles aufgezeichnet
zug 9 sackgasse, keine möglichkeiten ... zugtyp errreicht wert grösser als 8 und bekommt sämtliche werte von zug acht zurückgesetzt und probiert eine andere sprungmöcglichkeit aus .
ja wir machen es mit void main damit wir zum schluss kein return 0 schreiben müssen ^^.
-
Die Sackgasse ist wie lustig es bereits erwähnt hat
hier:while (Zugtyp>8){ Reihe1=Hilfsfeld[0][i-1]; Reihe2=Hilfsfeld[1][i-1]; Schachbrett[Reihe1][Reihe2]=0; Reihe1=Hilfsfeld[0][i-1]=0; Reihe2=Hilfsfeld[1][i-1]=0; Reihe1=Hilfsfeld[0][i-2]; Reihe2=Hilfsfeld[1][i-2]; Zugtyp=Hilfsfeld[2][i-2]; i--; Flag=1; Zugtyp++; }die schleife wird ausgeführt wenn zugtyp > 8 ist und das geht so lange weiter bis Zugtyp nicht mehr 8 ist. ABER Zugtype kann nie mehr unter 8 kommen weil du immer 1 dazu zählst....
-
sorry, mein Fehler, habe das Zugtyp=Hilfsfeld[2][i-2]; übersehen.
-
Ich denke der fehler liegt trotzdem in der while schleife..
edit: die position des springers wird nicht aktualisiert. Ich denke das ist der fehler :>while ((Schachbrett[Reihe1+a][Reihe2+b]!=0)||Reihe1+a>7||Reihe1+a<0||Reihe2+b>7||Reihe2+b<0)müsste imho heißen:
while (Reihe1+a>7||Reihe1+a<0||Reihe2+b>7||Reihe2+b<0 || (Schachbrett[Reihe1+a][Reihe2+b]!=0))dann
while (Zugtyp>8){ //kein zug möglich daher anderen zug beim vorgängerzug wählen (wenn möglich) Reihe1=Hilfsfeld[0][i-1]; //reihe1, reihe2 beschreibt denk ich mal die position des springers, richtig? oO. Reihe2=Hilfsfeld[1][i-1]; //-->position des springers vom letzten zug wird wieder genommen -->wofür? sollte eh die werte haben (wenn reihe1 und reihe 2 am ende der forschleife mal aktualisiert werden würden) Schachbrett[Reihe1][Reihe2]=0; //markierung auf dem schachbrett wird wieder entfernt -->logisch Reihe1=Hilfsfeld[0][i-1]=0; //überflüssig Reihe2=Hilfsfeld[1][i-1]=0; //überflüssig Reihe1=Hilfsfeld[0][i-2]; //springerposition vom vorletzten zug wird genommen (aktueller zug konnte nicht gefunden werden -> letzter zug ist falsch --> letzten zug löschen und vorletzte springerpositionnehmen) -> logisch Reihe2=Hilfsfeld[1][i-2]; // " Zugtyp=Hilfsfeld[2][i-2]; //letzten zugtyp merken und gleich eins weiter setzen um anderen zug zu ermöglichen -->logisch i--; Flag=1; //i eins zurücksetzen, da neuer letzter zug gefunden werden muss --> logisch .. Flag --> ?? Zugtyp++; }was soll eigentlich "flag" besagen? und hast du schonmal probiert, einfach mal nur 30 züge oder so berechnen zu lassen?
irgendwie fehlt auch ein "Reihe1+=a; Reihe2+=b;" nach jedem forschleifen durchlauf.. Ich glaub das ist der eigentliche fehler
-
lustig schrieb:
sorry, mein Fehler, habe das Zugtyp=Hilfsfeld[2][i-2]; übersehen.
Lol ich auch. Sorry
-
-
Hallo Leute,
zu dem Thema fällt mir ein, ich habe da letzten von einem Coder contest gelesen, wo genau dieses Problem gelöst werden sollte . Zwar haben die AFAIR in ASM programmiert(ging um schnellste Laufzeit und kleinstens Binary) , aber das Testprogramm, was die benutzt haben war in CPP soweit ich weiss.
Vielleicht ist es ja interessant für euch :
http://www.hugi.scene.org/compo/
also interessant finde ich das schon, wie kompakt man sowas in ASM lösen kann
:The Knight's Tour ;Hugi Compo 23 (www.hugi.de/compo) ;Coded by G3 (tgm80@mail.ru) ;fasm.exe entry.asm entry.com org 100h start: pop cx ;cx=0 push '$' std scasw ;di=di-2 L10: pusha scasw inc cx mov bl,8 L20: dec bx jz L30 add al,[bx+si+dxy-100h-1] test al,88h jnz L20 pusha cld aam 10h ;ah=al / 10h, al=al mod 10h stosw repnz scasw std L30: popa jz L20 cmp cl,0FFh-64 ;same as cmp cl,63 but zf=0 jns L10 mov dx,di xchg ax,bp ;ah=9 dxy db -3*16-3,+2*16+1 ;int 21h db -2*16+1,+4*16 ;loope $+40h (useless) db -3*16-3,+2*16 ;int 20h db -1*16+2gruss,
need_input
-
ich wollte nur noch etwas zu der geschwindigkeit sagen. Mach doch mal den Versuch, dein Programm über nacht laufen zu lassen, oder ändere es auf ein 7x7 Feld. Ich habe auch mal so ein Programm geschrieben (allerdings rekursiv). Jetzt habe ich mir den Quelltext nochmals angesehen und da steht:
//dieser Code hat nur bis 7x7 eine akzeptable geschwindigkeit (habe den Versuch mit dieser Funktion ein 8x8 Feld zu berechnen nach 30min abgebrochen).Vielleicht waren da ja ganz grobe schnitzer drin, aber bis 7x7 hat der Code gut funktioniert. Ich habe es dann so gelöst, dass ich immer als erstes Versuchte in eine Ecke zu springen, falls möglich. So ging es dann ziemlich schnell.