Home | History | Annotate | Download | only in test 
      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