고전적인 Boggle 단어 게임을 위한 솔버 구현입니다! Boggle의 강렬한 게임에서 보드에 있는 가능한 모든 단어를 다 써버렸다고 생각한 적이 있습니까? 더 이상 생각하지 마세요!
선택한 사전 파일과 사용자 정의 크기의 보드가 주어지면 Boggle 보드에 존재하는 모든 영어 단어를 즉시 얻을 수 있습니다! (내 컴퓨터의 알고리즘은 50x50 보드에서 3초 미만으로 실행됩니다!!) 제가 제공한 것 이외의 사전을 사용하고 싶다면 문제 없습니다. 각 단어가 개행 문자로 구분되어 있는지 확인하세요.
루트 프로젝트 디렉터리로 이동한 후 터미널에서 다음 명령을 사용합니다.
Mac OS X gradlew -PmainClass=Boggle solve
Windows gradlew.bat -PmainClass=Boggle solve
Boggle.java 파일이 수정되지 않았다고 가정하면 이 프로그램은 다음 보드에 포함된 모든 단어를 찾습니다.
Solving:
a r m
b e s
n i m
arsine
rabies
bismer
bersim
barmen
miners
minbar
abime
abies
abner
resin
bines
bisme
biers
benim
besin
besra
berms
bears
bearm
braes
barse
bares
barms
smear
serab
smear
nears
inerm
mines
miner
miser
arse
aren
ares
arms
rems
reim
rein
reis
rems
rabi
mems
mein
mear
mrem
bine
bise
bien
bier
beni
berm
bear
brei
bren
bars
bare
barm
ears
sime
sine
sier
semi
serb
sera
sear
nims
nies
near
inbe
mise
mien
mems
mear
aes
aer
abn
abr
ars
are
arb
arm
rem
rei
ren
res
reb
rem
rea
rms
rab
mem
men
mer
mea
mrs
bim
bin
bis
ben
bes
ber
bra
bae
bar
ems
ems
ers
era
ear
sim
sin
sie
sib
sem
sei
sen
sem
ser
sea
nim
nis
nib
nei
neb
nea
ism
ise
ism
iba
min
mis
mib
men
mem
mer
mea
상상할 수 있듯이, 가능한 모든 문자 순서가 영어 단어인지 확인하기 위해 사전을 찾는 것은 상당히 힘든 작업입니다. nxn 크기의 모든 보드에 대해 최대 n^2 x (n^2)가 있다는 것이 밝혀졌습니다! 유효성을 확인해야 하는 가능한 문자 순서입니다. 이는 분명히 매우 빠르게 분석됩니다. 간단한 3 x 3 보드에는 최대 3265920개의 검증이 필요하며 이는 실제 Boggle 보드 크기도 아닙니다! 그래서 내가 어떻게 했나요? 내 말은, 8 x 8 보드를 푸는 것조차 최대 대략 10^90 계산이 필요하다는 뜻입니다! 여기서 정말 영리한 일을 한 게 틀림없어요. 믿을 수 없을 만큼 더 효율적인 접근 방식이 존재한다는 것이 밝혀졌습니다. 해결 알고리즘의 핵심은 Trie라고 알려진 특정 데이터 구조를 중심으로 진행됩니다. 길이가 n 인 문자열이 주어지면 Trie는 우리가 찾고 있는 문자열이 O(n) (선형) 시간 내에 사전에 존재하는지 여부를 알려줄 수 있습니다! 이는 사전 파일에서 가능한 각 단어에 대해 이진 검색을 실행하는 것보다 크게 개선되었습니다. 실제로 Trie는 기존 문자열에 문자를 추가하면 일정한 시간 안에 또 다른 유효한 단어가 생성되는지 여부를 확인할 수 있습니다! 이것이 알고리즘을 빠른 속도로 만드는 이유입니다. 보드의 각 문자에서 깊이 우선 검색을 수행하고, 현재 구성한 단어에 인접한 문자를 추가하고, 포함된 단어가 나오면 결과에 추가합니다. 우리 사전에. 어느 시점에서 다른 단어의 접두사가 아닌 문자열에 도달하면 가장 가까운 유효한 접두사로 되돌아가 계속 진행합니다. 꽤 멋진 것들!
그러나 런타임 효율성에는 비용이 따릅니다. 내가 사용하는 사전 파일은 대략 5MB의 텍스트이므로 모든 단어를 사전 Trie로 컴파일하는 데 필요한 공간은 상당히 엄청납니다. 사전에서 Trie를 구성하는 것은 실제로 내 컴퓨터에서 평균 ~2.2초의 실행 속도로 완료하는 데 가장 오랜 시간이 걸립니다. 긍정적인 면을 보면, Trie 사전을 만드는 데는 우리가 풀고 있는 보드의 크기에 비해 일정한 시간과 공간이 필요합니다. 문제가 되는 유일한 요소는 해결 알고리즘의 런타임입니다. 이는 3초 이내에 최대 50 x 50 크기의 보드를 해결하는 데 효율적인 것으로 입증되었습니다. 극단적인 범위에 관심이 있다면 내 시스템에서 알고리즘이 250 x 250 보드에 대한 솔루션을 찾는 데 약 77초가 걸렸습니다.
