Language: C++

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	N    = 4
	BASE = 10007
	MOD  = 1000000007
)

// Go cannot create const array?
var solvedBoard [N * N]int = [N * N]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0}

type Puzzle struct {
	board [N * N]int // (x, y). (0, 0) = 0,  (1, 0) = 1, (0, 1) = 3
}

type SolveContext struct {
	current *Puzzle
	count   int
}

type Position struct {
	x int
	y int
}

func NewPuzzle(b [N * N]int) *Puzzle {
	return &Puzzle{board: b}
}

func (puzzle *Puzzle) hash() int {
	arr := puzzle.board
	sum := arr[0]
	for i := 1; i < len(arr); i++ {
		sum = sum*BASE + arr[i]
		if sum > MOD {
			sum = sum % MOD
		}
	}
	return sum
}

func (puzzle *Puzzle) isSolved() bool {
	return puzzle.board == solvedBoard
}

func swap(puzzle *Puzzle, one, two Position) *Puzzle {
	swapped := NewPuzzle(puzzle.board)
	swapped.board[one.y*N+one.x], swapped.board[two.y*N+two.x] =
		swapped.board[two.y*N+two.x], swapped.board[one.y*N+one.x]
	return swapped
}

func (puzzle *Puzzle) getEmptyPosition() *Position {
	for i := 0; i < N; i++ {
		for j := 0; j < N; j++ {
			if puzzle.board[i*N+j] == 0 {
				return &Position{x: j, y: i}
			}
		}
	}
	return nil
}

func (puzzle *Puzzle) nextPuzzles() []*Puzzle {
	emptyPosition := puzzle.getEmptyPosition()
	if emptyPosition == nil {
		panic(fmt.Errorf("emptyPostion must not be empty"))
	}
	basePosition := *emptyPosition
	directions := [][2]int{[2]int{-1, 0}, [2]int{1, 0}, [2]int{0, -1}, [2]int{0, 1}} // []{x, y}
	nexts := []*Puzzle{}
	for _, dir := range directions {
		nextPosition := Position{basePosition.x + dir[0], basePosition.y + dir[1]}
		if nextPosition.x >= 0 && nextPosition.x <= N-1 &&
			nextPosition.y >= 0 && nextPosition.y <= N-1 {
			nexts = append(nexts, swap(puzzle, basePosition, nextPosition))
		}
	}
	return nexts
}

func solve(initialPuzzle *Puzzle) int {
	goal := &Puzzle{board: solvedBoard}
	visitedF := make(map[int]*int)
	visitedB := make(map[int]*int)
	stackF := []SolveContext{SolveContext{initialPuzzle, 0}}
	stackB := []SolveContext{SolveContext{goal, 0}}
	direction := 1
	for {
		if direction == 1 {
			// forward
			solveContext := stackF[0]
			stackF = stackF[1:]
			current := solveContext.current
			count := solveContext.count

			if visitedB[current.hash()] != nil {
				return count + *visitedB[current.hash()]
			}
			visitedF[current.hash()] = &count

			for _, v := range current.nextPuzzles() {
				if visitedF[v.hash()] == nil {
					nextContext := SolveContext{v, count + 1}
					stackF = append(stackF, nextContext)
				}
			}
		} else {
			// backward
			solveContext := stackB[0]
			stackB = stackB[1:]
			current := solveContext.current
			count := solveContext.count

			if visitedF[current.hash()] != nil {
				return count + *visitedF[current.hash()]
			}
			visitedB[current.hash()] = &count

			for _, v := range current.nextPuzzles() {
				if visitedB[v.hash()] == nil {
					nextContext := SolveContext{v, count + 1}
					stackB = append(stackB, nextContext)
				}
			}
		}
		direction *= -1
	}
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	var arr [N * N]int
	for i := 0; i < len(arr); i++ {
		x, err := nextInt(sc)
		if err != nil {
			panic(err)
		}
		arr[i] = x
	}

	puzzle := NewPuzzle(arr)
	fmt.Println(solve(puzzle))
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}



Compiler output:
a.cc:1:1: error: 'package' does not name a type
    1 | package main
      | ^~~~~~~
a.cc:19:1: error: 'type' does not name a type; did you mean 'typeof'?
   19 | type Puzzle struct {
      | ^~~~
      | typeof
a.cc:23:1: error: 'type' does not name a type; did you mean 'typeof'?
   23 | type SolveContext struct {
      | ^~~~
      | typeof
a.cc:28:1: error: 'type' does not name a type; did you mean 'typeof'?
   28 | type Position struct {
      | ^~~~
      | typeof
a.cc:33:1: error: 'func' does not name a type
   33 | func NewPuzzle(b [N * N]int) *Puzzle {
      | ^~~~
a.cc:37:6: error: expected constructor, destructor, or type conversion before '(' token
   37 | func (puzzle *Puzzle) hash() int {
      |      ^
a.cc:49:6: error: expected constructor, destructor, or type conversion before '(' token
   49 | func (puzzle *Puzzle) isSolved() bool {
      |      ^
a.cc:53:1: error: 'func' does not name a type
   53 | func swap(puzzle *Puzzle, one, two Position) *Puzzle {
      | ^~~~
a.cc:60:6: error: expected constructor, destructor, or type conversion before '(' token
   60 | func (puzzle *Puzzle) getEmptyPosition() *Position {
      |      ^
a.cc:71:6: error: expected constructor, destructor, or type conversion before '(' token
   71 | func (puzzle *Puzzle) nextPuzzles() []*Puzzle {
      |      ^
a.cc:89:1: error: 'func' does not name a type
   89 | func solve(initialPuzzle *Puzzle) int {
      | ^~~~
a.cc:138:1: error: 'func' does not name a type
  138 | func main() {
      | ^~~~
a.cc:155:1: error: 'func' does not name a type
  155 | func nextInt(sc *bufio.Scanner) (int, error) {
      | ^~~~