Solve a Numbrix puzzle: Difference between revisions

Line 2,207:

=={{header|Phix}}==

with javascript_semantics

with javascript_semantics

sequence board, knownx, knowny

include sets.e

sequence board, placed, px, py

integer size, limit, nchars, tries

integer w, h, limit, missing

string fmt, blank

bool solved

constant ROW = 1, COL = 2

function get_moves(integer n)

constant moves = {{-1,0},{0,-1},{0,1},{1,0}}

sequence res = {}

integer x = px[n], y = py[n]

function onboard(integer row, integer col)

if x>1 and board[y,x-1]=0 then res &= {{x-1,y}} end if

return row>=1 and row<=size and col>=nchars and col<=nchars*size

if x<w and board[y,x+1]=0 then res &= {{x+1,y}} end if

end function

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

function solve(integer row, integer col, integer n)

return res

integer nrow, ncol

end function

tries+= 1

if n>limit then return 1 end if

procedure solve()

if knownx[n] then

if missing=0 then

for move=1 to length(moves) do

solved = true

nrow = row+moves[move][ROW]

else

ncol = col+moves[move][COL]*nchars

-- scan for next to place, which will be the lowest

if nrow = knownx[n]

-- of those with either n+1 or n-1 already placed,

and ncol = knowny[n] then

-- checking that all needed can still be placed.

if solve(nrow,ncol,n+1) then return 1 end if

integer place

exit

sequence moves

end if

for n=limit to 1 by -1 do

end for

if not placed[n] then

return 0

bool plus1 = false

end if

if n<limit and placed[n+1] then

sequence wmoves = {}

place = n

for move=1 to length(moves) do

plus1 = true

nrow = row+moves[move][ROW]

moves = get_moves(n+1)

ncol = col+moves[move][COL]*nchars

if length(moves)=0 then

if onboard(nrow,ncol)

return -- fail/backtrack

and board[nrow][ncol]='.' then

end if

board[nrow][ncol-nchars+1..ncol] = sprintf(fmt,n)

end if

if solve(nrow,ncol,n+1) then return 1 end if

if n>1 and placed[n-1] then

board[nrow][ncol-nchars+1..ncol] = blank

place = n

end if

if plus1 then

end for

moves = intersection(moves,get_moves(n-1))

return 0

else

end function

moves = get_moves(n-1)

end if

procedure Numbrix(sequence s)

if length(moves)=0 then

integer y, ch, ch2, k

return -- fail/backtrack

atom t0 = time()

end if

s = split(s,'\n')

end if

size = length(s)

end if

limit = size*size

end for

nchars = length(sprintf(" %d",limit))

missing -= 1

fmt = sprintf(" %%%dd",nchars-1)

for m in moves do

blank = repeat('.',nchars)

integer {x,y} = m

board = repeat(repeat(' ',size*nchars),size)

px[place] = x

knownx = repeat(0,limit)

py[place] = y

knowny = repeat(0,limit)

board[y,x] = place

for x=1 to size do

placed[place] = true

for y=nchars to size*nchars by nchars do

solve()

ch = s[x][y]

if solved then return end if

if ch!='.' then

placed[place] = false

k = ch-'0'

board[y,x] = 0

ch2 = s[x][y-1]

end for

if ch2!=' ' then

missing += 1

k += (ch2-'0')*10

end if

board[x][y-1] = ch2

end procedure

end if

knownx[k] = x

procedure Numbrix(string s)

knowny[k] = y

atom t0 = time()

end if

board = split(s,'\n')

board[x][y] = ch

for i,line in board do

end for

board[i] = apply(split(substitute(line,'.','0')),to_number)

end for

end for

tries = 0

w = length(board[1])

if solve(knownx[1],knowny[1],2) then

h = length(board)

puts(1,join(board,"\n"))

limit = w*h

printf(1,"\nsolution found in %d tries (%3.2fs)\n",{tries,time()-t0})

placed = repeat(false,limit)

else

px = repeat(0,limit)

puts(1,"no solutions found\n")

py = repeat(0,limit)

end if

missing = 0

end procedure

for x=1 to w do

for y=1 to h do

constant board1 = """

. . . . . . ~~. . .~~

integer byx = board[y][x]

. . 46 45 . 55 74 . .

if byx then

. 38 . . 43 . . 78 .

placed[byx] = true

. 35 . . . . . 71 .

px[byx] = x

. . 33 . . . 59 . .

py[byx] = y

. 17 . . . ~~. . 67 .~~

else

. 18 . . 11 . . 64 .

missing += 1

. . 24 21 . 1 ~~2 . .~~

end if

. . . ~~. . . . . ."""~~

end for

Numbrix(board1)

solved = false

solve()

constant board2 = """

printf(1,"%s\n\n",s)

. . . . . . . . .

. 11 12 15 ~~18 21 62 61 .~~

if not solved then

. 6 . ~~. . . . 60 .~~

puts(1,"No solutions\n\n")

else

. 33 . . . . . 57 .

integer nchars = length(sprintf("%d",limit))

. 32 . . . . . 56 .

. 37 . 1 . ~~. . 73 .~~

string fmt = sprintf(" %%%dd",nchars)

printf(1,"solution found in %s:\n\n",elapsed(time()-t0))

. 38 . . . . . 72 .

board = apply(true,join_by,{board,1,w,{""},{""},{fmt}})

. 43 44 47 48 51 76 77 .

. . . ~~. . . . . .~~"""~~~~

printf(1,"%s\n\n",{join(board,"\n")})

end if

Numbrix(board2)

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>

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

Line 2,381:

28 25 24 21 10 1 2 3 4

27 26 23 22 9 8 7 6 5

solution found in 580 tries (0.00s)

. . . . . . . . .

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

Line 2,403:

40 43 44 47 48 51 76 77 78

41 42 45 46 49 50 81 80 79

solution found in 334 tries (0.00s)

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>