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 14package main 15 16const 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. 21var 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. 37var center int 38 39func 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 52var 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. 57func 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. 69func 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). 80func 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 113func main() { 114 if !solve() { 115 println("no solution found") 116 } 117 println(moves, "moves tried") 118} 119