Springerproblem

[Nornagest]

Hallo Leute,
diese Aufgabe stammt von crux und es handelt sich um ein Schachproblem.
Es geht darum einen Springer von einem beliebigen Feld aus alle Felder des Schachbretts besuchen zu lassen, ohne ein Feld zweimal zu betreten.

Die Aufgabe ist lösbar, ich wünsche euch viel Spaß.

Norna

 

[ich_bins]

nun hier ist des Rätsles Lösung...war eine in meinem Schachclub ne beliebte Aufgabe für neue Mitglieder ;-)

1. d4
2. c2
3. a1
4. b3
5. c1
6. a2
7. b4
8. d3
9. c5
10. a6
11. b8
12. d7
13. f6
14. e8
15. g7
16. h5
17. g3
18. h1
19. f2
20. e4
21. d6
22. b5
23. a7
24. c8
25. e7
26. g8
27. h6
28. f5
29. h4
30. g2
31. e1
32. f3
33. e5
34. f7
35. h8
36. g6
37. f8
38. h7
39. g5
40. e6
41. f4
42. h3
43. g1
44. e2
45. c3
46. d1
47. b2
48. a4
49. b6
50. a8
51. c7
52. d5
53. e3
54. g4
55. h2
56. f1
57. d2
58. b1
59. a3
60. c4
61. a5
62. b7
63. d8
64. c6

gruss...ich

 

[Nornagest]

Danke für die Lösung, allerdings geht es darum ein Programm zu schreiben dass das Problem löst. (und bitte nicht indem es die Liste vorgegeben hat und nur ausgibt)

Aber danke, ist sicher hilfreich zum vergleichen, ohne gleich alles nachzuspielen.

 

[Boar]

Wow, hier tut sich ja mal wieder was.

Das klingt nach einem typischen Backtracking-Problem, bin mal gespannt wann die erste Lösung kommt. (ich setz mich heut oder morgen auch mal dran)

Gruß, Boar

 

[ich_bins]

[Habo] ? Software Home ? Code Kitchen ? Programmieraufgaben

sorry, hab ich net aufgepasst

gruss...ich

 

[Boar]

So, hat zwar etwas länger gedauert (Abi-Stress), aber hier kommt meine Lösung.

Das Ganze war komplizierter als gedacht. Im Moment ist mein Algorithmus auch noch nicht für ein normales Schachbrett zu gebrauchen (dauert zu lange). Bei 5x5 oder 6x6 Feldern brauch der Algo auf meinem Rechner keine ganze Sekunde. Bei 7x7 sind es ca. 5 Sekunden und bei 8x8 Feldern hab ich nach einer Minute abgebrochen . Es hängt im Moment aber nur am Rechenaufwand, die Lösung funktioniert ansonsten. Ich werd aber noch dran arbeiten, den Lösungsweg zu beschleunigen.

Zu erklären gibt es eigentlich nicht viel, ich hab ein paar vereinzelte Kommentare im Code, der Rest dürfte selbsterklärend sein. Die GUI ist nicht schick, aber erfüllt ihren Zweck. Die Felgröße steht im Moment fest auf 6x6.

Achso, Programmiersprache = Java (1.4.2)
Ich hab das ganze als .jar-file in den Anhang gepackt.

Springerproblem.java:

package prog;

import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.*;
import javax.swing.border.LineBorder;

public class Springerproblem extends JFrame implements ActionListener
{
    static int a = 6;
    Container cp = getContentPane();
    static JLabel[][] feld   = new JLabel[a][a];
    static int position[][] = new int[a][a];
    JPanel brett = new JPanel();
    JTextField coords = new JTextField("x,y",8);
    JLabel info = new JLabel("Starkoordinaten (von 0,0 bis "+(a-1)+","+(a-1)+"):");
    JButton start = new JButton("Berechnen");
    
    public Springerproblem()
    {
        super("Springerproblem");      
        this.setSize(350,400);
        this.setLocation((this.getToolkit().getScreenSize().width  - getSize().width ) / 2,
                         (this.getToolkit().getScreenSize().height - getSize().height) / 2);
        this.setResizable(false);
        this.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
        cp.setLayout(new FlowLayout(FlowLayout.LEFT,50,20));
        cp.add(brett);
        cp.add(info);
        cp.add(coords);
        cp.add(start);   
        brett.setLayout(new GridLayout(a,a));
        brett.setPreferredSize(new Dimension(200,200));
        info.setPreferredSize(new Dimension(350,13));
           
        for(int j=0; j<a; j++)
        {
          for(int i=0; i<a; i++)
          {
              feld[i][j]=new JLabel(" ",JLabel.CENTER);
              feld[i][j].setBorder( new LineBorder(Color.black,1));
              brett.add(feld[i][j]);
              feld[i][j].setOpaque(true);
              feld[i][j].setBackground(Color.lightGray);
              position[i][j]=0;
          }
        }
        start.addActionListener(this);                                     
    }
    public void actionPerformed(ActionEvent e) 
    {
        for(int i=0; i<a; i++)
            for(int j=0; j<a; j++)
                feld[i][j].setText("");
        for(int i=0; i<a*a; i++)
        {
            Algorithmus.xWeg[i]=0;
            Algorithmus.yWeg[i]=0;           
        }
        Algorithmus.first=true;
        int x,y;
        String s;        
        s=""+coords.getText().charAt(0);
        x=Integer.parseInt(s);
        s=""+coords.getText().charAt(2);
        y=Integer.parseInt(s);

        /* Der Backtracking-Algorithmus wird aufgerufen
         * Wenn das Springerproblem gelöst ist wird die Lösung ausgegeben
         */ 
        if(Algorithmus.solve(x,y,1)==true)
        {
            for(int i=0; i<a*a; i++)
                feld[Algorithmus.xWeg[i]][Algorithmus.yWeg[i]].setText(""+i);                     
            for(int i=0; i<a; i++)
                for(int j=0; j<a; j++)
                {
                    if(feld[i][j].getText().equals(""))
                        feld[i][j].setText("36");
                    if(feld[i][j].getText().equals("1")||feld[i][j].getText().equals("36"))
                        feld[i][j].setForeground(Color.blue);
                }            
        }
        else
            coords.setText("Keine Lösung");
        for(int i=0; i<a; i++)
            for(int j=0; j<a; j++)
                position[i][j]=0;       
    }
    public static void main(String[] args)
    {
        Springerproblem sp = new Springerproblem();
        sp.setVisible(true);
    }   
}

Algorithmus.java:

package prog;

public class Algorithmus 
{
    //Feldgröße: 6*6
    static int a=6;
    // xWerte und yWerte speichern alle 8 möglichen Richtungen, 
    // in die sich der Springer bewegen kann 
    // Das erste paar (00) wird nur beim ersten Aufruf benötigt
    final static int[] xWerte = {0,-1,-2, 1, 2,-1,-2, 1, 2};
    final static int[] yWerte = {0, 2, 1,-2, 1,-2,-1, 2,-1};
    static int[] xWeg  = new int[a*a];
    static int[] yWeg  = new int[a*a];
    static boolean first=true;
    
    public static boolean solve(int x,int y, int num)
    {    
        int xNeu, yNeu,k;
        boolean solved;
        k=0;       
        
        do{        
            ++k;
            
            if(first==true) 
            {
                --k;
                first=false;
            }
            solved=false;
            
            //Neue Koordinaten
            xNeu=x+xWerte[k];
            yNeu=y+yWerte[k];
            
            //Ist der Zug gültig?
            if(xNeu>=0 && yNeu>=0 && xNeu<a && yNeu<a)
            {
                //Ist das Feld frei?
                if(Springerproblem.position[xNeu][yNeu]==0)
                {          
                    //Setze in das Feld
                    Springerproblem.position[xNeu][yNeu]=num;
                    xWeg[num-1]=x;
                    yWeg[num-1]=y;
                    
                    //Problem gelöst?
                    if(num<(a*a))
                    {
                        //Wenn Problem noch nicht gelöst: Rekursion
                        solved=solve(xNeu,yNeu,num+1);
                        //Wenn der Rekursionsschritt in eine Sackgasse
                        //geführt hat, wird er zurück genommen
                        if(solved==false)
                        {
                            Springerproblem.position[xNeu][yNeu]=0;
                        }
                    }    
                    else
                        solved=true;
                    
                }
            }  
        } while(solved==false && k<8);
        return solved;
    }
}

Gruß, Boar

 

[sirphreak]

ich hab auch noch was auf meiner Platte gefunden:

wobei das schachbrett einfach mit durchlaufenden nummern dargestellt wird,
die man wenn manwill auch per konvert() zurückwandeln kann.

start per: "start."

start :- schachbrett(X), springer(10,X,Los), write(Los).

schachbrett([ 1, 2, 3, 4, 5, 6, 7, 8,
             9,10,11,12,13,14,15,16,
            17,18,19,20,21,22,23,24,
            25,26,27,28,29,30,31,32,
            33,34,35,36,37,38,39,40,
            41,42,43,44,45,46,47,48,
            49,50,51,52,53,54,55,56,
            57,58,59,60,61,62,63,64]).



%springer(_,[],_).
springer(_,[],[]).

springer(Feld,Felder,[Feld|Weg]):-F is Feld-17, member(F,Felder), del(F,Felder,Felder2), springer(F,Felder2,Weg).
springer(Feld,Felder,[Feld|Weg]):-F is Feld+17, member(F,Felder), del(F,Felder,Felder2), springer(F,Felder2,Weg).


springer(Feld,Felder,[Feld|Weg]):-F is Feld-15, member(F,Felder), del(F,Felder,Felder2), springer(F,Felder2,Weg).
springer(Feld,Felder,[Feld|Weg]):-F is Feld+15, member(F,Felder), del(F,Felder,Felder2), springer(F,Felder2,Weg).


springer(Feld,Felder,[Feld|Weg]):-F is Feld-6, member(F,Felder), del(F,Felder,Felder2), springer(F,Felder2,Weg).
springer(Feld,Felder,[Feld|Weg]):-F is Feld+6, member(F,Felder), del(F,Felder,Felder2), springer(F,Felder2,Weg).


springer(Feld,Felder,[Feld|Weg]):-F is Feld-10, member(F,Felder), del(F,Felder,Felder2), springer(F,Felder2,Weg).
springer(Feld,Felder,[Feld|Weg]):-F is Feld+10, member(F,Felder), del(F,Felder,Felder2), springer(F,Felder2,Weg).

del(_,[],[]).
del(X,[X|T],L):- del(X,T,L),!.
del(X,[Y|Z],[Y|T]):- del(X,Z,T),!.

edit: sollte ich erwähnen das das prolog ist ?

 

[JoBbE]

Also ich habe mich mal daran gemacht, VIM auszuprobieren und womit ginge das besser, als mit einem kleinen Prograemmchen?
Also habe ich hier herumgestoebert und mir das Springerproblem ausgesucht.
Selbstkritik: Der Algorithmus ist scheisse. Extrem schlecht. Er funktioniert zwar zuverlaessig, aber ist sowas von lahm.
Der rekursive Ansatz ist natuerlich wesentlich besser, aber irgendwie habe ich nicht daran gedacht beim Schreiben
Asche auf mein Haupt.
Draw() ist nur eine Hilfsfunktion, die ich zum debuggen benutzt habe, sie war ganz nuetzlich.
Das Beispiel akzeptiert Groessen von 1-9, das ist reine Willkuer. Der Algorithmus wuerde auch mit unendlich grossen Brettern funktionieren.
Nur halt auch ewig brauchen hihi

Naja, ich wollte den code trotzdem hier reinstellen. Geloeste Aufgabe ist geloeste Aufgabe.

#include <iostream>
#include <sstream>
#include <vector>
#include <map>
#include <stack>
#include <string>
using namespace std;

enum eState {EMPTY, CURRENT, VISITED, ERROR};
typedef pair<int, int> Pos;
typedef map<Pos, eState> PosStateMap;
typedef pair<Pos, Pos> Move;
typedef pair<Move, int> MoveBan;
typedef stack<MoveBan> MoveStack;

class Brett
{
	public: 
		Brett();
		~Brett();
		void SetSize(int iSize);
		int GetSize();
		void SetAt(int x, int y, eState state);
		void SetAt(Pos pNew, eState state);
		const eState GetAt(int x, int y);
		void SetCurrent(int x, int y);
		void SetCurrent(Pos pCurrent);
		void Draw();
		void FindSolution();

	protected:
		bool OnBoard(Pos pTest) const;
		bool OnBoard(int x, int y) const;
		bool ExEmpty();
		MoveBan BuildMoveBan( int x1, int y1, int x2, int y2, int ban);
		MoveBan NewMbFromLast(MoveBan &mbLast, Pos &pZiel);
		int mSize;
		Pos mCurrent;
		PosStateMap mStates;
		MoveStack mMoveHistory;

};

MoveBan Brett::BuildMoveBan( int x1, int y1, int x2, int y2, int ban)
{
	Pos pFrom(x1, y1), pTo(x2, y2);
	
	Move mvMove(pFrom, pTo);
	
	MoveBan mb(mvMove, ban);

	return mb;
}

MoveBan Brett::NewMbFromLast(MoveBan &mbLast, Pos &pZiel)
{
	return BuildMoveBan(mbLast.first.second.first,
				  mbLast.first.second.second,
				  pZiel.first, pZiel.second, 0);
}

bool Brett::ExEmpty()
{
	bool isEmpty = false;
	for( int i = 1; i <= mSize; ++i)
		for( int j = 1; j <= mSize; ++j)
			if( GetAt(i, j) == EMPTY )
				isEmpty = true;
	return isEmpty;
}

void Brett::FindSolution()
{
	/* Der Suchalgorithmus (Do-While-Schleife)
	 * 1) Auf moegliche Felder pruefen (auf Brett, nicht VISITED, kein BAN)
	 * 2) Keine vorhanden
	 * 3)	Leere Felder?
	 * 4)		Nein
	 * 5)			Erfolg!
	 * 6)			History ausgeben
	 * 7)		Ja
	 * 8) 			From (0, 0)? keine Loesung moeglich, abbrechen
	 * 9)			Feld zwischenspeichern
	 * 10)			Auf letztes Feld zurueckgehen
	 * 11) 			Gespeichertes Feld zur Banliste
	 * 12)			Naechste Schleife
	 * 13) Auf erstes moegliches Feld bewegen
	 * 14) Bewegung in History speichern	
	 */
	
	// Offsets fuer die moeglichen Felder
	map<int, Pos> pOffsets;
	pOffsets[0].first = 1;
	pOffsets[0].second = -2;
	pOffsets[1].first = 2;
	pOffsets[1].second = -1;
	pOffsets[2].first = 2;
	pOffsets[2].second = 1;
	pOffsets[3].first = 1;
	pOffsets[3].second = 2;
	pOffsets[4].first = -1;
	pOffsets[4].second = 2;
	pOffsets[5].first = -2;
	pOffsets[5].second = 1;
	pOffsets[6].first = -2;
	pOffsets[6].second = -1;
	pOffsets[7].first = -1;
	pOffsets[7].second = -2;

	bool bSolved = false;

	// Move History initialisieren
	MoveBan mbBuf = BuildMoveBan(-1, -1, mCurrent.first, mCurrent.second, 0);
	mMoveHistory.push( mbBuf);

	do
	{
		MoveBan mbTmp = mMoveHistory.top();
		int iBanLevel = mbTmp.second;

		// leere Felder vorhanden?
		if( !ExEmpty() )
		{
			bSolved = true;
			break;
		}
		
		// ersten moeglichen Zielpunkt finden.
		Pos pZiel;
		for(int i = (0+iBanLevel); i <= 7; ++i)
		{
		 pZiel.first = mCurrent.first + pOffsets[i].first;
		 pZiel.second = mCurrent.second + pOffsets[i].second;
		 if(OnBoard(pZiel) && GetAt(pZiel.first, pZiel.second) == EMPTY)
		 {
			 // Zielpunkt gefunden
			 // Banlevel updaten
			 mbTmp.second = i;
			 mMoveHistory.pop();
			 mMoveHistory.push(mbTmp);
			 
			 // bewegen
			 mMoveHistory.push( NewMbFromLast(mbTmp, pZiel) );
			 // und auch im Spielbrett bewegen
			 SetCurrent(mMoveHistory.top().first.second);
			 SetAt(mMoveHistory.top().first.first, VISITED);
			 // naechste Schleife!
			 break;
		 }	 
		 ++iBanLevel;
		}		
				
		if( iBanLevel >= 8)
		{
			// Aufgabe unloesbar?
			MoveBan mbTmp = mMoveHistory.top();
			Pos pNull(-1, -1);
			if( mbTmp.first.first == pNull )
			{
				// Startpunkt erreicht, Banlevel 8
				cout << "Die Aufgabe ist nicht loesbar.\n";
				break;
			}
			
			// alle Zielpunkte gebannt
			// -> Zurueck zum letzten Punkt, Banlevel erhoehen
			SetCurrent(mMoveHistory.top().first.first);
			mMoveHistory.pop();
			mbTmp = mMoveHistory.top();
			++mbTmp.second;
			mMoveHistory.pop();
			mMoveHistory.push(mbTmp);
		}
	} while (true);

	if( bSolved )
	{
		cout << "Juhu, geloest!" << endl << "Und so gehts:\n\n";
		// mMoveHistory umdrehen
		MoveStack msTmp;
		while( !mMoveHistory.empty() )
		{
			msTmp.push( mMoveHistory.top() );
			mMoveHistory.pop();
		}
		mMoveHistory = msTmp;

		// ...und ausgeben
		for( int i = 0; i < mSize; ++i)
		{
			for( int j = 0; j < mSize; ++j)
			{
				MoveBan mbTmp = mMoveHistory.top();
				cout << (char)(64+mbTmp.first.second.first);
				cout << mbTmp.first.second.second;
				cout << " ";
				mMoveHistory.pop();
			}
			cout << "\n\n";
		}	
	}
}

bool Brett::OnBoard(int x, int y) const
{
	if( x <= 0 || y <= 0 || x > mSize || y > mSize )
		return false;
	return true;
}

bool Brett::OnBoard(Pos pTest) const
{
	return OnBoard(pTest.first, pTest.second);
}

Brett::Brett()
{
	SetSize(1);
	SetCurrent(1, 1);
}

Brett::~Brett()
{
}

void Brett::SetSize(int iSize)
{
	if( iSize <= 0 )
		mSize = 1;
	mSize = iSize;

	Pos pTemp;
	
	//Brett initialisieren
	for( int i = 1; i <= iSize; ++i)
		for( int j = 1; j <= iSize; ++j)
		{
			pTemp.first = i;
			pTemp.second = j;
			mStates[pTemp] = EMPTY;
		}
}

int Brett::GetSize()
{
	return mSize;
}

void Brett::SetAt(int x, int y, eState state)
{
	if( OnBoard(x, y) )
	{
		Pos pTemp;
		pTemp.first = x;
		pTemp.second = y;
		mStates[pTemp] = state;
	}
}

void Brett::SetAt(Pos pNew, eState state)
{
	SetAt(pNew.first, pNew.second, state);
}

const eState Brett::GetAt(int x, int y)
{
	if( OnBoard(x, y) )
	{
		Pos pTemp;
		pTemp.first = x;
		pTemp.second = y;

		return mStates[pTemp];
	}
	return ERROR;
}

void Brett::SetCurrent(int x, int y)
{
	Pos pTemp;
	pTemp.first = x;
	pTemp.second = y;
	SetCurrent(pTemp);
}

void Brett::SetCurrent(Pos pCurrent)
{
	if( OnBoard(pCurrent) )
	{
		SetAt(mCurrent, EMPTY);
		mCurrent = pCurrent;
		SetAt(mCurrent, CURRENT);
	}
}

void Brett::Draw()
{
	cout << endl;
	for(int i = 0; i <= mSize; ++i)
	{
		for(int j = 0; j <= mSize; ++j)
		{


			switch( GetAt(j, i) )
			{
				case EMPTY:
				{
					cout << "_";
					break;
				}

				case CURRENT:
				{
					cout << "o";
					break;
				}

				case VISITED:
				{
					cout << "X";
					break;
				}

				case ERROR:
				default:
				{
						
					if( j == 0 && i > 0)
						cout << (i);

					if( j > 0 && i == 0)
						cout << (char)(64+j);

					if( j == 0 && i == 0 )
						cout << " ";
				}
			}

			cout << " ";
		}
		cout << endl;
	}
}

void GetDigit(string sLabel, int *iGet)
{
	string s;
	bool error;
	istringstream ins;

	while(true)
	{

		error = false;
		cout << sLabel << " : ";
		cin >> s;

		if( s.size() > 1)
			error = true;
		else
			if( !isdigit(s[0] ) )
					error = true;
		if(!error)
			break;	
	}
	ins.str(s);
	ins >> *iGet;
}

int main()
{
	int iGroesse = 0;
	
	Pos pStart;

	do
		GetDigit("Brettgroesse", &iGroesse);
	while (iGroesse <= 0);
	
	do
		GetDigit("Startposition(X)", &pStart.first);
	while (pStart.first <= 0 || pStart.first > iGroesse);
		
	do
		GetDigit("Startposition(Y)", &pStart.second);
	while (pStart.second <= 0 || pStart.second > iGroesse);	

	Brett myBrett;
	myBrett.SetSize(iGroesse);
	myBrett.SetCurrent(pStart);

	Pos pTemp;

	myBrett.FindSolution();

	return 0;
}

 

[kito]

@boar
beindruckend nicht schlecht dein proggi...die Geschwindigkeit verlangsamt sich bei größerem Feld wahrscheinlich durch die Rekursion die du drinnen hast. (denk ich mir mal)

Edit
Hab jetzt mal schnell ein Algo zusammengeschrieben...noch dazu in C (schon lange nicht mehr programmiert). Da ich auf dem Firmenpc bin und natürlich kein Compiler zur Hand habe, hab ich den Code nur im Notepad aus dem Kopf geschrieben.
Meiner Meinung nach müsste es so funktionieren, kann aber ruhig sein, dass Syntaxfehler oder sonstige Bugs vorhanden sind. Finde im Moment nur nicht so die Zeit sonst würd ich's Zuhause compilieren...Also wer Lust hat...
(Müsste mal jemand kompilieren :])
Grüße!

#include <stdio.h>

#define field_x 6
#define field_y 6

int visited[field_x][field_y];  //0 = not visited; 1 = visited


void initVisited(){
	int x=0;
	int y=0;
	for(y=0; i<field_y;y++){
		for(x=0; j<field_x; y++){
			visited[x][y] = 0;
		}
	}
}

int isVisited(int x, int y){
	//return -1 = out of bounds
	if(x>field_x || x<0) || (y>field_y || y<0) return -1;
	return visited[x][y];
}

void processPos(int x, int y){
	if(visited[][]==1 || visited[][]==-1) return;
	printf("visited pos(" + x + ";" + y + ")\n");
	processPos(x+1,y-2);
	processPos(x+2,y-1);
	processPos(x+2,y+1);
	processPos(x+1,y+2);
	processPos(x-1,y+2);
	processPos(x-2,y+1);
	processPos(x-2,y-1);
	processPos(x-1,y-2);
}

int main(void){
	//startpositions
	int startX = 0;
	int startY = 0; 	
	processPos(startX,startY);
}

 

[Boar]

@boar
beindruckend smile nicht schlecht dein proggi...die Geschwindigkeit verlangsamt sich bei größerem Feld wahrscheinlich durch die Rekursion die du drinnen hast. (denk ich mir mal)

Dankeschön! Ja, der hohe Rechenaufwand hängt mit der Rekursion zusammen. Beschleunigen ließe sich das ganze mit verbesserter Heuristik, bzw. Breitensuche. Wen es interessiert: klick

Gruß, Boar

 

[lotec]

hi, Leute! Ich find den Forum ziemlich cool. Bei unseren Klausuren ist es leider übrig, den Code auf Papier zu schreiben, und zwar in völlig unrealistischen Zeitrahmen, deswegen hab ich versucht, die Aufgabe um die Zeit auf stück Blatt zu lösen. Na ja, hat doch nicht ganz geklappt ohne Rechnereinsatz, aber hier der Code:

