Solve a Hidato puzzle: Difference between revisions
Added Go
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Syntax fix, "0" is true now. (didn't actually affect this particular problem)) |
(Added Go) |
||
Line 1,352:
17 7 6 3
5 4
</pre>
=={{header|Go}}==
{{trans|Java}}
<lang go>package main
import (
"fmt"
"sort"
"strconv"
"strings"
)
var board [][]int
var start, given []int
func setup(input []string) {
/* This task is not about input validation, so
we're going to trust the input to be valid */
puzzle := make([][]string, len(input))
for i := 0; i < len(input); i++ {
puzzle[i] = strings.Fields(input[i])
}
nCols := len(puzzle[0])
nRows := len(puzzle)
list := make([]int, nRows*nCols)
board = make([][]int, nRows+2)
for i := 0; i < nRows+2; i++ {
board[i] = make([]int, nCols+2)
for j := 0; j < nCols+2; j++ {
board[i][j] = -1
}
}
for r := 0; r < nRows; r++ {
row := puzzle[r]
for c := 0; c < nCols; c++ {
switch cell := row[c]; cell {
case "_":
board[r+1][c+1] = 0
case ".":
break
default:
val, _ := strconv.Atoi(cell)
board[r+1][c+1] = val
list = append(list, val)
if val == 1 {
start = append(start, r+1, c+1)
}
}
}
}
sort.Ints(list)
given = make([]int, len(list))
for i := 0; i < len(given); i++ {
given[i] = list[i]
}
}
func solve(r, c, n, next int) bool {
if n > given[len(given)-1] {
return true
}
back := board[r][c]
if back != 0 && back != n {
return false
}
if back == 0 && given[next] == n {
return false
}
if back == n {
next++
}
board[r][c] = n
for i := -1; i < 2; i++ {
for j := -1; j < 2; j++ {
if solve(r+i, c+j, n+1, next) {
return true
}
}
}
board[r][c] = back
return false
}
func printBoard() {
for _, row := range board {
for _, c := range row {
switch {
case c == -1:
fmt.Print(" . ")
case c > 0:
fmt.Printf("%2d ", c)
default:
fmt.Print("__ ")
}
}
fmt.Println()
}
}
func main() {
input := []string{
"_ 33 35 _ _ . . .",
"_ _ 24 22 _ . . .",
"_ _ _ 21 _ _ . .",
"_ 26 _ 13 40 11 . .",
"27 _ _ _ 9 _ 1 .",
". . _ _ 18 _ _ .",
". . . . _ 7 _ _",
". . . . . . 5 _",
}
setup(input)
printBoard()
fmt.Println("\nFound:")
solve(start[0], start[1], 1, 0)
printBoard()
}</lang>
{{out}}
<pre>
. . . . . . . . . .
. __ 33 35 __ __ . . . .
. __ __ 24 22 __ . . . .
. __ __ __ 21 __ __ . . .
. __ 26 __ 13 40 11 . . .
. 27 __ __ __ 9 __ 1 . .
. . . __ __ 18 __ __ . .
. . . . . __ 7 __ __ .
. . . . . . . 5 __ .
. . . . . . . . . .
Found:
. . . . . . . . . .
. 32 33 35 36 37 . . . .
. 31 34 24 22 38 . . . .
. 30 25 23 21 12 39 . . .
. 29 26 20 13 40 11 . . .
. 27 28 14 19 9 10 1 . .
. . . 15 16 18 8 2 . .
. . . . . 17 7 6 3 .
. . . . . . . 5 4 .
. . . . . . . . . .
</pre>
| |||