jump-all-but-one.go

/**
 * User: rfink <[email protected]>
 * Date: 12/20/13
 * Time: 12:00 PM
 */
package main

import (
    //"./board"
    "fmt"
    //"strconv"
)


type Board struct {
    Container [][]int8
}

func (this *Board) Init(startX int, startY int) {
    this.Container = make([][]int8, 5)
    for y := 0; y < 5; y++ {
        this.Container[y] = make([]int8, 5)
        for x := 0; x < 5; x++ {
            if x <= y {
                if startX == x && startY == y {
                    this.Container[y][x] = 0
                } else {
                    this.Container[y][x] = 1
                }
            } else {
                this.Container[y][x] = -1
            }
        }
    }
    return
}

func (this *Board) Move(x1 int, y1 int, x2 int, y2 int, x3 int, y3 int) (Board) {
    board := this.Clone()
    board.Container[y1][x1] = 0
    board.Container[y2][x2] = 0
    board.Container[y3][x3] = 1

    return board
}

func (this *Board) Clone() (Board) {
    var newContainer = make([][]int8, 5)
    for i := range this.Container {
        newContainer[i] = make([]int8, 5)
        for j := range this.Container[i] {
            newContainer[i][j] = this.Container[i][j]
        }
    }
    return Board{Container: newContainer}
}

type State struct {
    Moves []Board
    Current Board
}

func (this *State) Display() {
    for i := range this.Current.Container {
        fmt.Println(this.Current.Container[i])
    }
    fmt.Println("=============================")
}

func findSolution(state *State) (bool) {
    numPiecesLeft := 0
    board := state.Current

    for y := 0; y < 5; y++ {
        for x := 0; x <= y; x++ {
            if board.Container[y][x] != 1 {
                continue;
            }
            numPiecesLeft++
            // Try to move "upwards"
            if y > 1 {
                // Try to move "up-left"
                if  x > 1 && board.Container[y - 1][x - 1] == 1 && board.Container[y - 2][x - 2] == 0 {
                    fmt.Println("Moving up and left")
                    state.Current = board.Move(x, y, x - 1, y - 1, x - 2, y - 2)
                    state.Moves = append(state.Moves, state.Current.Clone())
                    solution := findSolution(state)
                    if solution {
                        return solution
                    }
                }
                // Try to move "up-up"
                if board.Container[y - 1][x] == 1 && board.Container[y - 2][x] == 0 {
                    fmt.Println("Moving straight up")
                    state.Current = board.Move(x, y, x, y - 1, x, y - 2)
                    state.Moves = append(state.Moves, state.Current.Clone())
                    solution := findSolution(state)
                    if solution {
                        return solution
                    }
                }
                // Try to move "up-right"
                if x < 3 && board.Container[y - 1][x + 1] == 1 && board.Container[y - 2][x + 2] == 0 {
                    fmt.Println("Moving up and right")
                    state.Current = board.Move(x, y, x + 1, y - 1, x + 2, y - 2)
                    state.Moves = append(state.Moves, state.Current.Clone())
                    solution := findSolution(state)
                    if solution {
                        return solution
                    }
                }
            }
            // Try to move "laterally"
            if y > 1 && x > 1 {
                // Try to move left
                if x > 1 && board.Container[y][x - 1] == 1 && board.Container[y][x - 2] == 0 {
                    fmt.Println("Moving straight left")
                    state.Current = board.Move(x, y, x - 1, y, x - 2, y)
                    state.Moves = append(state.Moves, state.Current.Clone())
                    solution := findSolution(state)
                    if solution {
                        return solution
                    }
                }

                // Try to move right
                if x < 3 && board.Container[y][x + 1] == 1 && board.Container[y][x + 2] == 0 {
                    fmt.Println("Moving straight right")
                    state.Current = board.Move(x, y, x + 1, y, x + 2, y)
                    state.Moves = append(state.Moves, state.Current.Clone())
                    solution := findSolution(state)
                    if solution {
                        return solution
                    }
                }
            }
            // Try to move "downwards"
            if y < 3 {
                // Try to move "down-left"
                if x > 1 && board.Container[y + 1][x - 1] == 1 && board.Container[y + 2][x - 2] == 0 {
                    fmt.Println("Moving down and left")
                    state.Current = board.Move(x, y, x - 1, y + 1, x - 2, y + 2)
                    state.Moves = append(state.Moves, state.Current.Clone())
                    solution := findSolution(state)
                    if solution {
                        return solution
                    }
                }
                // Try to move "down-down"
                if board.Container[y + 1][x] == 1 && board.Container[y + 2][x] == 0 {
                    fmt.Println("Moving straight down")
                    state.Current = board.Move(x, y, x, y + 1, x, y + 2)
                    state.Moves = append(state.Moves, state.Current.Clone())
                    solution := findSolution(state)
                    if solution {
                        return solution
                    }
                }
                // Try to move "down-right"
                if x < 3 && board.Container[y + 1][x + 1] == 1 && board.Container[y + 2][x + 2] == 0 {
                    fmt.Println("Moving down and right")
                    state.Current = board.Move(x, y, x + 1, y + 1, x + 2, y + 2)
                    state.Moves = append(state.Moves, state.Current.Clone())
                    solution := findSolution(state)
                    if solution {
                        return solution
                    }
                }
            }
        }
    }

    // We have a winner
    if numPiecesLeft == 1 {
        fmt.Println("We have a winner")
        return true
    }

    // Pop our last move off of the stack and return
    fmt.Println("Bumskis")
    state.Moves = state.Moves[:len(state.Moves) - 1]
    state.Current = state.Moves[len(state.Moves) - 1]
    return false
}

func main() {
    board := Board{}
    board.Init(2, 2)
    moves := make([]Board, 1)
    moves[0] = board
    fmt.Println(moves)
    state := State{Current: board, Moves: moves}
    _ = findSolution(&state)
    fmt.Println("Done")
    for i := range state.Moves {
        fmt.Println(state.Moves[i].Container)
    }
}