Zastanawiam się nad algorytmem do jednego z programów zaliczeniowych, który pozwoliłby w grze w statki zatopić je wszystkie strzelając jak najmniej razy. Czas wykonywania algorytmu nie jest aż tak ważny, głównie liczy się ilość oddanych strzałów. Dane jakie posiadam, to rozmiar planszy (zawsze kwadratowy i nieparzysty), ilość okrętów i ich rozmiar (wszystkie są takie same). Wiadomo jeszcze, że na środku jest kwadrat 3x3, w którym na pewno nie ma statków. Wokół każdego statku jest także jednopunktowy obwód, gdzie również nie ma żadnego z nich.
Myślałem nad wypełnieniem tablicy pewnymi wartościami. 0 - na pewno nie ma statku. W tym przypadku znane punkty wpisze od razu, dopisze następne po zatapianiu kolejnych statków bądź też pudłowaniu. 1 - mogę strzelać, ale tylko gdy "jestem na tropie" statku. 2 - strzelam gdy poszukuję pierwszego punktu jakiegoś statku. Generalnie wypełniłbym kilka punktów zerami i stworzył swego rodzaju siatkę z dwójek wielkości zależnej od długości statków (będąc pewnym, że siatka zawiera przynajmniej 1 punkt każdego ze statków). Od początku gry strzelam po siatce, a gdy znajdę pierwszy punkt, to oczywiście szukam reszty statku, następnie znowu po siatce itd aż do zatopienia wszystkich. Możliwe, że są gdzieś w sieci jakieś informacje na ten temat, przy czym ta wersja jest raczej niestandardowa, więc specjalnie nie szperałem. Może ma ktoś jakiś inny (może prostszy) pomysł?