Solve a Numbrix puzzle: Difference between revisions
Content added Content deleted
(made more idiomatic, using vector in place of new array, etc) |
Alpha bravo (talk | contribs) (Added AutoHotkey) |
||
Line 65: | Line 65: | ||
* [[Solve a Hopido puzzle]] |
* [[Solve a Hopido puzzle]] |
||
* [[Knight's tour]] |
* [[Knight's tour]] |
||
=={{header|AutoHotkey}}== |
|||
<lang AutoHotkey>SolveNumbrix(Grid, Locked, Max, row, col, num:=1, R:="", C:=""){ |
|||
if (R&&C) ; if neighbors (not first iteration) |
|||
{ |
|||
Grid[R, C] := ">" num ; place num in current neighbor and mark it visited ">" |
|||
row:=R, col:=C ; move to current neighbor |
|||
} |
|||
num++ ; increment num |
|||
if (num=max) ; if reached end |
|||
return map(Grid) ; return solution |
|||
if locked[num] ; if current num is a locked value |
|||
{ |
|||
row := StrSplit((StrSplit(locked[num], ",").1) , ":").1 ; find row of num |
|||
col := StrSplit((StrSplit(locked[num], ",").1) , ":").2 ; find col of num |
|||
if SolveNumbrix(Grid, Locked, Max, row, col, num) ; solve for current location and value |
|||
return map(Grid) ; if solved, return solution |
|||
} |
|||
else |
|||
{ |
|||
for each, value in StrSplit(Neighbor(row,col), ",") |
|||
{ |
|||
R := StrSplit(value, ":").1 |
|||
C := StrSplit(value, ":").2 |
|||
if (Grid[R,C] = "") ; a hole or out of bounds |
|||
|| InStr(Grid[R, C], ">") ; visited |
|||
|| Locked[num+1] && !(Locked[num+1]~= "\b" R ":" C "\b") ; not neighbor of locked[num+1] |
|||
|| Locked[num-1] && !(Locked[num-1]~= "\b" R ":" C "\b") ; not neighbor of locked[num-1] |
|||
|| Locked[num] ; locked value |
|||
|| Locked[Grid[R, C]] ; locked cell |
|||
continue |
|||
if SolveNumbrix(Grid, Locked, Max, row, col, num, R, C) ; solve for current location, neighbor and value |
|||
return map(Grid) ; if solved, return solution |
|||
} |
|||
} |
|||
num-- ; step back |
|||
for i, line in Grid |
|||
for j, element in line |
|||
if InStr(element, ">") && (StrReplace(element, ">") >= num) |
|||
Grid[i, j] := 0 |
|||
} |
|||
;-------------------------------- |
|||
;-------------------------------- |
|||
;-------------------------------- |
|||
Neighbor(row,col){ |
|||
return row-1 ":" col |
|||
. "," row+1 ":" col |
|||
. "," row ":" col+1 |
|||
. "," row ":" col-1 |
|||
} |
|||
;-------------------------------- |
|||
map(Grid){ |
|||
for i, row in Grid |
|||
{ |
|||
for j, element in row |
|||
line .= (A_Index > 1 ? "`t" : "") . element |
|||
map .= (map<>""?"`n":"") line |
|||
line := "" |
|||
} |
|||
return StrReplace(map, ">") |
|||
}</lang> |
|||
Examples:<lang AutoHotkey>;-------------------------------- |
|||
Grid := [[0, 0, 0, 0, 0, 0, 0, 0, 0] |
|||
,[0, 0, 46, 45, 0, 55, 74, 0, 0] |
|||
,[0, 38, 0, 0, 43, 0, 0, 78, 0] |
|||
,[0, 35, 0, 0, 0, 0, 0, 71, 0] |
|||
,[0, 0, 33, 0, 0, 0, 59, 0, 0] |
|||
,[0, 17, 0, 0, 0, 0, 0, 67, 0] |
|||
,[0, 18, 0, 0, 11, 0, 0, 64, 0] |
|||
,[0, 0, 24, 21, 0, 1, 2, 0, 0] |
|||
,[0, 0, 0, 0, 0, 0, 0, 0, 0]] |
|||
;-------------------------------- |
|||
; find locked cells, find row and col of first value "1" and max value |
|||
Locked := [] |
|||
max := 1 |
|||
for i, line in Grid |
|||
for j, element in line |
|||
{ |
|||
max ++ |
|||
if element = 1 |
|||
row :=i , col := j |
|||
if (element > 0) |
|||
Locked[element] := i ":" j "," Neighbor(i, j) ; save locked elements position and neighbors |
|||
} |
|||
;-------------------------------- |
|||
MsgBox, 262144, ,% SolveNumbrix(Grid, Locked, Max, row, col) |
|||
return |
|||
</lang> |
|||
Outputs:<pre>49 50 51 52 53 54 75 76 81 |
|||
48 47 46 45 44 55 74 77 80 |
|||
37 38 39 40 43 56 73 78 79 |
|||
36 35 34 41 42 57 72 71 70 |
|||
31 32 33 14 13 58 59 68 69 |
|||
30 17 16 15 12 61 60 67 66 |
|||
29 18 19 20 11 62 63 64 65 |
|||
28 25 24 21 10 1 2 3 4 |
|||
27 26 23 22 9 8 7 6 5</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |