Problem konika szachowego, powroty

Question

Witam, 

Napisałem algorytm który rozwiązuje problem konika szachowego. Jednak nie rozwiązuje go w sposób poprawny. A mianowicie nie mam pojęcia jak sprawić żeby algorytm się "cofał" do ostatniego pola na szachownicy i wykona inny ruch kiedy napotka pole z którego nie może wykonać ruchu. W tej chwili po prostu wstawia 0 w pola w których według mnie nie ma prawa być. 

int solve(int x, int y, int numer_ruch)
{
    int move = 0;

    if(numer_ruch == SIZE*SIZE)
    {
        return 1;
    }
    else if (szachownica[x][y] == 0)
    {
        while(move < 8)
        {
            szachownica[x][y] = numer_ruch;

            if ((ruchX(x, move) != -1) && (ruchY(y, move) != -1))
                if(solve(ruchX(x, move), ruchY(y, move), numer_ruch+1))
                    return 1;

            move++;
        }
        szachownica[x][y]=0;
    }

    return 0;
}

Może ktoś wytłumaczyć co robię źle?

Comments

Problem rozwiązany, algorytm po prostu wychodził poza tablicę.

---

To zablokuj temat :)

---

To teraz spróbuj ustawić hetmany aby się nie atakowały

Answer 1

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

void drukuj(int n,int** h)
{
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			printf("%5d ",h[i][j]);
		printf("\n");
	}
	printf("\n");
}

int probuj(int i,int n,int x,int y,int **h)
{
	int k,u,v;
	int q1;
	int a[8]={2,1,-1,-2,-2,-1,1,2};
	int b[8]={1,2,2,1,-1,-2,-2,-1};
	k=0;
	do
	{
		k++;
		q1=0;
		u=x+a[k-1];
		v=y+b[k-1];
		if(u>=0 && u<n && v>=0 && v<n)
			if(h[u][v]==0)
			{
				h[u][v]=i;
				if(i<n*n)
				{
					q1=probuj(i+1,n,u,v,h);
					if(!q1) h[u][v]=0;
				}
				else q1=1;
			}
	}
	while(!(q1||k==8));
	return q1;
}


int main(char argc, char** argv) {
	// your code goes here

	int i,j,n;
	int x,y;
	int **h;
	n=atoi(argv[1]);
	x=atoi(argv[2]);
	y=atoi(argv[3]);
	h=(int**)malloc(n*sizeof(int));
	for(i=0;i<n;i++)
		h[i]=(int*)malloc(n*sizeof(int));
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			h[i][j]=0;
	h[x-1][y-1]=1;
	if(probuj(2,n,x-1,y-1,h))
		drukuj(n,h);
	else printf("Brak rozwiazania\n");
	for(i=0;i<n;i++)
		free(h[i]);
	free(h);
	return 0;
}

Kod na podstawie algorytmy zamieszczonego u Wirtha

Można jeszcze dopisać informacje o sposobie użycia programu np
 

if(argc!=4)
    {
        printf("Poprawne uzycie : skoczek n x y [>> wynik.txt] \n");
        printf("n rozmiar planszy\n");
        printf("x numer wiersza pozycji startowej skoczka \n");
        printf("y numer kolumny pozycji startowej skoczka \n");
        printf("[>> wynik.txt] przekierowanie wyniku do pliku wynik.txt \n");
        return 1;
    }