Solve a Numbrix puzzle: Difference between revisions
(unneeded variables deleted!) |
({{Out}}) |
||
Line 1: | Line 1: | ||
{{task}} |
{{task}} |
||
Numbrix puzzles are similar to [[Solve a Hidato puzzle|Hidato]]. |
|||
The most important difference is that it is only possible to move 1 node left, right, up, or down (sometimes referred to as the [[wp:Von Neumann neighborhood|Von Neumann neighborhood]]). |
|||
Published puzzles also tend not to have holes in the grid and may not always indicate the end node. |
|||
Two examples follow: |
|||
;Example 1 |
;Example 1 |
||
Line 53: | Line 56: | ||
</pre> |
</pre> |
||
;Task |
;Task |
||
Write a program to solve puzzles of this ilk, |
Write a program to solve puzzles of this ilk, |
||
demonstrating your program by solving the above examples. |
|||
Extra credit for other interesting examples. |
|||
Related Tasks: |
|||
* [[Solve a Hidato puzzle]] |
* [[Solve a Hidato puzzle]] |
||
* [[Solve a Holy Knight's tour]] |
* [[Solve a Holy Knight's tour]] |
||
Line 219: | Line 224: | ||
} |
} |
||
</lang> |
</lang> |
||
{{Out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
49 50 51 52 53 54 75 76 81 |
49 50 51 52 53 54 75 76 81 |
||
Line 346: | Line 351: | ||
end</lang> |
end</lang> |
||
Sample runs: |
{{Out}}Sample runs: |
||
<pre> |
<pre> |
||
->numbrix <numbrix1.in |
->numbrix <numbrix1.in |
||
Line 676: | Line 681: | ||
end /*r*/ |
end /*r*/ |
||
say; return</lang> |
say; return</lang> |
||
{{Out}} when using the input of:<br> |
|||
<tt> 1 1 . . . . . . . . ./2 1 . . 24 21 . 1 2 . ./3 1 . 18 . . 11 . . 64 ./4 1 . 17 . . . . . 67 ./5 1 . . 33 . . . 59 . ./6 1 . 35 . . . . . 71 ./7 1 . 38 . . 43 . . 78 ./8 1 . . 46 45 . 55 74 . ./9 1 . . . . . . . . . </tt> |
|||
<pre> |
<pre> |
||
. . . . . . . . . |
. . . . . . . . . |
||
Line 702: | Line 707: | ||
27 26 23 22 9 8 7 6 5 |
27 26 23 22 9 8 7 6 5 |
||
</pre> |
</pre> |
||
{{Out}} when using the input of:<br> |
|||
<tt> 1 1 . . . . . . . . .\2 1 . 43 44 47 48 51 76 77 .\3 1 . 38 . . . . . 72 .\4 1 . 37 . 1 . . . 73 .\5 1 . 32 . . . . . 56 .\6 1 . 33 . . . . . 57 .\7 1 . 6 . . . . . 60 .\8 1 . 11 12 15 18 21 62 61 .\9 1 . . . . . . . . . </tt> |
|||
<pre> |
<pre> |
||
. . . . . . . . . |
. . . . . . . . . |
Revision as of 19:52, 22 October 2014
You are encouraged to solve this task according to the task description, using any language you may know.
Numbrix puzzles are similar to Hidato. The most important difference is that it is only possible to move 1 node left, right, up, or down (sometimes referred to as the Von Neumann neighborhood). Published puzzles also tend not to have holes in the grid and may not always indicate the end node. Two examples follow:
- Example 1
Problem.
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
Solution.
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
- Example 2
Problem.
0 0 0 0 0 0 0 0 0 0 11 12 15 18 21 62 61 0 0 6 0 0 0 0 0 60 0 0 33 0 0 0 0 0 57 0 0 32 0 0 0 0 0 56 0 0 37 0 1 0 0 0 73 0 0 38 0 0 0 0 0 72 0 0 43 44 47 48 51 76 77 0 0 0 0 0 0 0 0 0 0
Solution.
9 10 13 14 19 20 63 64 65 8 11 12 15 18 21 62 61 66 7 6 5 16 17 22 59 60 67 34 33 4 3 24 23 58 57 68 35 32 31 2 25 54 55 56 69 36 37 30 1 26 53 74 73 70 39 38 29 28 27 52 75 72 71 40 43 44 47 48 51 76 77 78 41 42 45 46 49 50 81 80 79
- Task
Write a program to solve puzzles of this ilk, demonstrating your program by solving the above examples. Extra credit for other interesting examples.
Related Tasks:
C++
<lang cpp>
- include <vector>
- include <sstream>
- include <iostream>
- include <iterator>
- include <stdlib.h>
- include <string.h>
using namespace std;
struct node {
int val; unsigned char neighbors;
};
class nSolver { public:
nSolver() { dx[0] = -1; dy[0] = 0; dx[1] = 1; dy[1] = 0;
dx[2] = 0; dy[2] = -1; dx[3] = 0; dy[3] = 1;
}
void solve( vector<string>& puzz, int max_wid ) {
if( puzz.size() < 1 ) return; wid = max_wid; hei = static_cast<int>( puzz.size() ) / wid; int len = wid * hei, c = 0; max = len; arr = new node[len]; memset( arr, 0, len * sizeof( node ) ); weHave = new bool[len + 1]; memset( weHave, 0, len + 1 );
for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ ) { if( ( *i ) == "*" ) { max--; arr[c++].val = -1; continue; } arr[c].val = atoi( ( *i ).c_str() ); if( arr[c].val > 0 ) weHave[arr[c].val] = true; c++; }
solveIt(); c = 0; for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ ) { if( ( *i ) == "." ) { ostringstream o; o << arr[c].val; ( *i ) = o.str(); } c++; } delete [] arr; delete [] weHave;
}
private:
bool search( int x, int y, int w, int dr ) {
if( ( w > max && dr > 0 ) || ( w < 1 && dr < 0 ) || ( w == max && weHave[w] ) ) return true;
node* n = &arr[x + y * wid]; n->neighbors = getNeighbors( x, y ); if( weHave[w] ) { for( int d = 0; d < 4; d++ ) { if( n->neighbors & ( 1 << d ) ) { int a = x + dx[d], b = y + dy[d]; if( arr[a + b * wid].val == w ) if( search( a, b, w + dr, dr ) ) return true; } } return false; }
for( int d = 0; d < 4; d++ ) { if( n->neighbors & ( 1 << d ) ) { int a = x + dx[d], b = y + dy[d]; if( arr[a + b * wid].val == 0 ) { arr[a + b * wid].val = w; if( search( a, b, w + dr, dr ) ) return true; arr[a + b * wid].val = 0; } } } return false;
}
unsigned char getNeighbors( int x, int y ) {
unsigned char c = 0; int a, b; for( int xx = 0; xx < 4; xx++ ) { a = x + dx[xx], b = y + dy[xx]; if( a < 0 || b < 0 || a >= wid || b >= hei ) continue; if( arr[a + b * wid].val > -1 ) c |= ( 1 << xx ); } return c;
}
void solveIt() {
int x, y, z; findStart( x, y, z ); if( z == 99999 ) { cout << "\nCan't find start point!\n"; return; } search( x, y, z + 1, 1 );
if( z > 1 ) search( x, y, z - 1, -1 ); }
void findStart( int& x, int& y, int& z ) { z = 99999;
for( int b = 0; b < hei; b++ ) for( int a = 0; a < wid; a++ ) if( arr[a + wid * b].val > 0 && arr[a + wid * b].val < z ) { x = a; y = b; z = arr[a + wid * b].val; }
}
int wid, hei, max, dx[4], dy[4]; node* arr; bool* weHave;
}; //------------------------------------------------------------------------------ int main( int argc, char* argv[] ) {
int wid; string p; //p = ". . . . . . . . . . . 46 45 . 55 74 . . . 38 . . 43 . . 78 . . 35 . . . . . 71 . . . 33 . . . 59 . . . 17 . . . . . 67 . . 18 . . 11 . . 64 . . . 24 21 . 1 2 . . . . . . . . . . ."; wid = 9; //p = ". . . . . . . . . . 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 . . . . . . . . . ."; wid = 9; p = "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"; wid = 9;
istringstream iss( p ); vector<string> puzz; copy( istream_iterator<string>( iss ), istream_iterator<string>(), back_inserter<vector<string> >( puzz ) ); nSolver s; s.solve( puzz, wid );
int c = 0; for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ ) {
if( ( *i ) != "*" && ( *i ) != "." ) { if( atoi( ( *i ).c_str() ) < 10 ) cout << "0"; cout << ( *i ) << " "; } else cout << " "; if( ++c >= wid ) { cout << endl; c = 0; }
} cout << endl << endl; return system( "pause" );
} </lang>
- Output:
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 01 02 03 04 27 26 23 22 09 08 07 06 05 09 10 13 14 19 20 63 64 65 08 11 12 15 18 21 62 61 66 07 06 05 16 17 22 59 60 67 34 33 04 03 24 23 58 57 68 35 32 31 02 25 54 55 56 69 36 37 30 01 26 53 74 73 70 39 38 29 28 27 52 75 72 71 40 43 44 47 48 51 76 77 78 41 42 45 46 49 50 81 80 79 17 16 13 12 11 10 09 60 59 18 15 14 05 06 07 08 61 58 19 20 03 04 65 64 63 62 57 22 21 02 01 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
Icon and Unicon
This is a Unicon-specific solution, based on the Unicon Hidato problem solver: <lang unicon>global nCells, cMap, best record Pos(r,c)
procedure main(A)
puzzle := showPuzzle("Input",readPuzzle()) QMouse(puzzle,findStart(puzzle),&null,0) showPuzzle("Output", solvePuzzle(puzzle)) | write("No solution!")
end
procedure readPuzzle()
# Start with a reduced puzzle space p := [] nCells := maxCols := 0 every line := !&input do { put(p,[: gencells(line) :]) maxCols <:= *p[-1] } # Now normalize all rows to the same length every i := 1 to *p do p[i] := [: !p[i] | (|-1\(maxCols - *p[i])) :] return p
end
procedure gencells(s)
static WS, NWS initial { NWS := ~(WS := " \t") cMap := table() # Map to/from internal model cMap["_"] := 0; cMap[0] := "_" }
s ? while not pos(0) do { w := (tab(many(WS))|"", tab(many(NWS))) | break w := numeric(\cMap[w]|w) if -1 ~= w then nCells +:= 1 suspend w }
end
procedure showPuzzle(label, p)
write(label," with ",nCells," cells:") every r := !p do { every c := !r do writes(right((\cMap[c]|c),*nCells+1)) write() } return p
end
procedure findStart(p)
if \p[r := !*p][c := !*p[r]] = 1 then return Pos(r,c)
end
procedure solvePuzzle(puzzle)
if path := \best then { repeat { loc := path.getLoc() puzzle[loc.r][loc.c] := path.getVal() path := \path.getParent() | break } return puzzle }
end
class QMouse(puzzle, loc, parent, val)
method getVal(); return val; end method getLoc(); return loc; end method getParent(); return parent; end method atEnd(); return (nCells = val, puzzle[loc.r,loc.c] = (val|0)); end method visit(r,c); return (/best, validPos(r,c), Pos(r,c)); end
method validPos(r,c) v := val+1 # number we're looking for xv := puzzle[r,c] | fail if (xv ~= 0) & (xv != v) then fail if xv = (0|v) then { ancestor := self while xl := (ancestor := \ancestor.getParent()).getLoc() do if (xl.r = r) & (xl.c = c) then fail return } end
initially
val := val+1 if atEnd() then return best := self QMouse(puzzle, visit(loc.r-1,loc.c) , self, val) # North QMouse(puzzle, visit(loc.r, loc.c+1), self, val) # East QMouse(puzzle, visit(loc.r+1,loc.c), self, val) # South QMouse(puzzle, visit(loc.r, loc.c-1), self, val) # West
end</lang>
- Output:
Sample runs
->numbrix <numbrix1.in Input with 81 cells: _ _ _ _ _ _ _ _ _ _ _ 46 45 _ 55 74 _ _ _ 38 _ _ 43 _ _ 78 _ _ 35 _ _ _ _ _ 71 _ _ _ 33 _ _ _ 59 _ _ _ 17 _ _ _ _ _ 67 _ _ 18 _ _ 11 _ _ 64 _ _ _ 24 21 _ 1 2 _ _ _ _ _ _ _ _ _ _ _ Output with 81 cells: 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 ->numbrix <numbrix2.in Input with 81 cells: _ _ _ _ _ _ _ _ _ _ 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 _ _ _ _ _ _ _ _ _ _ Output with 81 cells: 9 10 13 14 19 20 63 64 65 8 11 12 15 18 21 62 61 66 7 6 5 16 17 22 59 60 67 34 33 4 3 24 23 58 57 68 35 32 31 2 25 54 55 56 69 36 37 30 1 26 53 74 73 70 39 38 29 28 27 52 75 72 71 40 43 44 47 48 51 76 77 78 41 42 45 46 49 50 81 80 79 ->
Perl 6
Using the Warnsdorff solver from Solve_a_Hidato_puzzle: <lang perl6>my @adjacent = [-1, 0],
[ 0, -1], [ 0, 1], [ 1, 0];
solveboard q:to/END/;
__ __ __ __ __ __ __ __ __ __ __ 46 45 __ 55 74 __ __ __ 38 __ __ 43 __ __ 78 __ __ 35 __ __ __ __ __ 71 __ __ __ 33 __ __ __ 59 __ __ __ 17 __ __ __ __ __ 67 __ __ 18 __ __ 11 __ __ 64 __ __ __ 24 21 __ 1 2 __ __ __ __ __ __ __ __ __ __ __ END</lang>
- Output:
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 1275 tries
And
<lang perl6>solveboard q:to/END/;
0 0 0 0 0 0 0 0 0 0 11 12 15 18 21 62 61 0 0 6 0 0 0 0 0 60 0 0 33 0 0 0 0 0 57 0 0 32 0 0 0 0 0 56 0 0 37 0 1 0 0 0 73 0 0 38 0 0 0 0 0 72 0 0 43 44 47 48 51 76 77 0 0 0 0 0 0 0 0 0 0
END</lang>
- Output:
9 10 13 14 19 20 63 64 65 8 11 12 15 18 21 62 61 66 7 6 5 16 17 22 59 60 67 34 33 4 3 24 23 58 57 68 35 32 31 2 25 54 55 56 69 36 37 30 1 26 53 74 73 70 39 38 29 28 27 52 75 72 71 40 43 44 47 48 51 76 77 78 41 42 45 46 49 50 81 80 79 4631 tries
Oddly, reversing the tiebreaker rule that makes hidato run twice as fast causes this last example to run four times slower. Go figure...
Racket
This is a general "Hidato" style solver (which is why there is a search for a 0 start point (which supports Hopido). There is already a Racket implementation of Hidato, so to allow a variety of approaches to be demonstrated, the main library for this set of problems is here.
hidato-family-solver.rkt
<lang racket>#lang racket
- Used in my solutions of
- "Solve a Hidato Puzzle"
- "Solve a Holy Knights Tour"
- "Solve a Numbrix Puzzle"
- "Solve a Hopido Puzzle"
- As well as the solver being common, the solution renderer and input formats are common
(provide
;; Input: list of neighbour offsets ;; Output: a solver function: ;; Input: a puzzle ;; Output: either the solved puzzle or #f if impossible solve-hidato-family ;; Input: puzzle ;; optional minimum cell width ;; Output: a pretty string that can be printed puzzle->string)
- Cell values are
- zero? - unvisited
- positive? - nth visitied
- else - unvisitable. In the puzzle layout, it's a _. In the hash it's a -1, so we can care less
- about number type checking.
- A puzzle is a sequence of sequences of cell values
- We work with a puzzle as a hash keyed on (cons row-num col-num)
- Take a puzzle and get a working hash of it
(define (puzzle->hash p)
(for*/hash (((r row-num) (in-parallel p (in-naturals))) ((v col-num) (in-parallel r (in-naturals))) #:when (integer? v)) (values (cons row-num col-num) v)))
- Takes a hash and recreates a vector of vectors puzzle
(define (hash->puzzle h# (blank '_))
(define keys (hash-keys h#)) (define n-rows (add1 (car (argmax car keys)))) (define n-cols (add1 (cdr (argmax cdr keys)))) (for/vector #:length n-rows ((r n-rows)) (for/vector #:length n-cols ((c n-cols)) (hash-ref h# (cons r c) blank))))
- See "provide" section for description
(define (puzzle->string p (w #f))
(match p [#f "unsolved"] [(? sequence? s) (define (max-n-digits p) (and p (add1 (order-of-magnitude (* (vector-length p) (vector-length (vector-ref p 0))))))) (define min-width (or w (max-n-digits p))) (string-join (for/list ((r s)) (string-join (for/list ((c r)) (~a c #:align 'right #:min-width min-width)) " ")) "\n")]))
(define ((solve-hidato-family neighbour-offsets) board)
(define board# (puzzle->hash board)) ;; reverse mapping, will only take note of positive values (define targets# (for/hash ([(k v) (in-hash board#)] #:when (positive? v)) (values v k))) (define (neighbours r.c) (for/list ((r+.c+ neighbour-offsets)) (match-define (list r+ c+) r+.c+) (match-define (cons r c ) r.c) (cons (+ r r+) (+ c c+)))) ;; Count the moves, rather than check for "no more zeros" in puzzle (define last-move (length (filter number? (hash-values board#)))) ;; Depth first solution of the puzzle (we have to go deep, it's where the solutions are! (define (inr-solve-pzl b# move r.c) (cond [(= move last-move) b#] ; no moves needed, so solved [else (define m++ (add1 move)) (for*/or ; check each neighbour as an option ((r.c+ (in-list (neighbours r.c))) #:when (equal? (hash-ref targets# move r.c) r.c) ; we're where we should be! #:when (match (hash-ref b# r.c+ -1) (0 #t) ((== m++) #t) (_ #f))) (inr-solve-pzl (hash-set b# r.c+ m++) m++ r.c+))])) (define (solution-starting-at n) (define start-r.c (for/first (((k v) (in-hash board#)) #:when (= n v)) k)) (and start-r.c (inr-solve-pzl board# n start-r.c))) (define sltn (cond [(solution-starting-at 1) => values] ;; next clause starts from 0 for hopido [(solution-starting-at 0) => values])) (and sltn (hash->puzzle sltn)))</lang>
<lang racket>#lang racket (require "hidato-family-solver.rkt")
(define von-neumann-neighbour-offsets
'((+1 0) (-1 0) (0 +1) (0 -1)))
(define solve-numbrix (solve-hidato-family von-neumann-neighbour-offsets))
(displayln
(puzzle->string (solve-numbrix #(#(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)))))
(newline)
(displayln
(puzzle->string (solve-numbrix #(#(0 0 0 0 0 0 0 0 0) #(0 11 12 15 18 21 62 61 0) #(0 6 0 0 0 0 0 60 0) #(0 33 0 0 0 0 0 57 0) #(0 32 0 0 0 0 0 56 0) #(0 37 0 1 0 0 0 73 0) #(0 38 0 0 0 0 0 72 0) #(0 43 44 47 48 51 76 77 0) #(0 0 0 0 0 0 0 0 0)))))</lang>
- Output:
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 9 10 13 14 19 20 63 64 65 8 11 12 15 18 21 62 61 66 7 6 5 16 17 22 59 60 67 34 33 4 3 24 23 58 57 68 35 32 31 2 25 54 55 56 69 36 37 30 1 26 53 74 73 70 39 38 29 28 27 52 75 72 71 40 43 44 47 48 51 76 77 78 41 42 45 46 49 50 81 80 79
REXX
This solution is essentially same as the (REXX) Hidato puzzle solver.
Programming note: the coördinates for the cells used are the same as an X×Y grid, that is, the bottom left-most cell is (1,1) and the tenth cell on row 2 is (2,10). <lang rexx>/*REXX program solves a Numbrix (R) puzzle, displays puzzle & solution.*/ maxr=0; maxc=0; maxx=0; minr=9e9; minc=9e9; minx=9e9; cells=0; @.= parse arg xxx; PZ='Numbrix puzzle' /*get cell definitions from C.L. */ xxx=translate(xxx, , "/\;:_", ',') /*also allow other chars as comma*/
do while xxx\=; parse var xxx r c marks ',' xxx do while marks\=; _=@.r.c parse var marks x marks if datatype(x,'N') then x=abs(x/1) /*normalize X*/ minr=min(minr,r); maxr=max(maxr,r) minc=min(minc,c); maxc=max(maxc,c) if x==1 then do; !r=r; !c=c; end /*start cell.*/ if _\== then call err "cell at" r c 'is already occupied with:' _ @.r.c=x; c=c+1; cells=cells+1 /*assign mark*/ if x==. then iterate /*hole? Skip.*/ if \datatype(x,'W') then call err 'illegal marker specified:' x minx=min(minx,x); maxx=max(maxx,x) /*min & max X*/ end /*while marks¬= */ end /*while xxx ¬= */
call showGrid /* [↓] used for making fast moves*/ Nr = '0 1 0 -1 -1 1 1 -1' /*possible row for the next move.*/ Nc = '1 0 -1 0 1 -1 1 -1' /* " col " " " " */ pMoves=words(Nr) -4*(left(PZ,1)=='N') /*is this to be a Numbrix puzzle?*/
do i=1 for pMoves; Nr.i=word(Nr,i); Nc.i=word(Nc,i); end /*fast moves*/
if \next(2,!r,!c) then call err 'No solution possible for this' PZ"." say; say 'A solution for the' PZ "exists."; say; call showGrid exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────ERR subroutine──────────────────────*/ err: say; say '***error!*** (from' PZ"): " arg(1); say; exit 13 /*──────────────────────────────────NEXT subroutine─────────────────────*/ next: procedure expose @. Nr. Nc. cells pMoves; parse arg #,r,c; ##=#+1
do t=1 for pMoves /* [↓] try some moves.*/ parse value r+Nr.t c+Nc.t with nr nc /*next move coördinates*/ if @.nr.nc==. then do; @.nr.nc=# /*a move.*/ if #==cells then return 1 /*last 1?*/ if next(##,nr,nc) then return 1 @.nr.nc=. /*undo the above move. */ iterate /*go & try another move*/ end if @.nr.nc==# then do /*is this a fill-in ? */ if #==cells then return 1 /*last 1.*/ if next(##,nr,nc) then return 1 /*fill-in*/ end end /*t*/
return 0 /*This ain't working. */ /*──────────────────────────────────SHOWGRID subroutine─────────────────*/ showGrid: if maxr<1 | maxc<1 then call err 'no legal cell was specified.' if minx<1 then call err 'no 1 was specified for the puzzle start' w=length(cells); do r=maxr to minr by -1; _=
do c=minc to maxc; _=_ right(@.r.c,w); end /*c*/ say _ end /*r*/
say; return</lang>
- Output:
when using the input of
1 1 . . . . . . . . ./2 1 . . 24 21 . 1 2 . ./3 1 . 18 . . 11 . . 64 ./4 1 . 17 . . . . . 67 ./5 1 . . 33 . . . 59 . ./6 1 . 35 . . . . . 71 ./7 1 . 38 . . 43 . . 78 ./8 1 . . 46 45 . 55 74 . ./9 1 . . . . . . . . .
. . . . . . . . . . . 46 45 . 55 74 . . . 38 . . 43 . . 78 . . 35 . . . . . 71 . . . 33 . . . 59 . . . 17 . . . . . 67 . . 18 . . 11 . . 64 . . . 24 21 . 1 2 . . . . . . . . . . . A solution for the Numbrix puzzle exists. 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
- Output:
when using the input of
1 1 . . . . . . . . .\2 1 . 43 44 47 48 51 76 77 .\3 1 . 38 . . . . . 72 .\4 1 . 37 . 1 . . . 73 .\5 1 . 32 . . . . . 56 .\6 1 . 33 . . . . . 57 .\7 1 . 6 . . . . . 60 .\8 1 . 11 12 15 18 21 62 61 .\9 1 . . . . . . . . .
. . . . . . . . . . 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 . . . . . . . . . . A solution for the Numbrix puzzle exists. 9 10 13 14 19 20 63 64 65 8 11 12 15 18 21 62 61 66 7 6 5 16 17 22 59 60 67 34 33 4 3 24 23 58 57 68 35 32 31 2 25 54 55 56 69 36 37 30 1 26 53 74 73 70 39 38 29 28 27 52 75 72 71 40 43 44 47 48 51 76 77 78
Ruby
This solution uses HLPsolver from here <lang ruby>require 'HLPsolver'
ADJACENT = [[-1, 0], [0, -1], [0, 1], [1, 0]]
board1 = <<EOS
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
EOS HLPsolver.new(board1).solve
board2 = <<EOS
0 0 0 0 0 0 0 0 0 0 11 12 15 18 21 62 61 0 0 6 0 0 0 0 0 60 0 0 33 0 0 0 0 0 57 0 0 32 0 0 0 0 0 56 0 0 37 0 1 0 0 0 73 0 0 38 0 0 0 0 0 72 0 0 43 44 47 48 51 76 77 0 0 0 0 0 0 0 0 0 0
EOS HLPsolver.new(board2).solve</lang> Which produces:
Problem: 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 Solution: 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 Problem: 0 0 0 0 0 0 0 0 0 0 11 12 15 18 21 62 61 0 0 6 0 0 0 0 0 60 0 0 33 0 0 0 0 0 57 0 0 32 0 0 0 0 0 56 0 0 37 0 1 0 0 0 73 0 0 38 0 0 0 0 0 72 0 0 43 44 47 48 51 76 77 0 0 0 0 0 0 0 0 0 0 Solution: 9 10 13 14 19 20 63 64 65 8 11 12 15 18 21 62 61 66 7 6 5 16 17 22 59 60 67 34 33 4 3 24 23 58 57 68 35 32 31 2 25 54 55 56 69 36 37 30 1 26 53 74 73 70 39 38 29 28 27 52 75 72 71 40 43 44 47 48 51 76 77 78 41 42 45 46 49 50 81 80 79