Gyakorlati alapok II.
Rekurzió
Az N királynő-probléma
Az N királynő-problémát először egy Max Friedrich William Bezzel nevű sakkjátékos (1824 – 1871) vetette fel: hányféleképpen lehet 8 királynőt (vezért) egy 8×8-as sakktáblán úgy elhelyezni, hogy a sakkszabályok szerint ne üssék egymást. Ehhez a királynő lépési lehetőségeinek ismeretében az szükséges, hogy 2 bábu ne legyen azonos sorban, oszlopban vagy átlóban.
Tekintsünk el a feladat matematikai megoldásaitól, amelyek végeredményeit alapjában véve kombinatorikai, valamint egyéb képletekkel ki tudjuk számítani és fókuszáljunk a kódmegoldásra.
A probléma ciklikusan, azaz iterációval, valamint rekurzív módszerrel is megoldható. Amint ezt már megtanultuk, a kétféle eljárás szabadon egymásba alakítható. A feladat tanulmányozása során könnyen felfedezhetjük annak rekurzív jellegét: az alkalmazott algoritmusnak ciklikusan kell végeznie azonos jellegű tevékenységet.
Azt a rekurzív algoritmust, amelyik ezt a számításigényes műveletcsomagot elvégzi nekünk, először Edsger Dijkstra (1930 - 2002), holland matematikus és informatikus vázolta fel 1972-ben. Ő arra használta fel az úgynevezett backtrack vagy backtracking algoritmust, hogy bemutassa a strukturált programozás előnyeit.
A backtrack algoritmus egy olyan általános algoritmus, amivel (elméletileg) minden programozási feladat megoldható, bár jegyezzük meg, hogy erre az univerzalitásra sok más algoritmus is képes, ám egy jó ideje az informatikának ez már nem lehet elégséges, hiszen adatszerkezetek menedzselése során döntő mértékben számít:
az igénybevett számítási idő,
a bejárandó adatszerkezet alapstruktúrája,
a feldolgozandó adatmennyiség.
A fenti szempontok szigorú figyelembevételével a backtrack algoritmus sok esetben nem elég gyors (átlagosan exponenciális lépésszámú), de jól használható alacsony adatmennyiségű és/vagy kis bonyolultságú bemenetek esetén (például keresés labirintusban vagy könyvtárszerkezetben), illetve abban az esetben is, ha a megoldandó feladatról olyan többlettudással rendelkezünk, amellyel lényegesen csökkenthető a futási idő. Ez legtöbbször azt jelenti, hogy a keresés bizonyos ágait nem szükséges bejárni.
(Forrás - Source: mialmanach.mit.bme.hu)
A backtrack algoritmus akkor használható fel leghatékonyabban, ha a problémát meg tudjuk fogalmazni egymás utáni döntések sorozataként. Ez kiválóan érzékeltethető egy fa struktúra szerkezettel...
...amelynek teljes bejárása nyilvánvalóan függ a korábbi döntések értékeitől,
azaz annak
eltárolásától, hogy mi volt a döntés előtti utolsó lépés állapota. A backtrack algoritmus
pontosan így tesz, ugyanis nem számolja azt, hogy az egyes pozíciókban a királynő hány másik királynővel kerülne ütésbe,
hanem egyszerűen azt az első
alkalmas pozícióba helyezi. Ütés esetén kizárólag a szomszédos királynő
pozícióját befolyásoljuk közvetlenül. Az algoritmus további jellegzetessége,
hogy futásának kezdetén
egyetlen királynő sem tartózkodik a sakktáblán. A lerakás során
a királynők elhelyezésével oszloponként balról jobbra haladunk. Minden egyes
királynő elhelyezése során soronként vizsgáljuk, hogy az alkalmas-e a királynő
lerakására. Ha nem, úgy haladunk a következő sorra, egészen addig, amíg meg nem
találjuk az első alkalmas sort (ahol a királynőt el is helyezzük).
Előfordulhat, hogy ilyet nem találunk, ebben az esetben visszalépünk az előző
oszlopra, majd eltávolítjuk az ott tartózkodó királynőt. A korábbi
pozíciójából eltávolított királynőnek ugyanebben az oszlopban, a korábbi
pozícióját követő sorokban keresünk helyet. Ha ilyet találtunk, úgy a
visszalépegetés befejeződik és ismét megpróbáljuk az eredeti királynőnket
elhelyezni. Ha a korábbi királynőnknek nem találtunk alkalmas (új) pozíciót,
úgy ismét visszalépünk és ez ismétlődik mindaddig, amíg valamelyik oszlopban
az adott királynőt nem sikerül végre új pozícióban elhelyezni. Természetesen,
ha a sorok végére értünk és ezáltal adott lépésben nem adódott megoldás az
elhelyezésre, akkor az újbóli elhelyezés alkalmával a sor elejétől kezdjük
újra a próbálgatást.
A fenti gondolatmenetet követhetjük végig az alábbi videóban:
Az alábbi futtatható Java-kód a www.stackoverflow.com oldalról származik, az N királynő problémát oldja meg 4 királynő esetére backtrack algoritmussal. Az érthetőség kedvéért az eredeti kommenteket is benne hagyom a kódban:
/* Java program to solve N Queen Problem using
backtracking */
public class Main {
final int N = 4;
/* A utility function to print solution */
void printSolution(int board[][]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
System.out.print(" " + board[i][j]+ " ");
System.out.println();
}
}
/* A utility function to check if a queen can
be placed on board[row][col]. Note that this
function is called when "col" queens are already
placeed in columns from 0 to col -1. So we need
to check only left side for attacking queens */
boolean isSafe(int board[][], int row, int col {
int i, j;
/* Check this row on left side */
for (i = 0; i < col; i++)
if (board[row][i] == 1)
return false;
/* Check upper diagonal on left side */
for (i=row, j=col; i>=0 && j>=0; i--, j--)
if (board[i][j] == 1)
return false;
/* Check lower diagonal on left side */
for (i=row, j=col; j>=0 && i<N; i++, j--)
if (board[i][j] == 1)
return false;
return true;
}
/* A recursive utility function to solve N
Queen problem */
boolean solveNQUtil(int board[][], int col)
{
/* base case: If all queens are placed
then return true */
if (col >= N)
return true;
/* Consider this column and try placing
this queen in all rows one by one */
for (int i = 0; i < N; i++)
{
/* Check if the queen can be placed on
board[i][col] */
if (isSafe(board, i, col))
{
/* Place this queen in board[i][col] */
board[i][col] = 1;
/* recur to place rest of the queens */
if (solveNQUtil(board, col + 1) == true)
return true;
/* If placing queen in board[i][col]
doesn't lead to a solution then
remove queen from board[i][col] */
board[i][col] = 0; // BACKTRACK
}
}
/* If the queen can not be placed in any row in
this colum col, then return false */
return false;
}
/* This function solves the N Queen problem using
Backtracking. It mainly uses solveNQUtil () to
solve the problem. It returns false if queens
cannot be placed, otherwise, return true and
prints placement of queens in the form of 1s.
Please note that there may be more than one
solutions, this function prints one of the
feasible solutions.*/
boolean solveNQ()
{
int board[][] = {{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if (solveNQUtil(board, 0) == false)
{
System.out.print("Solution does not exist");
return false;
}
System.out.println();
printSolution(board);
return true;
}
// driver program to test above function
public static void main(String args[])
{
NQueenProblem Queen = new NQueenProblem();
Queen.solveNQ();
}
}
Végeredmény:
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
Pénzes László