How to resolve the algorithm Solve a Hopido puzzle step by step in the AutoHotkey programming language

Published on 12 May 2024 09:40 PM
#Autohotkey

How to resolve the algorithm Solve a Hopido puzzle step by step in the AutoHotkey programming language

Table of Contents

Problem Statement

Hopido puzzles are similar to Hidato. The most important difference is that the only moves allowed are: hop over one tile diagonally; and over two tiles horizontally and vertically. It should be possible to start anywhere in the path, the end point isn't indicated and there are no intermediate clues. Hopido Design Post Mortem contains the following: "Big puzzles represented another problem. Up until quite late in the project our puzzle solver was painfully slow with most puzzles above 7×7 tiles. Testing the solution from each starting point could take hours. If the tile layout was changed even a little, the whole puzzle had to be tested again. We were just about to give up the biggest puzzles entirely when our programmer suddenly came up with a magical algorithm that cut the testing process down to only minutes. Hooray!" Knowing the kindness in the heart of every contributor to Rosetta Code, I know that we shall feel that as an act of humanity we must solve these puzzles for them in let's say milliseconds. Example: Extra credits are available for other interesting designs.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Solve a Hopido puzzle step by step in the AutoHotkey programming language

Source code in the autohotkey programming language

SolveHopido(Grid, Locked, Max, row, col, num:=1, R:="", C:=""){
	if (R&&C)							; if neighbors (not first iteration)
	{
		Grid[R, C] := ">" num 					; place num in current neighbor and mark it visited ">"
		row:=R, col:=C						; move to current neighbor
	}

	num++								; increment num
	if (num=max)							; if reached end
		return map(Grid)					; return solution
 
	if locked[num]							; if current num is a locked value
	{
		row := StrSplit((StrSplit(locked[num], ",").1) , ":").1	; find row of num
		col := StrSplit((StrSplit(locked[num], ",").1) , ":").2	; find col of num
		if SolveHopido(Grid, Locked, Max, row, col, num)	; solve for current location and value
			return map(Grid)				; if solved, return solution
	}
	else
	{
		for each, value in StrSplit(Neighbor(row,col), ",")
		{
			R := StrSplit(value, ":").1
			C := StrSplit(value, ":").2
 
			if (Grid[R,C] = "")				; a hole or out of bounds
			|| InStr(Grid[R, C], ">")			; visited
			|| Locked[num+1] && !(Locked[num+1]~= "\b" R ":" C "\b") ; not neighbor of locked[num+1]
			|| Locked[num-1] && !(Locked[num-1]~= "\b" R ":" C "\b") ; not neighbor of locked[num-1]
			|| Locked[num]					; locked value
			|| Locked[Grid[R, C]]				; locked cell
				continue
 
			if SolveHopido(Grid, Locked, Max, row, col, num, R, C)	; solve for current location, neighbor and value
				return map(Grid)			; if solved, return solution
		}
	}
	num--								; step back
	for i, line in Grid
		for j, element in line
			if InStr(element, ">") && (StrReplace(element, ">") >= num)
				Grid[i, j] := 0
}
;--------------------------------
;--------------------------------
;--------------------------------
Neighbor(row,col){
	return Trim( ""
	. ","  row ":" col-3
	. ","  row ":" col+3
	. ","  row-3 ":" col
	. ","  row+3 ":" col
	
	. ","  row+2 ":" col+2
	. ","  row+2 ":" col-2
	. ","  row-2 ":" col+2
	. ","  row-2 ":" col-2
	, ",")
}
;--------------------------------
map(Grid){
	for i, row in Grid
	{
		for j, element in row
			line .= (A_Index > 1 ? "`t" : "") element
		map .= (map<>""?"`n":"") line
		line := ""
	}
	return StrReplace(map, ">")
}


;--------------------------------
Grid := [["",0 ,0 ,"",0 ,0 ,""]
	,[0 ,0 ,0 ,0 ,0 ,0 ,0]
	,[0 ,0 ,0 ,0 ,0 ,0 ,0]
	,["",0 ,0 ,0 ,0 ,0 ,""]
	,["","",0 ,0 ,0 ,"",""]
	,["","","",0 ,"","",""]]
;--------------------------------
; find locked cells, find max value 
Locked := []
max := 1
for i, line in Grid
	for j, element in line
		if (element >= 0)
			max++ 	, list .= i ":" j "`n"
	
random, rnd, 1, %max%
loop, parse, list, `n, `r
	if (A_Index = rnd)
	{
		row := StrSplit(A_LoopField, ":").1
		col := StrSplit(A_LoopField, ":").2
		Grid[row,col] := 1
		Locked[1] := row ":" col "," Neighbor(row, col)
		break
	}
;--------------------------------
MsgBox, 262144, ,% SolveHopido(Grid, Locked, Max, row, col)
return

You may also check:How to resolve the algorithm Pick random element step by step in the VBA programming language
You may also check:How to resolve the algorithm Arithmetic evaluation step by step in the Lua programming language
You may also check:How to resolve the algorithm Pig the dice game step by step in the Raku programming language
You may also check:How to resolve the algorithm Identity matrix step by step in the Ring programming language
You may also check:How to resolve the algorithm Greatest element of a list step by step in the Fortran programming language