Solve a Numbrix puzzle: Difference between revisions
m
→{{header|Phix}}: deserved a complete rewrite, added 3rd & 4th puzzle, use pygments
m (→{{header|Phix}}: deserved a complete rewrite, added 3rd & 4th puzzle, use pygments) |
|||
Line 2,207:
=={{header|Phix}}==
<!--
<syntaxhighlight lang="phix">
with javascript_semantics
include sets.e
sequence board, placed, px, py
integer w, h, limit, missing
bool solved
function get_moves(integer n)
sequence res = {}
integer x = px[n], y = py[n]
if x>1 and board[y,x-1]=0 then res &= {{x-1,y}} end if
if x<w and board[y,x+1]=0 then res &= {{x+1,y}} end if
if y>1 and board[y-1,x]=0 then res &= {{x,y-1}} end if
if y<h and board[y+1,x]=0 then res &= {{x,y+1}} end if
return res
end function
procedure solve()
if missing=0 then
solved = true
else
-- scan for next to place, which will be the lowest
-- of those with either n+1 or n-1 already placed,
-- checking that all needed can still be placed.
integer place
sequence moves
for n=limit to 1 by -1 do
if not placed[n] then
bool plus1 = false
if n<limit and placed[n+1] then
place = n
plus1 = true
moves = get_moves(n+1)
if length(moves)=0 then
return -- fail/backtrack
end if
end if
if n>1 and placed[n-1] then
place = n
if plus1 then
moves = intersection(moves,get_moves(n-1))
else
moves = get_moves(n-1)
end if
if length(moves)=0 then
return -- fail/backtrack
end if
end if
end if
end for
missing -= 1
for m in moves do
integer {x,y} = m
px[place] = x
py[place] = y
board[y,x] = place
placed[place] = true
solve()
if solved then return end if
placed[place] = false
board[y,x] = 0
end for
missing += 1
end if
end procedure
procedure Numbrix(string s)
atom t0 = time()
board = split(s,'\n')
for i,line in board do
board[i] = apply(split(substitute(line,'.','0')),to_number)
end for
w = length(board[1])
h = length(board)
limit = w*h
placed = repeat(false,limit)
px = repeat(0,limit)
py = repeat(0,limit)
missing = 0
for x=1 to w do
for y=1 to h do
end for
solved = false
solve()
printf(1,"%s\n\n",s)
else
integer nchars = length(sprintf("%d",limit))
printf(1,"solution found in %s:\n\n",elapsed(time()-t0))
board = apply(true,join_by,{board,1,w,{""},{""},{fmt}})
end if
end procedure
constant boards = {"""
. . . . . . . . .
. . 46 45 . 55 74 . .
. 38 . . 43 . . 78 .
. 35 . . . . . 71 .
. . 33 . . . 59 . .
. 17 . . . . . 67 .
. 18 . . 11 . . 64 .
. . 24 21 . 1 2 . .
. . . . . . . . .""","""
. . . . . . . . .
. 11 12 15 18 21 62 61 .
. 6 . . . . . 60 .
. 33 . . . . . 57 .
. 32 . . . . . 56 .
. 37 . 1 . . . 73 .
. 38 . . . . . 72 .
. 43 44 47 48 51 76 77 .
. . . . . . . . .""","""
17 . . . 11 . . . 59
. 15 . . 6 . . 61 .
. . 3 . . . 63 . .
. . . . 66 . . . .
23 24 . 68 67 78 . 54 55
. . . . 72 . . . .
. . 35 . . . 49 . .
. 29 . . 40 . . 47 .
31 . . . 39 . . . 45""","""
109 0 0 0 0 0 0 0 0 0 0 0 0 0 43
0 0 0 0 0 0 0 65 0 0 0 0 0 0 0
0 0 101 100 0 92 0 76 0 68 0 48 3 0 0
0 0 102 97 0 0 80 0 74 0 0 49 6 0 0
0 0 0 0 0 0 79 0 73 0 0 0 0 0 0
0 0 116 0 0 0 0 0 0 0 0 0 10 0 0
0 0 0 118 217 0 0 0 0 0 55 52 0 0 0
0 121 120 0 0 0 0 213 0 0 0 0 12 35 0
0 0 0 166 167 0 0 0 0 0 205 204 0 0 0
0 0 162 0 0 0 0 0 0 0 0 0 14 0 0
0 0 0 0 0 0 173 0 177 0 0 0 0 0 0
0 0 156 153 0 0 150 0 178 0 0 201 16 0 0
0 0 155 154 0 144 0 180 0 188 0 200 17 0 0
0 0 0 0 0 0 0 183 0 0 0 0 0 0 0
135 0 0 0 0 0 0 0 0 0 0 0 0 0 21"""}
papply(boards,Numbrix)
</syntaxhighlight>
{{out}}
<pre>
. . . . . . . . .
. . 46 45 . 55 74 . .
. 38 . . 43 . . 78 .
. 35 . . . . . 71 .
. . 33 . . . 59 . .
. 17 . . . . . 67 .
. 18 . . 11 . . 64 .
. . 24 21 . 1 2 . .
. . . . . . . . .
solution found in 0.1s:
49 50 51 52 53 54 75 76 81
48 47 46 45 44 55 74 77 80
Line 2,323 ⟶ 2,381:
28 25 24 21 10 1 2 3 4
27 26 23 22 9 8 7 6 5
. . . . . . . . .
. 11 12 15 18 21 62 61 .
. 6 . . . . . 60 .
. 33 . . . . . 57 .
. 32 . . . . . 56 .
. 37 . 1 . . . 73 .
. 38 . . . . . 72 .
. 43 44 47 48 51 76 77 .
. . . . . . . . .
solution found in 0.0s:
9 10 13 14 19 20 63 64 65
8 11 12 15 18 21 62 61 66
Line 2,333 ⟶ 2,403:
40 43 44 47 48 51 76 77 78
41 42 45 46 49 50 81 80 79
17 . . . 11 . . . 59
. 15 . . 6 . . 61 .
. . 3 . . . 63 . .
. . . . 66 . . . .
23 24 . 68 67 78 . 54 55
. . . . 72 . . . .
. . 35 . . . 49 . .
. 29 . . 40 . . 47 .
31 . . . 39 . . . 45
solution found in 0.0s:
17 16 13 12 11 10 9 60 59
18 15 14 5 6 7 8 61 58
19 20 3 4 65 64 63 62 57
22 21 2 1 66 79 80 81 56
23 24 69 68 67 78 77 54 55
26 25 70 71 72 75 76 53 52
27 28 35 36 73 74 49 50 51
30 29 34 37 40 41 48 47 46
31 32 33 38 39 42 43 44 45
109 0 0 0 0 0 0 0 0 0 0 0 0 0 43
0 0 0 0 0 0 0 65 0 0 0 0 0 0 0
0 0 101 100 0 92 0 76 0 68 0 48 3 0 0
0 0 102 97 0 0 80 0 74 0 0 49 6 0 0
0 0 0 0 0 0 79 0 73 0 0 0 0 0 0
0 0 116 0 0 0 0 0 0 0 0 0 10 0 0
0 0 0 118 217 0 0 0 0 0 55 52 0 0 0
0 121 120 0 0 0 0 213 0 0 0 0 12 35 0
0 0 0 166 167 0 0 0 0 0 205 204 0 0 0
0 0 162 0 0 0 0 0 0 0 0 0 14 0 0
0 0 0 0 0 0 173 0 177 0 0 0 0 0 0
0 0 156 153 0 0 150 0 178 0 0 201 16 0 0
0 0 155 154 0 144 0 180 0 188 0 200 17 0 0
0 0 0 0 0 0 0 183 0 0 0 0 0 0 0
135 0 0 0 0 0 0 0 0 0 0 0 0 0 21
solution found in 0.5s:
109 108 87 86 85 84 83 64 63 62 61 46 45 44 43
110 107 88 89 90 91 82 65 66 67 60 47 2 1 42
111 106 101 100 99 92 81 76 75 68 59 48 3 4 41
112 105 102 97 98 93 80 77 74 69 58 49 6 5 40
113 104 103 96 95 94 79 78 73 70 57 50 7 8 39
114 115 116 225 224 223 222 221 72 71 56 51 10 9 38
123 122 117 118 217 218 219 220 209 208 55 52 11 36 37
124 121 120 119 216 215 214 213 210 207 54 53 12 35 34
125 164 165 166 167 168 169 212 211 206 205 204 13 32 33
126 163 162 161 160 171 170 175 176 191 192 203 14 31 30
127 128 157 158 159 172 173 174 177 190 193 202 15 28 29
130 129 156 153 152 151 150 179 178 189 194 201 16 27 26
131 132 155 154 143 144 149 180 181 188 195 200 17 24 25
134 133 138 139 142 145 148 183 182 187 196 199 18 23 22
135 136 137 140 141 146 147 184 185 186 197 198 19 20 21
</pre>
|