Analiza

Ovaj problem se može rešiti primenom bektreka (backtracking). Ali da bi se bektrek ubrzao (tj. bio efikasniji), na početku se uradi preprocesiranje u kome se za svako polje na kome se nalaѕi kockica odredi koliko u njegovom susedstvu ima slobodnih polja ili polja na koja je već postavljen top i ako se taj broj poklapa sa brojem na kockici, onda se i na preostala slobodna polja postave topovi. Pri postavljanju topova markiraju se sva slobodna polja do kojih može stići taj top (to će nam kasnije omogućiti efikasnu proveru da li do svakog slobodnog polja može stići neki top). Nakon toga se proveri da li postoji polje na kome se nalazi kockica takvo da je broj susednih polja koja su slobodna ili se na njima nalazi top manji od broja na kockici. Ako takvo polje postoji onda nije moguće rasporediti topove na tu tablu tako da zadovoljavaju sva ograničenja, ispisuje broj ~-1~ i prekida izvršavanje programa. Posle ove pripremne faze započinje se raspoređivanje preostalih topova. To se izvodi tako što se obrađuje jedno po jedno polje table (na primer, vrsta po vrsta). Obrada narednog polja se obavlja pozivom funkcije, koja kao argumente dobija vrstu i kolonu u kojoj se nalazi to polje, a kao rezultat vraća informaciju da li je ostatak table uspešno obrađen/popunjen. Ako je polje koje trenutno obrađujemo zauzeto ili se na njega ne može postaviti top zato što bi onda oko neke kockice bilo previše topova, prelazi se na sledeće polje (tj. poziva funkcija za obradu sledećeg polja). U suprotnom se za to polje probaju dve varijante. Prva varijanta je da se na to polje postavi top, markiraju polja do kojih može stići taj top i nastavi sa obradom sledećeg polja na tabli. Ta obrada se obavlja tako što se rekurzivno poziva funkcija za obradu polja koja kao argumente dobija koordinate (vrstu i kolonu) polja koje se obrađuje. Ako je ostatak table uspešno popunjen, druga varijanta se ne razmatra već se prekida izvršavanje i vraća informacija da je uspešno popunjena tabla. U suprotnom, ako ostatak table nije uspešno popunjen, razmatra se druga varijanta, u kojoj se na to polje ne raspoređuje top, već se prelazi na naredno polje table, tj. rekurzivno poziva funkcija za rešavanje sledećeg polja. Ako se rešavanje ostatka table uspešno završi, onda funkcija vraća informaciju da je ostatak table uspešno rešen, u suprotnom, vraća informaciju da ostatak table nije uspešno rešen. Kada se obrade sva polja table, tj. pozove funkcija za obradu polja koje se nalai vrsti broj ~M+1~ i koloni broj ~1~, proverava se da li je popunjavanje korektno/ispravno: broj topova oko svake kockice se poklapa sa brojem na kockici i do svakog slobodnog polja može stići neki od topova. Ako je popunjavanje table ispravno funkcija vraća informaciju da je tabla popunjena ispravno, u suprotnom, vraća informaciju da tabla nije uspešno popunjena. Da bi se dodtno ubrzao postupak, može se pri svakom pozivu funkcije za obradu polja proveravati da li postoji kockica takva da je zbir broja postavljenih topova na susednim poljima i broja slobodnih susednih polja manji od broja na kockici. Ako takva kockica postoji, nije moguće rasporediti topove prema zahtevima, pa se prekida obrada tog polja i vraća nazad (tj. na obradu prethodnog polja).