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