Solver Campo Minado

34

Já geramos campos Campo Minado , mas alguém realmente precisa varrer as minas geradas antes que o PCG exploda!

Sua tarefa é escrever um Minesweeper Solver que seja compatível com uma versão ligeiramente modificada da solução aceita “Working Minesweeper” (as ações são separadas por espaços para permitir campos maiores).

Entrada: um campo Campo Minado, campos separados por espaços. A primeira linha indica o número total de minas.

  • x: Intocado
  • !: Flag
  • Dígito: número de minas em torno desse campo

Exemplo: 

10
0 0 1 x x x x x
0 0 2 x x x x x
0 0 2 ! x x x x
0 0 1 2 x x x x
0 0 0 1 x x x x
1 1 0 2 x x x x
x 1 0 2 x x x x
1 1 0 1 x x x x

Saída: sua próxima etapa no formato action row column(começando em zero)

Ações válidas:

  • 0: Abra
  • 1: Colocar uma bandeira

Exemplo:

0 1 2

Regras:

  • Você escreve um programa completo que utiliza um único campo como entrada (argumentos STDIN ou de linha de comando) e gera uma única ação (STDOUT). Portanto, você não pode salvar estados, exceto !.
  • Sua escolha deve seguir as melhores chances de sobrevivência. (ou seja, se houver uma movimentação 100% segura, faça-a)
  • Isso é código-golfe ; a solução mais curta (em bytes UTF-8) vence

Testes:

Esses testes têm a finalidade de testar situações claras comuns; seu programa deve funcionar para todos os campos de teste.

Em:

4
x x x x
1 2 x x
0 1 2 x
0 0 1 x

Fora (qualquer um destes):

1 1 2
0 0 2
0 1 3

Em:

2
x x x
1 ! x
1 1 x

Fora (qualquer um destes):

0 0 0
0 0 1
0 1 2
0 2 2
1 0 2

Em:

10
x x x x x x x x
1 3 3 x x x x x
0 1 ! 3 3 4 x x
0 2 3 ! 2 3 x x
0 1 ! 2 2 ! x x

Fora (qualquer um destes):

1 1 5
1 0 2

Em:

2
x x x
2 3 1
! 1 0

Fora (qualquer um destes):

0 0 1
1 0 0
1 0 2
code-golf game minesweeper TimWolla
fonte
Agradável! 1) Talvez para testar alguém escreva um equipamento de teste: dado um campo, ele imprime cada etapa executada e se o programa vence. O programa deve ganhar em mapas sem nenhuma ambiguidade. 2) Gostaria de saber se alguém usará a ação flag. Parece que nunca deve ser necessário.
Claudiu
Para o primeiro teste. Por que você é capaz de mudar para 0 0 2ou 0 1 3. Não vejo como um desses seria considerado seguro. (Eu não devo ser bom o suficiente em caça-minas ...)
FDinoff
1
Possivelmente Fou Pparece melhor bandeira que !:)
Visão
1
@JonathanVanMatre O campo é um em branco, mas é garantido a sua primeira abertura não é uma mina, como as minas são colocados após o primeiro clique :)
TimWolla
2
Curiosidade: Há apenas um número finito de placas disponíveis (pelo menos na versão XP, que é a canônica na cena competitiva). O quadro é deslocado ao clicar no primeiro local para garantir que você não esteja clicando em uma mina, mas fora isso, já está decidido qual painel você usará.
Undergroundmonorail

Respostas:

17

Mathematica

Ainda não jogou golfe. Precisa de mais trabalho em formatos de E / S.

t = {{0, 0, 1, x, x, x, x, x}, {0, 0, 2, x, x, x, x, x}, {0, 0, 2, F, x, x, x, x}, 
     {0, 0, 1, 2, x, x, x, x}, {0, 0, 0, 1, x, x, x, x}, {1, 1, 0, 2, x, x, x, x}, 
     {x, 1, 0, 2, x, x, x, x}, {1, 1, 0, 1, x, x, x, x}};
(*Sqrt[2] is  1.5*)
c = Sequence; p = Position;
nums = p[t, _?NumberQ];
fx = Nearest[p[t, x]];
flagMinus[flag_] := If[Norm[# - flag] < 1.5, t[[c @@ #]]--] & /@ nums
flagMinus /@ p[t, F];
g@x_List := Tr[q[#] & /@ x]
eqs = MapIndexed[t[[c @@ (nums[[#2]][[1]])]] == g[#1] &, (fx[#, {8, 1.5}] & /@nums)];
vars = Union@Cases[eqs, _q, 4];
s = Solve[Join[eqs, Thread[0 <= vars < 2]], vars, Integers];
res = (Transpose@s)[[All, All, 2]];
i = 1; plays = Select[{i++, #[[1]], Equal @@ #} & /@ res, #[[3]] &];
Flatten /@ ({#[[2]] /. 1 -> F, List @@ vars[[#[[1]]]] - 1} & /@ plays)

(*
{{0, 0, 3}, {F, 1, 3}, {F, 2, 4}, {0, 3, 4}, {0, 4, 4}, 
 {F, 5, 4}, {F, 6, 0}, {F, 6, 4}, {0, 7, 4}}
*)

Editar: faixa bônus

Criei um playground interativo que calcula as probabilidades de bombas, calculando todas as soluções possíveis para uma determinada configuração:

Gráficos do Mathematica

Instruções para testá-lo sem o Mathematica instalado:

  1. Faça o download de http://pastebin.com/asLC47BW e salve-o como * .CDF
  2. Faça o download do ambiente CDF gratuito da Wolfram Research em https://www.wolfram.com/cdf-player/ (não é um arquivo pequeno)

O controle deslizante altera as dimensões da placa. Este é apenas um programa superficial, não totalmente testado, por favor relate quaisquer erros. Eu não implementei o recurso "número total de bombas disponíveis a bordo". Supõe-se infinito.

Dr. belisarius
fonte