#include <stdio.h>
int* field;
int* resx;
int* resy;
int counter=0;
int max=0;
int i, j;
void init()
{
	int i;
	field=(int*)malloc(64*sizeof(int));
	resx=(int*)malloc(sizeof(int)*64);
	resy=(int*)malloc(sizeof(int)*64);
	for(i=0; i<64; i++)
		field[i]=0;
	
}
void func(int x, int y)
{
	resx[counter]=x;
	resy[counter]=y;
	counter++;
	if(counter==64)
		show();
/*	if(counter==63)
	{
		for(i=0; i<8; i++)
		{
			for(j=0; j<8; j++)
				if(field[j*8+i])
					printf("*");
				else
					printf("0");
				printf("\n");
		}
		printf("\n\n\n");
}*/
						
	if((x+1<=7&&y-2>=0)&&(!field[8*(x+1)+y-2]))
	{
		field[8*(x+1)+y-2]=1;
		func(x+1, y-2);
		field[8*(x+1)+y-2]=0;
	}
		
	if((x+2<=7&&y-1>=0)&&(!field[8*(x+2)+y-1]))
	{
		field[8*(x+2)+y-1]=1;
		func(x+2, y-1);
		field[8*(x+2)+y-1]=0;
	}	
	if((x+2<=7&&y+1<=7)&&(!field[8*(x+2)+y+1]))
	{
		field[8*(x+2)+y+1]=1;
		func(x+2, y+1);
		field[8*(x+2)+y+1]=0;
	}
	if((x+1<=7&&y+2<=7)&&(!field[8*(x+1)+y+2]))
	{
		field[8*(x+1)+y+2]=1;
		func(x+1, y+2);
		field[8*(x+1)+y+2]=0;
	}
	if((x-1>=0&&y+2<=7)&&(!field[8*(x-1)+y+2]))
	{
		field[8*(x-1)+y+2]=1;
		func(x-1, y+2);
		field[8*(x-1)+y+2]=0;
	}	
	if((x-2>=0&&y+1<=7)&&(!field[8*(x-2)+y+1]))
	{
		field[8*(x-2)+y+1]=1;
		func(x-2, y+1);
		field[8*(x-2)+y+1]=0;
	}	
	if((x-2>=0&&y-1>=0)&&(!field[8*(x-2)+y-1]))
	{
		field[8*(x-2)+y-1]=1;
		func(x-2, y-1);
		field[8*(x-2)+y-1]=0;
	}	
	if((x-1>=0&&y-2>=0)&&(!field[8*(x-1)+y-2]))
	{
		field[8*(x-1)+y-2]=1;
		func(x-1, y-2);
		field[8*(x-1)+y-2]=0;
	}
	counter--;
	
}
void show()
{
	int i;
	for(i=0; i<64; i++)
		printf("%c%d  ", 97+resx[i], resy[i]+1);
	printf("\n\n\n\n");
}
int main()
{
	init();
	func(0,0);
}

Ach ja, kennt ihr das ähnliche Acht Damen- Problem? Acht Damen auf Feld zu stellen, ohne dass sie sich schlagen. Fast dasselbe, wie Springer- Problem, aber- mehr Möglichkeiten, nach einer effektiven Lösung zu suchen.

 

[Ook!]

Meine Java Lösung... CDW hat wieder geholfen

public class Knightproblem {

	public static void main(String[] args) {
		System.out.println(new Knightproblem().new Solver().getResultField());
	}

	class Solver {

		private int[][] result = null;
		private final int size = 6;
		private int[][] jumps = { {-1,2}, {-2,1}, {1,-2}, {2,1}, {-1,-2}, {-2,-1}, {1,2}, {2,-1} };
		
		public Solver() {
			this.doIt(0, 0, new int[size][size], 1);
		}

		private boolean doIt(int x, int y, int[][] visited, int jump) {
			if(jump == (visited.length*visited.length)) {
				visited[x][y] = jump;
				result = visited;
				return true;
			}

			for(int i=0; i<8; i++) {
				if((x+jumps[i][0]) > -1 && (y+jumps[i][1]) > -1 && (x+jumps[i][0]) < visited.length && (y+jumps[i][1]) < visited.length) {
					if(visited[x+jumps[i][0]][y+jumps[i][1]] == 0) {
						visited[x][y] = jump;
						if(doIt((x+jumps[i][0]), (y+jumps[i][1]), visited, jump+1))
							return true;
						visited[x][y] = 0;
					}
				}
			}
			return false;
		}

		public String getResultField(){
			String returnString = "";
			for(int[] row : result) {
				for(int col : row) {
					returnString += (col +"\t");
				}
				returnString += "\n";
			}
			return returnString;
		}

	}

}

Gibt nur ein einziges Feld zurück, ich habe noch eine erweiterte Version... da brauch er allerdings recht lange um ein Ergebnis zu finden, deshalb werde ich die hier nicht posten!

Gruß
Felix

 

[Stein]

Ich habe das mal in Pytohn realiesiert:

Spoiler: Python

#Man muss versuchen einen Spinger ueber das ganze Schachbrett laufen zu lassen ohne, dass er ein Feld 2x betritt
def jump(x,y, betreten, spruenge):
    global i
    i += 1
    #print spruenge
    #rechte Seite
    if(im_feld(x + 1,y - 2) and was_there(betreten, x + 1,y - 2) == False):
        jump(x + 1,y - 2, betreten + "(" + str(x + 1) + "|" + str(y - 2) + ")", spruenge + 1 )
    if(im_feld(x + 1,y + 2) and was_there(betreten, x + 1,y + 2) == False):
        jump(x + 1,y + 2, betreten + "(" + str(x + 1) + "|" + str(y + 2) + ")", spruenge + 1 )
    if(im_feld(x + 2,y - 1) and was_there(betreten, x + 2,y - 1) == False):
       jump(x + 2,y - 1, betreten + "(" + str(x + 2) + "|" + str(y - 1) + ")", spruenge + 1 )
    if(im_feld(x + 2,y + 1) and was_there(betreten, x + 2,y + 1) == False):
       jump(x + 2,y + 1, betreten + "(" + str(x + 2) + "|" + str(y + 1) + ")", spruenge + 1)
    #linke Seite
    if(im_feld(x - 1,y - 2) and was_there(betreten, x - 1,y - 2) == False):
        jump(x - 1,y - 2, betreten + "(" + str(x - 1) + "|" + str(y - 2) + ")", spruenge + 1 )
    if(im_feld(x - 1,y + 2) and was_there(betreten, x - 1,y + 2) == False):
        jump(x - 1,y + 2, betreten + "(" + str(x - 1) + "|" + str(y + 2) + ")", spruenge + 1 )
    if(im_feld(x - 2,y - 1) and was_there(betreten, x - 2,y - 1) == False):
       jump(x - 2,y - 1, betreten + "(" + str(x - 2) + "|" + str(y - 1) + ")", spruenge + 1 )
    if(im_feld(x - 2,y + 1) and was_there(betreten, x - 2,y + 1) == False):
       jump(x - 2,y + 1, betreten + "(" + str(x - 2) + "|" + str(y + 1) + ")", spruenge + 1)
    if(spruenge == 63):
        print betreten
        exit()
def im_feld(x,y):
    if (x <= 8) and (x >= 1) and (y <= 8) and (y >= 1):
        return True
    else:
        return False
def was_there(betreten, x, y):
    if "(" + str(x) + "|" + str(y) + ")" in betreten:
        return True
    else:
        return False

i = 1
for x in range(1,9,1):
    for y in range(1,9,1):
        print "Start:" + str(x) + "|" + str(y)
        jump(x,y,"(" +str(x)+ "|" + str(y )+ ")",0)

Weil die aber so unfassbar langsam ist werde ich vielleich auch noch mal was in Java versuchen.

 

[MontyPerl]

Weil die aber so unfassbar langsam ist werde ich vielleich auch noch mal was in Java versuchen.

Java's not quite there yet, write in C.
Naja, das liegt hauptsächlich am stumpfen backtrack-Algo. Der ist hier halt richtig lahm.

Hab das mal in C gemacht:

Spoiler: springerproblem.c

#include <stdio.h>
#include <stdlib.h>
#include "stackChar.h"

#define VISITED 1

typedef struct {
    int xdim, ydim;
    int **f;
    int **moves;
} field;

field *getField(int x, int y);
int isValidPos(field *f, int x, int y);
void *xmalloc(int size);
void printField(field *f, int currx, int curry);
void clearField(field *f);
int solve(field *f, stack s, int x, int y, int visited);

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "usage: %s <m> <n>\n", argv[0]);
        exit(EXIT_FAILURE);
    }
    int x, y;
    x = atoi(argv[1]);
    y = atoi(argv[2]);
    field *f = getField(x, y);
    stack solution = newStack(64);
    int success = solve(f, solution, 0, 0, 0);
    if (success) {
        clearField(f);
        while (!isEmptyStack(solution)) {
            y = popStack(solution);
            x = popStack(solution);
            f->f[y][x] ^= VISITED;
            printField(f, x, y);
        }
    }
    return success ? EXIT_SUCCESS : EXIT_FAILURE;
}

int solve(field *f, stack s, int x, int y, int visited) {
    f->f[y][x] ^= VISITED;
    pushStack(s, x);
    pushStack(s, y);
    visited++;
    if (visited == (f->xdim * f->ydim)) {
        return 1;
    }
    int i, newx, newy;
    for (i = 0; i < 8; i++) {
        newx = x + f->moves[i][0];
        newy = y + f->moves[i][1];
        if (isValidPos(f, newx, newy)) {
            if (solve(f, s, newx, newy, visited)) {
                return 1;
            }
        }
    }
    popStack(s);
    popStack(s);
    f->f[y][x] ^= VISITED;
    return 0;
}

