Potapanje brodova

Potapanje brodova je logička slagalica bazirana na igri . Ova igra se pojavljivala na nekolicini takmičenja, uključujući Svetsko takmičenje u slagalicama^[1], i magazinima o slagalicama, kao što je magazin .^[2]

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=.

Potapanje brodova

Potapanje brodova je nastalo u Argentini, a tvorac je Haime Ponjačik. Igra se prvi put se pojavila 1982. godine u argentinskom magazinu . Potapanje brodova je postalo popularno u celom svetu nakon svoje međunarodne premijere na prvom svetskom šampionatu u slagalicama u Njujorku 1992. Potapanje brodova se pojavilo u magazinu sledeće godine i od tada je postala redovna pojava u istom magazinu. Nakon prvog svetskog šampionata u slagalicama nastale su mnoge varijante potapanja brodova.

Istorijat

Pasijans verzija Potapanja brodova je izmišljena u Argentini 1982. godine pod imenom , gde su se prve slagalice pojavile 1982. godine u španskom magazinu . Potapanje brodova su napravili Haime Ponjačik, osnivač i Eduardo Abel Himenez, Horhe Varlota i Daniel Samoilovič, koji su bili urednici magazina.

Nakon 1982, Potapanje brodova nije bilo objavljivano tek do 1987, kada je igra objavljena u , preimenovanoj verziji . Izdavačka kuća regularno objavljuje Potapanje brodova u mesečnom magazinu .

Potapanje brodova je napravilo međunarodnu premijeru na prvom svetskom takmičenju slagalica u Njujorku 1992. godine i tada je postalo popularno. Sledeće takmičenje 1993. je imalo varijantu Potapanja brodova koje nije imalo određene brojeve u redovima i kolonama. Posle toga je nastalo još varijanti, uključujući Potapanje brodova, dijagonalno Potapanje brodova, itd.^[3][4]

Potapanje brodova je prvi put objavljeno 1993. u magazinu , godinu dana nakon Svetskog prvenstva u slagalicama.

Pravila

U potapanju brodova, grupa brodova je sakrivena u mreži kvadrata veličine 10*10 kvadrata. Grupa brodova uključuje jedan ratni brod veličine 4 kvadrata, 2 obična broda veličine 3 kvadrata, 3 uništiteljska broda veličine 2 kvadrata, i 4 podmornice veličine 1 kvadrata. Svaki brod okupira broj uzastopnih polja na mreži, poređanih horizontalno ili vertikalno. Brodovi su postavljeni tako da ni jedan brod ne dodiruje drugi, čak ni dijagonalno.

Cilj ove društvene igre je da se otkrije gde se brodovi nalaze. Mreža može početi sa tragovima u formi kvadrata koji već imaju rešenje, pokazujući podmornice, krajnji deo broda, srednji deo broda, ili vode. Svaki red i kolona takođe imaju broj pored sebe, koji pokazuje broj kvadrata okupiran od strane delova broda koji je u tom redu ili koloni.^[5]

Varijante standardne forme potapanja brodova uključuju korišćenje većeg ili manjeg broja kvadrata u mreži, kao i korišćenje heksagonalne mreže.

Strategija

Klasično rešenje Potapanja brodova je da se dodaju segmenti u nedovršene brodove gde je to primereno, nacrta se voda u kvadrate gde se zna da ne postoji brod, i da završe brodove za redom ili kolonom čiji je broj isti kao i broj nerešenih kvadrata u tom redu ili koloni. Naprednija strategija uključuje gledanje mesta gde najveći brod još uvek nije bio i može da stane na mrežu, kao i gledanje redova i kolona koji su gotovo potpuni i odlučivanje da li postoji samo jedan način da se oni popune.^[5]

Računari i Potapanje brodova

Potapanje brodova je NP-Kompletan problem.^[6] 1997. godine, bivši urednik kolumne Potapanja brodova u magazinu ^[7] objavio je , popularnu implementaciju Potapanja brodova.^[8]