/************************************************************************** Simulation des Springer-Problems Ziel des Springer-Problems ist es mit einem Springer auf einem Schachbrett jedes Spielfeld nacheinander nur einmal zu betreten dieses Programm simuliert dieses Problem mit Hilfe des Backtracking Verfahrens und findet Lösungen Leistungsdaten mit einen P133: ca. 180000 Spielzüge pro Sekunde ca. 4000 Lösungen pro Sekunde Autor: Werner Hoch Datum: 21.07.98 04.07.01 Portierung nach Linux ****************************************************************************/ #include #include /********************** Allgemeine Konstanten ******************************/ #define STARTX 5 /* festlegen der Startposition des Springers */ #define STARTY 5 /* in Zeitabstand soll neu dargestellt werden? [in Sekunden] */ #define DARSTELLUNGSZEIT 5 /* Berechnung des Startpunkts bezogen auf das eindimensionalen Spielfelds */ #define START (STARTX+1+(STARTY+1)*12) /********************** Global variables **********************************/ /* Festlegung der erlaubten Spielzüge eines Springers auf dem Schachbrett unter Berücksichtigung des eindimensionalen Spielfelds; die Zahlen wurden folgendermaßen festgelegt: (0) kein Zug,(-25) entspricht dem Sprung (-1,-2), (-23) -> (1,-2) usw. die Wiederholung der Zahlen wird in der Backtracking- Funktion zur Einsparung von Rechenzeit benötigt.*/ const short ERLAUBTE_ZUEGE[17]={0,-25,-23,-10,14,25,23,10,-14,-25,-23, -10,14,25,23,10,-14}; long loadCounter=100000; short Spielfeld[144], Spielfeld2[144], Status[144], Statusfeld2[144]; short Spielzuege[66], Spielzuege2[66]; short neueLoesung, NrSpielzug, Spripos; long zuegegesamtlow,zuegegesamthigh,Loesungen,Min_SpZug; long clk1,clk2; float delta_t; /****************************** FUNKTIONEN ********************************/ int LoadGame(); int SaveGame(); int InitGame(); /* Initialisierung von Variablen... */ inline int BackTracking(); /* Simulation des Springer-Problems */ inline int Eval(); /* Exported from Backtracking */ int Paint(); /* Ausgabe von Daten auf dem Bildschirm */ /* Speichert alle notwendigen Daten um zu einem anderen Zeitpunkt weiterrechnen zu können*/ int SaveGame() { FILE *f; int i; if ((f = fopen("sprist.sss","w")) == NULL) { fprintf(stderr, "Error: Cannot open file: sprist.sss\n"); return (0); } fprintf(f,"%ld\n",zuegegesamtlow); fprintf(f,"%ld\n",zuegegesamthigh); fprintf(f,"%ld\n",Min_SpZug); fprintf(f,"%ld\n",Loesungen); fprintf(f,"%hd\n",NrSpielzug); fprintf(f,"%hd\n",Spripos); for (i=0;i<144;i++) { fprintf(f,"%hd\n",Spielfeld[i]); fprintf(f,"%hd\n",Status[i]); } for (i=0;i<66;i++) fprintf(f,"%hd\n",Spielzuege[i]); fclose(f); return 1; } /* Lädt alle notwendigen Daten, ein Fehlen der Datei stört nicht. */ int LoadGame() { FILE *f; int i; if ((f = fopen("sprist.sss","r")) == NULL) { fprintf(stderr, "Error: Cannot open file: sprist.sss\n"); return (0); } fscanf(f,"%ld\n",&zuegegesamtlow); fscanf(f,"%ld\n",&zuegegesamthigh); fscanf(f,"%ld\n",&Min_SpZug); fscanf(f,"%ld\n",&Loesungen); fscanf(f,"%hd\n",&NrSpielzug); fscanf(f,"%hd\n",&Spripos); for (i=0;i<144;i++) { fscanf(f,"%hd\n",&Spielfeld[i]); fscanf(f,"%hd\n",&Status[i]); } for (i=0;i<66;i++) fscanf(f,"%hd\n",&Spielzuege[i]); fclose(f); return 1; } /* Generiert notwendige Daten und bereitet das Spielfeld vor*/ int InitGame() { int i,j; for (i=0;i<144;i++) /* Imaginäres Spiel- und Statusfeld 12x12, das Innenquadrat 8x8 wird mit 0 gekennzeichnet */ if ((i/12<2) || (i/12>9) || (i%12<2) || (i%12>9)) { Spielfeld[i]=99; Status[i]=99; } else { Status[i]=0; Spielfeld[i]=0; } for (i=0;i<144;i++) /* Check how many jumps are possible from every field. */ if (Status[i]<99) { for (j=1;j<9;j++) if (Spielfeld[i+ERLAUBTE_ZUEGE[j]]==0) Status[i]++; } for (i=0;i<66;i++) /* Spielzüge zurücksetzten */ Spielzuege[i]=0; /* Startposition festlegen und sonstige Initialisierungen */ printf("Start: %d\n",START); Spielfeld[START]=1; Spripos=START; zuegegesamtlow=zuegegesamthigh=0; Loesungen=0; NrSpielzug=2; Min_SpZug=64; } int BackTracking() { long counter=loadCounter; int i,j; zuegegesamtlow += loadCounter; /* Spielzüge zählen; Variable zweigeteilt */ if (zuegegesamtlow > 1000000000) { zuegegesamtlow -= 1000000000; zuegegesamthigh +=1; } neueLoesung=0; while (counter && (NrSpielzug > 1)) /* execute counter turns */ { /* neuen Spielzug generieren: Wird der maximale Spielzug 8 überschritten, so muß dieser ungültige Zug zurückgenommen werden*/ if (++Spielzuege[NrSpielzug]>8) { /* eine neue Lösung wird festgestellt und zwischengespeichert */ if (NrSpielzug>64) { Loesungen++; /* save the first solution of each Backtracking call. */ if (!neueLoesung) { for (i=24;i<120;i++) Spielfeld2[i]=Spielfeld[i]; for (i=0;i<66;i++) Spielzuege2[i]=Spielzuege[i]; neueLoesung=1; } } if (Min_SpZug>NrSpielzug) /* evaluate the lowest changed position. */ --Min_SpZug; /* undo one turn: game and status field. */ Spielzuege[NrSpielzug]=0; --NrSpielzug; Spielfeld[Spripos]=0; Spripos-=ERLAUBTE_ZUEGE[Spielzuege[NrSpielzug]]; if (NrSpielzug>2) for (i=1;i<9;i++) Status[Spripos+ERLAUBTE_ZUEGE[i]]++; } else /* Check the turn and execute it if it is o.k. */ { if (Eval()) { /* Execute the turn an change game field, status field. */ if (NrSpielzug>2) for (i=1;i<9;i++) Status[Spripos+ERLAUBTE_ZUEGE[i]]--; Spripos+=ERLAUBTE_ZUEGE[Spielzuege[NrSpielzug]]; Spielfeld[Spripos]=NrSpielzug; ++NrSpielzug; --counter; } } } } int Eval() /* decide wheter the turn is ok */ { int dummy=Spielzuege[NrSpielzug]; /* IF-Statment: Die 1. Zeile prüft, ob die Spielfeldposition frei ist. Zeile 2 bis 16 verhindert die Sackgassenbildung, denn es wird ein Spielzug nur gestattet wenn bei den anderen 7 Zuegen keine Sackgasse entsteht. Das Spielfeld muß dazu entweder belegt sein oder einen Status ungleich 2 besitzten. Status 2 wird dann zu einer Sackgasse, wenn dieses Feld nicht angesprungen wird. Zwar läßt sich ein solches Feld später noch erreichen, aber nicht wieder verlassen. Zeile 18 bis 25 stellt sicher, das ein Feld in der Umgebung des START-Feldes frei bleibt, damit sich mit dem letzten Zug Nr. 64 der Sprungkreis schließen kann. Der letzte Zug ist deshalb in Zeile 17 ausgenommen, da kein leeres Feld mehr benötigt wird. */ if ( !Spielfeld[Spripos+ERLAUBTE_ZUEGE[dummy]] && (Spielfeld[Spripos+ERLAUBTE_ZUEGE[dummy+1]] || Status[Spripos+ERLAUBTE_ZUEGE[dummy+1]]!=2) && (Spielfeld[Spripos+ERLAUBTE_ZUEGE[dummy+2]] || Status[Spripos+ERLAUBTE_ZUEGE[dummy+2]]!=2) && (Spielfeld[Spripos+ERLAUBTE_ZUEGE[dummy+3]] || Status[Spripos+ERLAUBTE_ZUEGE[dummy+3]]!=2) && (Spielfeld[Spripos+ERLAUBTE_ZUEGE[dummy+4]] || Status[Spripos+ERLAUBTE_ZUEGE[dummy+4]]!=2) && (Spielfeld[Spripos+ERLAUBTE_ZUEGE[dummy+5]] || Status[Spripos+ERLAUBTE_ZUEGE[dummy+5]]!=2) && (Spielfeld[Spripos+ERLAUBTE_ZUEGE[dummy+6]] || Status[Spripos+ERLAUBTE_ZUEGE[dummy+6]]!=2) && (Spielfeld[Spripos+ERLAUBTE_ZUEGE[dummy+7]] || Status[Spripos+ERLAUBTE_ZUEGE[dummy+7]]!=2) && (NrSpielzug>63 || !Spielfeld[START+ERLAUBTE_ZUEGE[1]] || !Spielfeld[START+ERLAUBTE_ZUEGE[2]] || !Spielfeld[START+ERLAUBTE_ZUEGE[3]] || !Spielfeld[START+ERLAUBTE_ZUEGE[4]] || !Spielfeld[START+ERLAUBTE_ZUEGE[5]] || !Spielfeld[START+ERLAUBTE_ZUEGE[6]] || !Spielfeld[START+ERLAUBTE_ZUEGE[7]] || !Spielfeld[START+ERLAUBTE_ZUEGE[8]])) { return 1; } else { return 0; } } int Paint() { int i; printf("\n\n Simulation of the Knights Tour"); printf("\n ===================================="); /* print the saved gaming field */ for (i=0;i<144;i++) { if ((i%12) == 0) /* new line after 12 elements */ printf("\n "); if (Spielfeld[i] < 80) /* don't print the dummy-corner */ printf("%4d",Spielfeld2[i]); } printf("\n SolutionCount: %ld Minimum: %ld StartPosition: (%d,%d)\n" ,Loesungen,Min_SpZug,START%12-1,START/12-1); printf(" These are the jumps the knight did for this solution: \n"); for (i=2;i<65;i++) printf("%2d",Spielzuege2[i]); printf("\n JumpingCounter: %.0f", (double)zuegegesamthigh*1000000000+zuegegesamtlow); printf("\n LoadCounter: %d Time: %.2lfs, Jumps/Second: %.0lf\n",loadCounter, delta_t,(float)loadCounter/(delta_t+0.00000001)); // exit(0); } /******************* MAIN ***************************************************/ int main(void) { InitGame(); LoadGame(); Paint(); while (1) { clk1=clock(); BackTracking(); if (zuegegesamtlow < loadCounter ) /* Save after each 1 billion turns, ugly!! */ SaveGame(); clk2=clock(); delta_t=(float)(clk2-clk1)/CLOCKS_PER_SEC; Paint(); /* regulate the turns, so that the computer needs the calculating time that is eqal to DARSTELLUNGSZEIT */ loadCounter = (float)loadCounter*(DARSTELLUNGSZEIT+1)/(delta_t+1); } return 1; }