16
\$\begingroup\$

In a few British newspapers there is a game known as Hidato. It is somewhat similar to Sudoku, albeit instead of having 1-9 in a line and block, it's about placing numbers such that they connect in order from 01 all the way up to the highest one, so they are all touching horizontally, diagonally or vertically.

Inputs will contain multiple lines separated by \n, containing blocks separated by a space, which you can assume to be two characters wide. Each block will be a number, a blank space to be filled (indicated by --), or a wall that cannot have numbers in (XX).

Your output should match the provided one albeit with empty blocks provided with numbers. Note that there may not be a unique, or even the existence of, a solution – some may yield multiple due to their ambiguity, much like Sudoku, and some may be literally unsolvable, in which case you should give a falsey output, but you can assume inputs are formatted as below.

Use a standard header Language: XX bytes. Happy golfing!

Examples

Inputs 01 XX 03, 01 -- 04, 01 --, etc should all return something falsey.

Input:

01 -- --
-- XX 05

Output:

01 03 04
02 XX 05

Input:

-- 33 35 -- -- XX XX XX    
-- -- 24 22 -- XX XX XX      
-- -- -- 21 -- -- XX XX
-- 26 -- 13 40 11 XX XX
27 -- -- -- 09 -- 01 XX
XX XX -- -- 18 -- -- XX
XX XX XX XX -- 07 -- --
XX XX XX XX XX XX 05 --

Output:

32 33 35 36 37 XX XX XX
31 34 24 22 38 XX XX XX
30 25 23 21 12 39 XX XX
29 26 20 13 40 11 XX XX
27 28 14 19 09 10 01 XX
XX XX 15 16 18 08 02 XX
XX XX XX XX 17 07 06 03
XX XX XX XX XX XX 05 04

Input:

XX XX XX XX -- 53 XX XX XX XX
XX XX XX XX -- -- XX XX XX XX
XX XX 56 -- -- -- 30 -- XX XX
XX XX -- -- -- -- -- -- XX XX
XX -- -- 20 22 -- -- -- -- XX
XX 13 -- 23 47 -- 41 -- 34 XX
-- -- 11 18 -- -- -- 42 35 37
-- -- -- -- 05 03 01 -- -- --
XX XX XX XX -- -- XX XX XX XX
XX XX XX XX 07 -- XX XX XX XX

Output:

XX XX XX XX 52 53 XX XX XX XX
XX XX XX XX 54 51 XX XX XX XX
XX XX 56 55 28 50 30 31 XX XX
XX XX 26 27 21 29 49 32 XX XX
XX 25 24 20 22 48 45 44 33 XX
XX 13 19 23 47 46 41 43 34 XX
14 12 11 18 04 02 40 42 35 37
15 16 17 10 05 03 01 39 38 36
XX XX XX XX 09 06 XX XX XX XX
XX XX XX XX 07 08 XX XX XX XX
\$\endgroup\$
  • \$\begingroup\$ Making sure I understand: Given a grid with some non-walkable cells, find a Hamiltonian path that fits the prefilled cells? \$\endgroup\$ – Geobits Aug 4 '15 at 20:21
  • \$\begingroup\$ @AmiRuse Wow. That looks tricky. (Of course, this is coming from a person who hates photo editing.) It's kind of nice to know of someone else here who has a VG character as their logo. :O \$\endgroup\$ – kirbyfan64sos Aug 4 '15 at 20:23
  • \$\begingroup\$ Can we see a solution for the example? More examples are going to be helpful as well. \$\endgroup\$ – Kade Aug 4 '15 at 20:29
  • \$\begingroup\$ Brilliant :). You could also have a generator challenge later \$\endgroup\$ – Beta Decay Aug 4 '15 at 20:33
  • 3
    \$\begingroup\$ Could the input method be simplified? Maybe use a 2D array of integers, and have -1 be a wall, and 0 be a blank? That'd make it easier to focus on the real challenge of the puzzle, and then there's no complexity of padding numbers with zeros or parsing strings. \$\endgroup\$ – mbomb007 Jan 5 '17 at 22:32
1
\$\begingroup\$

JavaScript (Node.js), 482 bytes

This is a brute-force solution, it starts at 01 and checks every neighbouring cell checking for empty cells (--) or the desired number and following the path to completion or impossibility. If the desired number exists and isn't a neighbour it shortcuts this solution. Takes a few seconds for the largest grid.

This probably isn't particularly interesting, but I thought I'd try my hand at making a solution before looking at the answers linked on Rosetta Code and I enjoyed tackling a slightly more difficult challenge!

Finds all solutions when many exist. The body is a function that accepts a two dimensional array and the footer processes the input to the desired format, and returns the result to the desired format too. Happy to provide more information (and a less golfed implementation if there's interest).

f=a=>{F=(D,n,j)=>[Z=[].concat(...D),z=Z.indexOf(j),z>-1&&[x=z%w,y=z/w|0],z>-1&&[[x-1,y-1],[x,y-1],[x+1,y-1],[x-1,y],[x+1,y],[x-1,y+1],[x,y+1],[x+1,y+1]]][n];C=q=>q.map(Q=>Q.slice());w=a[0][L='length'];l=F(a,0).filter(c=>c!='XX')[L];R=[];r=(s,d)=>{let n=`0${+s+1}`.slice(-2);N=F(d,2,n);n>l?R.push(C(d)):~F(d,1,s)?(p=F(d,3,s),p.filter(P=>P==N+'')[L]?r(n,C(d)):!~F(d,1,n)?p.map(I=>{[x,y]=I,(x<0||x>w-1||y<0||y>d[L]-1)||d[y][x]=='--'&&(D=C(d),r(D[y][x]=n,D))}):0):0};r('01',a);return R}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.