Talk:Solve a Hidato puzzle

Needed improvements

I'm really reluctant to admit this as a full task just yet, as it is dependent on a complex applet in an external website. Better would be to put a description (which could involve a link to wikipedia) and specific problem to solve in this page. We can always judge for ourselves whether someone's solved the actual problem or just the specific instance of it. –Donal Fellows 13:31, 12 January 2012 (UTC)

Technically I think the complex applet is a complex servlet. From the link you have changed this to following the external links to Hidato Home Page and then Hidato Daily Adventures will take one to the same place. In spite of what's said below I've just enjoyed a few mins research there. –Nigel Galloway

There's a bit of a difference between research when writing a task or because it tweaked your interest. :) And potentially every contributor for every (400+) languages on RC having to do research to solve the task. :( In my experience, they just ignore the task. :( --Dgamey 20:54, 13 January 2012 (UTC)

How about two separate task? One for creating the puzzles, one for solving them? --Michael Mol 17:39, 12 January 2012 (UTC)

It seems like an interesting problem but there really needs to be more supporting information for this task.

• The linked WP article wp:Hidato is of poor quality and provides very little of use, there isn't even a through discussion of rules there saying how to get to the solution. The solution doesn't seem to be full of consecutive numbers in every row, column, or diagonal; and it certainly isn't clear how the numbers got laid down. Some lines are consecutive except for one number. Others aren't consecutive at all. There may be a method but it's far from obvious.

• Oh! The numbers wind through the grid from lowest to highest. Now why didn't it say that clearly instead of just leaving it at 'consecutive numbers'? --Dgamey 20:10, 12 January 2012 (UTC)

• What's with the Knights Tour extra credit reference (we already have a task)? Maybe it's an easy step up but I don't see it and the task already seems complex enough. It's a nice fact that this can used for this, but why make it even optionally part of the task?
• I think this is a solution task. Generating a board should be another task.

Generally if I can't figure out most of what I need to do a task (at least broadly) from the task page then I'm not very interested in going off and researching it. Nor am I interested in reverse engineering the entire solution from a language I'm unfamiliar with. Task descriptions should be be able to paint enough of a picture to draw in contributors without requiring potentially a few hundred contributors to do that level of research or translation. That's my $.02 --Dgamey 19:57, 12 January 2012 (UTC)

well, for starters the example problem on wikipedia could be used as the input to be solved. a solution is there too, and a better description for what the rules are can be made. maybe even a better drawing for the solution that includes a thread that connects all the numbers in sequence. alternatively though maybe a square 3x3 problem is easier, so that just needs to be found. are any other details missing to make the task solvable?--eMBee 02:21, 13 January 2012 (UTC)

Certainly a set example and result are needed. A better description. The wp diagram or one like it should be fine if accompanied by a better description. I guess one of my concerns is making sure we have a properly set puzzle with a unique solution. For a small example, this can be validated via brute force. That raises the question if there is any requirement to find a solution by means other than brute force? And of course copyright if we have to use another source. I'd also remove the extra credit as a task; although, noting this as an application with some kind of reference would be interesting background. I'll leave the task of setting a puzzle and observe that we don't have such a task for Sudoku yet. That just about covers it for me. --Dgamey 04:28, 13 January 2012 (UTC)

I'm not convinced that the Knight's Tour part adds anything at all to this, as one of the most useful techniques that is applicable to this problem (pruning pathing solution candidates that provably can't reach the goal; that's implied by the use of the Moore Neighborhood) doesn't apply at all. The nice thing seems to be that this is a fast problem, despite needing fairly complex searching. –Donal Fellows 19:15, 15 January 2012 (UTC)

Donal, I'm with you on this. While I might be interested in a link to some side reading as background, I can't see doing both. I don't think it's a simple as just swapping in another adjacency function and we already have a separate Knight's Tour task. --Dgamey 20:02, 15 January 2012 (UTC)

Rules

The rules are:

• You are given a grid with some numbers placed in it. The other squares in the grid will be blank.
  • The grid is not necessarily rectangular.
  • The grid may have holes in it.
  • The grid is always connected.
  • The number “1” is always present, as is another number that is equal to the number of squares in the grid. Other numbers are present so as to force the solution to be unique.
• The aim is to place a natural number in each blank square so that in the sequence of numbered squares from “1” upwards, each square is in the wp:Moore neighborhood of the squares immediately before and after it in the sequence (except for the first and last squares, of course, which only have one-sided constraints).
  • Thus, if the grid was overlaid on a chessboard, a king would be able to make legal moves along the path from first to last square in numerical order.
  • A square may only contain one number.
• In a proper Hidato puzzle, the solution is unique. (Only really relevant during construction, but might make solving easier.)

I think that sums them up properly. –Donal Fellows 10:41, 13 January 2012 (UTC)

That's very good. I think it could be a bit less formal:

The rules are:

• You are given a grid with cells. Some cells have numbers while others are blank.
  • The grid is not necessarily rectangular and could have holes (non-cells).
  • All cells are connected/adjacent (no islands).
  • At the start the high and low (normally numbered from 1) cells are marked. Other numbers are provided to ensure there is a unique solution to the puzzle.
  • When completed each cell contains a single integer and the grid contains the integers in sequence winding through the grid like a King on a Chess board. More formally, each square is in the wp:Moore neighborhood of the squares immediately before and after it in the sequence except for the first and last cells which only have only one connection each.

The task is to write a program to solve these puzzles. A sample grid and its solution has been provided.

How's that? Also,

• We still need the samples, the ones from Wikipedia should work.
• I still don't know anything about the hardness of this and if brute force or elegance is preferred/needed. It seems to me that given the Moore Neighbourhood constraint that puzzles would have to get really quite large before brute force would have any problems (but that's just gut feel). --Dgamey 17:58, 13 January 2012 (UTC)

Thinking about it, finding a unique solution to Knights Tour given similar clues and a unique solution is likely much easier than solving Knights Tours. An alternate name for this might seem to be a Kings Tour (sadly, not very exciting).

See http://en.wikipedia.org/wiki/Adjacency_list fo a discussion of implementations. The Mathprog example Rule 3 is such a list. As is Rule 3 in the Mathprog Knights Tour example. Only the definition of adjacency has changed. We could add extra credit if it also solves Numbrix which is a von Neuman Neighbourhood. –Nigel Galloway

Perhaps worthy of its own task. There are probably lots of interesting research and discussion for Numbrix. --Dgamey 21:05, 13 January 2012 (UTC)

Tcl counterexample

The Tcl code logic is unsound: even if a unique solution exists, it doesn't mean any "leg" of the initial puzzle has a unique partial solution. Try this: <lang tcl>solveHidato " . 4 . 0 7 0 1 0 0 "

1. solution:
2. . 4 .
3. 3 7 5
4. 1 2 6</lang> and the program will fail to find anything. --Ledrug 18:15, 1 May 2012 (UTC)