void clearField(field *f) {
    int x, y;
    for (y = 0; y < f->ydim; y++) {
        for (x = 0; x < f->xdim; x++) {
            f->f[y][x] = 0;
        }
    }
}

void printField(field *f, int currx, int curry) {
    int x, y;
    printf("\n");
    for (x = 0; x < f->xdim; x++) {
        printf("--");
    }
    printf("\n");
    for (y = 0; y < f->ydim; y++) {
        for (x = 0; x < f->xdim; x++) {
            if (x == currx && y == curry) {
                printf("@ ");
            }
            else {
                printf("%s", f->f[y][x] & VISITED ? "o " : ". ");
            }
        }
        printf("\n");
    }
}

field *getField(int x, int y) {
    int *rows = xmalloc(x * y * sizeof(int));
    int **arr = xmalloc(y * sizeof(int *));
    int i, j;
    for (i = 0; i < y; i++) {
        arr[i] = &rows[i * x];
        for (j = 0; j < x; j++) {
            arr[i][j] = 0;
        }
    }
    field *f = xmalloc(sizeof(field));
    f->f = arr;
    f->xdim = x;
    f->ydim = y;
    /* these are the 8 movement possibilities
     * written in the form (xoffset, yoffset):
     * 2, 1; 2, -1; -2, 1; -2, -1;
     * 1, 2; -1, 2; 1, -2; -1, -2;
     */
    int *move = malloc(2 * 8 * sizeof(int));
    int **moves = malloc(8 * sizeof(int *));
    int xd, yd; /* x delta and y delta */
    i = 0;
    for (xd = -2; xd <= 2; xd++) {
        for (yd = -2; yd <= 2; yd++) {
            if (xd && yd && (abs(xd) != abs(yd))) {
                move[i*2] = xd;
                move[(i*2)+1] = yd;
                moves[i] = &move[i*2];
                i++;
            }
        }
    }
    f->moves = moves;
    return f;
}

int isValidPos(field *f, int x, int y) {
    if (x < 0 || y < 0 || x >= f->xdim || y >= f->ydim) {
        return 0;
    }
    else if (f->f[y][x] & VISITED) {
        return 0;
    }
    return 1;
}

void *xmalloc(int size) {
    void *ptr = malloc(size);
    if (ptr == NULL) {
        fprintf(stderr, "not enough memory\n");
        exit(EXIT_FAILURE);
    }
    return ptr;
}

Hier der char-Stack code:

Spoiler: stackChar.h

#include <stdlib.h>
#include <stdio.h>

/* stackChar.h -- a simple char stack */

#define POP_EMPTY '\0'
/* this is the char to be returned
 * by pop() on an empty stack.
 */


typedef struct stack {
    char *arr;
    int pos;
    int size;
    int alloc;  /* chunks to be (re)allocated at once on stack growth */
} *stack;


stack newStack(int allocChunk);        /* "constructor" if you will */
void destroyStack(stack s);            /* destructor */

void pushStack(stack s, char c);
char popStack(stack s);
char topStack(stack s);


stack newStack(int allocChunk) {
    struct stack *s = malloc(sizeof(struct stack));
    char *arr = malloc(allocChunk);
    if (arr == NULL || s == NULL) {
        fprintf(stderr, "Couldn't allocate memory for new stack-object (newStack())\n");
        exit(EXIT_FAILURE);
    }
    s->arr = arr;
    s->pos = -1;
    s->alloc = allocChunk;
    s->size = s->alloc;
    return s;
}

void destroyStack(stack s) {
    free(s->arr);
    free(s);
    return;
}

void pushStack(stack s, char c) {
    if (s->pos == (s->size - 1)) {
        s->size += s->alloc;
        s->arr = realloc(s->arr, s->size);
        if (s->arr == NULL) {
            fprintf(stderr, "Couldn't reallocate memory for stack (pushStack())\n");
            exit(EXIT_FAILURE);
        }
    }
    s->pos++;
    s->arr[s->pos] = c;
    return;
}

char popStack(stack s) {
    if (s->pos == -1) {
        return POP_EMPTY;
    }
    char c = s->arr[s->pos];
    s->pos--;
    return c;
}

char topStack(stack s) {
    if (s->pos == -1) {
        return POP_EMPTY;
    }
    else {
        return s->arr[s->pos];
    }
}

int isEmptyStack(stack s) {
    if (s->pos == -1) {
        return 1;
    }
    return 0;
}

Für ein n * m Feld. Gibt zu jedem Schritt das entsprechende Feld aus. (Auch zu schritten, die nicht zum Ziel führen.)
Wenn man den printField-Aufruf aus der Lösungsfunktion rausnimmt, "schaff" er ein 8x8 Feld in knapp unter 6 Sekunden. (Ich wollte das eigentlich mit deinem python Script vergleichen, aber das hab ich nach 3 Minuten abgebrochen.) Mit dem printField Aufruf dauert das weeeeeeeeeesentlich länger. Wobei das Ausgeben des Feldes eh etwas sinnfrei ist, da schaut man dem Computer halt beim wild rumprobieren zu.
Ich schau mal, dass ich ne Version nachreiche, die nur den richtigen Lösungsweg (insofern denn einer gefunden wurde) ausgibt.

edit: done. Das braucht jetzt 7.5 Sekunden für ein 8x8 Brett und gibt die gefundene Lösung dann aus.

Hier mal die Ausgabe für ein 5x5 Brett:

Spoiler: Lösung für ein 5x5 Brett

$ time ./springerproblem 5 5

----------
. . . . . 
. . . . . 
. . . . . 
. . . . . 
. . . . @ 

----------
. . . . . 
. . . . . 
. . . . . 
. . @ . . 
. . . . o 

----------
. . . . . 
. . . . . 
. . . . . 
. . o . . 
@ . . . o 

----------
. . . . . 
. . . . . 
. @ . . . 
. . o . . 
o . . . o 

----------
. . . . . 
. . . . . 
. o . . . 
. . o . . 
o . @ . o 

----------
. . . . . 
. . . . . 
. o . . . 
. . o . @ 
o . o . o 

----------
. . . . . 
. . . @ . 
. o . . . 
. . o . o 
o . o . o 

----------
. @ . . . 
. . . o . 
. o . . . 
. . o . o 
o . o . o 

----------
. o . . . 
. . . o . 
@ o . . . 
. . o . o 
o . o . o 

----------
. o . . . 
. . . o . 
o o . . . 
. . o . o 
o @ o . o 

----------
. o . . . 
. . . o . 
o o . . . 
. . o @ o 
o o o . o 

----------
. o . . . 
. . . o @ 
o o . . . 
. . o o o 
o o o . o 

----------
. o . . . 
. . . o o 
o o @ . . 
. . o o o 
o o o . o 

----------
. o . . . 
. . . o o 
o o o . . 
@ . o o o 
o o o . o 

----------
. o . . . 
. @ . o o 
o o o . . 
o . o o o 
o o o . o 

----------
. o . @ . 
. o . o o 
o o o . . 
o . o o o 
o o o . o 

----------
. o . o . 
. o . o o 
o o o . @ 
o . o o o 
o o o . o 

----------
. o . o . 
. o . o o 
o o o . o 
o . o o o 
o o o @ o 

----------
. o . o . 
. o . o o 
o o o . o 
o @ o o o 
o o o o o 

----------
. o . o . 
@ o . o o 
o o o . o 
o o o o o 
o o o o o 

----------
. o @ o . 
o o . o o 
o o o . o 
o o o o o 
o o o o o 

----------
. o o o . 
o o . o o 
o o o @ o 
o o o o o 
o o o o o 

----------
. o o o @ 
o o . o o 
o o o o o 
o o o o o 
o o o o o 

----------
. o o o o 
o o @ o o 
o o o o o 
o o o o o 
o o o o o 

----------
@ o o o o 
o o o o o 
o o o o o 
o o o o o 
o o o o o 

real    0m0.009s
user    0m0.003s
sys     0m0.003s

edit2:
Hab mal ein kleines perlscript geschrieben, mit dem man sich die Ausgabe animiert ausgeben lassen kann:

Spoiler: springerAnimat0r.pl

#!/usr/bin/env perl
use strict;
use warnings;

my $idleness = shift || .25;
my $clearstr = `clear`;

