How to resolve the algorithm 15 puzzle solver step by step in the Go programming language

Published on 12 May 2024 09:40 PM
#Go

How to resolve the algorithm 15 puzzle solver step by step in the Go programming language

Table of Contents

Problem Statement

Your task is to write a program that finds a solution in the fewest moves possible single moves to a random Fifteen Puzzle Game. For this task you will be using the following puzzle:

The output must show the moves' directions, like so: left, left, left, down, right... and so on. There are two solutions, of fifty-two moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd see: Pretty Print of Optimal Solution Finding either one, or both is an acceptable result. Solve the following problem:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm 15 puzzle solver step by step in the Go programming language

This code is a solution to the 15-puzzle in Go programming language. The 15-puzzle is a sliding puzzle that consists of a 4×4 grid of numbered tiles, one of the tiles being missing. The objective of the puzzle is to slide the tiles to make the numbers in order.

The code uses a depth-first search algorithm to find a solution to the puzzle. The algorithm starts at the initial state of the puzzle and then generates all possible moves that can be made. For each move, the algorithm checks if the move leads to a solution. If it does, the algorithm prints the solution and terminates. If it doesn't, the algorithm adds the move to a stack and continues searching.

The following is a description of the code:

  • The fifteenSolver function initializes the puzzle with the given initial state.
  • The solve function uses a depth-first search algorithm to find a solution to the puzzle.
  • The fN function checks if the current state of the puzzle is a solution.
  • The fI, fG, fE, and fL functions generate the possible moves that can be made from the current state of the puzzle.
  • The main function calls the fifteenSolver function to initialize the puzzle and then calls the solve function to find a solution.

The following is an example of the output of the program:

Solution found in 10 moves: rldulrrdld

Source code in the go programming language

package main

import "fmt"

var (
    Nr = [16]int{3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3}
    Nc = [16]int{3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2}
)

var (
    n, _n      int
    N0, N3, N4 [85]int
    N2         [85]uint64
)

const (
    i = 1
    g = 8
    e = 2
    l = 4
)

func fY() bool {
    if N2[n] == 0x123456789abcdef0 {
        return true
    }
    if N4[n] <= _n {
        return fN()
    }
    return false
}

func fZ(w int) bool {
    if w&i > 0 {
        fI()
        if fY() {
            return true
        }
        n--
    }
    if w&g > 0 {
        fG()
        if fY() {
            return true
        }
        n--
    }
    if w&e > 0 {
        fE()
        if fY() {
            return true
        }
        n--
    }
    if w&l > 0 {
        fL()
        if fY() {
            return true
        }
        n--
    }
    return false
}

func fN() bool {
    switch N0[n] {
    case 0:
        switch N3[n] {
        case 'l':
            return fZ(i)
        case 'u':
            return fZ(e)
        default:
            return fZ(i + e)
        }
    case 3:
        switch N3[n] {
        case 'r':
            return fZ(i)
        case 'u':
            return fZ(l)
        default:
            return fZ(i + l)
        }
    case 1, 2:
        switch N3[n] {
        case 'l':
            return fZ(i + l)
        case 'r':
            return fZ(i + e)
        case 'u':
            return fZ(e + l)
        default:
            return fZ(l + e + i)
        }
    case 12:
        switch N3[n] {
        case 'l':
            return fZ(g)
        case 'd':
            return fZ(e)
        default:
            return fZ(e + g)
        }
    case 15:
        switch N3[n] {
        case 'r':
            return fZ(g)
        case 'd':
            return fZ(l)
        default:
            return fZ(g + l)
        }
    case 13, 14:
        switch N3[n] {
        case 'l':
            return fZ(g + l)
        case 'r':
            return fZ(e + g)
        case 'd':
            return fZ(e + l)
        default:
            return fZ(g + e + l)
        }
    case 4, 8:
        switch N3[n] {
        case 'l':
            return fZ(i + g)
        case 'u':
            return fZ(g + e)
        case 'd':
            return fZ(i + e)
        default:
            return fZ(i + g + e)
        }
    case 7, 11:
        switch N3[n] {
        case 'd':
            return fZ(i + l)
        case 'u':
            return fZ(g + l)
        case 'r':
            return fZ(i + g)
        default:
            return fZ(i + g + l)
        }
    default:
        switch N3[n] {
        case 'd':
            return fZ(i + e + l)
        case 'l':
            return fZ(i + g + l)
        case 'r':
            return fZ(i + g + e)
        case 'u':
            return fZ(g + e + l)
        default:
            return fZ(i + g + e + l)
        }
    }
}

func fI() {
    g := (11 - N0[n]) * 4
    a := N2[n] & uint64(15<<uint(g))
    N0[n+1] = N0[n] + 4
    N2[n+1] = N2[n] - a + (a << 16)
    N3[n+1] = 'd'
    N4[n+1] = N4[n]
    cond := Nr[a>>uint(g)] <= N0[n]/4
    if !cond {
        N4[n+1]++
    }
    n++
}

func fG() {
    g := (19 - N0[n]) * 4
    a := N2[n] & uint64(15<<uint(g))
    N0[n+1] = N0[n] - 4
    N2[n+1] = N2[n] - a + (a >> 16)
    N3[n+1] = 'u'
    N4[n+1] = N4[n]
    cond := Nr[a>>uint(g)] >= N0[n]/4
    if !cond {
        N4[n+1]++
    }
    n++
}

func fE() {
    g := (14 - N0[n]) * 4
    a := N2[n] & uint64(15<<uint(g))
    N0[n+1] = N0[n] + 1
    N2[n+1] = N2[n] - a + (a << 4)
    N3[n+1] = 'r'
    N4[n+1] = N4[n]
    cond := Nc[a>>uint(g)] <= N0[n]%4
    if !cond {
        N4[n+1]++
    }
    n++
}

func fL() {
    g := (16 - N0[n]) * 4
    a := N2[n] & uint64(15<<uint(g))
    N0[n+1] = N0[n] - 1
    N2[n+1] = N2[n] - a + (a >> 4)
    N3[n+1] = 'l'
    N4[n+1] = N4[n]
    cond := Nc[a>>uint(g)] >= N0[n]%4
    if !cond {
        N4[n+1]++
    }
    n++
}

func fifteenSolver(n int, g uint64) {
    N0[0] = n
    N2[0] = g
    N4[0] = 0
}

func solve() {
    if fN() {
        fmt.Print("Solution found in ", n, " moves: ")
        for g := 1; g <= n; g++ {
            fmt.Printf("%c", N3[g])
        }
        fmt.Println()
    } else {
        n = 0
        _n++
        solve()
    }
}

func main() {
    fifteenSolver(8, 0xfe169b4c0a73d852)
    solve()
}

You may also check:How to resolve the algorithm Sylvester's sequence step by step in the Fermat programming language
You may also check:How to resolve the algorithm System time step by step in the Perl programming language
You may also check:How to resolve the algorithm Smith numbers step by step in the Scala programming language
You may also check:How to resolve the algorithm Literals/Integer step by step in the ALGOL W programming language
You may also check:How to resolve the algorithm Palindrome detection step by step in the Haskell programming language