solve knight touring problem

knight.go

package main

import (
	"bytes"
	"fmt"
	"math/rand"
	"os"
	"sort"
	"time"
)

type Board struct {
	width  int
	height int
	grids  [][]bool
}

type Grid struct {
	x int
	y int
}

type Knight struct {
	current Grid
	paths   []Grid
	board   *Board
}

func makeKnight(width, height int) *Knight {
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	board := Board{
		width:  width,
		height: height,
		grids:  make([][]bool, height),
	}
	for i := 0; i < height; i++ {
		board.grids[i] = make([]bool, width)
	}
	return &Knight{
		current: Grid{r.Intn(8), r.Intn(8)},
		board:   &board,
	}
}

type Choices struct {
	grids []Grid
	board *Board
}

func (choices Choices) Len() int {
	return len(choices.grids)
}

func (choices Choices) Less(i, j int) bool {

	grid1 := choices.grids[i]
	grid2 := choices.grids[j]
	return len(choices.board.Available(grid1)) < len(choices.board.Available(grid2))
}

func (choices Choices) Swap(i, j int) {
	swap := choices.grids[j]
	choices.grids[j] = choices.grids[i]
	choices.grids[i] = swap
}

func (board *Board) Available(g Grid) []Grid {
	x, y := g.x, g.y
	grids := [8]Grid{Grid{x - 1, y - 2}, Grid{x - 1, y + 2}, Grid{x - 2, y - 1}, Grid{x - 2, y + 1}, Grid{x + 1, y - 2}, Grid{x + 1, y + 2}, Grid{x + 2, y - 1}, Grid{x + 2, y + 1}}

	next := []Grid{}
	for _, grid := range grids {
		if grid.x >= 0 && grid.x < board.width && grid.y >= 0 && grid.y < board.height && !board.grids[grid.x][grid.y] {
			next = append(next, grid)
		}
	}
	return next
}

func (knight *Knight) tour() {
	knight.paths = append(knight.paths, knight.current)
	x, y := knight.current.x, knight.current.y
	knight.board.grids[x][y] = true

	next := knight.board.Available(knight.current)

	if len(next) == 0 {
		return
	}
	choices := Choices{next, knight.board}
	sort.Sort(choices)
	knight.current = choices.grids[0]
	knight.tour()
}

func main() {
	knight := makeKnight(8, 8)
	knight.tour()
	buf := new(bytes.Buffer)
	for index, grid := range knight.paths {
		buf.WriteString(fmt.Sprintf("(%d,%d)", grid.x, grid.y))
		if index != 63 {
			if (index % 8) == 7 {
				buf.WriteString("\n")
			} else {
				buf.WriteString(",")
			}
		}
	}
	buf.WriteString("\n")
	buf.WriteTo(os.Stdout)
	for _, line := range knight.board.grids {
		for _, g := range line {
			if g {
				buf.WriteString("x")
			} else {
				buf.WriteString("o")
			}
		}
		buf.WriteString("\n")
	}
	buf.WriteTo(os.Stdout)
}