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