Сапер - популярная игра-головоломка, в которой вы должны выяснить, какие плитки являются «минами», не нажимая на эти плитки. Вместо этого вы нажимаете на соседние плитки, чтобы показать количество смежных мин. Недостатком игры является то, что возможно оказаться в сценарии, где есть несколько действительных ответов, и вы можете только догадываться. Например, возьмите следующую доску:

1110
2*31
3*??
2*4?
112?

В этом формате число представляет количество соседних мин, an *представляет известную шахту, и "?" представляет потенциальную шахту. К сожалению, в этой конкретной загадке есть четыре различных и правильных возможных решения:

1110    1110    1110    1110    
2*31    2*31    2*31    2*31
3*4*    3*5*    3**2    3**1
2*42    2*4*    2*4*    2*42
112*    1121    1121    112*

Это означает, что доска неразрешима . Вот пример решаемой платы:

1121
1??*
12?*
0122

Эта доска разрешима, потому что есть только одно возможное правильное решение:

1121
1*4*
12**
0122

Ваша задача - написать программу или функцию, которая использует действующую платформу тральщика и определяет, разрешима она или нет. Под «действительной доской тральщика» я подразумеваю, что входные данные всегда будут прямоугольными, имеют хотя бы одно решение и не будут содержать недопустимых символов.

Ваш ввод может быть массивом символов, массивом строк, строкой, содержащей новые строки и т. Д. Выходные данные должны быть истинным значением, если оно разрешимо, и ложным значением, если это не так. Я не очень беспокоюсь о производительности, но ваше решение теоретически должно работать для любого размера ввода.

Как обычно, применяются стандартные лазейки и выигрывает самое короткое решение в байтах!

Примеры:

Следующие примеры все разрешимы:

1121
1??*
12?*
0122

1110
1???
1110
0000

1110
3???
??20
*310

****
****
****
****

0000
0000
0000
0000

1100
*100
2321
??*2
13*2
1221
1*10
1110

1121
2*??
2*31
2220
1*10

Следующие примеры неразрешимы:

1110
2*31
3*??
2*4?
112?

01??11*211
12??2323*1
1*33*2*210
12?2122321
13?3101**1
1***101221

1***
3*52
2*31
12??
02??
01??

00000111
000012*1
00001*21
22101110
**100111
?31123*1
?311**31
**113*20

GNU Prolog, 493 байта

z(_,[_,_]).
z(F,[A,B,C|T]):-call(F,A,B,C),z(F,[B,C|T]).
i([],[],[],[]).
i([H|A],[I|B],[J|C],[H-I-J|T]):-i(A,B,C,T).
c(A/_-B/_-C/_,D/_-_/T-E/_,F/_-G/_-H/_):-T#=A+B+C+D+E+F+G+H.
r(A,B,C):-i(A,B,C,L),z(c,L).
q(63,V):-var(V).
q(42,1/_).
q(X,0/Y):-Y#=X-48.
l([],[0/_]).
l([H|T],[E|U]):-q(H,E),l(T,U).
p([],[[0/_,0/_]],0).
p([],[[0/_|T]],N):-M#=N-1,p([],[T],M).
p([H|T],[[0/_|E]|U],N):-p(T,U,N),l(H,E).
m([H|A],B):-length(H,N),p([],[R],N),p([H|A],M,N),z(r,[R|M]),p(B,M,N).
s(A):-setof(B,m(A,B),[_]).

Дополнительный предикат, который может быть полезен для тестирования (не является частью представления):

d([]).
d([H|T]):-format("~s~n",[H]),d(T).

Пролог, безусловно, является подходящим языком для решения этой задачи с практической точки зрения. Эта программа в значительной степени просто устанавливает правила Minesweeper и позволяет решателю ограничений GNU Prolog решить проблему оттуда.

zи iявляются служебными функциями ( zвыполняет своего рода операцию, подобную складке, но на наборах из трех смежных элементов, а не 2; iпереносит 3 списка из n элементов в список из n 3-х кортежей). Мы внутренне сохраняем ячейку как , где x равно 1 для мин и 0 для немина, а y - количество смежных мин; выражает это ограничение на доске. применяется к каждому ряду доски; и поэтому проверяет, является ли доска действительной.x/ycrcz(r,M)M