while (my $line = <STDIN>) {
    if ($line =~ /^-/) {
        select undef, undef, undef, $idleness;
        print $clearstr;
    }
    else {
        print $line;
    }
}

Auf windows muss man aus dem `clear` ein `cls` machen. (Afaik...)
Der input wird von stdin genommen und die Zeit in Sekunden (floats sind möglich) zwischen einzelnen Frames wird als erstes Argument genommen (oder default auf 0.25 gesetzt).
Mögliche Aufrufe:

$ ./springerproblem 10 10 > foo
$ ./springerAnimat0r.pl .5 < foo
$ # oder direkt durch die pipe:
$ ./springerproblem 5 5 | ./springerAnimat0r.pl .15

Enjoy the show.

 

[Lesco]

..write in C.

Das halte ich in 90% der Fälle für unnötig, umständlich und fehleranfällig(wobei Java auch nicht viel besser ist).

Hier eine Lösung in Haskell:

Spoiler: code

import Control.Monad.ST
import Control.Monad.Cont
import Control.Applicative
import Data.Array.ST
import Data.Ix
import Data.List
import Data.Ord
import System.Environment

type Pos = (Int,Int)
type Board s = STUArray s Pos Int
type BoardAction r s a = ContT r (ST s) a

validMoves :: Board s -> Pos -> BoardAction r s [Pos]
validMoves b = sortWith (fmap length . valids) <=< valids
    where sortWith f l = map fst <$> sortBy (comparing snd) <$> mapM (\x -> (,) x <$> f x) l
          valids (x,y) = do
            bs <- lift $ getBounds b
            filterM (free b) [(x',y') | (dx,dy) <- [(1,2),(2,1)]
                             , x' <- [x-dx,x+dx], y' <- [y-dy,y+dy]
                             , inRange bs (x',y')]

free :: Board s -> Pos -> BoardAction r s Bool
free b p = (0==) <$> lift (readArray b p)

set :: Board s -> Pos -> Int -> BoardAction r s ()
set b p k = lift $ writeArray b p k

solve :: Board s -> Pos -> Int -> (String -> BoardAction r s ()) -> BoardAction r s ()
solve b pos k exit = lift (getBounds b) >>= \(_,(n,m)) -> do
  when (k > n*m) $ exit =<< printBoard b
  vms <- validMoves b pos
  forM_ vms $ \pos' -> set b pos' k >> solve b pos' (k+1) exit >> set b pos' 0

printBoard :: Board s -> BoardAction r s String
printBoard b = lift (getBounds b) >>= \(_,(n,m)) -> do
  let max = ceiling . logBase 10 . fromIntegral $ n*n + 1
      pad i = let s = show i in replicate (max-length s) ' ' ++ s
  lst <- mapM (mapM $ lift . readArray b) [[(i,j) | j <- [1..m]] | i <- [1..n]]
  return . unlines . map (unwords . map pad) $ lst

runIt :: Pos -> Pos -> IO ()
runIt size start = putStrLn <=< stToIO . flip runContT return $ do
                     b <- lift $ newArray ((1,1),size) 0
                     set b start 1
                     callCC $ \exit -> solve b start 2 exit >> fail "no solution"

main = map read <$> getArgs >>= \(size:start:[]) -> runIt size start

Schafft ein 160x160 Feld in ca 0.4s auf meinem Rechner(Core2Duo 2Ghz), wenn man es mit -O2 oder -O3 kompiliert(ghc 6.10.1). Aufruf mit: ./program "(n,m)" "(startx,starty)" (Beginnend bei 1). Die Geschwindigkeit kommt durch eine verbesserte Heuristik, die von einem Feld aus zuerst die Felder versucht, die die wenigsten gültigen Nachfolgefelder haben.

Beispiel-Ausgabe für ein 8x8-Feld:

Spoiler: ausgabe

 1 16 59 34  3 18 21 36
58 33  2 17 60 35  4 19
15 54 57 62 43 20 37 22
32 63 46 53 56 61 42  5
49 14 55 64 47 44 23 38
28 31 48 45 52 41  6  9
13 50 29 26 11  8 39 24
30 27 12 51 40 25 10  7

 

[CDW]

Spoiler: Backtracking mit einfacher Heuristik

SICStus/SWI

 :- use_module(library(between)).
 :- use_module(library(lists)).

solve(N,S,R) :-	numlist(1,N,L),pairs(L,Ps),delete(Ps,S,NPs),!,get(S,NPs,R).

pairs(L,Ps) :- findall((X,Y),(member(X,L),member(Y,L)),Ps).

distance((X,Y),(DX,DY),N) :- N =:= (X-DX)**2+(Y-DY)**2.

next(P,L,Ps) :- findall(E,(member(E,L),distance(E,P,5)),Ps).

eval(P,L,(X,Y))	:- next(P,L,Ps),
	findall((Len,E),(member(E,Ps),next(E,L,Es),length(Es,Len)),Us),
	sort(Us,Sorted),member((_,X,Y),Sorted).

get(_,[],[]).
get(P,L,[N|Sol]) :- eval(P,L,N),delete(L,N,NL),get(N,NL,Sol).

Eingabe:
solve(Boardgroesse,(StartX,StartY),Ergebnis).
Bsp:
solve(5,(1,1),Res).
für 5x5 Board mit (1,1) alst Startfeld.

kann sich zwar nicht mit Lescos Implementierung messen (entweder nutzt er noch ein paar Regeln oder ich sollte weniger Speicher "fressen" ), braucht aber für 8x8 ~31ms, 20x20 ~ 1.7 Sek, 50x50 ~ 70 Sek.

Ausgabe für 5x5:

Spoiler: spoiler

?- solve(5,(1,1),R),write(R).
[(2,3),(1,5),(3,4),(5,5),(4,3),(5,1),(3,2),(1,3),(2,1),(4,2),(5,4),(3,5),(1,4),(2,2),(4,1),(5,3),(4,5),(2,4),(1,2),(3,1),(5,2),(3,3),(2,5),(4,4)]

 

[Lesco]

Original von CDW
(entweder nutzt er noch ein paar Regeln oder ich sollte weniger Speicher "fressen" )

Die einzige (algorithmische) Optimierung, die ich verwendet habe ist die Sortierung der Nachfolgefelder anhand der Anzahl ihrer jeweiligen gültigen Nachfolger. Meine Prolog-Unkenntnis hindert mich jedoch daran, zu erkennen, ob das bei deiner Lösung auch schon so gemacht wird.

 

[CDW]

Original von Lesco Meine Prolog-Unkenntnis hindert mich jedoch daran, zu erkennen, ob das bei deiner Lösung auch schon so gemacht wird.

Spoiler: spoiler

eigentlich schon:

eval(P,L,(X,Y))	:- next(P,L,Ps),
	findall((Len,E),(member(E,Ps),next(E,L,Es),length(Es,Len)),Us),
	--->>sort(Us,Sorted),member((_,X,Y),Sorted) <<----.

Allerdings gehe ich grob zusammengefasst so vor:
generiere erstmal 2D Koordinatenliste der einzelnen Felder. Diese wird nun benutzt, um jeweils Nachfolgezüge auszuwählen (und deren Nachfolgezüge für Bewertung). Es kann also sein, dass hier noch Listenoperationen an dem Performanceeinbruch schuld sind. Auch zeigt mir der Profiler an, dass "distance" >90% aller Rechenzeit verbraucht. Ich werde dann bei Gelegenheit probieren, neue Züge zu generieren, anstatt alles aus einer Liste auszuwählen und per "distance" zu prüfen, ob das ein gültiger Zug sein kann.

EDIT:
Ich hab das ein wenig "optimiert" - statt einer vorgefertigten Koordinatenliste wird nun erst bei Bedarf ein Zug generiert. Auch wird für die Prüfung/Speicherung getätigter Züge statt einfacher Liste nun eine Associations (Bintree) benutzt. Entsprechend sind auch die Zeiten:
1.7Sek werden nun für 80x80 Feld gebraucht, 160x160 ist immerhin in 6Sek gemacht, 200x200 in ~10 Sek.

Spoiler: nicht mehr so elegant

Nur Associations (SWI/SICStus)

:- use_module(library(lists)).
:- use_module(library(assoc)).

solve(N,S,R) :- put_assoc(S,_,_,Tree),Max is N*N-1,get(N,S,Tree,Max,R).

next((X,Y),(NX,NY),N):-
        ((X>2,NX is X-2;X+1<N,NX is X+2), (Y>1,NY is Y-1;Y<N,NY is Y+1));
        ((X>1,NX is X-1;X<N,NX is X+1), (Y>2,NY is Y-2;Y+1<N,NY is Y+2)).
