Solve a Hidato puzzle: Difference between revisions

{{task}}

 

The rules are:

* In a proper Hidato puzzle, the solution is unique.

 

[[File:Hidato_Start.png|center|Sample Hidato problem, from Wikipedia]]

 

 

[[File:HEnd.png|center|Solution to sample Hidato problem]]

 

=={{header|Bracmat}}==

( hidato

= Line solve lowest Ncells row column rpad

: ?board

& out$(hidato$!board)

Output:

<pre>

=={{header|C}}==

Depth-first graph, with simple connectivity check to reject some impossible situations early. The checks slow down simpler puzzles significantly, but can make some deep recursions backtrack much earilier.

#include <stdlib.h>

#include <string.h>

 

return 0;

{{out}}

<pre> Before:

17 7 6 3

5 4</pre>

 

=={{header|C++}}==

#include <iostream>

#include <sstream>

}

//--------------------------------------------------------------------------------------------------

Output:

<pre>

01 20 21 24 25 26 35 34 33

</pre>

 

=={{header|D}}==

This version retains some of the characteristics of the original C version. It uses global variables, it doesn't enforce immutability and purity. This style is faster to write for prototypes, short programs or less important code, but in larger programs you usually want more strictness to avoid some bugs and increase long-term maintainability.

{{trans|C}}

 

int[][] board;

solve(start[0], start[1], 1);

printBoard;

{{out}}

<pre> . . . . . . . . . .

 

With this coding style the changes in the code become less bug-prone, but also more laborious. This version is also faster, its total runtime is about 0.02 seconds or less.

std.algorithm, std.exception, std.range, std.typetuple;

 

. . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ . . _ _ ."

);

{{out}}

<pre>Problem:

. . 4 . 7 . 10 . 13 . 16 . 19 . 22 . 25 . 28 . 31 . 34 . 37 . 40 . 43 . 46 . 49 . 52 . 55 . 58 . 61 . 64 . 67 . 70 . 73 .

. . . 5 6 . . 11 12 . . 17 18 . . 23 24 . . 29 30 . . 35 36 . . 41 42 . . 47 48 . . 53 54 . . 59 60 . . 65 66 . . 71 72 .</pre>

 

=={{header|Erlang}}==

To simplify the code I start a new process for searching each potential path through the grid. This means that the default maximum number of processes had to be raised ("erl +P 50000" works for me). The task takes about 1-2 seconds on a low level Mac mini. If faster times are needed, or even less performing hardware is used, some optimisation should be done.

-module( solve_hidato_puzzle ).

 

 

store( {Key, Value}, Dict ) -> dict:store( Key, Value, Dict ).

{{out}}

<pre>

5 4

</pre>

 

{-# LANGUAGE Rank2Types #-}

import qualified Data.IntMap as I

import Data.IntMap (IntMap)

import Data.Time.Clock

 

 

tupIns x y v m = I.insert x (I.insert y v (I.findWithDefault I.empty x m)) m

tupLookup x y m = I.lookup x m >>= I.lookup y

 

 

 

printCellMap cellmap = putStrLn $ concat strings

 

main = do

 

<pre> 0 33 35 0 0

0 0 24 22 0

 

This is an Unicon-specific solution but could easily be adjusted to work in Icon.

record Pos(r,c)

 

QMouse(puzzle, goWest(), self, val)

QMouse(puzzle, goNW(), self, val)

 

Sample run:

{{trans|D}}

{{works with|Java|7}}

import java.util.Collections;

import java.util.List;

}

}

 

Output:

. . . . . . . 5 4 .

. . . . . . . . . .</pre>

 

=={{header|Mathprog}}==

 

Find a solution to a Hidato problem

;

Using the data in the model produces the following:

{{out}}

</pre>

 

 

 

 

 

__ __ 24 22 __ . . .

__ __ __ 21 __ __ . .

__ 26 __ 13 40 11 . .

27 __ __ __ 9 __ 1 .

echo("")

echo("Found:")

{{out}}

<pre> . . . . . . . . . .

 

=={{header|Perl}}==

use List::Util 'max';

 

 

print "\033[2J";

32 33 35 36 37

31 34 24 22 38

