1 // This program solves the (English) peg 2 // solitaire board game. 3 // http://en.wikipedia.org/wiki/Peg_solitaire 4 5 package main 6 7 import "fmt" 8 9 const N = 11 + 1 // length of a row (+1 for \n) 10 11 // The board must be surrounded by 2 illegal 12 // fields in each direction so that move() 13 // doesn't need to check the board boundaries. 14 // Periods represent illegal fields, 15 // are pegs, and are holes. 16 17 var board = []rune( 18 `........... 19 ........... 20 ........ 21 ........ 22 .... 23 .... 24 .... 25 ........ 26 ........ 27 ........... 28 ........... 29 `) 30 31 // center is the position of the center hole if 32 // there is a single one; otherwise it is -1. 33 var center int 34 35 func init() { 36 n := 0 37 for pos, field := range board { 38 if field == '' { 39 center = pos 40 n++ 41 } 42 } 43 if n != 1 { 44 center = -1 // no single hole 45 } 46 } 47 48 var moves int // number of times move is called 49 50 // move tests if there is a peg at position pos that 51 // can jump over another peg in direction dir. If the 52 // move is valid, it is executed and move returns true. 53 // Otherwise, move returns false. 54 func move(pos, dir int) bool { 55 moves++ 56 if board[pos] == '' && board[pos+dir] == '' && board[pos+2*dir] == '' { 57 board[pos] = '' 58 board[pos+dir] = '' 59 board[pos+2*dir] = '' 60 return true 61 } 62 return false 63 } 64 65 // unmove reverts a previously executed valid move. 66 func unmove(pos, dir int) { 67 board[pos] = '' 68 board[pos+dir] = '' 69 board[pos+2*dir] = '' 70 } 71 72 // solve tries to find a sequence of moves such that 73 // there is only one peg left at the end; if center is 74 // >= 0, that last peg must be in the center position. 75 // If a solution is found, solve prints the board after 76 // each move in a backward fashion (i.e., the last 77 // board position is printed first, all the way back to 78 // the starting board position). 79 func solve() bool { 80 var last, n int 81 for pos, field := range board { 82 // try each board position 83 if field == '' { 84 // found a peg 85 for _, dir := range [...]int{-1, -N, +1, +N} { 86 // try each direction 87 if move(pos, dir) { 88 // a valid move was found and executed, 89 // see if this new board has a solution 90 if solve() { 91 unmove(pos, dir) 92 fmt.Println(string(board)) 93 return true 94 } 95 unmove(pos, dir) 96 } 97 } 98 last = pos 99 n++ 100 } 101 } 102 // tried each possible move 103 if n == 1 && (center < 0 || last == center) { 104 // there's only one peg left 105 fmt.Println(string(board)) 106 return true 107 } 108 // no solution found for this board 109 return false 110 } 111 112 func main() { 113 if !solve() { 114 fmt.Println("no solution found") 115 } 116 fmt.Println(moves, "moves tried") 117 } 118
