We love our weird puzzles, us Brits

16

4

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

Mia yun Ruse

Posted 2015-08-04T20:04:20.920

Reputation: 177

Making sure I understand: Given a grid with some non-walkable cells, find a Hamiltonian path that fits the prefilled cells? – Geobits – 2015-08-04T20:21:30.390

@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 – kirbyfan64sos – 2015-08-04T20:23:09.727

Can we see a solution for the example? More examples are going to be helpful as well. – Kade – 2015-08-04T20:29:49.457

Brilliant :). You could also have a generator challenge later – Beta Decay – 2015-08-04T20:33:45.817

@Geobits The cells must be in a path in which 01 is adjacent to 02, 02 to 03… so on to the maximum number, in a Hamiltonian path, yes. – Mia yun Ruse – 2015-08-04T20:33:53.740

@Vioz- I… uh… don't actually have the answer, as the newspaper (yes, it's from a newspaper) said it would have the answer tomorrow, by which I'll (hopefully remember to) edit it in. Solving it may show a few tricks – and problems you'll have to overcome – that may help, though. – Mia yun Ruse – 2015-08-04T20:36:14.123

@AmiRuse I figured out the solution on my own :) If you can maybe go through some past puzzles, that could help to add extra examples. – Kade – 2015-08-04T20:38:07.993

Here's the solution to the example given, so it can be added to the post: http://pastebin.com/SAAUVLvz

– Kade – 2015-08-04T20:43:32.443

@Vioz- Thanks! I've added another with a solution. – Mia yun Ruse – 2015-08-04T20:47:03.253

I've made such improvements as I could (and removed the bit about a three-day deadline, which is quite against the philosophy of this site), but there are a couple of things which I wasn't sure about. 1. You talk about testing it, but there's nothing in the spec which requires answers to finish in the next 100 years. You probably need to add a flexible but reasonable time limit. 2. You don't state whether answers can assume that the solution, if it exists, is unique. This could possibly help some lines of logic and provide a significant speed-up if you're willing to guarantee it. – Peter Taylor – 2015-08-04T20:47:08.973

If our solution solves all solvable puzzles in a minute, but doesn't exit after the first minute on the unsolvables, can this be considered valid? – Kade – 2015-08-04T20:56:22.110

@PeterTaylor I was editing as you improved it, so sadly my SE client didn't want to show me your edit as I pushed mine. I've made a few things clearer, but please edit it as you want. – Mia yun Ruse – 2015-08-04T20:56:34.013

@Vioz- Ah, that's the challenge (I only just edited this in, mind, per request). If you don't determine it's unsolvable in the time, it won't work – timeout, and hope it's not a complex one, or any other method, but it must be in the time limit, elsewise brute force programs could have a field day on the challenge (and my CPU). – Mia yun Ruse – 2015-08-04T20:58:57.333

I added the link to its Wikipedia page, since I think the explanation and graphics there are helpful. – mbomb007 – 2015-08-04T21:25:33.487

Also, could you post an example or two that are more diverse (unsolvable or multiple solutions)? – mbomb007 – 2015-08-04T21:29:15.637

This website has some very consise solutions to this problem in multiple languages... http://rosettacode.org/wiki/Hidato

– gahrae – 2015-10-25T17:46:04.830

Will there always be a 1 and whatever the last number is, revealed in the input? – Whothehellisthat – 2016-08-29T18:28:11.643

@Whothehellisthat Yes. You can assume the highest number you see is the amount of cells. – Mia yun Ruse – 2016-08-30T04:11:39.917

Some simpler examples would be nice for early testing: gist

– Whothehellisthat – 2016-08-30T09:57:21.883

Did you say if the lines are separated by \n or not? – Whothehellisthat – 2016-08-30T09:57:52.460

I kind of think maybe the input walls could be left as "XX". Makes it a lot easier to parse, and I would guess the parsing isn't really the point of this challenge. – Whothehellisthat – 2016-08-30T11:18:00.183

Okay @Whothehellisthat, I've added a few more examples and clarifications :) – Mia yun Ruse – 2016-08-30T15:37:40.050

3Could 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. – mbomb007 – 2017-01-05T22:32:16.087

Placeholder: https://jsfiddle.net/rtgdm9bb/

– Stephen – 2017-05-26T20:04:00.240

Answers

1

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!

Dom Hastings

Posted 2015-08-04T20:04:20.920

Reputation: 16 415