rush

package module
v0.0.0-...-3e3b839 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jun 10, 2024 License: MIT Imports: 8 Imported by: 0

README

Rush Hour (the puzzle)

This repo contains a bunch of stuff related to Rush Hour, a sliding block puzzle. You may also know this game from one of its iOS implementations, such as Unblock Me.

Read the Article

https://www.michaelfogleman.com/rush/

Play Online

https://www.michaelfogleman.com/static/rush/

Overview

The Go code can solve puzzles, render puzzles to PNG, generate puzzles, and more.

The C++ code "solves" the entire game - identifying all "interesting" puzzles that are possible. Read the article for more information. A database of puzzles is available.

The JavaScript code is for the online player.

51

Documentation

Index

Constants

View Source 
const MaxBoardSize = 16
View Source 
const MaxPieces = 18
View Source 
const MinBoardSize = MinPieceSize + 1
View Source 
const MinPieceSize = 2

Variables

This section is empty.

Functions

func Graph 

func Graph(input *Board)

Types

type Board 

type Board struct {
	Width  int
	Height int
	Pieces []Piece
	Walls  []int
	// contains filtered or unexported fields
}

Board represents the complete puzzle state. The size of the grid, the placement, size, orientation of the pieces. The placement of walls (immovable obstacles). Which cells are occupied, either by a piece or a wall.

func NewBoard 

func NewBoard(desc []string) (*Board, error)

func NewBoardFromString 

func NewBoardFromString(desc string) (*Board, error)

func NewEmptyBoard 

func NewEmptyBoard(w, h int) *Board

func NewRandomBoard 

func NewRandomBoard(w, h, primaryRow, primarySize, numPieces, numWalls int) *Board

func (*Board) AddPiece 

func (board *Board) AddPiece(piece Piece) bool

func (*Board) AddWall 

func (board *Board) AddWall(i int) bool

func (*Board) BlockedSquares 

func (board *Board) BlockedSquares() []int

func (*Board) Canonicalize 

func (board *Board) Canonicalize() *Board

func (*Board) Copy 

func (board *Board) Copy() *Board

func (*Board) DoMove 

func (board *Board) DoMove(move Move)

func (*Board) Energy 

func (board *Board) Energy() float64

func (*Board) HasFullRowOrCol 

func (board *Board) HasFullRowOrCol() bool

func (*Board) Hash 

func (board *Board) Hash() string

func (*Board) Impossible 

func (board *Board) Impossible() bool

func (*Board) MemoKey 

func (board *Board) MemoKey() *MemoKey

func (*Board) Moves 

func (board *Board) Moves(buf []Move) []Move

func (*Board) Mutate 

func (board *Board) Mutate() UndoFunc

func (*Board) ReachableStates 

func (board *Board) ReachableStates() int

func (*Board) RemoveLastPiece 

func (board *Board) RemoveLastPiece()

func (*Board) RemovePiece 

func (board *Board) RemovePiece(i int)

func (*Board) RemoveWall 

func (board *Board) RemoveWall(i int)

func (*Board) Render 

func (board *Board) Render() image.Image

func (*Board) Solve 

func (board *Board) Solve() Solution

func (*Board) SortPieces 

func (board *Board) SortPieces()

func (*Board) StateIterator 

func (board *Board) StateIterator() <-chan *Board

func (*Board) String 

func (board *Board) String() string

func (*Board) Target 

func (board *Board) Target() int

func (*Board) UndoMove 

func (board *Board) UndoMove(move Move)

func (*Board) UnsafeSolve 

func (board *Board) UnsafeSolve() Solution

func (*Board) UnsafeUnsolve 

func (board *Board) UnsafeUnsolve() (*Board, Solution)

func (*Board) Unsolve 

func (board *Board) Unsolve() (*Board, Solution)

func (*Board) Validate 

func (board *Board) Validate() error

type Enumerator 

type Enumerator struct {
	// contains filtered or unexported fields
}

func NewDefaultEnumerator 

func NewDefaultEnumerator() *Enumerator

func NewEnumerator 

func NewEnumerator(w, h, pr, ps, mins, maxs int) *Enumerator

func (*Enumerator) Count 

func (e *Enumerator) Count() uint64

func (*Enumerator) Enumerate 

func (e *Enumerator) Enumerate(channelBufferSize int) <-chan EnumeratorItem

