0h n0 to bardzo prosta i przyjemna gra, trochę jak Sudoku lub trałowiec.

Zasady gry

(Polecam użycie samouczka w grze, jeśli możesz, jest to bardzo proste i przydatne)

Łamigłówka zaczyna się od n * nplanszy zawierającej pewne ustalone elementy i niektóre puste komórki, a solver musi znaleźć sposób na wypełnienie pustych komórek elementami i spełnienie wszystkich ograniczeń nałożonych przez ustalone elementy. Oto rodzaje sztuk, których będziemy używać ze skrótem:

• # Kawałek czerwony (blokuje widok niebieskiego kawałka)
• O Niebieski kawałek
• . Pusta lokalizacja
• numberNumerowany niebieski kawałek ( numberjest liczbą jednocyfrową> 0)

Wszystkie ponumerowane elementy muszą widzieć dokładnie tyle samo niebieskich elementów co liczba. Na przykład:

#1O#O
...O.

1Kawałek można zobaczyć tylko jeden inny kawałek niebieskiego.

Jak kawałki się widzą

Dwa niebieskie elementy mogą się widzieć, jeśli są w tym samym rzędzie lub kolumnie i między nimi nie ma czerwonego elementu. Przykład:

( Sjest to miejsce, które Okawałek widzi, Xnie można go zobaczyć)

   S
   S
X#SOSS
   #
   X

Każdy niebieski element musi widzieć co najmniej jeden inny niebieski element:

#O#

Nie zadziała, ale:

#OO

Lub:

###

Wykonać pracę.

Rozwiąż planszę demo

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

Prawy dolny 2 może widzieć tylko nad sobą, więc muszą być niebieskie, a prawe górne czerwone.

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

Ponieważ 1jest on wypełniony, możemy go otoczyć czerwonymi kawałkami.

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

Lewy górny róg 1może teraz widzieć tylko w jednym kierunku, więc możemy go wypełnić.

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

Teraz o tych ostatnich 2. Możemy nałożyć na nie 2 niebieskie kawałki.

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

Ostatni zostanie wypełniony #

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

Wejście

Dane wejściowe są łańcuchem wieloliniowym. Rozmiar będzie 9x9bez spacji końcowych. Ma następujące rodzaje sztuk:

• . Pusty
• # Wstępnie ustawiony czerwony, nie można go zmienić
• number Zaprogramowanego numeru nie można zmienić

(Uwaga: niebieski nigdy nie będzie na wejściu)

Wynik

Dane wyjściowe są takie same jak dane wejściowe, z tą zmianą, że pusty ( .) jest zastępowany przez czerwony lub niebieski, aby rozwiązać planszę, a liczby są zastępowane przez niebieskie elementy ( O).

Przykłady

(Pamiętaj, że dla każdej układanki może być dostępnych wiele rozwiązań, ale wystarczy pokazać tylko jedno z nich)

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

_{Dzięki @PeterTaylor i @apsillers za wszelką pomoc w piaskownicy!}

Haskell, 224 bajty

Nie w pełni przetestowane, ponieważ jest tak wolne (przynajmniej 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

Wyjaśnienie:

Podstawową ideą jest przedstawienie tablicy Red, Blueelementów jako listy list 0, 1, gdzie lista list jest spakowana w jedną liczbę całkowitą dla łatwiejszego wyliczenia. Wszystkie takie liczby całkowite dla rozmiaru płyty są generowane i konwertowane na formularz z liczeniem sąsiadów. Pierwsza taka tablica, która jest prawidłowym rozwiązaniem wejścia, jest zwracana.

-- 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

Część, która mogłaby prawdopodobnie najbardziej golfed jest: and.map and$zipWith(zipWith(%)). W przeciwnym razie wyłapałem kilka błędów jeden po drugim, które zwiększyły długość i prawdopodobnie mogłyby być bardziej golfa.