Săritura calului

Problemă:

Se consideră o tablă de șah de dimensiune nxn și un cal plasat în colțul de stânga sus. Se cere să se afișeze toate posibilitățile de mutare a acestei piese de șah astfel încât să treacă o singură dată prin fiecare pătrat al tablei.

Implementare:

Cod Sursa C++

 

// DeplasareCaiCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>
 
using namespace std;
 
int n, nr;
int b[80][80], xi = 0, yi = 0;
int d[][2] = { { -2, -1 }, { -2, 1 }, { -1, 2 }, { 1, 2 }, { 2, 1 }, { 2, -1 }, { 1, -2 }, { -1, -2 } };
 
void Citire()
{
	printf("\n Dati marimea tablei de sah: ");
	scanf("%d", &n);
	printf("\n Dati pozitia de start a calului:");
	printf("\n xi=");
	scanf("%d", &xi);
	printf(" yi=");
	scanf("%d", &yi);
	//xi--;yi--;
	b[xi][yi] = 2;
}
 
int Plin()
{
	int i, j;
	for (i = 0; i<n; i++)
	for (j = 0; j<n; j++)
	if (b[i][j] == 0)
		return 0;
	return 1;
}
 
void Solutie()
{
	int i, j;
	static int w = 1;
	printf("\n solutia %d: \n", w++);
	for (i = 0; i<n; i++)
	{
		for (j = 0; j<n; j++)
			printf("%d ", b[i][j]);
		printf("\n");
	}
	getch();
}
 
int Posibil(int x, int y)
{
	if (x<0 || y<0 || x>n - 1 || y>n - 1)
		return 0;
	if (b[x][y])
		return 0;
	return 1;
}
 
 
void Bkt(int x, int y)
{
	static int r = 3;
	int i;
	//Solutie();
	if (Plin()) {
		Solutie();
		getch();
		exit(1);
	}
	for (i = 0; i<8; i++)
	if (Posibil(x + d[i][0], y + d[i][1]))
	{
		b[x + d[i][0]][y + d[i][1]] = r++;
		Bkt(x + d[i][0], y + d[i][1]);
		b[x + d[i][0]][y + d[i][1]] = 0;
		r--;
	}
}
 
void main()
{
 
	Citire();
	Bkt(xi, yi);
	printf("\nNu se poate deplasa calul pe toate casutele!!");
	system("pause");
}
 

Rezultat: