Documentation ¶
Index ¶
- Constants
- func AreTheSame(a []int, b []int) bool
- func Contains(s []*Node, n *Node) bool
- func Heuristic1(p []int) int
- func Heuristic2(p []int) int
- type Item
- type Node
- func (n *Node) ClonePuzzle() []int
- func (n *Node) GenerateMoves()
- func (n *Node) MoveDown(p []int, i int)
- func (n *Node) MoveDownLeft(p []int, i int)
- func (n *Node) MoveDownRight(p []int, i int)
- func (n *Node) MoveLeft(p []int, i int)
- func (n *Node) MoveRight(p []int, i int)
- func (n *Node) MoveUp(p []int, i int)
- func (n *Node) MoveUpLeft(p []int, i int)
- func (n *Node) MoveUpRight(p []int, i int)
- func (n *Node) PathTrace() []*Node
- type PriorityQueue
Constants ¶
const ( // NumberRows of the board NumberRows = 3 // NumberColumns of the board NumberColumns = 4 )
Variables ¶
This section is empty.
Functions ¶
func Heuristic2 ¶
Heuristic2 sum of permutation inversions + number of misplaced tiles
Types ¶
type Item ¶
type Item struct { Node *Node // The value of the item; arbitrary. Heuristic int // The priority of the item in the queue. // The index is needed by update and is maintained by the heap.Interface methods. Index int // The index of the item in the heap. }
An Item is something we manage in a priority queue.
type Node ¶
type Node struct { Puzzle []int Value int // the index of the "0" in the puzzle Children []*Node Parent *Node Move string // used for printing files Heuristic int G int // the depth of the node in the search tree }
Node represents a in the search tree
func BestFirstSearch ¶
BestFirstSearch algorithm
func ContainsAndRemove ¶
ContainsAndRemove checks if an slice of Nodes contains a given Node and removes the node if it is theres
func (*Node) ClonePuzzle ¶
ClonePuzzle copies the puzzle of a given Node
func (*Node) GenerateMoves ¶
func (n *Node) GenerateMoves()
GenerateMoves generates the possible moves
func (*Node) MoveDownLeft ¶
MoveDownLeft moves the empty tile diagonally down-left by 1 tile
func (*Node) MoveDownRight ¶
MoveDownRight moves the empty tile diagonally down-right by 1 tile
func (*Node) MoveUpLeft ¶
MoveUpLeft moves the empty tile diagonally up-left by 1 tile
func (*Node) MoveUpRight ¶
MoveUpRight moves the empty tile diagonally up-right by 1 tile
type PriorityQueue ¶
type PriorityQueue []*Item
A PriorityQueue implements heap.Interface and holds Items.
func (PriorityQueue) Contains ¶
func (pq PriorityQueue) Contains(n *Node) (bool, *Item)
Contains checks if it is there
func (PriorityQueue) Len ¶
func (pq PriorityQueue) Len() int
func (PriorityQueue) Less ¶
func (pq PriorityQueue) Less(i, j int) bool
func (PriorityQueue) Swap ¶
func (pq PriorityQueue) Swap(i, j int)