Насколько разрешим Minesweeper?

и задачки для интервью.
User avatar
olley
Мистер Привет 2015
Posts: 7606
Joined: 26 Mar 2002 10:01
Location: San Diego

Насколько разрешим Minesweeper?

Post by olley » 04 May 2012 22:59

Чего-то я раз за разом подрываюсь на большом поле :oops:
Вообще, Minesweeper он насколько разрешим без угадывания?

Вот сейчас подорвался на такой ситуации (см. картинку). Сделал предположение о минах (верхнаяя часть картинки). Оказалось неверным. В нижней части картинки приведено реальное расположение. Я где-то торможу или действительно тут можно только гадать?
You do not have the required permissions to view the files attached to this post.
olley

User avatar
Dweller
Уже с Приветом
Posts: 10443
Joined: 20 Dec 2000 10:01
Location: Bellevue, WA

Re: Насколько разрешим Minesweeper?

Post by Dweller » 04 May 2012 23:13

Стандартная техника это тыкать в новое поле и смотреть есть ли перспектива играть дальше, т.е. можно перебрать 5-10 полей пока не дойдешь до нормально угадываемого. Когда то за 75 секунд угадывал :) Правда, с планшетом и пером.

User avatar
olley
Мистер Привет 2015
Posts: 7606
Joined: 26 Mar 2002 10:01
Location: San Diego

Re: Насколько разрешим Minesweeper?

Post by olley » 04 May 2012 23:17

угадывание как стратегия для начала это понятно. Мне интересно, чисто с математической стороны, есть ли комбинации, которые неразрешимы без угадывания, когда поле начало открываться.
olley

User avatar
Dweller
Уже с Приветом
Posts: 10443
Joined: 20 Dec 2000 10:01
Location: Bellevue, WA

Re: Насколько разрешим Minesweeper?

Post by Dweller » 04 May 2012 23:50

olley wrote:угадывание как стратегия для начала это понятно. Мне интересно, чисто с математической стороны, есть ли комбинации, которые неразрешимы без угадывания, когда поле начало открываться.

Конечно есть. Если поле частично открылось это не значит что все можно логически открыть. Поле должно открыться больше чем на 50-70% после 2-5 случайных тычков чтобы можно было играть дальше.

xtigr
Уже с Приветом
Posts: 617
Joined: 23 Sep 2005 06:56
Location: SFBA

Re: Насколько разрешим Minesweeper?

Post by xtigr » 07 May 2012 22:44

В указанной ситуации можно было применить логику. А вобще да - бывают неразрешимые ситуации, где только тыкать надо.

User avatar
olley
Мистер Привет 2015
Posts: 7606
Joined: 26 Mar 2002 10:01
Location: San Diego

Re: Насколько разрешим Minesweeper?

Post by olley » 08 May 2012 16:13

xtigr wrote:В указанной ситуации можно было применить логику.

Сейчас глянул на свежую голову. Да, действительно вопросики неправильно поставил, можно было бы по-другому.
olley

Tauril
Уже с Приветом
Posts: 821
Joined: 24 Nov 2004 04:47
Location: NY

Re: Насколько разрешим Minesweeper?

Post by Tauril » 31 Aug 2012 00:11

На первой картинке сходу видно что есть мины над 4 и 2 скраю слева :oops: После того как будут открыты клетки рядом с этими минами, будет видно что есть еще одна мина над 1. После этого станет понятно где именно находится еще мина возле второй 4.
You do not have the required permissions to view the files attached to this post.

Tauril
Уже с Приветом
Posts: 821
Joined: 24 Nov 2004 04:47
Location: NY

Re: Насколько разрешим Minesweeper?

Post by Tauril » 31 Aug 2012 00:12

Упс. Тема старая оказывается, надо было мне на дату посмотреть перед тем как отвечать ;)

User avatar
olley
Мистер Привет 2015
Posts: 7606
Joined: 26 Mar 2002 10:01
Location: San Diego

Re: Насколько разрешим Minesweeper?

Post by olley » 31 Aug 2012 00:22

Tauril wrote:Упс. Тема старая оказывается, надо было мне на дату посмотреть перед тем как отвечать ;)

Но она все равно мне интересна.
Да, я потом уже прозрел по поводу засланных картинок. Но вроде бы все равно время от времени попадаются ситуации неразрешимые логически и требующие гадания.
olley

User avatar
perasperaadastra
Уже с Приветом
Posts: 20128
Joined: 21 Feb 2009 22:55
Location: Лох Онтарио

Re: Насколько разрешим Minesweeper?

Post by perasperaadastra » 11 Feb 2013 13:40

У меня тоже были ситуации, когда я не мог вычислить положение мин. В связи с этим вопрос: это были объективно неразрешимые ситуации или я просто не видел решения?

User avatar
Flash-04
Уже с Приветом
Posts: 57754
Joined: 03 Nov 2004 05:31
Location: RU -> Toronto, ON

Re: Насколько разрешим Minesweeper?

Post by Flash-04 » 11 Feb 2013 14:42

по теме:
Minesweeper is NP-complete: http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm
простейшее следствие - нет алгоритма для его решения.
Not everyone believes what I believe but my beliefs do not require them to.

Deynekin
Уже с Приветом
Posts: 367
Joined: 22 Feb 2005 02:14
Location: New York

Re: Насколько разрешим Minesweeper?

Post by Deynekin » 11 Jan 2014 01:24

Дисклаймер: я в этот Minesweeper уже лет двадцать, как не играл, пишу по старой памяти.

Эта игра, как и всякая другая игра с неполной (но только для вас!) информацией потенциально некорректна, т.е. бывают ситуации, когда программа в принципе, "если бы хотела"(!), вполне могла бы и передёргивать. Я не утверждаю, что она это наверняка делает, но гарантии, что это не так, нет никакой.

...Например, у вас остались два поля, на которых есть одна мина, и она с одинаковой вероятностью может располагаться либо на одном поле, либо на другом. Т.е. логика здесь уже больше не помощник, и при честной игре ваши шансы "50-на-50".
Но что бы вы ни выбрали на последнем шаге, ничто не мешает программе всегда подставлять мину под вас уже после вашего хода: "А вот и не угадали!.."

Те же ситуации возможны в любых других играх с неполной информацией. Например, в преферансе "остальне игроки" за вашей спиной вполне могли бы обмениваться информацией, а то и вообще перекладывать карты, подтасовывая расклад против вас. Потому что "неполная информация" — это только у вас, а программа знает всё, и потенциальный простор для "жульничества" у неё есть.

Return to “Головоломки”