fork(1) download
copy 
  1. // This program solves the (English) peg solitaire
  2. // board game.  See also:
  3. //   http://e...content-available-to-author-only...a.org/wiki/Peg_solitaire
  4.  
  5. package main
  6.  
  7. import "fmt"
  8.  
  9. const N = 11 + 1 // length of a board row (+1 for \n)
  10.  
  11. // The board must be surrounded by 2 illegal fields 
  12. // in each direction so that move() doesn't need to 
  13. // check the board boundaries. Periods represent 
  14. // illegal fields, ● are pegs, and ○ are holes.
  15. var board = []int(
  16. 	`...........
  17. ...........
  18. ....●●●....
  19. ....●●●....
  20. ..●●●●●●●..
  21. ..●●●○●●●..
  22. ..●●●●●●●..
  23. ....●●●....
  24. ....●●●....
  25. ...........
  26. ...........
  27. `)
  28.  
  29.  
  30. // center is the position of the center hole if 
  31. // there is a single one; otherwise it is -1.
  32. var center int
  33.  
  34. func init() {
  35. 	n := 0
  36. 	for pos, field := range board {
  37. 		if field == '○' {
  38. 			center = pos
  39. 			n++
  40. 		}
  41. 	}
  42. 	if n != 1 {
  43. 		center = -1 // no single hole
  44. 	}
  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.  
  66. // unmove reverts a previously executed valid move.
  67. func unmove(pos, dir int) {
  68. 	board[pos] = '●'
  69. 	board[pos+dir] = '●'
  70. 	board[pos+2*dir] = '○'
  71. }
  72.  
  73.  
  74. // solve tries to find a sequence of moves such that 
  75. // there is only one peg left at the end; if center is 
  76. // >= 0, that last peg must be in the center position.
  77. // If a solution is found, solve prints the board after
  78. // each move in a backward fashion (i.e., the last 
  79. // board position is printed first, all the way back to
  80. // the starting board position).
  81. func solve() bool {
  82. 	var last, n int
  83. 	for pos, field := range board {
  84. 		// try each board position
  85. 		if field == '●' {
  86. 			// found a peg
  87. 			for _, dir := range [...]int{-1, -N, +1, +N} {
  88. 				// try each direction
  89. 				if move(pos, dir) {
  90. 					// a valid move was found and executed,
  91. 					// see if this new board has a solution
  92. 					if solve() {
  93. 						unmove(pos, dir)
  94. 						println(string(board))
  95. 						return true
  96. 					}
  97. 					unmove(pos, dir)
  98. 				}
  99. 			}
  100. 			last = pos
  101. 			n++
  102. 		}
  103. 	}
  104. 	// tried each possible move
  105. 	if n == 1 && (center < 0 || last == center) {
  106. 		// there's only one peg left
  107. 		println(string(board))
  108. 		return true
  109. 	}
  110. 	// no solution found for this board
  111. 	return false
  112. }
  113.  
  114.  
  115. func main() {
  116. 	if !solve() {
  117. 		fmt.Println("no solution found")
  118. 	}
  119. 	fmt.Println(moves, "moves tried")
  120. }
  121.  
Success #stdin #stdout 0.03s 2408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
...........
...........
....○○○....
....○○○....
..○○○○○○○..
..○○○●○○○..
..○○○○○○○..
....○○○....
....○○○....
...........
...........

...........
...........
....○○○....
....○○○....
..○○○○○○○..
..○○○○○○○..
..○○○●○○○..
....○●○....
....○○○....
...........
...........

...........
...........
....○○○....
....○○○....
..○○○○○○○..
..○○○○○○○..
..○○○○●●○..
....○●○....
....○○○....
...........
...........

...........
...........
....○○○....
....○○○....
..○○○○●○○..
..○○○○●○○..
..○○○○○●○..
....○●○....
....○○○....
...........
...........

...........
...........
....○○○....
....○○○....
..○○○○●○○..
..○○○○●○○..
..○○○●●○○..
....○●○....
....○○○....
...........
...........

...........
...........
....○○○....
....○○○....
..○○○○●○○..
..○○○○●○○..
..○●●○●○○..
....○●○....
....○○○....
...........
...........

...........
...........
....○○○....
....○○○....
..○○○○●○○..
..○○○○●○○..
..○●○○●○○..
....●●○....
....●○○....
...........
...........

...........
...........
....○○○....
....○○○....
..○○○○●○○..
..○○○○●○○..
..○●○○●○○..
....●●○....
....○●●....
...........
...........

...........
...........
....○○○....
....○○○....
..○○○○●○○..
..○○●○●○○..
..○●●○●○○..
....○●○....
....○●●....
...........
...........

...........
...........
....○○○....
....○○○....
..○○○○●○○..
..○○●○●○○..
..○●○○●○○..
....●●○....
....●●●....
...........
...........

...........
...........
....○○○....
....○○○....
..○○○○●○○..
..○○●○●○○..
..○●○○○●●..
....●●○....
....●●●....
...........
...........

...........
...........
....○○○....
....○○○....
..○○○○●○○..
..○○●○○○○..
..○●○○●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....○○○....
....○○○....
..○○○○●○○..
..○○●○○○○..
..○○●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....○○○....
....○○○....
..○○○○●○○..
..○○●○○○○..
..●●○●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....○○○....
....●○○....
..○○●○●○○..
..○○○○○○○..
..●●○●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....○○○....
....●○○....
..○○○○●○○..
..○○●○○○○..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....○○●....
....●○●....
..○○○○○○○..
..○○●○○○○..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....○○●....
....●○○....
..○○○○●○○..
..○○●○●○○..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....○○●....
....●○○....
..○○○○●○○..
..○○●○○●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....○○●....
....●○○....
..○○○○●○○..
..○○○●●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....○○●....
....○○○....
..○○●○●○○..
..○○●●●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....○○●....
....○○○....
..○○●○●○○..
..●●○●●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....●○●....
....●○○....
..○○○○●○○..
..●●○●●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....●○●....
....○○○....
..○○●○●○○..
..●●●●●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....●○●....
....○○○....
..○○●○○●●..
..●●●●●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....●○○....
....○○●....
..○○●○●●●..
..●●●●●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....●○○....
....○○●....
..●●○○●●●..
..●●●●●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....●○○....
....○○●....
..●○●●●●●..
..●●●●●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....○●●....
....○○●....
..●○●●●●●..
..●●●●●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....●●●....
....●○●....
..●○○●●●●..
..●●●●●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....●●●....
....●○●....
..●●●○●●●..
..●●●●●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

...........
...........
....●●●....
....●●●....
..●●●●●●●..
..●●●○●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........

391865 moves tried
https://ideone.com/2QLmc
language:
Go (go 1.12.1)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!