Problema Regilor

Cerință: Se dau N regi și o tablă de șah de dimensiune NxN. Să se găsească toate modalitățile de a aranja toți regii astfel încât oricare doi regi să nu se atace. Un rege atacă un alt rege dacă este plasat într-un pătrat vecin în oricare dintre cele 8 direcții (sus, jos, stânga, stânga sus, stânga jos, dreapta, dreapta sus, dreapta jos). Se cere să se afișeze prima soluție în ordine lexicografică și numărul total de soluții.

Indicații de rezolvare

Aranjarea regilor 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.

Implementare:

Cod Sursa C++

 

// RegiCPP.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 N 100
#define ADEVARAT 1
#define FALS     0
 
typedef unsigned short int LOGIC;
 
LOGIC Posibil(int,int);
void CitireDate();
void AfisareSolutie();
void Back(int);
void EvalueazaSolutie();
void Marchiaza(int,int,int);
LOGIC AmenintareTotala();
 
int matr[N][N],maux[N][N],msol[N][N],n,
	depl[][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
//matr este plina de 0   - variabila globala deci nu mai trebuie initializata cu 0
/*******************************************************************/
void main()
{
	 CitireDate();
	 Back(0);
	 AfisareSolutie();
}
/*******************************************************************/
LOGIC Posibil(int cx,int cy)
{
	 int i;
	 for(i=0;i<8;i++)
		if(matr[cx+depl[i][0]][cy+depl[i][1]]==1||matr[cx][cy]==1)
					return FALS;
	 return ADEVARAT;
}
/*******************************************************************/
void CitireDate()
{
	 printf("\nDati numarul de linii si coloane pentru tabla de sah: ");
	 scanf("%d",&n);
}
/*******************************************************************/
void Back(int px)
{
	 int cx,cy;
	 if(AmenintareTotala()) 
		 EvalueazaSolutie();
	 else 
	 for(cx=px;cx<n;cx++)
			for(cy=0;cy<n;cy++)
				if(Posibil(cx,cy))
					{
					 matr[cx][cy] = 1;
					 Back(cx);
					 matr[cx][cy] = 0;
					}
}
/*******************************************************************/
void EvalueazaSolutie()
{
	 static int nr=1;
	 int i,j,rp;
	 static int r=0;
	 if(r==0)
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				{
				msol[i][j] = matr[i][j];
				if(matr[i][j] == 1)
					r++;
				}
	 else 
	 {
		   rp = 0;
		   for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				if(matr[i][j] == 1) rp++;
		   if(rp<r)
			{
			 for(i=0;i<n;i++)
				for(j=0;j<n;j++)
					msol[i][j] = matr[i][j];
			  r = rp;
			}
	 }
	 nr++;
	 /*
	 printf("\nSolutia nr. %d:\n",nr++);
	 for(i=0;i<n;i++)
		{
		for(j=0;j<n;j++)
			if(matr[i][j]==1)
				printf(" R ");
			else printf(" * ");
		printf("\n");
		}
	 printf("\n");
	 // getch();
	 */
}
/*******************************************************************/
LOGIC AmenintareTotala()
//se copie matr in maux si se marchiaza toate casutele atacate
//se verifica daca toata tabla de sah este tinuta sub amenintare de regii
//pusi pe tabla
{
	 //copiem matr in maux
	 int i,j,l;
	 for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			maux[i][j] = matr[i][j];
 
	 for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(maux[i][j]==1)
				for(l=0;l<8;l++)
					Marchiaza(i,j,l);
	 for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(!maux[i][j])
				return FALS;
	 return ADEVARAT;
}
/*******************************************************************/
void Marchiaza(int i,int j,int l)
{
	 //se lucreaza in maux
	 if(i+depl[l][0]>=0 && i+depl[l][0]<n && j+depl[l][1]>=0 &&j+depl[l][1]<n)
	 //daca este pe tabla
		  if(maux[i+depl[l][0]][j+depl[l][1]] == 0)
		 maux[i+depl[l][0]][j+depl[l][1]] = 2;
}
/*******************************************************************/
void AfisareSolutie()
{
	 int nrr=0,i,j;
	 printf("\nSolutia cu cel mai mic numar de regi asezati pe tabla este:\n");
	 for(i=0;i<n;i++)
		{
		for(j=0;j<n;j++)
			if(msol[i][j]==1)
				{
					printf(" R ");
					nrr++;
				}
			else printf(" * ");
		printf("\n");
		}
	 printf("\nPe tabla sunt %d regi care ameninta toata tabla.",nrr);
	 system("pause");
}

Rezultat: