ако тя не може да я реши, всеки да се чувства свободен да предложи неговото решение

играта на миночистач (стандартно включена в Windows, всеки я е играл):

по зададена някаква начална конфигурация от открити и закрити полета (откритите са празни или с цифра показваща колко мини има в съседните полета, в закритите са скрити мини) да се напише програма (или поне опише алгоритъм) проверяваща дали конфигурацията е възможна, т.е. дали има такова разположение на мините което удовлетворява входните данни

Обещах повече да не пиша във форума и това наистина е последният ми пост просто заради задачата на демонд.


Това са двете функций които решават задачата, всъщност в задачата не е казано че има "unknown" полета(отбелязани с "?"), така, че първата функция може да бъде:






Moje bi trqbva malko da se obosnova, za tezi na koito ne im e qsno, i pak da ne zemat da me besqt zaradi google.. ta ideqta e slednata:
- minnoto pole se zadava kato dvumeren masiv s razmer [ROWS][COLS]
-funkciata goal_state() obikalja vsjako kvadratche ot poleto zapochvajki ot [0][0]
-za vsjako kvadratche proverjava kakvo chislo e zapisano v nego ( vjako chislo pokazva broja na "bombite" koito obgrajdat tekushtoto kvadratche) i vika funkcijata "surrounding_bombs()"
-"surrounding_bombs()" obikalja kvadratchetata koito obgrajdat tekushtoto kvadratche (za koeto se pravi proverkata) i vryshta broja na bombite koito go obgrajdat
-vav funkciata goal_state() se proverjava dali broja na bombite zapisani v tekushtoto kvadratche ("bombs_expected") e raven na broja na bombite koito go obgrajdat (t.e. stojnostta na chisloto vyrnato ot "surrounding_bombs()")
-ako bombs_expected == surrounding_bombs() za vsichki kvadratcheta (t.e. za vseki element na masiva MSgrid[ROWS][COLS] znachi taka zadadenite vhodni danni (minno pole) sa verni.
bombite sa otbeljazani s "B"
Tova e obshto vzeto.




demond DA RAZBRAH VECHE KAKVO IMASH V PREDVID SHTE POPRAVQ NESHTATA I SHTE GI SLAGAM V TOZI POST TYI KATO TOVA E POSLEDNIQT MI POST. NO MALKO PO KUSNO SHE Q SLOJA ZA DA Q POPRAVQ....







kakto i edna funkcija kojato namira "unknown" poletata zaobikaljashti dadenoto kvadratche




tova e matrica (dvumeren masiv) s razmeri [ROWS][COLS], kakto se zabelqzva
stojnostta na vseki element ot masiva e ili bomba, ili chislo, ili "neizvestno"
algoritama e sys slojnost 0(2^n), kadeto n=ROWSxCOLS


vav funkciata gal_state se dobavja syshto:


ova parche kod vzema pod vnimanie "praznite" poleta


GRESHKA GRESHKA
obache sega kato cheta - zadachata ZA 10 TI PAT e malko po razlichna:

dadena e reshetkata s chisla i zakriti poleta
tyrsi se vazmojnite razpolojenia na bombite v zakritite poleta, taka che da udovoletvorjavat reshetkata i da ne nadvishavat predvaritelno zadadenija broj bombi
hm ........"consistentnostta" pokazva che dadenia grid ima reshenie pri taka zadadenite chisla v reshetkata
"goal_state" pokazva che dadenoto konkretno reshenie (t.e. s veche opredeleni mesta na "bombite") e vjarno,
taka che:


se reshava tochno ot funkciata "consitency()"

samo trjabva kato parametar da se vkluchi broja na minite, kojto e zadaden predvaritelno

sajalqvam che pisha taka no se nalaga.....




da de, ama trjabva da znaesh kolko broja mini imash predvaritelno
i da proverish dali toja broj mini moje da se razpoloji v igralnoto pole, taka che da udovoletvori dadenite cifri: primerno znaesh che trjabva da tyrsish 20 mini i tolkova.

Ta znachi algoritama kojto se seshtam i moje da reshi tova e "back-trecking"
imame dadena matrica kato na snimkata
zapochvame ot kvadratche [0][0]
ako e markitano s '?' (t.e. e zakrito i njama chislo v nego) - postavjame bomba (zapisvame v nego 'B')
minavame kym sledvashtoto kvadratche
i taka dokato broja na bombite koito sme postavili dostigne predvaritelno zadadenija

vtora chast:
proverjavame s goal_state() dali reshenieto e vjarno
ako ne e se vryshtame nazad - t.e. premestvame poslednoto kvadratche, i taka dokato izcherpim vsichki kombinacii s nego
ako ne stane - vryshtame se na predposlednoto kvadratche i probvame s premestvane na nego
i t.n.
Trqbva mi malko vreme za da napisha gorespomenatiq algoritym....na 70% sym gotova...


Mislq che e tova:




moje i da ima malka logicheska greshka njakade - rekursia ne sam pisala ot mnogo otdavna.


Доказано е, че всяка задача, която може да се реши рекурсивно, може да се реши итеративно (без рекурсия) и обратно. Има обаче такива задачи, които се решават много лесно с рекурсия, а иначе създават доста проблеми. Такава е задачата за търсене на път в лабиринт. Поставете се в ролята на човече, което обикаля в огромен лабиринт и търси изхода. Да приемем, че единственото оръжие, с което разполага човечето е силна памет или просто парче тебешир, с което да си отбелязва пътя. Тази задача наистина се решава трудно без рекурсия, но с рекурсия решението е доста лесно. Всъщност този алгоритъм съвсем несъзнателно се прилага от всеки човек, който се е загубил. Идеята за рекурсивно решение е следната:



Така сведохме задачата за търсене на изхода до 4 подзадачи - търсене на изход наляво, търсене на изход надясно, търсене на изход нагоре и търсене на изход надолу. Същевременно знаем как да определим дали най-простата задача е решена - ако сме намерили изхода, или че не е решена - ако сме се “задънили”. Същевременно проверяваме да не би да се въртим в кръг. Този подход се нарича “търсене с връщане назад” (backtracking).

Ta klasicheskoto prilojenie na "backtracking" algorityma e pri reshavane na zadachata "tyrsene na pyt v labirint" a syshto i na "Hanojskite kuli"


v sluchaja az pravja neshto podobno - opitvam se da slagam posledovatelno mini edna sled druga i kato dostigna neobhodimija broj - proverjavam dali imame reshenie na zadachata ("goal_state")
ako njamame reshenie - vryshtam nazad kato premestvam poslednata slojena mina
kato izcherpam vsichki vazmojnosti - maham poslednata i premestvam predposlednata, slagam sled tova pak poslednata mina - i proverjavam
i taka dokato poluchim (ili ne) reshenie.

Ami tova e umstvenite mi sposobnosti sa tolkova sajalqvam no nemoga da izmislq nishto drugo kato gledam tova si e nqkakav matematicheski problem i horata disertacii pishat za nego...


Ami tova e naistina az bqh do tuk poveche nishto nemoga da izmislq jelaq na vsichki vsichko nai hubavo i uspeh sys zadachata...

не върши работа

тази програмка работи само с открити полета, а целта на задачата - както недвусмислено е казано в условието - е да се провери дали има разположение на известен брой мини в зададена конфигурация от открити и ЗАКРИТИ полета което удовлетворява цифрите в откритите полета - т.е. мините не са маркирани

пропуснах да подчертая че се търси решение в общия случай, за всякакви ROWS и COLS, т.е. те не са константи; освен това не се приема решение тип "brute force" - примерно генериране на всички комбинации от зададения брой мини в закритите полета и проверка на всяка от тях дали е валидна - понеже е близко до ума че подобна стратегия ще може да смята в разумен период от време само на игрални полета с малки размери

ако не е станало ясно, началните данни са дъска като тази:





задачата е да се провери дали тия цифри са валидни

kakvo to4no 6te re4e dali sa validni ?

ще рече дали има такава подредба на зададения брой мини при която зададените цифри отразяват вярно броя на мините в съседните на всяка цифра полета

очевидно при истинска игра на Minesweeper цифрите винаги са верни - компютъра не те лъже - но задачата е да се проверят цифри зададени неизвестно от кого - може от компютър като етап на истинска игра на Minesweeper, при което програмата ти трябва да отговори YES (демек, цифрите на дъската са валидни), а може и от лъжлив унибг админ който ти обещава линия ако намериш мините, но всъщност е задал такива цифри при които е невъзможно да има валидно разположение на мините, при което програмата ти трябва да отговори NO

още някой неразбрал?

ot nyakude mirishe na ctrl+c ctrl+v

Ima 2 vuzmojnosti.. neshto ne sum dorazbral ili puk reshenieto na zadachata e adski prosto i prosto ne se vpisva vuv vsichkiat toia source kopiran bog znae otkude..
Az si mislya, che za vsyako pole s cifra v nego tryabva da se proveri, dali okolo nego ima pone tolkova svobodni poleta, kolkoto e vaprosnata cifra. Estestveno pri podoben analiz ne se vklyuchvat faktori, kato naprimer tova, che broiat mini spored otkritite poleta moje da nadhvurlya realniat broj mini... ili pone cyalostna kartina shte moje da bude dadena, ako broiat svobodni poleta e raven na broiat mini, prosto zashtoto nyama da imame informacia za obkrujavashtiat ni svyat - neotkritite poleta, koito ne granichat s nito edno otkrito pole.

Ta sled vsichkiat source, kojto mernah dokato scroll-vah nadolu, sledniat otkus code prosto nyama kak da e reshenie

...би трябвало да отбележа че на пръв поглед задачата е проста, но даже и в Google няма да ви дадат по-сложна от нея на интервюто

хайде, никой ли не иска да спечели 1000000 долара?

не се шегувам, решаването на задачата (или доказването че няма решение) индиректно води до разрешаване на проблем за което има официална награда 1 милион

O da Tova opredeleno e zadacha kato za teodora, moite umstveni sposobnosti ne sa kato nejnite i sa ogranicheni da prinedlejat samo na P

Този алгоритъм не се ли използва в minesweeper?

не, програмата Minesweeper няма алгоритъм, ти си този който действа по алгоритъм когато играеш на Minesweeper; има алгоритми за тази игра, естествено негарантиращи успех (понякога просто е въпрос на шанс да не уцелиш мината); но всичко това няма отношение към задачата

смята се че проблема чието решение се търси в задачата е класически NP (non-deterministic polynomial time) проблем, т.е. проблем чието решение не може да се намери за време което може да се изрази като полиномиална функция от началните условия (размера и конфигурацията на дъската), но чието решение може да се провери в полиномиално време (демек, лесно е да провериш дали дадена конфигурация на мините удовлетворява началните условия, но е много трудно - или поне така се смята - да отговориш на въпроса дали има или не такова решение)

решението на задачата (или доказването че такова не е възможно да се намери в задоволитено/полиномиално време) би довело до отговор на въпроса дали проблемите от NP клас могат да се причислят към клас P (deterministic polynomial) - казват че това е най-важния въпрос в theoretical computer science, и един от най-важните в съвременната математика

има още 6 въпросчета като това, за решението на всеки от които има награда $1 милион от някаква математическа фондация; но те са чисто математически и не са свързани директно с програмиране и компютри; досега само един руснак има шанс да вземе милиона, за доказването на хипотезата на Поанкаре

теодора:

не се засягай от коментарите по твой адрес, имаш моите поздравления че се опита - решението ти е комбинаторен вариант, което не е много подходящо за общия случай, но това не е важно - важното е че се опита

co-sign.

Практически имаме информация за "ръба" - крайните полета.
От тях може да направим един ред от полета, на които да дадем номера.
този ред може да се раздели на множества според информацията, която имаме (цифричките).
Като например в трите първи единици в горния пример №№ 1 и 2 има едно заето и едно не заето място - два варианта.
№№ 1 2 3 - имат едно заето и едно не заето място,
№№ 2 3 4 - имат едно заето и едно не заето място
което прави вариантите пак два.
заети № 1 и 4 или 2.
Всяко следващо условие внася някакви варианти, но и някои ограничения , така че възможните вариянти мисля, че няма да станат невъзможно многобройни.
И така ако стигнем да края на редицата без да сме стигнали до невъзможно условие - значи задачката има решение. До колкото разбрах това е въпроса.
Ако по пътя се стигне до невъзможно условие - значи няма решение.
мисля, че всяко условие внася достатъчно ограничения и вариантите няма да станат толкова много, че да не могат да се проследят.
Не знам как да се направи на програма, но нещо като алгоритъм е това.

№№ 1 2 3 - имат едно заето и две не заети места,
№№ 2 3 4 - имат едно заето и две не заети места