knight-tour-warnsdorff.go

package main

import "fmt"

// Distance defines the distance of a point
// using row and column as measurement.
type Distance struct {
	Row    int
	Column int
}

var (
	// KnightMoves defines all moves of a knight.
	KnightMoves = []Distance{
		{Row: 1, Column: 2},
		{Row: 1, Column: -2},
		{Row: 2, Column: 1},
		{Row: 2, Column: -1},
		{Row: -1, Column: 2},
		{Row: -1, Column: -2},
		{Row: -2, Column: 1},
		{Row: -2, Column: -1},
	}
	// NumOfKnightMoves defines the number of all knight moves.
	NumOfKnightMoves = 8
)

func isValidCell(row, column, size int) bool {
	return row >= 0 && row < size && column >= 0 && column < size
}

func isVisitableCell(val int) bool {
	return val == 0
}

func getSize() int {
	var size int
	fmt.Printf("insert size: ")
	_, err := fmt.Scanf("%d", &size)
	if err != nil {
		panic(err)
	}
	if size < 5 {
		panic("size must be at least 5")
	}
	return size
}

func createBoard(size int) [][]int {
	board := make([][]int, size)
	for i := 0; i < size; i++ {
		board[i] = make([]int, size)
		for j := 0; j < size; j++ {
			board[i][j] = 0
		}
	}
	return board
}

func countAccessibilityValue(board [][]int, row, column, size int) int {
	value := 0
	for _, move := range KnightMoves {
		neighbourRow := row + move.Row
		neighbourColumn := column + move.Column

		if isValidCell(neighbourRow, neighbourColumn, size) && isVisitableCell(board[neighbourRow][neighbourColumn]) {
			value++
		}
	}
	return value
}

func traverseBoard(board [][]int, currentRow, currentColumn, size int) {
	board[currentRow][currentColumn] = 1

	boardSize := size * size
	for i := 2; i <= boardSize; i++ {
		minAccessibilityValue := NumOfKnightMoves
		choosenNextRow := 0
		choosenNextColumn := 0

		for _, move := range KnightMoves {
			nextRowCandidate := currentRow + move.Row
			nextColumnCandidate := currentColumn + move.Column

			if isValidCell(nextRowCandidate, nextColumnCandidate, size) && isVisitableCell(board[nextRowCandidate][nextColumnCandidate]) {
				accessibilityValue := countAccessibilityValue(board, nextRowCandidate, nextColumnCandidate, size)
				if accessibilityValue < minAccessibilityValue {
					minAccessibilityValue = accessibilityValue
					choosenNextRow = nextRowCandidate
					choosenNextColumn = nextColumnCandidate
				}
			}
		}

		if minAccessibilityValue == NumOfKnightMoves {
			panic("no solution")
		}

		currentRow = choosenNextRow
		currentColumn = choosenNextColumn
		board[currentRow][currentColumn] = i
	}

}

func printBoard(board [][]int, size int) {
	for i := 0; i < size; i++ {
		for j := 0; j < size; j++ {
			fmt.Printf("%3d", board[i][j])
		}
		fmt.Println()
	}
}

func main() {
	size := getSize()
	board := createBoard(size)

	traverseBoard(board, 0, 0, size)
	printBoard(board, size)
}