17 7 6 3

5 4

 

 

 

 

 

=={{header|PicoLisp}}==

 

(de hidato (Lst)

(disp Grid 0

'((This)

Test:

(quote

(T 33 35 T T)

(NIL NIL T T 18 T T)

(NIL NIL NIL NIL T 7 T T)

Output:

<pre> +---+---+---+---+---+---+---+---+

Works with SWI-Prolog and library(clpfd) written by '''Markus Triska'''.<br>

Puzzle solved is from the Wilkipedia page : http://en.wikipedia.org/wiki/Hidato

 

hidato :-

 

my_write_1(X) :-

{{out}}

<pre>?- hidato.

 

=={{header|Python}}==

given = []

start = None

solve(start[0], start[1], 1)

print

{{out}}

<pre> __ 33 35 __ __

 

=={{header|Racket}}==

Algorithm is depth first search for each number, repeating for all numbers in ascending order.

It currently runs slowish due to temporary shortcomings in untyped Racket's array indexing, but finished

immediately when tested with custom 2d vector library.

 

#lang racket

(require math/array)

;main function

(define (hidato board) (put-path board (hidato-path board)))

{{out}}

<pre>

#[#f #f #f #f #f #f 5 4]])

</pre>

 

=={{header|REXX}}==

<br>If ''any'' marker is negative, then it's assumed to be a Numbrix puzzle (and the absolute value is used).

<br>Over half of the REXX program deals with validating the input and displaying the puzzle.

 

parse var marks x marks

end

if \datatype(x,'W') then call err 'illegal marker specified:' x

end /*while marks¬='' */

end /*while xxx ¬='' */

next: procedure expose @. Nr. Nc. cells pMoves; parse arg #,r,c; ##=#+1

<br> <tt> 1 7 5 .\2 5 . 7 . .\3 3 . . 18 . .\4 1 27 . . . 9 . 1\5 1 . 26 . 13 40 11\6 1 . . . 21 . .\7 1 . . 24 22 .\8 1 . 33 35 . .</tt>

<pre>

===Without Warnsdorff===

The following class provides functionality for solving a hidato problem:

#

class Hidato

(msg ? [msg] : []) + str + [""]

end

 

'''Test:'''

board1 = <<EOS

. 4

t0 = Time.now

Hidato.new(board3).solve

 

{{out}}

===With Warnsdorff===

I modify method as follows to implement [[wp:Knight's_tour#Warnsdorff|Warnsdorff]] like

#

class HLPsolver

Cell = Struct.new(:value, :used, :adj)

def initialize(board, pout=true)

@board = []

board.each_line do |line|

end

@board.each_with_index do |row, x|

row.each_with_index do |cell, y|

end

end

@end = @board.flatten.compact.size

puts to_s('Problem:') if pout

end

def solve

@zbl = Array.new(@end+1, false)

puts (try(@board[@sx][@sy], 1) ? to_s('Solution:') : "No solution")

end

def try(cell, seq_num)

value = cell.value

cell.used = false

end

def wdof(adj)

adj.count {|x,y| not @board[x][y].used}

end

def to_s(msg=nil)

str = (0...@xmax).map do |x|

end

(msg ? [msg] : []) + str + [""]

end

Which may be used as follows to solve Hidato Puzzles:

 

ADJACENT = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]

t0 = Time.now

HLPsolver.new(board3).solve

 

Which produces:

<pre>

Problem:

 

Solution:

 

Problem:

5 6 11 12 17 18 23 24 29 30 35 36 41 42 47 48 53 54 59 60 65 66 71 72

 

</pre>

 

HLPsolver may be used to solve [[Knight's tour#Ruby|Knight's tour]]:

 

=={{header|Tcl}}==

global grid max filled

set max 1

puts ""

printgrid

Demonstrating (dots are “outside” the grid, and zeroes are the cells to be filled in):

0 33 35 0 0 . . .

0 0 24 22 0 . . .

. . . . 0 7 0 0

. . . . . . 5 0

{{out}}

<pre>

More complex cases are solvable with an [[/Extended Tcl solution|extended version of this code]], though that has more onerous version requirements.

 

 

[[Category:Puzzles]]