[HaBo]

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);
    }   
}

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;
    }
}

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),!.

#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;
}

#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);
}

#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);
}

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;
		}

	}

}