next(P,Tree,Ps,N):- findall(E,(next(P,E,N), \+ get_assoc(E,Tree,_)),Ps),!.

eval(P,Tree,(X,Y),N):- next(P,Tree,Ps,N),
      findall((Len,E),(member(E,Ps),next(E,Tree,Es,N),length(Es,Len)),Us),
      sort(Us,Sorted),!,member((S,X,Y),Sorted).

get(_,_,_,0,[]).
get(N,P,Tree,Count,[P2|Sol]) :- eval(P,Tree,P2,N),put_assoc(P2,Tree,_,NTree),
                                NC is Count-1,get(N,P2,NTree,NC,Sol).

Oder AVL Trees (nur SICStus, dafür aber ca 3 mal schneller als allgemeine Version)

:- use_module(library(lists)).
:- use_module(library(avl)).
 solve(N,S,R) :- avl_store(S,_,S,Tree),Max is N*N-1,get(N,S,Tree,Max,R).

 next((X,Y),(NX,NY),N):-
	 ((X>2,NX is X-2;X+1<N,NX is X+2), (Y>1,NY is Y-1;Y<N,NY is Y+1));
  	 ((X>1,NX is X-1;X<N,NX is X+1), (Y>2,NY is Y-2;Y+1<N,NY is Y+2)).
 next(P,Tree,Ps,N):- findall(E,(next(P,E,N), \+avl_fetch(E,Tree)),Ps),!.	 
 
 eval(P,Tree,(X,Y),N):- next(P,Tree,Ps,N),
 	findall((Len,E),(member(E,Ps),next(E,Tree,Es,N),length(Es,Len)),Us),
 	sort(Us,Sorted),!,member((S,X,Y),Sorted).

 get(_,_,_,0,[]).
 get(N,P,Tree,Count,[P2|Sol]) :- eval(P,Tree,P2,N), avl_store(P2,Tree,P2,NTree),
	 NC is Count-1, get(N,P2,NTree,NC,Sol).

 

[MontyPerl]

Na dann will ich doch auch nochmal

Spoiler: springerproblemReloaded

Mit der stumpfen (aber effektiven) Optimierung + es ist jetzt reines ANSI C (also viel portabler geht nimma). Außerdem nimmts jetzt die Startx- und Starty-Koordinaten als optionales 3. und 4. Argument. (Default ist 0 0)

#include <stdio.h>
#include <stdlib.h>
#include "stackChar.h"

#define VISITED 1

typedef struct {
    int xdim, ydim;
    int **f;
    int **moves;
} field;

typedef struct stepStruct {
    int dx, dy;     /* delta x and delta y */
    int succ;       /* number of valid successors */ 
} step;

field *getField(int x, int y);
int isValidPos(field *f, int x, int y);
step *getSteps(field *f, int x, int y);
void *xmalloc(int size);
void printField(field *f, int currx, int curry);
void clearField(field *f);
int solve(field *f, stack s, int x, int y, int visited);
int stepsort(const void *a, const void *b);

int main(int argc, char *argv[]) {
    int x, y, startx, starty, success;
    field *f;
    stack solution;
    if (argc == 3) {
        startx = 0;
        starty = 0;
    }
    else if (argc == 5) {
        startx = atoi(argv[3]);
        starty = atoi(argv[4]);
    }
    else {
        fprintf(stderr, "usage: %s <x> <y> [<startx> <starty>]\n", argv[0]);
        exit(EXIT_FAILURE);
    }
    x = atoi(argv[1]);
    y = atoi(argv[2]);
    solution = newStack(x * y * 2);
    f = getField(x, y);
    success = solve(f, solution, startx, starty, 1);
    if (success) {
        printf("success\n");
        if (x <= 50 && y <= 40) {
            clearField(f);
            while (!isEmptyStack(solution)) {
                x = shiftStack(solution);
                y = shiftStack(solution);
                f->f[y][x] |= VISITED;
                printField(f, x, y);
            }
        }
    }
    else {
        printf("couldn't find a solution\n");
    }
    return success ? EXIT_SUCCESS : EXIT_FAILURE;
}

int solve(field *f, stack s, int x, int y, int visited) {
    int i;
    step *steps;
    f->f[y][x] ^= VISITED;
    pushStack(s, x);
    pushStack(s, y);
    if (visited == (f->xdim * f->ydim)) {
        return 1;
    }

    if ((steps = getSteps(f, x, y)) == NULL) {
        f->f[y][x] ^= VISITED;
        return 0;
    }
    for (i = 0; i < 8 && steps[i].succ != -1; i++) {
        if (solve(f, s, x + steps[i].dx, y + steps[i].dy, visited + 1)) {
            return 1;
        }
    }
    popStack(s);    /* y */
    popStack(s);    /* x */
    free(steps);
    f->f[y][x] ^= VISITED;
    return 0;
}

void clearField(field *f) {
    int x, y;
    for (y = 0; y < f->ydim; y++) {
        for (x = 0; x < f->xdim; x++) {
            f->f[y][x] = 0;
        }
    }
}

void printField(field *f, int currx, int curry) {
    int x, y;
    printf("\n");
    for (x = 0; x < f->xdim; x++) {
        printf("--");
    }
    printf("\n");
    for (y = 0; y < f->ydim; y++) {
        for (x = 0; x < f->xdim; x++) {
            if (x == currx && y == curry) {
                printf("@ ");
            }
            else {
                printf("%s", f->f[y][x] & VISITED ? "o " : ". ");
            }
        }
        printf("\n");
    }
}

field *getField(int x, int y) {
    int *rows = xmalloc(x * y * sizeof(int));
    int **arr = xmalloc(y * sizeof(int *));
    int *move, **moves, xd, yd;
    int i, j;
    field *f;
    for (i = 0; i < y; i++) {
        arr[i] = &rows[i * x];
        for (j = 0; j < x; j++) {
            arr[i][j] = 0;
        }
    }
    f = xmalloc(sizeof(field));
    f->f = arr;
    f->xdim = x;
    f->ydim = y;
    /* these are the 8 movement possibilities
     * written in the form (xoffset, yoffset):
     * 2, 1; 2, -1; -2, 1; -2, -1;
     * 1, 2; -1, 2; 1, -2; -1, -2;
     */
    move = malloc(2 * 8 * sizeof(int));
    moves = malloc(8 * sizeof(int *));
    i = 0;
    for (xd = -2; xd <= 2; xd++) {
        for (yd = -2; yd <= 2; yd++) {
            if (xd && yd && (abs(xd) != abs(yd))) {
                move[i*2] = xd;
                move[(i*2)+1] = yd;
                moves[i] = &move[i*2];
                i++;
            }
        }
    }
    f->moves = moves;
    return f;
}

int isValidPos(field *f, int x, int y) {
    if (x < 0 || y < 0 || x >= f->xdim || y >= f->ydim) {
        return 0;
    }
    else if (f->f[y][x] & VISITED) {
        return 0;   /* this one was already visited! */
    }
    return 1;
}

step *getSteps(field *f, int x, int y) {
    int i, j, k, succ;
    step *steps = xmalloc(8 * sizeof(step));
    j = 0;
    for (i = 0; i < 8; i++) {
        if (isValidPos(f, x + f->moves[i][0], y + f->moves[i][1])) {
            steps[j].dx = f->moves[i][0];
            steps[j].dy = f->moves[i][1];
            succ = 0;
            for (k = 0; k < 8; k++) {
                if (
                  isValidPos(f, x + steps[j].dx + f->moves[k][0], y + steps[j].dy + f->moves[k][1])
                ) {
                    succ++;
                }
            }
            steps[j].succ = succ;
            j++;
        }
    }
    if (j == 0) {
        free(steps);
        return NULL;
    }
    else if (j < 8) {
        steps[j].succ = -1;
    }
    qsort(steps, j, sizeof(step), &stepsort);
    return steps;
}

int stepsort(const void *a, const void *b) {
    if (( (step *) a)->succ == ( (step *) b)->succ) {
        return 0;
    }
    if (( (step *) a)->succ > ( (step *) b)->succ) {
        return 1;
    }
    else {
        return -1;
    }
}

void *xmalloc(int size) {
    void *ptr = malloc(size);
    if (ptr == NULL) {
        fprintf(stderr, "not enough memory\n");
        exit(EXIT_FAILURE);
    }
    return ptr;
}

