-
Notifications
You must be signed in to change notification settings - Fork 0
/
lib.ua
92 lines (82 loc) · 2.23 KB
/
lib.ua
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
# Random choice
RC ← ⊡⌊×⚂⧻.
# Permutations
Perms ← ☇1⍉∧(≡↻⇡⟜↯+1⟜⊂)↘1⇡:¤¤0
LoadNKings ↚ ↯⊟∞:°⋯↯⊟∞⧻∩⋯⟜:°⊂&frab$"cache/_"
NKingsImpl ↚ ▽≡/×≠1⌵≡(≡/-◫)2.Perms
# Number of ways to arrange N non attacking kings
# on an NxN board with 1 per row and 1 per column
NKings ← memo⍣LoadNKings NKingsImpl
Adjs ← ⊂¯.⊟⇌.0_1
RawProgressBar ← ⊂▽:@█:⊡⌊×⧻⟜:"▏▎▍▌▋▊▉":⟜-⌊.×
ProgressBar ← $"[_]"⬚@\s↙⟜RawProgressBar
GenSol ← ⬚0≡°⊚ RC NKings
LabelSol ← ⍜⊚(▽+1⇡⧻.)
Solve ← ⊚/×=1↘1⍉⬚0≡°⊚⍜⍉≡⊏NKings⧻.
Solvable ← =1⧻Solve
GrowPuz ← (
RC.⊚±.
⊙⊙:⊃⊙⧻⊡⊙,
⊙.:+Adjs¤
▽≡/××⊓≥<0,
▽¬∊⟜:
⍜⊡◌⊙:RC
)
PreGrow ← (
=⟜:+1⇡⧻⟜¤
/↥×≡GrowPuz
)
# Recursive superposition-collapse exhaustive search with
# optimized solvability and contiguous adjacency checking
IncGenPuzRec ↚ |3.3 (
# Accessibility check
°□∧⍜⊙◇⊡(⍚▽≠,)⟜⍚(
↥0-⊓≠×1:2∵◇⊃⧻/↥=
⊚=1⍜⊜□⍚(∵⋅∘⟜/↥)±.
)+1⇡⧻⟜¤.
⍤"unreachable cell"/×±♭∵◇⧻.
⟜(
∵◇⊢×=1∵◇⧻.
# Contiguousness check
=∩⧻,⊜⊢..
⍤"not contiguous"
# Solvability check and filtering
⬚0≡°⊚⍜⍉≡⊏⊏:NKings⧻,,
=1/+∩/×⊓=<1,2↘1⍉
▽⍤"not solvable"
)
∵◇⧻.
&p.&pf$"\x1b[_A\r\x1b[J"+5⧻.
⊙.××-1..:/+♭⟜⧻-1.
&p $"\x1b[2K\r_" ProgressBar 20 ×.¬÷
&p $"\x1b[2K\runcertainty: _"
&p $"\x1b[2K\rsearch size: _" ⧻:⊙,
&pf $"\x1b[2K\rrecursion depth: _" :⊙:⊙⊙⊃:⋅(+1)
¬/×♭=1
# Runs once iff the puzzle is incomplete
⍥(
∵≍⍚¤+1⇡⧻⟜¤.
⍚(◴/⊂≡(+Adjs¤)⊚)
⍚(▽≡/×)×⊓≤>,0,⧻,
:>1⍚≡◇⧻.⍚⊡,¤,
⍚▽×⍚≡◇∊+1⇡⧻.
∩▽,+1⇡⧻.±≡◇⧻.
∩⊡⟜:⌊×⚂⧻.
⊙◇RC
⍣(
IncGenPuzRec⍜⊡◌⊙::□¤
| IncGenPuzRec⍜⊙⊡(□▽≠⊙◇.)
)
)
)
IncGenPuz ← (
:¤¤+1⇡⧻.
≡⍚⟨⋅∘|¤⟩±.
:⇡⧻NKings⧻.
&p∵⋅0.
&p▽2@\n
⊙⊙0
IncGenPuzRec
&p""
∵◇⊢⊙∩◌
)