К сожалению, формат ввода, необходимый для непосредственной работы, нецелесообразен, поэтому мне также пришлось включить синтаксический анализатор (который, вероятно, учитывает больше кода, чем фактический механизм правил, и большую часть времени проводил отладку; механизм правил Minesweeper в значительной степени работал первый раз, но парсер был полон мыслителей). qпреобразует одну ячейку между кодом символа и нашим форматом. преобразует одну строку доски (оставляя одну ячейку, которая, как известно, не является миной, но с неизвестным количеством соседних мин, на каждом краю линии как граница);x/ylpпреобразует всю доску (включая нижнюю границу, но исключая верхнюю). Все эти функции могут быть запущены как вперед, так и назад, что позволяет как анализировать, так и печатать доску. (Есть несколько раздражающих шатаний с третьим аргументом p, который задает ширину доски; это потому, что у Пролога нет матричного типа, и если я не ограничу доску прямоугольной, программа перейдет в бесконечный цикл, пытающийся постепенно расширить границы вокруг доски.)

mявляется главной функцией решения Сапер. Он анализирует входную строку, генерируя доску с правильной границей (используя рекурсивный регистр pдля преобразования большей части доски, затем вызывая базовый случай напрямую для генерации верхней границы, которая имеет ту же структуру, что и нижняя граница). Тогда это вызываетz(r,[R|M])запустить механизм правил Minesweeper, который (с этим шаблоном вызовов) становится генератором, генерирующим только допустимые доски. На этом этапе правление все еще выражается в виде набора ограничений, что потенциально неудобно для нас; возможно, у нас может быть один набор ограничений, который может представлять более одной доски. Кроме того, мы еще нигде не указали, что каждый квадрат содержит не более одной шахты. Таким образом, нам необходимо явно «свернуть форму волны» каждого квадрата, требуя, чтобы он был конкретно либо (одиночным), либо минным, и самый простой способ сделать это - запустить его через анализатор в обратном направлении ( var(V)на q(63,V)Корпус предназначен для предотвращения ?обратного хода корпуса, и, таким образом, отклонение доски заставляет ее быть полностью известной). Наконец, мы возвращаем разобранную доску изm; mтаким образом, становится генератором, который принимает частично неизвестную доску и генерирует все известные платы в соответствии с ней.

Этого действительно достаточно, чтобы решить Сапер, но вопрос явно просит проверить, есть ли точно одно решение, а не найти все решения. Поэтому я написал дополнительный предикат, sкоторый просто преобразует генератор mв набор, а затем утверждает, что набор содержит ровно один элемент. Это означает, что sвернет truey ( yes), если действительно есть только одно решение, или falsey ( no), если существует более одного или меньше одного.

dне является частью решения и не входит в число байтов; это функция для печати списка строк, как если бы это была матрица, которая позволяет проверять платы, сгенерированные m(по умолчанию, GNU Prolog печатает строки в виде списка кодов ASCII, потому что он обрабатывает две эти функции как синонимы; этот формат довольно трудно читать). Это полезно во время тестирования или если вы хотите использовать mв качестве практического решателя Minesweeper (потому что он использует решатель ограничений, он очень эффективен).

Haskell, 193 169 168 байт

c '?'="*!"
c x=[x]
g x|t<-x>>" ",w<-length(words x!!0)+1=1==sum[1|p<-mapM c$t++x++t,and[sum[1|m<-[-1..1],n<-[j-w,j,j+w],p!!(m+n)=='*']==read[d]|(j,d)<-zip[0..]p,d>'/']]

Пример использования: g "1121 1??* 12?* 0122"-> True.

Как это работает: составьте список всех возможных плат с ?заменой либо на, *либо !( !значит, пропустите позже). Это делается с помощью mapM c, но прежде чем мы добавим и добавим несколько пробелов к входной строке, чтобы наша индексация не выходила за пределы диапазона. Для каждой такой проверки платы , если это правильная плата, обернув по всем элементам (индекса j) , и если это число ( d>'/') также на своих соседей (индекс n, m), подсчитать *и сравнить с числом. Наконец, проверьте длину списка действительных досок.

Mathematica, 214 192 190 180 176 174 168 165 байтов

0&/@Cases[b="*";If[!FreeQ[#,q="?"],(x#0@MapAt[x&,#,#&@@#~Position~q])/@{b,0},BlockMap[If[#[[2,2]]==b,b,Count[#,b,2]]&,#~ArrayPad~1,{3,3},1]]&@#,#/.q->_,All]=={0}&

Содержит U + F4A1 (для частного использования). Эта безымянная функция находит все возможные комбинации для "?"(т.е. заменяет все "?"s на "*"или 0) и проверяет, существует ли только одно допустимое решение.

объяснение

b="*";

Установите bв "*".

!FreeQ[#,q="?"]

Установите qв строку "?". Проверьте, есть ли "?"на входе.

If[ ..., (x#0 ... ,0}, BlockMap[ ... ]]

Если True...

(x#0@MapAt[x&,#,#&@@#~Position~q])/@{b,0}

Замените первое вхождение q(= "?") на b(= "*") или 0(т.е. два выхода) и примените всю функцию снова.

Если False...

#~ArrayPad~1

Дополните вход одним слоем 0.

BlockMap[If[#[[2,2]]==b,b,Count[#,b,2]]&, ... ,{3,3},1]

Разделите входные данные на матрицы 3 x 3 со смещением 1. Для каждого раздела примените функцию, так что если среднее значение равно b(= "*"), выходным значением является b(= "*"), а если средним значением не является b(= "*"), output - это число b(= "*") на входе. Этот шаг повторно оценивает все числовые ячейки.

Cases[ ... ,#/.q->_,All]

Из всех результатов найдите те, которые соответствуют входным

0&/@ ... =={0}

Проверьте, имеет ли вход длину 1.

Perl, 215 байт

213 байтов кода + -p0флаги (2 байта).

/.*/;$c="@+";$_=A x$c."
$_".A x$c;s/^|$/A/mg;sub t{my($_)=@_;if(/\?/){for$i(0..8,"*"){t(s/\?/$i/r)}}else{$r=1;for$i(/\d/g){$r&=!/(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%!=$i?"":R})/}$e+=$r}}t$_;$_=$e==1

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

Более читабельный код выглядит так:

/.*/ ; $ c = "@ +" ; # посчитать размер строки. 
$ _ = A x $ c . "\ n $ _" . A x $ c ; # добавить строку «А» в начале и еще одну в конце. 
с / ^ | $ / А / мг ; # добавить «А» в начале и конце каждой строки.                     

# Функция, которая на самом деле решает проблему
 sub t { my $ _ = pop ; # Получить параметр, сохранить его в $ _ (аргумент по умолчанию для регулярных выражений). if ( / \? / ) { # если есть другой неизвестный символ. для $ i ( 0 .. 8 , "*" ) { # пробовать каждую возможность 
            t ( s / \? / $ i / r ) # рекурсивного вызова, когда первый неизвестный символ был заменен } } else { 
     
        
            
        
     # больше нет неизвестного символа, поэтому здесь мы проверяем, является ли доска действительной 
        $ r = 1 ; # если r == 1 в конце, то доска действительна, в противном случае это не для $ i ( / \ d / g ) { # для каждого числа, присутствующего на доске # следующее регулярное выражение проверяет, окружен ли номер либо # слишком много, либо слишком мало мин. # (как это работает: волшебство!) 
         $ r & =! /(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%! = $ i? "": R}) / } 
        $ e + = $ r # Увеличить количество допустимых досок. } } 
t $ _ ;  
          
            
            
             
        
    
 # Вызов предыдущей функции 
$ _ = $ e == 1 # Проверяет, существует ли только одна действительная доска ($ _ неявно печатается благодаря флагу -p). 

О регулярном выражении в середине:

/(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%!=$i?"":R})/

Обратите внимание, что [^V]просто означает «любой символ, включая \ n».
Идея такова: 3 символа на линии, затем 3 на следующей (с $iсерединой), затем 3 на следующей. эти 3 группы из 3 чисел выровнены, [^V]{$c}и интересующий нас номер находится посередине.
И затем "$1$2$3"=~y%*%%подсчитывает количество *(бомб) среди этих 9 символов: если оно отличается от $i, мы добавляем пустую строку для сопоставления ( ""=> мгновенное сопоставление, регулярное выражение возвращает истину), в противном случае мы принудительно завершаем неудачу, пытаясь сопоставить R( который не может быть в строке).
Если регулярное выражение соответствует, то плата не действует, поэтому мы устанавливаем $rна 0с $r&=!/.../.
И именно поэтому мы добавляем некоторыеAповсюду вокруг каждой строки: так что нам не нужно беспокоиться о случаях краев чисел, которые находятся рядом с краями доски: они будут иметь в Aкачестве соседей, которые не являются минами (конечно, примерно любой символ может работать, Я выбрал A).

Вы можете запустить программу из командной строки следующим образом:

perl -p0E '/.*/;$c="@+";$_=A x$c."\n$_".A x$c;s/^|$/A/mg;sub t{my($_)=@_;if(/\?/){for$i(0..8,"*"){t(s/\?/$i/r)}}else{$r=1;for$i(/\d/g){$r&=!/(...)[^V]{$c}(.$i.)[^V]{$c}(...)(??{"$1$2$3"=~y%*%%!=$i?"":R})/}$e+=$r}}t$_;$_=$e==1' <<< "1121
1??*
12?*
0122"

Сложность не может быть худшей: это O(m*9^n)где nчисло ?на доске и mколичество ячеек на доске (без учета сложности регулярного выражения в середине, что, вероятно, довольно плохо). На моей машине это работает довольно быстро до 4 ?, и начинает работать медленнее 5, занимает несколько минут для 6, и я не пытался увеличить число.

JavaScript (ES6), 221 229

g=>(a=>{for(s=i=1;~i;g.replace(x,c=>a[j++],z=j=0).replace(/\d/g,(c,p,g)=>([o=g.search`
`,-o,++o,-o,++o,-o,1,-1].map(d=>c-=g[p+d]=='*'),z|=c)),s-=!z)for(i=a.length;a[--i]='*?'[+(c=a[i]<'?')],c;);})(g.match(x=/\?/g)||[])|!s

Если все входные данные, как ожидается, будет действительно - то есть, по крайней мере , 1 решение - тогда я могу сохранить байт меняется s==1сs<2

Меньше гольфа

g=>{
  a = g.match(/\?/g) || []; // array of '?' in a
  s = 1; // counter of solutions
  for(i=0; ~i;) // loop to find all configurations of ? and *
  {
    // get next configuration
    for(i = a.length; a[--i] = '*?'[+( c = a[i] < '?')], c; );
    z = 0; // init at 0, must stay 0 if all cells count is ok
    g
    .replace(/\?/g,c=>a[j++],j=0) // put ? and * at right places
    .replace(/\d/g,(c,p,g)=>(
       // look for mines in all 8 directions
       // for each mine decrease c
       // if c ends at 0, then the count is ok
       [o=g.search`\n`,-o,++o,-o,++o,-o,1,-1].map(d=>c-=g[p+d]=='*'),
       z|=c // z stays at 0 if count is ok
    )) // check neighbour count
    s-=!z // if count ok for all cells, decrement number of solutions
  }
  return s==0 // true if exactly one solution found
}

Тест

F=
g=>(a=>{for(s=i=1;~i;g.replace(x,c=>a[j++],z=j=0).replace(/\d/g,(c,p,g)=>([o=g.search`
`,-o,++o,-o,++o,-o,1,-1].map(d=>c-=g[p+d]=='*'),z|=c)),s-=!z)for(i=a.length;a[--i]='*?'[+(c=a[i]<'?')],c;);})(g.match(x=/\?/g)||[])|!s

out=x=>O.textContent+=x+'\n'

Solvable=['1121\n1??*\n12?*\n0122'
,'1110\n1???\n1110\n0000'
,'1110\n3???\n??20\n*310'
,'****\n****\n****\n****'
,'0000\n0000\n0000\n0000'
,'1100\n*100\n2321\n??*2\n13*2\n1221\n1*10\n1110'
,'1121\n2*??\n2*31\n2220\n1*10']
Unsolvable=['1110\n2*31\n3*??\n2*4?\n112?'
,'01??11*211\n12??2323*1\n1*33*2*210\n12?2122321\n13?3101**1\n1***101221'
,'1***\n3*52\n2*31\n12??\n02??\n01??'
,'00000111\n000012*1\n00001*21\n22101110\n**100111\n?31123*1\n?311**31\n**113*20']
out('Solvable')
Solvable.forEach(t=>out(t+'\n'+F(t)+'\n'))
out('Unsolvable')
Unsolvable.forEach(t=>out(t+'\n'+F(t)+'\n'))

<pre id=O></pre>

JavaScript (Node.js) , 167 байт

s=>g=(r=c='',[p,...q]=s,w)=>w?0:p?(g(r+0,q,p=='*')+g(r+1,q,1/p),c==1):c-=-![...s].some((p,i)=>p>' '&&[-1,1,-q,-1-q,-2-q,q,q+1,q+2].map(j=>p-=~~r[i+j])|p,q=s.search`
`)

Попробуйте онлайн!

Несмотря на то, что оператор говорит: «вход всегда будет прямоугольным, есть хотя бы одно решение», ложный образец 3 не совпадает, поэтому мне все еще требуется 1 решение, а не <2 решения

s=>(        // p.s. Here "block" can also mean \n
  c=0,          // possible mine count
  g=(           // recursive
    r='',       // mine states
    [p,...q]=s, // known info to check possible state for a block
    w           // invert condition, stop if true
  )=>
    w?0:
      p?(       // for each block
        g(r+0,q,p=='*')+   // possibly not bomb if doesn't say so
        g(r+1,q,1/p),      // number/newline can't be bomb
        c==1               // only one bomb
      ):
        c-=-![...s].some(  // no block doesn't satisfy
          (p,i)=>
            p>' '&& // \n don't mean number
                    // other symbols turn into NaN when counting
            [-1,1,-q,-1-q,-2-q,q,q+1,q+2].map(j=>p-=~~r[i+j])
                    // subtract each neighbor, OOB = 0
            |p,     // difference between intended and actual
            q=s.search('\n') // how many blocks in a line
        )
)