123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117 |
- // This program solves the (English) peg
- // solitaire board game.
- // http://en.wikipedia.org/wiki/Peg_solitaire
- package main
- import "fmt"
- const N = 11 + 1 // length of a row (+1 for \n)
- // The board must be surrounded by 2 illegal
- // fields in each direction so that move()
- // doesn't need to check the board boundaries.
- // Periods represent illegal fields,
- // ● are pegs, and ○ are holes.
- var board = []rune(
- `...........
- ...........
- ....●●●....
- ....●●●....
- ..●●●●●●●..
- ..●●●○●●●..
- ..●●●●●●●..
- ....●●●....
- ....●●●....
- ...........
- ...........
- `)
- // center is the position of the center hole if
- // there is a single one; otherwise it is -1.
- var center int
- func init() {
- n := 0
- for pos, field := range board {
- if field == '○' {
- center = pos
- n++
- }
- }
- if n != 1 {
- center = -1 // no single hole
- }
- }
- var moves int // number of times move is called
- // move tests if there is a peg at position pos that
- // can jump over another peg in direction dir. If the
- // move is valid, it is executed and move returns true.
- // Otherwise, move returns false.
- func move(pos, dir int) bool {
- moves++
- if board[pos] == '●' && board[pos+dir] == '●' && board[pos+2*dir] == '○' {
- board[pos] = '○'
- board[pos+dir] = '○'
- board[pos+2*dir] = '●'
- return true
- }
- return false
- }
- // unmove reverts a previously executed valid move.
- func unmove(pos, dir int) {
- board[pos] = '●'
- board[pos+dir] = '●'
- board[pos+2*dir] = '○'
- }
- // solve tries to find a sequence of moves such that
- // there is only one peg left at the end; if center is
- // >= 0, that last peg must be in the center position.
- // If a solution is found, solve prints the board after
- // each move in a backward fashion (i.e., the last
- // board position is printed first, all the way back to
- // the starting board position).
- func solve() bool {
- var last, n int
- for pos, field := range board {
- // try each board position
- if field == '●' {
- // found a peg
- for _, dir := range [...]int{-1, -N, +1, +N} {
- // try each direction
- if move(pos, dir) {
- // a valid move was found and executed,
- // see if this new board has a solution
- if solve() {
- unmove(pos, dir)
- fmt.Println(string(board))
- return true
- }
- unmove(pos, dir)
- }
- }
- last = pos
- n++
- }
- }
- // tried each possible move
- if n == 1 && (center < 0 || last == center) {
- // there's only one peg left
- fmt.Println(string(board))
- return true
- }
- // no solution found for this board
- return false
- }
- func main() {
- if !solve() {
- fmt.Println("no solution found")
- }
- fmt.Println(moves, "moves tried")
- }
|