Problema calului in C++ – Backtracking

Problema primita pe pagina de Facebook

Salutare si bine v-am regasit, astazi vom raspunde unei probleme primite pe pagina noastra de Facebook.

Enuntul problemei:

Se da o tabla de sah cu dimensiunea NxN. Un cal se gaseste in linia 1 si coloana 1. Gasiti un sir de mutari ale calului astfel incat acesta sa acopere intreaga tabla de sah fara a trece printr-o casuta de 2 ori.

Acesta problema este foarte asemanatoare cu problema labirintului. Doar ca difera ceva, de data asta nu ne mai deplasam nord – sud – est – vest, ne deplasam cum se deplaseaza calul pe tabla de sah.

Toate mutarile posibile

Am incercat mai sus sa desenez toate mutarile posibile pe care le poate face calutul nostru. Daca transpunem poza in doi vectori de directii, rezultatul este urmatorul:

#include    <iostream>

using namespace std;

int n;
int matrice[105][105], xi = 0, yi = 0;

const int directii = 8;
const int di[directii] = {-2, -1, 1, 2,  2,  1, -1, -2};
const int dj[directii] = { 1,  2, 2, 1, -1, -2, -2, -1};

void Citire()
{
    cin >> n;
    cin >> xi >> yi;
    matrice[xi][yi] = 1;
}

bool isFull()
{
    for(int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (matrice[i][j] == 0)
                return false;
    return true;
}

void Solutie()
{
    static int w = 1;

    cout << "Solutia nr. " << w << ": \n";
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
            cout << matrice[i][j] << " ";
        cout << "\n";
    }

    w ++;
    cout << "\n\n";
}

bool isOK(int i, int j)
{
    if(i > n - 1 || i < 0)
        return false;
    if(j > n - 1 || j < 0)
        return false;
    if(matrice[i][j])
        return false;

    return true;
}

void Rezolvare(int x, int y)
{
    static int r = 2;
    if(isFull())
    {
        Solutie();
        //exit(1);
        return ;
    }
    for(int i = 0; i < directii; i++)
    {
        int i_vecin = x + di[i];
        int j_vecin = y + dj[i];
        if (isOK(i_vecin, j_vecin))
        {
            matrice[i_vecin][j_vecin] = r++;
            Rezolvare(i_vecin, j_vecin);
            matrice[i_vecin][j_vecin] = 0;
            r--;
        }
    }
}

int main()
{
    Citire();
    Rezolvare(xi, yi);
    return 0;
}

Functia bool isOK(int x, int y)

• Primeste ca si parametrii doua numere intregi x si y (sunt numere intregi deoarece pot sa primeasca si -1, altfel le-am fi declarat „unsigned int”)
• Functia noastra verifica prima oara daca noile coordonate sunt in-afara matricei
• De asemenea, casuta este respinsa daca a mai fost vizitata in trecut (valoarea mai mare ca 1)

Functia bool isFull()

• Verifica daca toate casutele sunt diferite de 0
• Cele doua for-uri pot fi inlocuite cu o conditie de genu
  • if(numar_mutare_curenta >= n)
    return false;

Functia void Rezolvare(int x, int y)

• Este o functie recursiva ce parcurge pe rand vecinii, iar mai apoi se intoarce de unde a plecat – similar algoritmului lui Lee
• Aceasta functie verifica pe rand toti cei 8 vecini. In cazul in care casuta poate fi vizitata, aceasta functie o viziteaza, iar cand se intoarce din recursivitate marcheaza casuta cu „0” (casuta nevizitata)

Daca doriti sa generati doar o solutie, decomentati linia cu exit(1);