Problema Cailor

Cerință:

Se dau N cai și o tablă de șah de dimensiune NxN. Să se găsească toate modalitățile de a aranja toți caii astfel încât oricare doi cai să nu se atace. Doi cai se atacă dacă unul e așezat în formă de ”L” față de celălalt. Se cere să se afișeze soluția rezultată și numărul total de piese ce pot fi puse pe tablă.

Indicație de rezolvare:

Aranjarea cailor pe tabla de șah este o problema clasica de backtracking. Metoda de rezolvare cu backtracking presupune generarea tuturor soluțiilor si testarea lor daca sunt valide sau nu. Un cal poate fi plasat pe tabla de șah daca pentru fiecare cal aranjat deja, acesta nu se afla în formă de ”L” cu niciunul dintre ei.

Implementare:

Cod Sursa C++

// CaiCPP.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;
 
#define FALS 0
#define ADEVARAT 1
#define N 20
 
typedef unsigned short LOGIC;
 
void Citire();
void RetineSolutie(int);
LOGIC Posibil(int,int);
void Back();
void AfisareSolutie();
 
int n,m[N][N],msol[N][N],ncrt=0;
int d[][2]={{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};
LOGIC x = FALS;
 
/****************************************************/
void main()
/****************************************************/
{
	 Citire();
	 Back();
	 if(x) AfisareSolutie();
	 else printf("\nNu s-a gasit nici o solutie pentru cazul dat");
	 system("pause");
}
 
/****************************************************/
void Back()
/****************************************************/
{
int cx,cy;
if(ncrt>0) RetineSolutie(ncrt);
for(cx=0;cx<n;cx++)
	for(cy=0;cy<n;cy++)
		if(Posibil(cx,cy))
			{
				m[cx][cy] = 1;
				ncrt++;
				Back();
				ncrt--;
				m[cx][cy] = 0;
			}
}
/****************************************************/
void Citire()
/****************************************************/
{
	 printf("\nDati numarul de linii si coloane pentru tabla de sah: ");
	 scanf("%d",&n);
}
/****************************************************/
void RetineSolutie(int ord)
/****************************************************/
{
 static int nmax=0;
 int i,j;
 if(ord>nmax)
	{
		x = ADEVARAT;
		nmax = ord;
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				msol[i][j]=m[i][j];
	}
}
/****************************************************/
LOGIC Posibil(int cx,int cy)
/****************************************************/
{
	 int i;
	 if(m[cx][cy])
		return FALS;
	 for(i=0;i<8;i++)
		if(cx+d[i][0]>=0 && cx+d[i][0]<n && cy+d[i][1]>=0 && cy+d[i][1]<n)
			if(m[cx+d[i][0]][cy+d[i][1]])
				return FALS;
	 return ADEVARAT;
}
/****************************************************/
void AfisareSolutie()
/****************************************************/
{
 int i,j,nr=0;
 printf("\nS-a obtinut solutia:\n");
 for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			if(msol[i][j]) 
			{
					printf(" C ");
					nr++;
			}
			else printf(" - ");
		printf("\n");
	}
 printf("\nNumarul maxim de cai ce pot fi pusi pe tabla de sah de %dx%d este %d ",n,n,nr);
 system("pause");
}

Rezultat: