Resolver uma placa 0h n0

19

0h n0 é um jogo muito simples e agradável, um pouco como o Sudoku ou o caça-minas.

Regras do jogo

(Eu recomendo usar o tutorial no jogo, se puder, é muito simples e útil)

O quebra-cabeça começa com um n * ntabuleiro contendo algumas peças fixas e algumas células vazias, e o solucionador deve encontrar uma maneira de preencher as células vazias com peças e satisfazer todas as restrições impostas pelas peças fixas. Aqui estão os tipos de peças que usaremos com a abreviação:

  • # Peça vermelha (vista em bloco de uma peça azul)
  • O Peça azul
  • . Local vazio
  • numberPeça azul numerada ( numberé um número de um dígito> 0)

Todas as peças numeradas devem ver exatamente a mesma quantidade de peças azuis que o número. Por exemplo:

#1O#O
...O.

A 1peça pode ver apenas uma outra peça azul.

Como as peças se vêem

Duas peças azuis podem se ver se estiverem na mesma linha ou coluna e nenhuma peça vermelha estiver entre elas. Exemplo:

( Sé um local que a Opeça pode ver, Xnão pode ser vista)

   S
   S
X#SOSS
   #
   X

Cada peça azul deve ver pelo menos uma outra peça azul:

#O#

Não vai funcionar, mas:

#OO

Ou:

###

Faça trabalho.

Placa de demonstração resolver

.1..
..1.
....
22#2

O canto inferior direito 2 só pode ver acima de si, portanto deve ser azul e o canto superior direito deve ser vermelho.

.1.#
..1O
...O
22#2

Uma vez que o 1é preenchido, podemos cercá-lo com pedaços vermelhos.

.1##
.#1O
..#O
22#2

A parte superior esquerda 1só pode ver em uma direção agora, para que possamos preenchê-la.

O1##
.#1O
..#O
22#2

Agora, sobre os últimos 2s. Podemos colocar 2 peças azuis sobre eles.

O1##
.#1O
OO#O
22#2

O último será preenchido com #

O1##
##1O
OO#O
22#2

Entrada

Entrada é uma sequência de linhas múltiplas. O tamanho será 9x9sem espaço à direita. Possui os seguintes tipos de peças:

  • . Esvaziar
  • # Predefinido em vermelho, não pode ser alterado
  • number Número predefinido, não pode ser alterado

(Observe que o azul nunca estará na entrada)

Resultado

A saída é igual à entrada, com a mudança de vazio ( .) é substituído por vermelho ou azul para resolver o quadro e os números são substituídos por peças azuis ( O).

Exemplos

(Observe que várias soluções podem ser possíveis para cada quebra-cabeça, mas você só precisa mostrar uma)

Input:
........4
...3.1...
45...2.3.
..9......
1..6#44..
....4..5.
....4.36.
2.......6
1....4...

Output:
OOO###OOO
OOOO#O#OO
OOO#OO#OO
#OOOO#O##
O#OO#OOOO
O#OOOO#OO
#OOOO#OOO
OO#O#OOOO
O#OOOO#O#

Input:
..7..#...
#...8..11
2....5...
..5...48.
...#...4.
.5...6...
...1.2...
2.....6.8
.7..#....

Output:
OOOOO####
##OOOO#OO
O#OOOO###
OOO#OOOOO
OO##O##O#
#O##OOOOO
#O#O#O#OO
OO#OOOOOO
OOO###O#O

Input:
5.3..33..
...4...23
.6.6.34..
...3#....
....5..4.
.5....3..
7.98.6#.3
.5.6..2..
..6...2..

Output:
OOOOO####
##OOOO#OO
O#OOOO###
OOO#OOOOO
OO##O##O#
#O##OOOOO
#O#O#O#OO
OO#OOOOOO
OOO###O#O

Obrigado a @PeterTaylor e @apsillers por toda a ajuda na caixa de areia!

J Atkin
fonte
Fiz apenas uma edição bem menor do título porque "an" soa melhor se a palavra seguinte começar com uma vogal - não espero que falantes de inglês não nativos ou mesmo falantes nativos se preocupem com isso, mas é gramatical.
gato

Respostas:

2

Haskell, 224 bytes

Não foi totalmente testado, porque é muito lento (pelo menos O(n*2^n^2)).

t=1<2
x!p|p<0=0|t=mod(div x$2^p)2
l#x=[[sum$map(p&)[-1,1,l+1,-l-1]|p<-[q..q+l]]|q<-[0,l..l*l],let i&v|x!i<1=0|t=x!(i+v)+(i+v)&v]
b%v|b<1=t|t=b==v
s b|l<-length b-1=[l#x|x<-[0..2^l^2],and.map and$zipWith(zipWith(%))b(l#x)]!!0

Explicação:

A idéia básica é representar um quadro de Red, Bluepeças como uma lista de listas de 0, 1, onde a lista de listas é compactada em um único número inteiro para facilitar a enumeração. Todos esses números inteiros para o tamanho da placa são gerados e convertidos em um formulário com contagens de vizinhos. A primeira placa desse tipo que é uma solução válida da entrada é retornada.

-- integer x at position p with out of bounds defined to be 0 (so no bounds checking)
(!) :: (Integral b, Integral r) => r -> b -> r
x ! p | p < 0     = 0 
      | otherwise = mod (div x (2^p)) 2


-- Sum of values from position p along vector v (x is implicit)
-- Note that a cartesian vector (x,y) in this representation is (l*x + y)
(&) :: (Integral a, Integral b) => b -> b -> a
p & v | x ! p == 0 = 0
      | otherwise  = x ! (p+v)  +  (p+v) & v


-- Value of board at position p (implicit x, l)
value :: Integral a => a -> a
value p = sum $ map (p&) [-1, 1, l+1, -l-1]


-- Integer to board, where l is length, x is input integer
(#) :: (Integral t, Integral a) => a -> t -> [[t]]
l # x = [[sum $ map (p&) [-1,1,l+1,-l-1] | p <- [q..q+l-1]] | q <- [0,l..l*l]]


-- Comparison operator, to see whether a solved board is a solution of the input
(%) :: (Num a, Ord a) => a -> a -> Bool
b % v | b == 0    = True
      | otherwise = b == v


-- Check one possible solution
check :: Integral a => [[a]] -> Int -> [[a]] -> Bool
check b l x = (and . (map and)) zipWith(zipWith (%)) b (l # x)

-- Solver
solve :: Integral t => [[t]] -> [[t]]
solve b = [l # x | x <- [0..2^l^2], check b l x]
  where
    l = length b

A parte que provavelmente poderia ser mais golfed é: and.map and$zipWith(zipWith(%)). Caso contrário, eu peguei alguns erros que adicionavam comprimento e provavelmente poderiam ser mais jogados.

Michael Klein
fonte