Außerdem ein patch für den char Stack: (hat jetzt eine shift Methode, damit man den "replay" in der richtigen Reihenfolge anschauen kann)

23a24
> char shiftStack(stack s);
61a63,77
> char shiftStack(stack s) {
>     int i;
>     char c;
>     if (s->pos == -1) {
>         return POP_EMPTY;
>     }
>     c = s->arr[0];
>     for (i = 1; i <= s->pos; i++) {
>         s->arr[i-1] = s->arr[i];
>     }
>     s->arr[s->pos] = '\0';
>     s->pos--;
>     return c;
> }
> 
62a79
>     char c;
66c83
<     char c = s->arr[s->pos];
---
>     c = s->arr[s->pos];

Das Feld wird jetzt auch nur noch ausgegeben, wenn n <= 50 und m <= 40 ist. (Größeres ist für die meisten Terminals einfach nicht sinnvoll darstellbar.)

$ time ./springerproblem 360 360
success

real    0m0.309s
user    0m0.219s
sys     0m0.069s
$ # Vergleich mit Lesco's Lösung:
$ time ./haskellLoesung '(50,50)' '(1,1)' >/dev/null

real    0m0.324s
user    0m0.242s
sys     0m0.010s

$ time ./springerproblem 50 50
success

real    0m0.008s
user    0m0.005s
sys     0m0.003s

CWD's Lösung (zumindest die SWIPL Lösung, denn die konnte ich ausprobieren..) ist nochmal ein paar Dimensionen langsamer. Und bei mir bricht sie bereits bei 100x100 Feldern ab mit "Out of global stack", trotz 500mb stack..
Mein Rechner:

$ grep 'name' /proc/cpuinfo 
model name      : Intel(R) Pentium(R) 4 CPU 1.70GHz
$ grep MemTotal /proc/meminfo 
MemTotal:       512684 kB

Genug Sch****vergleich?

 

[CDW]

Pff, richtige Männer messen in cm (oder: traue keiner Statistik, die du nicht selbst gefälscht hast )
Erweiterte Heuristik rein: (aus gleichwertigen Zügen werden nun zuerst die zum Rand nächsten abgearbeitet)

Spoiler: SICStus

Zeile 12,14 "Erweiterung" (prädikat border)

:- use_module(library(lists)).
:- use_module(library(avl)).
solve(N,S,R) :- Max is N*N-1,empty_avl(Tree),get(N,S,Tree,Max,R).

next((X,Y),(NX,NY),N):-
	((X>2,NX is X-2;X+1<N,NX is X+2), (Y>1,NY is Y-1;Y<N,NY is Y+1));
	((X>1,NX is X-1;X<N,NX is X+1), (Y>2,NY is Y-2;Y+1<N,NY is Y+2)).

successors(P,N,Tree,R):- findall(_,(next(P,E,N), \+avl_fetch(E,Tree)),List),length(List,R),!.
eval(P,Tree,Res,N):- 
   	findall((Len,Dist,E),(next(P,E,N), \+avl_fetch(E,Tree),
			      successors(E,N,Tree,Len),border(E,N,Dist)),Us),
   	sort(Us,Sorted),!,member((_,_,Res),Sorted).
border((X,Y),N,R):- R is min(min(X-1,N-X),min(Y-1,N-Y)).

get(_,P,_,0,[P]).
get(N,P,Tree,Count,[P|Res]) :- avl_store(P,Tree,P,NTree),!,eval(P,NTree,P2,N),
	NC is Count-1, get(N,P2,NTree,NC,Res).

Nun cheaten wir:

Spoiler: cheat 1, SICStus

?- time2(solve(50,(0,0),R)).      
 0.609 sec.                <--- vorher
 ?- compile(springer).  <- produziert VM-Code
% compiling e:/home/cdw/eigene dateien/prolog/springer.pl...
% compiled e:/home/cdw/eigene dateien/prolog/springer.pl in module user, 0 msec -416 bytes
yes
| ?- time2(solve(50,(1,1),_)).
 0.281 sec.              <----- nachher
yes
| ?-

Spoiler: cheat2, SICSTus

Heuristikzeitmessungen sind immer problematisch, da die Laufzeit von gewählen Startparametern und z.B Auswahlreihenfolge bei gleichwertigen Zügen abhängig ist . Außerdem ist es gegenüber Prolog nicht fair, da aufgrund von Choicepunkten die "nächste" Lösung viel schneller berechnet werden kann:

Stattdessen messen wir mal ein paar 1000 Werte
( ms(Zeit) gibt an, zu welchem Zeitpunkt nach dem Programmstart die Lösung verfügbar war).
Messung für 1000 Werte

| ?- forall(time2(solve(50,(1,1),_),T),(write(T),nl)).
ms(281)
ms(281)
ms(281)
ms(281)
...
995 Antworten später
ms(1750)

1750ms für 1000 Lösungen= 1.7 ms/Lösung
und das 360x360 Brett:
10000 Werte

| ?- forall(time2(solve(360,(1,1),_),T),(write(T),nl)).
ms(19671)
ms(19671)
ms(19671)
ms(19671)
ms(19671)
... 9994 Lösungen
ms(30562)

Die erste Lösung war zwar erst in der 19 Sekunde verfügbar - aber die 10000 ste in der 30ten.
30562/10000 = 3 ms pro Lösung.

Speicherverbrauch ist natürlich ein Problem - aber eher Interpreterbezogen.
Bsp:

Spoiler: 100*100 Feld, SICStus

time2(solve(100,(1,1),R),T),statistics.
R = [(1,1),(2,3),(1,5),(2,7),(1,9),(2,11),(1,13),(2,15),(1,17),(2,19)|...],
T = ms(1280) ?
memory (total)      12739304 bytes
   global stack      8713236 bytes:    5443848 in use,   3269388 free
   local stack        353016 bytes:     280012 in use,     73004 free
   trail stack        260122 bytes:      94364 in use,    165758 free
   control stack      525550 bytes:     359792 in use,    165758 free
   atoms              115842 bytes:       3843 in use,   1044732 free
   program space     2887380 bytes:    1159476 in use,   1727904 free

das ist die Statisitk nach der Ausgabe der ersten Lösung (d.h die Choicepoints für andere sind noch im Speicher). Wie man sieht sind nur 5 MB global stack belegt.
dasselbe mit SWI-Prolog, 32 bits, Version 5.6.55, Windows:

Spoiler: 100*100 Feld

Spoiler: SWI Code

nix wildes, nur avl wieder auf associations gestellt.

:- use_module(library(lists)).
:- use_module(library(avl)).
solve(N,S,R) :- Max is N*N-1,get(N,S,t,Max,R).

next((X,Y),(NX,NY),N):-
        ((X>2,NX is X-2;X+1<N,NX is X+2), (Y>1,NY is Y-1;Y<N,NY is Y+1));
        ((X>1,NX is X-1;X<N,NX is X+1), (Y>2,NY is Y-2;Y+1<N,NY is Y+2)).

successors(P,N,Tree,R):- findall(_,(next(P,E,N), \+get_assoc(E,Tree,_)),List),length(List,R).
eval(P,Tree,Res,N):- 
        findall((Len,Dist,E),(next(P,E,N), \+get_assoc(E,Tree,_),
                              successors(E,N,Tree,Len),border(E,N,Dist)),Us),
        sort(Us,Sorted),!,member((_,_,Res),Sorted).
border((X,Y),N,R):- R is min(min(X-1,N-X),min(Y-1,N-Y)).

get(_,P,_,0,[P]):-!.
get(N,P,Tree,Count,[P|Res]) :- put_assoc(P,Tree,P,NTree),!,eval(P,NTree,P2,N),
        NC is Count-1, get(N,P2,NTree,NC,Res).

6 ?- solve(100,(1,1),R),statistics.
6.44 seconds cpu time for 17,933,062 inferences
4,973 atoms, 3,062 functors, 2,891 predicates, 73 modules, 101,768 VM-codes

                       Limit    Allocated       In use
Heap         :                               1,192,200 Bytes
Local  stack :    33,554,432    1,368,064    1,360,660 Bytes
Global stack :   134,217,728    6,287,360    6,285,556 Bytes
Trail  stack :   134,217,728      376,832      375,580 Bytes

9 garbage collections gained 8,406,576 bytes in 0.44 seconds.
1 threads, 0 finished threads used 0.00 seconds.
R = [ (1, 1), (2, 3), (1, 5), (2, 7), (1, 9), (2, 11), (1, 13), (2, 15), (..., ...)|...]

Sind zwar etwas mehr - aber auch noch deutlich unter 10 MB.