KnightL on a Chessboard

main.go

package main

import (
	"fmt"
	"sort"
	"strconv"
	"sync"
)

type Point struct {
	x, y, n, first, last int32
	history              [][]int32
	possible             []Point
}

func (p Point) can_move_up_left() bool {
	return (p.y-p.first >= 0) && (p.x-p.last >= 0)
}

func (p Point) can_move_up_right() bool {
	return (p.y-p.first >= 0) && (p.x+p.last <= p.n)
}

func (p Point) can_move_down_left() bool {
	return (p.y+p.first <= p.n) && (p.x-p.last >= 0)
}

func (p Point) can_move_down_right() bool {
	return (p.y+p.first <= p.n) && (p.x+p.last <= p.n)
}

func (p Point) can_move_right_up() bool {
	return (p.x+p.first <= p.n) && (p.y-p.last >= 0)
}

func (p Point) can_move_right_down() bool {
	return (p.x+p.first <= p.n) && (p.y+p.last <= p.n)
}

func (p Point) can_move_left_up() bool {
	return (p.x-p.first >= 0) && (p.y-p.last >= 0)
}

func (p Point) can_move_left_down() bool {
	return (p.x-p.first >= 0) && (p.y+p.last <= p.n)
}

func (p Point) getPossible() []Point {
	possible := []Point{}

	if p.can_move_down_right() && p.notInHistory(p.x+p.last, p.y+p.first) {
		possible = append(possible, Point{x: p.x + p.last, y: p.y + p.first, n: p.n, first: p.first, last: p.last})
	}

	if p.can_move_right_down() && p.notInHistory(p.x+p.first, p.y+p.last) {
		possible = append(possible, Point{x: p.x + p.first, y: p.y + p.last, n: p.n, first: p.first, last: p.last})
	}

	if p.can_move_up_right() && p.notInHistory(p.x+p.last, p.y-p.first) {
		possible = append(possible, Point{x: p.x + p.last, y: p.y - p.first, n: p.n, first: p.first, last: p.last})
	}

	if p.can_move_right_up() && p.notInHistory(p.x+p.first, p.y-p.last) {
		possible = append(possible, Point{x: p.x + p.first, y: p.y - p.last, n: p.n, first: p.first, last: p.last})
	}

	if p.can_move_down_left() && p.notInHistory(p.x-p.last, p.y+p.first) {
		possible = append(possible, Point{x: p.x - p.last, y: p.y + p.first, n: p.n, first: p.first, last: p.last})
	}

	if p.can_move_left_down() && p.notInHistory(p.x-p.first, p.y+p.last) {
		possible = append(possible, Point{x: p.x - p.first, y: p.y + p.last, n: p.n, first: p.first, last: p.last})
	}

	if p.can_move_up_left() && p.notInHistory(p.x-p.last, p.y-p.first) {
		possible = append(possible, Point{x: p.x - p.last, y: p.y - p.first, n: p.n, first: p.first, last: p.last})
	}

	if p.can_move_left_up() && p.notInHistory(p.x-p.first, p.y-p.last) {
		possible = append(possible, Point{x: p.x - p.first, y: p.y - p.last, n: p.n, first: p.first, last: p.last})
	}

	for i := range possible {
		tmphistory := make([][]int32, len(p.history), cap(p.history)+1)
		copy(tmphistory, p.history)
		tmphistory = append(tmphistory, []int32{p.x, p.y})
		possible[i].history = tmphistory
	}

	return possible
}

func (p Point) notInHistory(x, y int32) bool {
	for i := range p.history {
		if (p.history[i][0] == x) && (p.history[i][1] == y) {
			return false
		}
	}

	return true
}

func (p Point) expandPath(points map[string]Point) map[string]Point {
	if len(points) == 0 {
		posibles := p.getPossible()

		for i := range posibles {
			point := posibles[i]
			points["["+strconv.Itoa(int(point.x))+","+strconv.Itoa(int(point.y))+"]"] = point
		}
	} else {
		keys := make([]string, 0, len(points))
		for k := range points {
			keys = append(keys, k)
		}
		sort.Strings(keys)

		for _, k := range keys {
			point := points[k]
			posibles := point.getPossible()

			for i := range posibles {
				point := posibles[i]
				key := "[" + strconv.Itoa(int(point.x)) + "," + strconv.Itoa(int(point.y)) + "]"
				v, ok := points[key]
				if ok {
					if len(point.history) < len(v.history) {
						points[key] = point
					}
				} else {
					points[key] = point
				}
			}
		}
	}

	return points
}

func (p Point) findSmallestPath() int32 {
	// Known results
	if p.first == p.n && p.last == p.n {
		return 1
	}

	if p.first == 1 && p.last == 1 {
		return p.n
	}

	end := Point{x: p.n, y: p.n, n: p.n, first: p.first, last: p.last, history: [][]int32{}}
	left := map[string]Point{}
	rigth := map[string]Point{}

	for i := 1; i <= 50; i++ {
		left = p.expandPath(left)
		rigth = end.expandPath(rigth)

		var min int32
		for x := range left {
			v, ok := rigth[x]

			if ok {
				steps := int32(len(v.history) + len(left[x].history))
				if min == 0 {
					min = steps
				} else if steps < min {
					min = steps
				}
			}
		}
		if min > 0 {
			return min
		}
	}
	return -1
}

func knightlOnAChessboard(n int32) [][]int32 {
	n = n - 1

	result := make([][]int32, n, n)
	for y := range result {
		lineResult := make([]int32, n, n)
		for x := range lineResult {
			lineResult[x] = Point{
				x:       0,
				y:       0,
				n:       n,
				first:   int32(y + 1),
				last:    int32(x + 1),
				history: [][]int32{},
			}.findSmallestPath()
		}
		result[y] = lineResult
	}

	return result
}

func knightlOnAChessboardMulti(n int32) [][]int32 {
	n = n - 1

	result := make([][]int32, n, n)
	ch := make(chan [][]int32, int(n))
	wg := sync.WaitGroup{}

	wg.Add(int(n))

	for y := range result {
		go func(y int) {
			defer wg.Done()
			lineResult := make([]int32, n, n)
			for x := range lineResult {
				lineResult[x] = Point{
					x:       0,
					y:       0,
					n:       n,
					first:   int32(y + 1),
					last:    int32(x + 1),
					history: [][]int32{},
				}.findSmallestPath()

				ch <- [][]int32{{int32(y)}, lineResult}
			}

		}(y)
	}

	go func() {
		wg.Wait()
		close(ch)
	}()

	for point := range ch {
		result[point[0][0]] = point[1]
	}

	return result
}

func main() {
	fmt.Println(knightlOnAChessboardMulti(17))
}