func (*Enumerator) MaxGroup 

func (e *Enumerator) MaxGroup() int

type EnumeratorItem 

type EnumeratorItem struct {
	Board   *Board
	Group   int
	Counter uint64
}

type Generator 

type Generator struct {
	Width       int
	Height      int
	PrimarySize int
	PrimaryRow  int
}

func NewDefaultGenerator 

func NewDefaultGenerator() *Generator

func (*Generator) Generate 

func (g *Generator) Generate(iterations int) *Board
type Link struct {
	Src, Dst int
}
func MakeLink(id1, id2 int) Link

type Memo 

type Memo struct {
	// contains filtered or unexported fields
}

func NewMemo 

func NewMemo() *Memo

func (*Memo) Add 

func (memo *Memo) Add(key *MemoKey, depth int) bool

func (*Memo) Hits 

func (memo *Memo) Hits() uint64

func (*Memo) Set 

func (memo *Memo) Set(key *MemoKey, depth int)

func (*Memo) Size 

func (memo *Memo) Size() int

type MemoKey 

type MemoKey [MaxPieces]int

func MakeMemoKey 

func MakeMemoKey(pieces []Piece) MemoKey

func (*MemoKey) Less 

func (a *MemoKey) Less(b *MemoKey, primary bool) bool

type Move 

type Move struct {
	Piece int
	Steps int
}

Move represents a move to make on the board. Piece indicates which piece (by index) to move and Steps is a non-zero positive or negative int that specifies how many cells to move the piece.

func (Move) AbsSteps 

func (move Move) AbsSteps() int

func (Move) Label 

func (move Move) Label() string

func (Move) String 

func (move Move) String() string

type Orientation 

type Orientation int

Orientation indicates which direction a Piece can move. Horizontal pieces can move left and right. Vertical pieces can move up and down. 

const (
	Horizontal Orientation = iota
	Vertical
)

type Piece 

type Piece struct {
	Position    int
	Size        int
	Orientation Orientation
}

Piece represents a piece (a car or a truck) on the grid. Its position is a zero-indexed int, 0 <= Position < W*H. Its size specifies how many cells it occupies. Its orientation specifies whether it is vertical or horizontal.

func (*Piece) Col 

func (piece *Piece) Col(w int) int

func (*Piece) Row 

func (piece *Piece) Row(w int) int

func (*Piece) Stride 

func (piece *Piece) Stride(w int) int

type Solution 

type Solution struct {
	Solvable bool
	Moves    []Move
	NumMoves int
	NumSteps int
	Depth    int
	MemoSize int
	MemoHits uint64
}

type Solver 

type Solver struct {
	// contains filtered or unexported fields
}

func NewSolver 

func NewSolver(board *Board) *Solver

func NewSolverWithStaticAnalyzer 

func NewSolverWithStaticAnalyzer(board *Board, sa *StaticAnalyzer) *Solver

func (*Solver) Solve 

func (solver *Solver) Solve() Solution

func (*Solver) UnsafeSolve 

func (solver *Solver) UnsafeSolve() Solution

type StaticAnalyzer 

type StaticAnalyzer struct {
	// contains filtered or unexported fields
}

func NewStaticAnalyzer 

func NewStaticAnalyzer() *StaticAnalyzer

func (*StaticAnalyzer) BlockedSquares 

func (sa *StaticAnalyzer) BlockedSquares(board *Board) []int

func (*StaticAnalyzer) Impossible 

func (sa *StaticAnalyzer) Impossible(board *Board) bool

type UndoFunc 

type UndoFunc func()

type Unsolver 

type Unsolver struct {
	// contains filtered or unexported fields
}

func NewUnsolver 

func NewUnsolver(board *Board) *Unsolver

func NewUnsolverWithStaticAnalyzer 

func NewUnsolverWithStaticAnalyzer(board *Board, sa *StaticAnalyzer) *Unsolver

func (*Unsolver) UnsafeUnsolve 

func (u *Unsolver) UnsafeUnsolve() (*Board, Solution)

func (*Unsolver) Unsolve 

func (u *Unsolver) Unsolve() (*Board, Solution)

Source Files

View all Source files

Directories

Path Synopsis
cmd
bench
canonical
enumerate
example
forty
generate
graph
impossible
multi
profile
render
solve
solver
static
universe
unsolver

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.