Исцрпна претрага (енгл. Backtracking) - претрага у ширину и претрага у дубину
Увод
Бектрекинг (енгл. backtracking) или исцрпна претрага је стратегија за решавање проблема која се заснива на систематичном испитивању свих могућих опција како би се пронашло решење. Бектрекинг је суштински заснован на индуктивно-рекурзивној техници за конструкцију алгоритама и гради решење део по део.
Алгоритам у сваком кораку доноси одлуку о наставку претраге и прелази на следећи ниво. Ако приликом доношења одлуке, алгоритам схвати да тај пут или грана не може да доведе до валидног решења, алгоритам одустаје и враћа се назад на претходни ниво, тј. ради бектрек.
Најлакше га можемо замислити као истраживање лавиринта. Све време идемо једним путем док не ударимо у зид, тј. не наиђемо на ћорсокак. Када ударимо у зид, враћамо се назад до последње раскрснице и настављамо претрагу неким другим путем. Јасно је да овакав приступ врло лако може да нас заглави у циклусу, па је уобичајена тактика за разбијање циклуса да током претраге остављамо трагове, слично Ивици и Марици, да бисмо знали које смо путеве већ посетили и/или одбацили.
Концептуално у сваком кораку алгоритма радимо следеће:
- Одлучивање/избор - Бирамо једну од доступних опција у текућем кораку. У случају лавиринта бирамо да ли ћемо ићи лево, десно, напред или назад.
- Провера услова - Да ли је одлика/избор коју смо направили валидна према условима проблема? У случају лавиринта, занима нас да ли ћемо након донете одлуке о смеру кретања ударити у зид или не. Ако ударамо у зид, потез није валидан, па морамо да покушамо са неком другом од дозвољених операција.
- Рекурзија - Ако је избор валидан, настављамо са потрагом за следећим делом решења. У случају са лавиритном, ово би било еквивалентно томе да се померимо у следећу позицију у односу на изабрани потез и да поновимо поступак разматрања.
- Враћање назад/бектрек - Ако ниједан дозвољени потез не води ка решењу, напуштамо текући корак и враћамо се у претходно стање.
Прелазак у наредно стање, једнак је рекурзивном позиву. Враћање у претходно стање, једнако је одмотавању рекурзије. С обзиром да се ради о рекурзивним имплементацијама, сва међустања имплицитно чувамо на системском стеку. Псеудокод описаног поступка је следећи:
Бектрекинг се разликује од грубе силе зато што одмах одсеца све оне путање за које закључи да не могу довести до решења проблема. Са друге стране, груба сила слепо иде до краја сваке могуће комбинације потеза.
Главна предност бектрекинга огледа се у томе што ће решење сигурно пронаћи, ако оно постоји. Мане бектрекинга су спорост, јер ипак проверава сва могућа решења, па је простор претраге експоненцијалан. Друга мана је меморијска захтевност, јер користи рекурзију, па дубина стабла израчунавања може бити изузетно велика.
Бектрекинг се користи за проблеме који имају огроман простор претраге, али постоје јасна правила која нам дозвољавају да рано одбацимо лоше путеве. Карактеристични проблеми су:
- Судоку - попуњавамо таблу број по број, чим унесемо број који крши правила, одбацујемо га и покушавамо са следећим.
- Проблем краљица - Постављање краљица на шаховску таблу тако да се међусобно не нападају.
- Проблем трговачког путника - Тражење најкраћег могућег пута кроз све градове.
- Генерисање комбинаторних објеката према унапред задатим правилима.
Напомена: У свим решењима бавићемо се искључиво алгоритмима, док учитавање и штампање резултата препуштамо читаоцу за вежбу.
Задатак 1
Напиши програм који испитује да ли се у правоуаоном лавиринту може стићи од горњег левог до доњег десног угла.
Улаз: Са стандардног улаза се учитавају димензије лавиринта и раздвојене једним размаком. Након тога се учитава матрица којом је представљен лавиринт. Поља кроз која се може проћи су обележена бројем , а поља на којима је препрека бројем .
Излаз: На стандардни излаз исписати da ако пут постоји тј. ne ако пут не постоји.
Решење
Задатак решавамо исцрпном претрагом свих могућих путања. Претрагу свих могућих путања можемо да организујемо на један од два популарна начина:
- Претрагом у дубину (енгл. Depth First Search, DFS) - Претрага у дубину се може поистоветити са кореном биљке који копа све дубље у потрази за водом. Корен ће копати све дубље и дубље, без гранања и разматрања алтернатива, све док не удари у камен. У пракси, то значи да чим наиђемо на дозвољени потез у текућој позицији одмах га извршавамо и прелазимо у нову позицију, без разматрања осталих потенцијално дозвољених потеза.
- Претрага у ширину (енгл. Breadth First Search, BFS) - Претрага у ширину се може поистоветити са поплавом која креће из угла просторије. Вода ће постепено у концентричним круговима освајати просторију, што поистовећујемо са разматрањем свих суседа на једном нивоу, пре него што пређемо на следећи. У пракси, то значи да ћемо из текуће позиције прво размотрити све могуће потезе, пре него што пређемо у наредно стање.
БФС и ДФС су најпопуларнији видови претрага, али нису једини. Да би се претрага успешно имплементирала потребно је пажљиво одредити околине, тј. суседе текуће позиције. Када се ради о кретању кроз матрицу, што је случај са лавиринтом, најчешће се користи појам повезаности. У општем случају, повезаност може бити:
-4-повезаност - За дато поље у матрици суседима сматрамо поља која су горе, десно, доле и лево у односу на текућe поље. У терминима координата то ће редом бити поља , , и . Шематски, то можемо приказати на следећи начин:
-8-повезаност - За дато поље у матрици суседима сматрамо поља која су горе, горе десно, десно, доле десно, доле, доле лево, лево и горе лево у односу на текућe поље. У терминима координата то ће редом бити поља , , , , , , и . Шематски, то можемо приказати на следећи начин:
У пракси, суседна поља се најчешће приказују само низом који представља разлике координата, што нам омогућава да у имплементацији алгоритма системаски пролазимо кроз све суседе на исти начин, независно од тога колико их има и како су организовани. Редослед суседа одређује којим редом обилазимо поља матрице.
Претрагу у дубину можемо остварити помоћу рекрузивне функције. Функција прима матрицу препрека и поље на ком се тренутно налазимо, које се мења током рекурзије. Ако се стартно поље поклапа са циљним (доњим десним углом), пут је успешно пронађен. У супротном, испитујемо 4 суседа стартног поља и претрагу рекурзивно настављамо из сваког од њих ако је то могуће. Дакле, потребно је да имамо метод којим можемо да проверимо да ли сусед кандидат постоји. Ако постоји прелазимо на суседно поље и рекурзивно настављамо поступак. Ако се на пољу на које смо прешли налази препрека, претрагу прекидамо, јер тај корак није дозвољен, па функција враћањем говори да тим путем није могуће пронаћи пут. Потребно је и да обезбедимо да се већ посећена стартна поља не обрађују поново и за то користимо помоћну матрицу у којој за свако поље региструјемо да ли је посећено или није. Ако приликом позива функције установимо да је поље на које смо дошли већ раније посећено, претрагу одмах прекидамо, док у супротном означавамо да је то поље посећено и прелазимо на анализу њега и његових суседа.
// дефинишемо листу суседа
static int[,] susedi = new int[4,2] {
{-1,0}, {0,1}, {1,0}, {0,-1}
};
// помоћна функција која испитује да ли је поље у матрици
static bool u_matrici(int[,] mat, int i, int j)
{
// издвајамо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// проверавамо да ли су индекси у дозвољеном опсегу
if (0 <= i && i < m && 0 <= j && j < n)
return true;
return false;
}
static bool DFS(int[,] mat, int i, int j, int ei, int ej, bool[,] poseceni)
{
// ако смо ударили у зид или ако смо поље већ посетили
// прекидамо претрагу, јер не води ка излазу
if (mat[i,j] == 0 || poseceni[i,j])
return false;
// ако смо стигли до краја, нашли смо излаз
if (i == ei && j == ej)
return true;
// обележавамо поље као посећено
poseceni[i,j] = true;
// проверавамо све суседе
for (int k = 0; k < susedi.GetLength(0); k++)
{
// одређујемо координате суседа
int ii = i + susedi[k,0];
int jj = j + susedi[k,1];
// ако је сусед у матрици и води ка излазу из лавиринта
if (u_matrici(mat, ii, jj) && DFS(mat, ii, jj, ei, ej, poseceni))
{
// прекидамо претрагу и шаљемо сигнал да смо нашли излаз
return true;
}
}
// ако ниједан сусед не води ка излазу, прекидамо претрагу из текућег
// поља и враћамо се на претходно поље.
return false;
}
static bool postoji_put(int[,] mat, int si, int sj, int ei, int ej)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// креирамо помоћну матрицу у којој одржавамо која смо
// поља посетили током обиласка
bool[,] poseceni = new bool[m,n];
// претрагом у дубину одређујемо да ли постоји пут или не
return DFS(mat, si, si, ei, ej, poseceni);
}Претрага у дубину се може имплементирати и итеративно уз помоћ структуре података Stack<>. На стеку ћемо чувати тренутно стање претраге, тј. координате поља која су део текућег пута. У итеративној имплементацији ћемо користити већ дефинисан низ susedi и помоћни метод u_matrici(). Итеративна имплементација је у наставку:
static bool DFS(int[,] mat, int si, int sj, int ei, int ej)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// креирамо помоћну матрицу у којој одржавамо која смо
// поља посетили током обиласка
bool[,] poseceni = new bool[m,n];
// креирамо празан стек
Stack<Tuple<int,int>> stek = new Stack<Tuple<int,int>>();
// додајемо почетно поље на стек
stek.Push(Tuple.Create(si, sj));
// и обележавамо га као посећено
poseceni[si, sj] = true;
// све док постоји барем један елемент на стеку
while (stek.Count > 0)
{
// скидамо га са врха стека и реконструишемо координате
Tuple<int,int> koord = stek.Pop()
int i = koord.Item1;
int j = koord.Item2;
// ако смо стигли до излаза, прекидамо претрагу
if (i == ei && j == ej)
return true;
// ако нисмо, испитујемо његове суседе
for (int k = 0; k < susedi.GetLength(0); k++)
{
int ii = i + susedi[k, 0];
int jj = j + susedi[k, 1];
// ако је сусед у матрици, није зид и није већ посећен
if (u_matrici(mat, ii, jj) && mat[ii,jj] == 1 && !poseceno[ii, jj])
{
// обележавамо поље као посећено
poseceno[ii,jj] = true;
// и додајемо га на стек
stek.Push(Tuple.Create(ii, jj));
}
}
}
// ако смо испразнили стек, нисмо нашли пут
return false;
}Уместо претраге у дубину, могуће је употребити и претрагу у ширину. Имплементација је веома слична нерекурзивно имплементираној претрази у дубину, при чему се уместо стека користи ред, чиме се постиже да се поља обрађују у редоследу њиховог растојања од полазног поља, што омогућава да се лако очита и дужина најкраћег пута до крајњег поља. У итеративној имплементацији ћемо користити већ дефинисан низ susedi и помоћни метод u_matrici(). Итеративна имплементација је у наставку:
static bool BFS(int[,] mat, int si, int sj, int ei, int ej)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// креирамо помоћну матрицу у којој одржавамо која смо
// поља посетили током обиласка
bool[,] poseceni = new bool[m,n];
// креирамо празан ред
Queue<Tuple<int,int>> red = new Queue<Tuple<int,int>>();
// додајемо почетно поље у ред
red.Enqueue(Tuple.Create(si, sj));
// и обележавамо га као посећено
poseceni[si, sj] = true;
// све док постоји барем један елемент у реду
while (red.Count > 0)
{
// скидамо га са врха реда и реконструишемо координате
Tuple<int,int> koord = red.Dequeue()
int i = koord.Item1;
int j = koord.Item2;
// ако смо стигли до излаза, прекидамо претрагу
if (i == ei && j == ej)
return true;
// ако нисмо, испитујемо његове суседе
for (int k = 0; k < susedi.GetLength(0); k++)
{
int ii = i + susedi[k, 0];
int jj = j + susedi[k, 1];
// ако је сусед у матрици, није зид и није већ посећен
if (u_matrici(mat, ii, jj) && mat[ii,jj] == 1 && !poseceno[ii, jj])
{
// обележавамо поље као посећено
poseceno[ii,jj] = true;
// и додајемо га у ред
red.Enqueue(Tuple.Create(ii, jj));
}
}
}
// ако смо испразнили стек, нисмо нашли пут
return false;
}Имплементације које смо написали омогућавају испитивање да ли пут постоји. Мећутим, често нам поред информације да ли решење постоји, треба и начин како да до тог решења дођемо. Прецизније, након што утврдимо да излаз из лавиринта постоји, требало би да можемо и да реконструишемо пут. Да би се пут реконструисао, треба да се понашамо као Ивица и Марица и да током истраживања простора претраге памтимо које смо потезе предузели у ком тренутку.
Да бисмо то постигли потребно је да поред матрице посећених поља чувамо и матрицу родитеља. Током обиласка ћемо у свако поље да упишемо које је његово родитељско поље, тј. из којег поља смо у текуће поље дошли. Ради једноставности, пољима можемо да доделимо редне бројеве почевши од један полазећи од горњег левог ћошка матрице слева на десно одозго на доле. Други начин да ово постигнемо јесте да у сваком пољу памтимо коју смо акцију предузели.
Реконструкција путева одређених помоћу ДФС-а уз помоћ матрице родитеља је у наставку:
static <Tuple<int, int>[] rekonstruisi_put(int[] roditelji, int si, int sj, int ei, int ej)
{
// памтимо димензије матрице
int m = roditelji.GetLength(0);
int n = roditelji.GetLength(1);
// креирамо празан стек
Stack<Tuple<int,int>> stek = new Stack<Tuple<int,int>>();
// крећемо од последњег поља
int i = ei, j = ej;
// додајемо последњи елемент на стек
stek.Push(Tuple.Create(i, j));
// све док постоји родитељ
while (roditelji[i,j] != -1)
{
// одређујемо родитеља текуће позиције
int pi = roditelji[i,j] / n;
int pj = roditelji[i,j] % n;
// додајемо родитеља на стек
stek.Push(Tuple.Create(pi, pj));
// родитељ постаје текућа позиција за наредну итерацију
i = pi;
j = pj;
}
// враћамо низ позиција које чине наш пут
return stek.ToArray();
}
static bool DFS(int[,] mat, int i, int j, int ei, int ej, bool[,] poseceni, int[,] roditelji, int roditelj)
{
// ако смо ударили у зид или ако смо поље већ посетили
// прекидамо претрагу, јер не води ка излазу
if (mat[i,j] == 0 || poseceni[i,j])
return false;
// ако смо стигли до краја, нашли смо излаз
if (i == ei && j == ej)
return true;
// обележавамо поље као посећено
poseceni[i,j] = true;
// памтимо родитеља текуће позиције
roditelji[i,j] = roditelj;
// рачунамо редни број текућег поља, јер је он родитељ својим суседима
int num = i*mat.GetLength(1) + j;
// проверавамо све суседе
for (int k = 0; k < susedi.GetLength(0); k++)
{
// одређујемо координате суседа
int ii = i + susedi[k,0];
int jj = j + susedi[k,1];
// ако је сусед у матрици и води ка излазу из лавиринта
if (u_matrici(mat, ii, jj) && DFS(mat, ii, jj, ei, ej, poseceni, roditelji, num))
{
// прекидамо претрагу и шаљемо сигнал да смо нашли излаз
return true;
}
}
// ако ниједан сусед не води ка излазу, прекидамо претрагу из текућег
// поља и враћамо се на претходно поље.
return false;
}
static bool postoji_put(int[,] mat, int si, int sj, int ei, int ej)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// креирамо помоћну матрицу у којој одржавамо која смо
// поља посетили током обиласка
bool[,] poseceni = new bool[m,n];
// креирамо матрицу родитеља
int[,] roditelji = new int[m,n];
// претрагом у дубину одређујемо да ли постоји пут или не
return DFS(mat, si, si, ei, ej, poseceni, roditelji, -1);
}Реконструкција је увек иста након што конструишемо матрицу родитеља, независно од тога да ли се ради о БФС или ДФС алгоритму претраге. Различити алгоритми најчешће генеришу различите путеве, за излазак из лавиринта, али ако излаз постоји било који од ова два алгоритма ће га сигурно пронаћи. Њихове временске и просторне сложености су идентичне у итеративном случају.
Кориснику за вежбу препуштамо генерисање и реконструкцију путева помоћу БФС-а.
Задатак 2
Написати програм којим се за црно-белу матрицу ( – бела, – црна боја) одређује број белих области. Белу област чине повезана бела поља. Два бела поља су повезана ако су она почетно и крајње поље неког низа белих поља у коме узастопна поља имају заједничку страницу.
Улаз: У првој линији стандардног улаза се учитава број редова матрице (), у другој број колона (). У следећих редова учитава се по бројева чија је вредност или .
Излаз: Број белих области.
Решење
Прво ћемо описати поступак којим можемо обележити једну белу област. Потребно је да у матрици пронађемо прво бело поље уобичајеним проласком кроз матрицу. Када такво поље пронађемо, потребно је да испитамо све његове суседе. Као релацију суседства можемо да користимо 4-повезаност. Чим наиђемо на белог суседа, можемо одмах да пређемо у њега и да рекурзивно обележимо све његове беле суседе. Понављајући овај поступак за сваког суседа обележићемо комплетну белу област. Из овог описа лако се закључује да се ради о претрази у дубину, тј. ДФС алгоритму. Да бисмо одредили колико има белих области, потребно је само да у матрици наставимо претрагу за новим белим необележеним пољем из којег ћемо поново покренути претрагу у дубину. Понављајући ово покретање све док не дођемо до краја матрице обележићемо све беле области. Број белих области биће једнак броју покретања претраге.
Имплементација претраге у дубину је у наставку:
// дефинишемо листу суседа
static int[,] susedi = new int[4,2] {
{-1,0}, {0,1}, {1,0}, {0,-1}
};
// помоћна функција која испитује да ли је поље у матрици
static bool u_matrici(int[,] mat, int i, int j)
{
// издвајамо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// проверавамо да ли су индекси у дозвољеном опсегу
if (0 <= i && i < m && 0 <= j && j < n)
return true;
return false;
}
static void DFS(int[,] mat, int i, int j, bool[,] poseceni)
{
// обележавамо поље као посећено
poseceni[i,j] = true;
// проверавамо све суседе
for (int k = 0; k < susedi.GetLength(0); k++)
{
// одређујемо координате суседа
int ii = i + susedi[k,0];
int jj = j + susedi[k,1];
// ако је сусед у матрици, није обележен и бео је
if (u_matrici(mat, ii, jj) && mat[ii,jj] == 0 && !poseceni[ii,jj])
{
// настављамо обележавање из суседа
DFS(mat, ii, jj, poseceni);
}
}
}
static int broj_belih_oblasti(int[,] mat)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// креирамо помоћну матрицу у којој одржавамо која смо
// поља посетили током обиласка
bool[,] poseceni = new bool[m,n];
// број белих области на старту је нула
int br = 0;
// у петљи тражимо бела необележена поља
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
// ако се ради о непосећеном и белом пољу
if (!posecen[i,j] && mat[i,j] == 0)
{
// обележавамо област која садржи то поље
DFS(mat, i, j, poseceni);
// увећавамо број области
br += 1;
}
}
}
// враћамо број белих области
return br;
}Из претходног задатка смо видели да избор алгоритма претраге не утиче на коначни резултат, па задатак можемо решити и претрагом у ширину. Готово комплетан костур решења остаје непромењен. Потребно је само имплементирати нову функцију BFS() и у линији 53 претходног решења изменити позив DFS() у BFS(). Имплементација претраге у ширину је у наставку:
// дефинишемо листу суседа
static int[,] susedi = new int[4,2] {
{-1,0}, {0,1}, {1,0}, {0,-1}
};
// помоћна функција која испитује да ли је поље у матрици
static bool u_matrici(int[,] mat, int i, int j)
{
// издвајамо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// проверавамо да ли су индекси у дозвољеном опсегу
if (0 <= i && i < m && 0 <= j && j < n)
return true;
return false;
}
static void BFS(int[,] mat, int i, int j, bool[,] poseceni)
{
// креирамо помоћни ред у којем одржавамо текућу област
Queue<Tuple<int,int>> red = new Queue<Tuple<int,int>>();
// стартно поље обележавамо као посећено и додајемо га у ред
poseceni[i,j] = true;
red.Enqueue(Tuple.Create(i, j));
// све док у реду постоји макар и једно поље
while (red.Count > 0)
{
// скидамо поље са врха реда и реконструишемо координате
Tuple<int,int> polje = red.Dequeue();
i = polje.Item1;
j = polje.Item2;
// испитујемо суседе текућег поља
for (int k = 0; k < susedi.GetLength(0); k++)
{
// генеришемо координате суседа
int ii = i + susedi[k,0];
int jj = j + susedi[k,1];
// ако је сусед у матрици, није раније посећен и бео је
if (u_matrici(mat, ii, jj) && mat[ii,jj] == 0 && !poseceni[ii,jj])
{
// обележавамо га као посећеног
poseceni[ii,jj] = true;
// и додајемо га у нашу област
red.Enqueue(Tuple.Create(ii,jj));
}
}
}
}
static int broj_belih_oblasti(int[,] mat)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// креирамо помоћну матрицу у којој одржавамо која смо
// поља посетили током обиласка
bool[,] poseceni = new bool[m,n];
// број белих области на старту је нула
int br = 0;
// у петљи тражимо бела необележена поља
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
// ако се ради о непосећеном и белом пољу
if (!poseceni[i,j] && mat[i,j] == 0)
{
// обележавамо област која садржи то поље
BFS(mat, i, j, poseceni);
// увећавамо број области
br += 1;
}
}
}
// враћамо број белих области
return br;
}На крају, треба приметити да су ДФС и БФС општи приступи у претрази и да се готово увек прилагођавају проблему који решавамо. Избор да ли ћемо користити ДФС или БФС често зависи од структуре решења проблема или од начина на који желимо да обилазимо простор претраге. И један и други алгоритам ће решење сигурно пронаћи ако оно постоји, али пут којим ће доћи до решење се може разликовати.
Задатак 3
Ако је матрицом и дата мапа која изражава зараженост биљног света у некој области, где представља незаражено поље области, а заражено, одредите број поља максималне заражене области. Два заражена поља припадају истој области ако им се странице наслањају једна на другу.
Улаз: У првој линији стандардног улаза се учитава број редова матрице (), у другој број колона (). У следећих редова учитава се по бројева чија је вредност или .
Излаз: Број поља највеће заражене области ( ако нема заражених поља).
Решење
Задатак можемо да решимо слично као и претходни. У овом случају приликом покретања претраге у свакој белој области није довољно само да је обележимо, већ треба да пребројимо колико поља је чине. Логика је врло једноставна. Ако замислимо да смо тренутнo на зараженом пољу у матрици које има само једног зараженог суседа, тада ће укупан број заражених поља у области која почиње у пољу бити за већи од броја заражених поља у области која почиње у његовом зараженом суседу, тј. од оне вредности које ће одредити рекурзивни позив којим прелазимо на суседно поље. Очигледно, описани поступак опет представља претрагу у дубину. Имплементација је у наставку:
// дефинишемо листу суседа
static int[,] susedi = new int[4,2] {
{-1,0}, {0,1}, {1,0}, {0,-1}
};
// помоћна функција која испитује да ли је поље у матрици
static bool u_matrici(int[,] mat, int i, int j)
{
// издвајамо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// проверавамо да ли су индекси у дозвољеном опсегу
if (0 <= i && i < m && 0 <= j && j < n)
return true;
return false;
}
static int DFS(int[,] mat, int i, int j, bool[,] poseceni)
{
// на старту, знамо само да је текуће поље бело
int br_polja = 1;
// обележавамо поље као посећено
poseceni[i,j] = true;
// проверавамо све суседе
for (int k = 0; k < susedi.GetLength(0); k++)
{
// одређујемо координате суседа
int ii = i + susedi[k,0];
int jj = j + susedi[k,1];
// ако је сусед у матрици, није обележен и заражен је
if (u_matrici(mat, ii, jj) && mat[ii,jj] == 0 && !poseceni[ii,jj])
{
// настављамо бројање елемената у области која почиње у суседу
br_polja += DFS(mat, ii, jj, poseceni);
}
}
// на крају укупан број заражених поља у области одговара збиру
// резултат из суседа увећаном за 1
return br_polja;
}
static int broj_polja_u_najvecoj_zarazenoj_oblasti(int[,] mat)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// креирамо помоћну матрицу у којој одржавамо која смо
// поља посетили током обиласка
bool[,] poseceni = new bool[m,n];
// на старту максимум је нула
int br = 0;
// у петљи тражимо заражена необележена поља
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
// ако се ради о непосећеном и зараженом пољу
if (!poseceni[i,j] && mat[i,j] == 0)
{
// покрећемо претрагу и по потреби ажурирамо максимум
br = Math.Max(br, DFS(mat, i, j, poseceni));
}
}
}
// враћамо број поља у највећој зараженој области
return br;
}Као и у претходном задатку, решење се може добити и применом претраге у ширину. Имплементација је у наставку:
// дефинишемо листу суседа
static int[,] susedi = new int[4,2] {
{-1,0}, {0,1}, {1,0}, {0,-1}
};
// помоћна функција која испитује да ли је поље у матрици
static bool u_matrici(int[,] mat, int i, int j)
{
// издвајамо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// проверавамо да ли су индекси у дозвољеном опсегу
if (0 <= i && i < m && 0 <= j && j < n)
return true;
return false;
}
static int BFS(int[,] mat, int i, int j, bool[,] poseceni)
{
// креирамо помоћни ред у којем одржавамо текућу област
Queue<Tuple<int,int>> red = new Queue<Tuple<int,int>>();
// стартно поље обележавамо као посећено и додајемо га у ред
poseceni[i,j] = true;
red.Enqueue(Tuple.Create(i, j));
// број заражених поља у области на старту једнак је почетном пољу
int br_polja = 1;
// све док у реду постоји макар и једно поље
while (red.Count > 0)
{
// скидамо поље са врха реда и реконструишемо координате
Tuple<int,int> polje = red.Dequeue();
i = polje.Item1;
j = polje.Item2;
// испитујемо суседе текућег поља
for (int k = 0; k < susedi.GetLength(0); k++)
{
// генеришемо координате суседа
int ii = i + susedi[k,0];
int jj = j + susedi[k,1];
// ако је сусед у матрици, није раније посећен и заражен је
if (u_matrici(mat, ii, jj) && mat[ii,jj] == 0 && !poseceni[ii,jj])
{
// обележавамо га као посећеног
poseceni[ii,jj] = true;
// и додајемо га у нашу област
red.Enqueue(Tuple.Create(ii,jj));
// са сваким пољем које додамо у ред, увећавамо бројач
br_polja += 1;
}
}
}
// враћамо број поља у области
return br_polja;
}
static int broj_polja_u_najvecoj_zarazenoj_oblasti(int[,] mat)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// креирамо помоћну матрицу у којој одржавамо која смо
// поља посетили током обиласка
bool[,] poseceni = new bool[m,n];
// на старту максимум је нула
int br = 0;
// у петљи тражимо необележена заражена поља
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
// ако се ради о непосећеном и зараженом пољу
if (!poseceni[i,j] && mat[i,j] == 0)
{
// покрећемо претрагу и по потреби ажурирамо максимум
br = Math.Max(br, BFS(mat, i, j, poseceni));
}
}
}
// враћамо број поља у највећој зараженој области
return br;
}Задатак 4
Напиши програм који приказује садржај поља у игрици Minesweeper након отварања једног поља.
Улаз: У првој линији стандардног улаза се учитава број редова матрице (), у другој број колона (). У следећих редова учитава се по бројева чија је вредност између и , при чему означава бомбу. У наредном реду се учитавају координате поља које се отвара (број врсте и број колоне између раздвојени једним размаком).
Излаз: На стандардни излаз исписати стање које се кориснику приказује након отварања тог поља. Ако је на пољу бомба, исписати boom. У супротном приказати матрицу димензије тако да се на неотвореним пољима приказује x, на празним пољима (пољима која су отворена и немају бомби у околини) приказује ., а на отвореним пољима која имају бомбе у околини приказује број бомби у околини.
Решење
Игрица као околину сваког поља поставља 8-повезаност, што повлачи да и ми у решење задатка треба да за суседе узмемо свих 8 поља из околине. Да бисмо отворили целу област, потребно је да из сваког поља прво отворимо све његове безбедне суседе на растојању 1, затим отварамо све безбедне суседе на растојању два итд., све док не стигнемо до руба области. Руб области чине или ивице матрице којом је игра представљена или поља која су обележена позитивним бројевима, тј. поља у чијој се околини налазе мине. Из описа поступка лако се може закључити да се ради о претрази у ширину. Имплементација претраге у ширину је у наставку:
// дефинишемо листу суседа (8-повезаност)
static int[,] susedi = new int[,]{
{-1,-1}, {-1,0}, {-1,1},
{0, -1}, {0,1},
{1,-1}, {1,0}, {1,1}
};
// помоћна функција која испитује да ли је поље у матрици
static bool u_matrici(int[,] mat, int i, int j)
{
// издвајамо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// проверавамо да ли су индекси у дозвољеном опсегу
if (0 <= i && i < m && 0 <= j && j < n)
return true;
return false;
}
static void BFS(int[,] mat, int i, int j, bool[,] poseceni)
{
// помоћни ред у којем чувамо текућу област
Queue<Tuple<int, int>> red = new Queue<Tuple<int, int>>();
// додајемо текући елемент у ред
red.Enqueue(Tuple.Create(i, j));
// све док у реду постоји макар један елемент
while (red.Count > 0)
{
// реконструишемо координате
Tuple<int, int> polje = red.Dequeue();
i = polje.Item1;
j = polje.Item2;
// ако поље није празно, не разматрамо његове суседе (граница области)
if (mat[i, j] > 0)
continue;
// ако је празно, проверавамо све суседе
for (int k = 0; k < susedi.GetLength(0); k++)
{
// одређујемо координате суседа
int ii = i + susedi[k, 0];
int jj = j + susedi[k, 1];
// ако је сусед у матрици, није оболежен и није бомба
if (uMatrici(ii, jj) && !poseceni[ii,jj] && mat[ii,jj] != -1)
{
// обележавамо га
poseceni[ii,jj] = true;
// и додајемо га у ред
red.Enqueue(Tuple.Create(ii, jj));
}
}
}
}
static bool minsweeper_otvaranje(int[,] mat, int i, int j)
{
// проверавамо да ли се ради о бомби
if (mat[i,j] == -1)
return false;
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// креирамо помоћну матрицу у којој одржавамо која смо
// поља посетили током обиласка
bool[,] poseceni = new bool[m,n];
// отварамо област која није под минама
BFS(mat, i, j, poseceni);
return true;
}Задатак се може урадити и претрагом у дубину, али то препуштамо читаоцу за вежбу.
Задатак 5
Дата је матрица у којој се налазе мине означене са , остала поља садрже природне бројеве. Треба из било ког поља у првој колони доћи на било које поље у последњој колони матрице безбедним путем. Пут је безбедан ако не садржи мину и не садржи поље коме је сусед, горњи, доњи, леви или десни, мина. Кроз матрицу можемо да се крећемо у четири правца: горе, доле, десно и лево и при томе на једно поље можемо стати највише једанпут. Одредити максимални збир бројева који се могу наћи на неком безбедном путу од прве до последње колоне.
Улаз: Прва линија стандардног улаза садржи димензије матрице, два природна броја, и (). На стандардном улазу у следећих линија налазе се по целих бројева већих или једнаких , бројеви су одвојени са по једним бланко карактером, и представљају редом елементе матрице.
Излаз: На стандардном излазу приказати природан број који представља максималну суму безбедног пута од прве до последње колоне. Ако безбедан пут не постоји приказати .
Решење
У фази претпроцесирања у матрици ћемо обележити сва небезбедна поља. То можемо урадити тако што ћемо анализирати сваки елемент матрице и за сваку мину коју нађемо, обележићемо њена 4 суседна поља на којима није мина као небезбедна.
Дефинисаћемо рекурзивну функцију која одређује максимални збир бројева на путањи од датог текућег поља до неког поља у последњој колони матрице. Максимум иницијализујемо на , чиме наглашавамо да путања до последње колоне још није пронађена. Ако се текуће поље налази у последњој колони, тада ажурирамо максимум на вредност текућег поља, али не враћамо коначан резултат, јер је могуће да се још померамо и дођемо на неко друго поље на десној ивици. На пример, можемо се померити горе или доле и да и даље останемо у последњој колони. Након ажурирања вредности текућег поља, анализирамо његова четири суседна поља. Рекурзивно израчунавамо резултат за свако од суседних поља и максимум ажурирамо ако пронађемо да је са неког од њих било могуће стићи до десне ивице преко неке путање која има већи збир од текућег максимума. При том морамо да водимо рачуна да се не враћамо на поља која смо посетили (што можемо постићи тако што памтимо већ посећена поља било у посебној матрици, било модификујући вредности у полазној матрици).
Напоменимо да је због мноштва потенцијалних путања описани рекурзивни алгоритам веома неефикасан. Имплементација је у наставку:
// дефинишемо листу суседа (4-повезаност)
static int[,] susedi = new int[4,2] {
{-1,0}, {0,1}, {1,0}, {0,-1}
};
// помоћна функција која испитује да ли је поље у матрици
static bool u_matrici(int[,] mat, int i, int j)
{
// издвајамо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// проверавамо да ли су индекси у дозвољеном опсегу
if (0 <= i && i < m && 0 <= j && j < n)
return true;
return false;
}
// помоћна функција која обележава небезбедна поља
static void obelezi_nebezbedna(int[,] mat)
{
// тражимо мине у матрице
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
// ако је поље мина
if (mat[i,j] == 0)
{
// сваког његовог суседа обелажавамо као небезбедног
for (int k = 0; k < susedi.GetLength[0]; k++)
{
// реконструишемо координате суседа
int ii = i + susedi[k,0];
int jj = j + susedi[k,1];
// ако је сусед у матрици и није мина, обележавамо га као
// небезбедног
if (u_matrici(mat, ii, jj) && mat[ii,jj] != 0)
{
mat[ii,jj] = -1;
}
}
}
}
}
}
static int DFS(int[,] mat, int i, int j, bool[,] poseceni)
{
// одређујемо величину матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// на старту, максимални пут је -1
int maks = -1;
// ако се налазимо у последњој колони, тада је максимални пут
// једнак вредности поља на којем стојимо
if (j == n - 1)
maks = mat[i,j];
// обележавамо текуће поље као посећено
poseceni[i,j] = true;
// проверавамо све суседе текућег поља
for (int k = 0; k < susedi.GetLength(0); k++) {
// рекунструишемо координате
int ii = i + susedi[k,0];
int jj = j + susedi[k,1];
// ако је сусед у матрици, није обележен и безбедно је поље
if (u_matrici(mat, ii, jj) && !poseceni[ii, jj] && mat[ii,jj] > 0)
{
// одређујемо збир пута од суседа до краја
int put = DFS(mat, ii, jj, poseceni);
// ако пут постоји, упоређујемо га са максимумом
// и ажурирамо по потреби
if (put != -1)
maks = Math.Max(maks, put + mat[i,j]);
}
}
// након што смо проверили сва путеве који садрже текуће поље
// обележавамо га као непосећено, да би могло да буде део неких других путева
poseceni[i,j] = false;
// на крају враћамо пут највећег збира
return maks;
}
static int odredi_najveci_zbir_bezbednog_puta(int[,] mat)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// обележавамо небезбедна поља
obelezi_nebezbedna(mat);
// на старту не знамо да ли пут постоји
int maks = -1;
// покрећемо претрагу из сваког поља у првој колони
for (int i = 0; i < m; i++)
{
// ако је поље безбедно
if (mat[i, 0] > 0)
{
// помоћна матрица у којој чувамо информације о посећеним пољима
// дуж пута
bool[] poseceni = new bool[m,n];
// одређујемо пут највећег збира до последње колоне
int put = (mat, i, j, poseceni);
// и по потреби ажурирамо максимум
if (put != -1)
maks = Math.Max(maks, put);
}
}
// враћамо највећи збир од прве до последње колоне
return maks;
}Задатак 6
Испред тебе се налази необична стаза. Стаза се састоји од поља задатих матрицом и свако поље је обојено једном од боје (црвена поља су обележена бројем , плава бројем , жута бројем и зелена бројем ). Правила кретања су таква да се мора поћи са црвеног поља, са црвеног поља се може прећи само на плаво, са плавог на жуто, са жутог на зелено и са зеленог на црвено (мора се поћи са броја и током кретања бројеви морају бити ). Напиши програм који одређује да ли се од доњег реда стазе може стићи до горњег.
Улаз: Са стандардног улаза се уносе димензије стазе и (), раздвојене размаком. Након тога се уноси матрица попуњена бројевима од до .
Излаз: На стандардни излаз исписати da, ако пут постоји тј. ne, ако пут не постоји
Решење
Задатак решавамо рекурзивном претрагом у дубину. Рекурзивна функција прима поље на којем се тренутно налазимо. Ако се оно налази у највишој врсти, пут је успешно пронађен. У супротном, анализирамо суседна поља која раније нисмо посетили (посете региструјемо посебном матрицом) а на којима се налази наредни број и померамо се на свако од њих (чим се за неко одреди да успешно води до врха, можемо прекинути даље испитивање). Ако бројеве приликом учитавања пребацимо на бројеве од до , онда проверу да ли је следећи број одговарајући можемо извршити тако што проверимо да ли се на том следећем пољу налази број који се од тренутног добија увећањем за један и проналажењем остатка при дељењу са (тј. бројем боја).
Описани поступак подразумева 4-повезаност и представља претрагу у дубину. Имплементација је у наставку:
// дефинишемо листу суседа (4-повезаност)
static int[,] susedi = new int[4,2] {
{-1,0}, {0,1}, {1,0}, {0,-1}
};
// помоћна функција која испитује да ли је поље у матрици
static bool u_matrici(int[,] mat, int i, int j)
{
// издвајамо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// проверавамо да ли су индекси у дозвољеном опсегу
if (0 <= i && i < m && 0 <= j && j < n)
return true;
return false;
}
static bool DFS(int[,] mat, int i, int j, bool[,] poseceni)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// ако је текуће поље на врху, онда смо нашли излаз
if (i == 0)
return true;
// обележавамо текуће поље као посећено
poseceni[i,j] = true;
// проверавамо све његове суседе
for (int k = 0; k < susedi.GetLength(0); k++)
{
// реконструишемо координате суседа
int ii = i + susedi[k,0];
int jj = j + susedi[k,1];
// ако поље задовољава услове преласка
if (u_matrici(mat, ii, jj) && !poseceni[ii,jj] &&
mat[ii,jj] == (mat[i,j] + 1) %4 && DFS(mat, ii, jj, poseceni))
{
return true;
}
}
// ако не постоји излаз из суседа, онда ослобађамо поље
// за неки наредни пут
poseceni[i,j] = false;
// ако ниједан сусед не води до врха, онда не постоји пут из текућег поља
return false;
}
// у решењу подразумевамо да су бројеви 1-4 пресликани на 0-3
static bool postoji_obojeni_put(int[,] mat)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// помоћна матрица у којој чувамо поља посећена у текућем путу
bool[] poseceni = new bool[m,n];
// проверавамо поља у последњем реду
for (int j = 0; j < n; j++)
{
// ако поље има вредност 1 и постоји пут од њега до врха
// прекидамо претрагу
if (mat[m-1,j] == 1 && DFS(mat, m-1, j, poseceni))
return true;
}
// ако проверимо сва поља, тада нисмо нашли пут
return false;
}Задатак 7
Лоптица се испушта са висине и пада кроз простор испуњен препрекама. Када испод ње нема препрека, она пада директно наниже. Када је препрека испод ње, она се зауставља и тада је можемо гурнути било лево, било десно до ивице препреке, након чега она наставља да пада. Напиши програм који одређује да ли лоптица може да дође до дна.
Улаз: Са стандардног улаза се учитавају прво бројеви и као димензије матрице, затим се у редова уности по поља матрице. Слободно поље је означено са , а заузето поље са .
Излаз: На стандардни излаз исписати da ако лоптица може да падне до дна тј. ne ако не може.
Решење
Решење градимо рекурзивном претрагом у дубину. Рекурзивна функција која испитује да ли лоптица може да падне до дна прима матрицу препрека и тренутни положај лоптице. На почетку функције проверавамо да ли се лоптица налази у последњој врсти и ако се налази, враћамо информацију да је лоптица пала. У супротном, проверавамо да ли се испод лоптице налази препрека. Ако се не налази, тада лоптицу померамо наниже и враћамо резултат који нам врати рекурзивни позив за тако померену лоптицу. Ако се налази, тада вршимо два рекурзивна позива - један у коме лоптицу померамо налево, а други за који лоптицу померамо надесно. Ако нам било који од њих јави да је лоптица пала до дна, враћамо вредност тачно, а у супротном враћамо вредност нетачно. Да бисмо избегли да се лоптица стално помера лево-десно, у помоћној матрици памтимо посећена поља и ако је неко поље већ посећено, прескачемо рекурзивни позив (на уласку у функцију у помоћној матрици записујемо да је тренутно поље посећено).
// помоћна функција која испитује да ли је поље у матрици
static bool u_matrici(int[,] mat, int i, int j)
{
// издвајамо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// проверавамо да ли су индекси у дозвољеном опсегу
if (0 <= i && i < m && 0 <= j && j < n)
return true;
return false;
}
static bool DFS(int[,] mat, int i, int j, bool[,] poseceni)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// ако смо стигли до последњег реда, лоптица је пала
if (i == m-1)
return true;
// обележавамо поље као посећено
poseceni[i,j] = true;
// ако лоптица може да пређе на поље испод
// рекурзивно испитујемо поље испод
if (i < && mat[i + 1,j] == 0)
return DFS(mat, i+1, j, poseceni)
// испитујемо лево поље
if (j > 0 && mat[i,j-1] != 1 && !posecen[i,j-1] && DFS(mat, i, j-1, poseceni))
return true;
// испитујемо десно поље
if (j < n && mat[i,j+1] != 1 && !posecen[i, j+1] && DFS(mat, i, j+1, posecen))
return true;
// обележавамо поље као слободно за неки други пут
poseceni[i,j] = false;
// ако нисмо нашли пут у суседима, пута нема
return false;
}
static bool moze_da_padne(int[,] mat) {
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// помоћна матрица у којој чувамо поља посећена у текућем путу
bool[] poseceni = new bool[m,n];
// проверавамо поља у првом реду
for (int j = 0; j < n; j++)
{
// ако поље има вредност 1 и постоји пут од њега до врха
// прекидамо претрагу
if (mat[0,j] == 0 && DFS(mat, m-1, j, poseceni))
return true;
}
// ако проверимо сва поља, тада нисмо нашли пут
return false;
}Задатак 8
Напиши програм који попуњава Судоку загонетку чији је циљ да се у матрицу димензије пута распореде бројеви од до , тако да у свакој врсти, у свакој колони и у сваком од квадрата димензије пута сви бројеви буду различити.
Улаз: Са стандардног улаза се учитава матрица димензије пута у којој су већ уписани неки бројеви, а на пољима која су празна уписана је нула.
Излаз: На стандардни излаз исписати решење загонетке или - ако решење за задати улаз не постоји.
Решење
Задатак решавамо бектрекингом тј. рекурзивно имплементираном претрагом у дубину. Рекурзивна функција уз матрицу која се попуњава добија и редни број поља које треба попунити (она враћа информацију о томе да ли је матрицу било могуће потпуно попунити). Попуњавање креће од горњег левог угла и тече врсту по врсту, све док не попунимо целу матрицу. Координате поља се веома једноставно могу одредити на основу његовог редног броја. Ако је тренутно поље већ попуњено (јер су у старту нека поља већ попуњена), тада одмах прелазимо на наредно поље. У супротном проверавамо све могуће вредности за то поље. Након уписа вредности проверавамо да ли је тиме направљен неки конфликт тј. да ли се десило да је у истој врсти, у истој колони или у истом квадрату већ постојао број који је уписан. Ако јесте, претрагу прекидамо, а ако није, настављамо је даље, попуњавањем наредног поља. Чим неки од рекурзивних позива успе да попуни целу матрицу, претрага се прекида и наредни рекурзивни позиви се не врше.
static bool konflikt(int[,] mat, int i, int j)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// провера колоне
for (int k = 0; k < n; k++)
if (k != i && mat[i,j] == mat[k,j])
return true;
// провера реда
for (int k = 0; k < m; k++)
if (k != j && mat[i,j] == mat[i,k])
return true;
// провера квадрата
int x = (i/3)*3, y = (j/3)*3;
for (int k = startI; k < startI + 3; k++)
{
for (int l = startJ; l < startJ + 3; l++)
{
if (mat[k,l] == mat[i,j] && k != i && l != j)
{
return true;
}
}
}
// ако прођу све провере, нема конфликта
return true;
}
static bool sudoku(int[,] mat, int i, int j)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// ако је поље већ иницијализовано
if (mat[i,j] != 0)
{
// ако смо стигли до последњег поља, онда је судоку решен
if (i == m - 1 && j == n - 1)
return true;
// ако није последње поље, прелазимо на наредно
j++;
// прелазимо у наредни ред, ако смо прошли кроз све колоне
if (j >= 0)
{
i++;
j = 0;
}
// рекурзивно решавамо судоку од наредног поља
return sudoku(mat, i, j);
}
// ако је поље слободно
else
{
// покушавамо на то поље да поставимо сваки број
for (int k = 1; k < 10; k++)
{
// постављамо број
mat[i,j] = k;
// ако нема конфликта
if (!konflikt(mat, i, j))
{
// рекурзивно решавамо судоку и ако га решимо,
// прекидамо претрагу
if (sudoku(mat, i, j))
return true;
}
// ресетујемо поље на нула, ако претрага није била успешна
mat[i,j] = 0;
}
// ако ниједан број није решење, онда се враћамо назад
return false;
}
}Задатак 9
Латински квадрат димензије садржи бројеве од до распоређене тако да су у свакој врсти и у свакој колони сви елементи различити. Напиши програм који дати делимично попуњени квадрат на све начине попуњава до латинског квадрата.
Улаз: Са стандардног улаза се учитава димензија (), а затим и елементи квадрата (празна поља су обележена цифром ).
Излаз: На стандардни излаз исписати све латинске квадрате (иза сваког написати празну линију).
Решење
Задатак решавамо рекурзивном претрагом у дубину (слично као у задатку Судоку). Дефинишемо рекурзивну процедуру која ће да испише сва решења. Уз матрицу која се попуњава добија се и редни број поља које треба попунити. Попуњавање креће од горњег левог угла и тече врсту по врсту, све док не попунимо целу матрицу (када је цела матрица попуњена, процедура је исписује, али се претрага након тога наставља да би се пронашла сва решења). Координате поља се веома једноставно могу одредити на основу његовог редног броја. Ако је тренутно поље већ попуњено (јер су у старту нека поља већ попуњена), тада одмах прелазимо на наредно поље. У супротном проверавамо све могуће вредности за то поље. Након уписа вредности проверавамо да ли је тиме направљен неки конфликт тј. да ли се десило да је у истој врсти или у истој колони већ постојао број који је уписан. Ако јесте, претрагу прекидамо, а ако није, настављамо је даље, попуњавањем наредног поља.
static bool konflikt(int[,] mat, int i, int j)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// провера колоне
for (int k = 0; k < m; k++)
if (i != k && mat[i,j] == mat[k, j])
return true;
// провера врсте
for (int k = 0; k < n; k++)
if (j != k && mat[i,j] == mat[i,k])
return true;
// ако прођу све провере, онда нема конфликта
return true;
}
static void latinski_kvadrati(int[,] mat, int i, int j)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// ако је поље заузето
if (mat[i,j] != 0)
{
// ако смо стигли до последњег поља, квадрат је попуњен
if (i == m - 1 && j == n - 1)
{
// приказујемо попуњени квадрат
for (int k = 0; k < m; k++)
{
for (int l = 0; l < n; l++)
{
Console.WriteLine("{0,6} ", mat[k,l]);
}
Console.WriteLine();
}
}
// ако нисмо стигли до последњег поља
else
{
// прелазимо на наредно
j++;
// ако смо прошли кроз цео ред, прелазимо на наредни
if (j >= n)
{
j = 0;
i += 1;
}
// рекурзивно попуњавамо квадрат
latinski_kvadrati(mat, i, j);
}
}
// ако није
else
{
// пролазимо кроз све могуће вредности
for (int k = 1; k <= n; k++)
{
// уписујемо их у поље
mat[i,j] = k;
// ако нема конфликта, рекурзивно попуњавамо латински квадрат
if (!konflikt(mat, i, j))
latinski_kvadrati(mat, i, j);
// поништавамо уписани број
mat[i,j] = 0;
}
}
}Задатак 10
Напиши програм који одређује све могуће обиласке шаховске табле дате димензије скакачем. Скакач креће из горњег левог угла табле, у сваком кораку се креће у облику ћириличног слова Г, два поља хоризонтално и једно вертикално или два поља вертикално и једно хоризонтално и током обиласка свако поље на табли посећује тачно једном.
Улаз: Са стандардног улаза се уносе димензије табле ().
Излаз: На стандардни излаз исписати све могуће редоследе обиласка поља (у произвољном редоследу). Бро- јање поља започети од . Сваки број исписати са два карактера (испред једноцифрених додати размак) и иза сваког броја одштампати размак. Након сваког успешног обиласка исписати и један празан ред.
Решење
Задатак се може решити претрагом са повратком (бектрекингом), по узору на технике које смо користили приликом генерисања комбинаторних објеката. Парцијално решење у сваком кораку проширујемо тако што одређујемо све могуће начине да скакач пређе са текућег на наредно поље. За то је потребно да знамо које је поље већ обиђено, а које је слободно. Пошто ћемо желети да решења прикажемо у неком прегледном облику, можемо одржавати матрицу у којој ћемо на непосећеним пољима чувати нуле, а на посећеним пољима редне бројеве потеза када је то поље посећено. Током обиласка одржаваћемо и редни број тренутног потеза. Дефи- нисаћемо рекурзивну функцију чији је задатак да прошири започети обилазак тиме што ће се наредни потез чији је редни број дат одиграти на поље чије су координате такође дате. Претпоставићемо да ће функција бити позивана само ако смо сигурни да тај потез може бити одигран. Након одигравања потеза, провераваћемо да ли је табла комплетно попуњена (то можемо једноставно открити на основу димензија табле и редног броја одиграног потеза) и ако јесте, исписиваћемо пронађено решење. Ако није, бираћемо наредни потез тако што анализирамо све могуће потезе скакача, проверавати који је могуће одиграти (који води на неко непопуњено поље у оквирима табле) и позиваћемо рекурзивно функцију да настави обилазак од тог поља.
// дефинишемо околину, тј. дозвољене потезе
static int[,] susedi = new int[,] {
{-1, -2}, {-1, 2}, {1, -2}, {1, 2},
{-2, -1}, {-2, 1}, {2, -1}, {2, 1}
};
// помоћна функција која испитује да ли је поље у матрици
static bool u_matrici(int[,] mat, int i, int j)
{
// издвајамо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// проверавамо да ли су индекси у дозвољеном опсегу
if (0 <= i && i < m && 0 <= j && j < n)
return true;
return false;
}
static void skakaceva_tura(int[,] mat, int i, int j, int broj_poteza)
{
// одређујемо димензије матрице
int m = mat.GetLength(0);
int n = mat.GetLength(1);
// на поље уписујемо редни број потеза
mat[i,j] = broj_poteza;
// ако смо одиграли последњи потез, попунили смо таблу
if (potez == n*m)
{
// приказујемо попуњену таблу
for (int k = 0; k < m; k++)
{
for (int l = 0; l < n; l++)
{
Console.WriteLine("{0,6} ", mat[k,l]);
}
Console.WriteLine();
}
}
// проверавамо све суседе
for (int k = 0; k < susedi.GetLength(0); k++)
{
// реконструишемо координате суседа
int ii = i + susedi[k,0];
int jj = j + susedi[k,1];
// ако поље задовољава услове преласка
if (u_matrici(mat, ii, jj) && mat[ii,jj] == 0)
{
skakaceva_tura(mat, ii, jj, broj_poteza + 1);
}
}
// ослобађамо поље за неку наредну туру
mat[i,j] = 0;
}