Memecahkan papan 0j n0

19

0h n0 adalah gim yang sangat sederhana dan menyenangkan, sedikit mirip dengan Sudoku atau kapal penyapu ranjau.

Aturan gim

(Saya sarankan menggunakan tutorial dalam game jika Anda bisa, itu sangat sederhana dan bermanfaat)

Teka-teki dimulai dengan n * npapan yang berisi beberapa potongan tetap dan beberapa sel kosong, dan pemecah harus menemukan cara untuk mengisi sel kosong dengan potongan dan memenuhi semua kendala yang dikenakan oleh potongan tetap. Berikut adalah jenis potongan yang akan kami gunakan dengan singkatan:

  • # Potongan merah (menghalangi tampilan potongan biru)
  • O Sepotong biru
  • . Lokasi kosong
  • numberPotongan biru bernomor ( numberadalah angka satu digit> 0)

Semua bagian yang bernomor harus melihat jumlah yang sama persis dengan bagian yang biru. Sebagai contoh:

#1O#O
...O.

The 1piece bisa melihat hanya satu bagian biru lainnya.

Bagaimana potongan saling melihat

Dua keping biru dapat saling melihat jika berada di baris atau kolom yang sama dan tidak ada keping merah di antara keduanya. Contoh:

( Sadalah lokasi yang Odapat dilihat potongan itu, Xtidak dapat dilihat)

   S
   S
X#SOSS
   #
   X

Setiap keping biru harus melihat setidaknya satu keping biru lainnya:

#O#

Tidak akan bekerja, tetapi:

#OO

Atau:

###

Bekerja.

Papan demo dipecahkan

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

Bagian kanan bawah 2 hanya dapat melihat di atas itu sendiri, sehingga mereka harus berwarna biru, dan kanan atas harus berwarna merah.

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

Karena 1diisi, kita bisa mengelilinginya dengan potongan merah.

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

Kiri atas 1hanya bisa melihat satu arah sekarang, jadi kita bisa mengisinya.

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

Sekarang tentang yang terakhir 2. Kita bisa meletakkan 2 potongan biru di atasnya.

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

Yang terakhir akan diisi #

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

Memasukkan

Input adalah string multi-line. Ukurannya akan 9x9tanpa spasi tambahan. Ini memiliki jenis potongan berikut:

  • . Kosong
  • # Merah standar, tidak dapat diubah
  • number Nomor preset, tidak dapat diubah

(Perhatikan bahwa biru tidak akan pernah ada dalam input)

Keluaran

Output sama dengan input, dengan perubahan yang kosong ( .) diganti dengan merah atau biru untuk menyelesaikan papan, dan angka diganti dengan potongan biru ( O).

Contohnya

(Perhatikan bahwa beberapa solusi dimungkinkan untuk setiap puzzle, tetapi Anda hanya perlu menunjukkan salah satunya)

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

Terima kasih kepada @PeterTaylor dan @apsillers untuk semua bantuan mereka di kotak pasir!

J Atkin
sumber
Saya membuat sedikit pengeditan untuk judul karena "sebuah" terdengar lebih baik jika kata berikut dimulai dengan vokal - Saya tidak berharap penutur bahasa Inggris non-pribumi atau bahkan penutur asli terganggu dengan hal itu, tetapi ini gramatikal.
kucing

Jawaban:

2

Haskell, 224 byte

Tidak sepenuhnya diuji, karena sangat lambat (setidaknya 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

Penjelasan:

Ide dasarnya adalah untuk mewakili papan Red, Bluepotongan sebagai daftar daftar0, 1 , di mana daftar daftar dikemas ke dalam bilangan bulat tunggal untuk enumerasi yang lebih mudah. Semua bilangan bulat untuk ukuran papan dihasilkan dan dikonversi ke formulir dengan jumlah tetangga. Papan pertama yang merupakan solusi input yang valid dikembalikan.

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

Bagian yang mungkin bisa paling golfed adalah: and.map and$zipWith(zipWith(%)). Kalau tidak, saya menangkap beberapa kesalahan satu per satu yang menambah panjang dan mungkin bisa golf lebih banyak.

Michael Klein
sumber