Solve triangle solitaire puzzle: Difference between revisions
m
→{{header|Phix}}: use pygments, simplified by using reinstate, which also fixes a couple of p2js violations
(Added Sidef) |
m (→{{header|Phix}}: use pygments, simplified by using reinstate, which also fixes a couple of p2js violations) |
||
| (61 intermediate revisions by 17 users not shown) | |||
Line 23:
Reference picture: http://www.joenord.com/puzzles/peggame/
<br/>Updated link (June 2021):
https://www.joenord.com/triangle-peg-board-game-solutions-to-amaze-your-friends/
Line 30 ⟶ 32:
Start with empty peg in '''X''' and solve with one peg in position '''Y'''.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F DrawBoard(board)
V peg = [‘’] * 16
L(n) 1.<16
peg[n] = ‘.’
I n C board
peg[n] = hex(n)
print(‘ #.’.format(peg[1]))
print(‘ #. #.’.format(peg[2], peg[3]))
print(‘ #. #. #.’.format(peg[4], peg[5], peg[6]))
print(‘ #. #. #. #.’.format(peg[7], peg[8], peg[9], peg[10]))
print(‘ #. #. #. #. #.’.format(peg[11], peg[12], peg[13], peg[14], peg[15]))
F RemovePeg(&board, n)
board.remove(n)
F AddPeg(&board, n)
board.append(n)
F IsPeg(board, n)
R n C board
V JumpMoves = [1 = [(2, 4), (3, 6)],
2 = [(4, 7), (5, 9)],
3 = [(5, 8), (6, 10)],
4 = [(2, 1), (5, 6), (7, 11), (8, 13)],
5 = [(8, 12), (9, 14)],
6 = [(3, 1), (5, 4), (9, 13), (10, 15)],
7 = [(4, 2), (8, 9)],
8 = [(5, 3), (9, 10)],
9 = [(5, 2), (8, 7)],
10 = [(9, 8)],
11 = [(12, 13)],
12 = [(8, 5), (13, 14)],
13 = [(8, 4), (9, 6), (12, 11), (14, 15)],
14 = [(9, 5), (13, 12)],
15 = [(10, 6), (14, 13)]]
[(Int, Int, Int)] Solution
F Solve(=board)
I board.len == 1
R board
L(peg) 1.<16
I IsPeg(board, peg)
V movelist = JumpMoves[peg]
L(over, land) movelist
I IsPeg(board, over) & !IsPeg(board, land)
V saveboard = copy(board)
RemovePeg(&board, peg)
RemovePeg(&board, over)
AddPeg(&board, land)
Solution.append((peg, over, land))
board = Solve(board)
I board.len == 1
R board
board = copy(saveboard)
Solution.pop()
R board
F InitSolve(empty)
V board = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
RemovePeg(&board, empty)
Solve(board)
V empty_start = 1
InitSolve(empty_start)
V board = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
RemovePeg(&board, empty_start)
L(peg, over, land) Solution
RemovePeg(&board, peg)
RemovePeg(&board, over)
AddPeg(&board, land)
DrawBoard(board)
print("Peg #. jumped over #. to land on #.\n".format(hex(peg), hex(over), hex(land)))</syntaxhighlight>
{{out}}
<pre>
1
. 3
. 5 6
7 8 9 A
B C D E F
Peg 4 jumped over 2 to land on 1
1
. 3
4 . .
7 8 9 A
B C D E F
Peg 6 jumped over 5 to land on 4
.
. .
4 . 6
7 8 9 A
B C D E F
Peg 1 jumped over 3 to land on 6
.
2 .
. . 6
. 8 9 A
B C D E F
Peg 7 jumped over 4 to land on 2
.
2 .
. 5 6
. . 9 A
B . D E F
Peg C jumped over 8 to land on 5
.
2 .
. 5 6
. . 9 A
B C . . F
Peg E jumped over D to land on C
.
2 .
. 5 .
. . . A
B C D . F
Peg 6 jumped over 9 to land on D
.
. .
. . .
. . 9 A
B C D . F
Peg 2 jumped over 5 to land on 9
.
. .
. . .
. . 9 A
B . . E F
Peg C jumped over D to land on E
.
. .
. . 6
. . 9 .
B . . E .
Peg F jumped over A to land on 6
.
. .
. . .
. . . .
B . D E .
Peg 6 jumped over 9 to land on D
.
. .
. . .
. . . .
B C . . .
Peg E jumped over D to land on C
.
. .
. . .
. . . .
. . D . .
Peg B jumped over C to land on D
</pre>
=={{header|ALGOL 68}}==
{{Trans|Go|which is a translation of Kotlin}}
Also shows the number of backtracks required for each starting position and simplifies testing for a solution.
<syntaxhighlight lang="algol68">
BEGIN # solve a triangle solitaire puzzle - translation of the Go sample #
MODE SOLUTION = STRUCT( INT peg, over, land );
MODE MOVE = STRUCT( INT from, to );
INT number of pegs = 15;
INT empty start := 1;
[ number of pegs ]BOOL board;
[][]MOVE jump moves
= ( []MOVE( ( 2, 4 ), ( 3, 6 ) )
, []MOVE( ( 4, 7 ), ( 5, 9 ) )
, []MOVE( ( 5, 8 ), ( 6, 10 ) )
, []MOVE( ( 2, 1 ), ( 5, 6 ), ( 7, 11 ), ( 8, 13 ) )
, []MOVE( ( 8, 12 ), ( 9, 14 ) )
, []MOVE( ( 3, 1 ), ( 5, 4 ), ( 9, 13 ), ( 10, 15 ) )
, []MOVE( ( 4, 2 ), ( 8, 9 ) )
, []MOVE( ( 5, 3 ), ( 9, 10 ) )
, []MOVE( ( 5, 2 ), ( 8, 7 ) )
, []MOVE( MOVE( 9, 8 ) )
, []MOVE( MOVE( 12, 13 ) )
, []MOVE( ( 8, 5 ), ( 13, 14 ) )
, []MOVE( ( 8, 4 ), ( 9, 6 ), ( 12, 11 ), ( 14, 15 ) )
, []MOVE( ( 9, 5 ), ( 13, 12 ) )
, []MOVE( ( 10, 6 ), ( 14, 13 ) )
);
[ number of pegs ]SOLUTION solutions;
INT s size := 0;
INT backtracks := 0;
PROC init board = VOID:
BEGIN
FOR i TO number of pegs DO
board[ i ] := TRUE
OD;
board[ empty start ] := FALSE
END; # init board #
PROC init solution = VOID:
BEGIN
s size := 0;
backtracks := 0
END; # init solutions #
PROC split solution = ( REF INT peg, over, land, SOLUTION sol )VOID:
BEGIN
peg := peg OF sol; over := over OF sol; land := land OF sol
END; # split solution #
PROC split move = ( REF INT from, to, MOVE mv )VOID:
BEGIN
from := from OF mv; to := to OF mv
END; # split move #
OP TOHEX = ( INT v )CHAR:
IF v < 10 THEN REPR ( ABS "0" + v ) ELSE REPR ( ABS "A" + ( v - 10 ) ) FI;
PROC draw board = VOID:
BEGIN
PROC println = ( STRING s )VOID: print( ( s, newline ) );
[ number of pegs ]CHAR pegs;
FOR i TO number of pegs DO
pegs[ i ] := IF board[ i ] THEN TOHEX i ELSE "." FI
OD;
println( " " + pegs[ 1 ] );
println( " " + pegs[ 2 ] + " " + pegs[ 3 ] );
println( " " + pegs[ 4 ] + " " + pegs[ 5 ] + " " + pegs[ 6 ] );
println( " " + pegs[ 7 ] + " " + pegs[ 8 ] + " " + pegs[ 9 ] + " " + pegs[ 10 ] );
println( " " + pegs[ 11 ] + " " + pegs[ 12 ] + " " + pegs[ 13 ] + " " + pegs[ 14 ] + " " + pegs[ 15 ] )
END; # draw board #
PROC solved = BOOL: s size = number of pegs - 2;
PROC solve = VOID:
IF NOT solved THEN
BOOL have solution := FALSE;
FOR peg TO number of pegs WHILE NOT have solution DO
IF board[ peg ] THEN
[]MOVE jm = jump moves[ peg ];
FOR mv pos FROM LWB jm TO UPB jm WHILE NOT have solution DO
INT over, land;
split move( over, land, jm[ mv pos ] );
IF board[ over ] AND NOT board[ land ] THEN
[]BOOL save board = board;
board[ peg ] := FALSE;
board[ over ] := FALSE;
board[ land ] := TRUE;
solutions[ s size +:= 1 ] := ( peg, over, land );
solve;
IF NOT ( have solution := solved ) THEN
# not solved - backtrack #
backtracks +:= 1;
board := save board;
s size -:= 1
FI
FI
OD
FI
OD
FI; # solve #
FOR start peg TO number of pegs DO
empty start := start peg;
init board;
init solution;
solve;
IF empty start = 1 THEN
init board;
draw board
FI;
print( ( "Starting with peg ", TOHEX empty start, " removed" ) );
IF empty start = 1 THEN
print( ( newline, newline ) );
FOR pos TO s size DO
SOLUTION solution = solutions[ pos ];
INT peg, over, land;
split solution( peg, over, land, solution );
board[ peg ] := FALSE;
board[ over ] := FALSE;
board[ land ] := TRUE;
draw board;
print( ( "Peg ", TOHEX peg, " jumped over ", TOHEX over, " to land on ", TOHEX land ) );
print( ( newline, newline ) )
OD
FI;
print( ( whole( backtracks, -8 ), " backtracks were required", newline ) )
OD
END
</syntaxhighlight>
{{out}}
<pre style="height:80ex;overflow:scroll">
.
2 3
4 5 6
7 8 9 A
B C D E F
Starting with peg 1 removed
1
. 3
. 5 6
7 8 9 A
B C D E F
Peg 4 jumped over 2 to land on 1
1
. 3
4 . .
7 8 9 A
B C D E F
Peg 6 jumped over 5 to land on 4
.
. .
4 . 6
7 8 9 A
B C D E F
Peg 1 jumped over 3 to land on 6
.
2 .
. . 6
. 8 9 A
B C D E F
Peg 7 jumped over 4 to land on 2
.
2 .
. 5 6
. . 9 A
B . D E F
Peg C jumped over 8 to land on 5
.
2 .
. 5 6
. . 9 A
B C . . F
Peg E jumped over D to land on C
.
2 .
. 5 .
. . . A
B C D . F
Peg 6 jumped over 9 to land on D
.
. .
. . .
. . 9 A
B C D . F
Peg 2 jumped over 5 to land on 9
.
. .
. . .
. . 9 A
B . . E F
Peg C jumped over D to land on E
.
. .
. . 6
. . 9 .
B . . E .
Peg F jumped over A to land on 6
.
. .
. . .
. . . .
B . D E .
Peg 6 jumped over 9 to land on D
.
. .
. . .
. . . .
B C . . .
Peg E jumped over D to land on C
.
. .
. . .
. . . .
. . D . .
Peg B jumped over C to land on D
814 backtracks were required
Starting with peg 2 removed 22221 backtracks were required
Starting with peg 3 removed 12274 backtracks were required
Starting with peg 4 removed 15782 backtracks were required
Starting with peg 5 removed 1948 backtracks were required
Starting with peg 6 removed 71565 backtracks were required
Starting with peg 7 removed 814 backtracks were required
Starting with peg 8 removed 98940 backtracks were required
Starting with peg 9 removed 5747 backtracks were required
Starting with peg A removed 814 backtracks were required
Starting with peg B removed 22221 backtracks were required
Starting with peg C removed 19097 backtracks were required
Starting with peg D removed 814 backtracks were required
Starting with peg E removed 18563 backtracks were required
Starting with peg F removed 10240 backtracks were required
</pre>
=={{header|D}}==
{{trans|Ruby}}
<
immutable N = [0,1,1,1,1,1,1,1,1,1,1,1,1,1,1];
Line 85 ⟶ 518:
}
writeln(l.empty ? "No solution found." : l);
}</
{{out}}
<pre>
Line 185 ⟶ 618:
0 0 1 0 0
Solved</pre>
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
brd$[] = strchars "
┏━━━━━━━━━┓
┃ · ┃
┃ ● ● ┃
┃ ● ● ● ┃
┃ ● ● ● ● ┃
┃● ● ● ● ●┃
┗━━━━━━━━━┛"
proc solve . solution$ .
solution$ = ""
for pos = 1 to len brd$[]
if brd$[pos] = "●"
npegs += 1
for dir in [ -13 -11 2 13 11 -2 ]
if brd$[pos + dir] = "●" and brd$[pos + 2 * dir] = "·"
brd$[pos] = "·"
brd$[pos + dir] = "·"
brd$[pos + 2 * dir] = "●"
solve solution$
brd$[pos] = "●"
brd$[pos + dir] = "●"
brd$[pos + 2 * dir] = "·"
if solution$ <> ""
solution$ = strjoin brd$[] & solution$
return
.
.
.
.
.
if npegs = 1
solution$ = strjoin brd$[]
.
.
solve solution$
print solution$
</syntaxhighlight>
=={{header|Elixir}}==
Inspired by Ruby
<
def task(i \\ 0, n \\ 5) do
fmt = Enum.map_join(1..n, fn i ->
Line 230 ⟶ 703:
end
IQ_Puzzle.task</
{{out}}
Line 331 ⟶ 804:
0 0 1 0 0
Solved
</pre>
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
// Solve triangle solitaire puzzle. Nigel Galloway: May 28th., 2024
type hole= O|X
type cand={board:hole[];p2go:int;hist:list<hole[]*int*int*int>}
let G = [0,1,3;0,2,5;1,3,6;1,4,8;2,4,7;2,5,9;3,4,5;3,6,10;3,7,12;4,7,11;4,8,13;5,8,12;5,9,14;6,7,8;7,8,9;10,11,12;11,12,13;12,13,14;3,1,0;5,2,0;6,3,1;8,4,1;7,4,2;9,5,2;5,4,3;10,6,3;12,7,3;11,7,4;13,8,4;12,8,5;14,9,5;8,7,6;9,8,7;12,11,10;13,12,11;14,13,12]
let move n (from,over,To)=let g=Array.copy n.board in g[from]<-O; g[over]<-O; g[To]<-X; {board=g;p2go=n.p2go-1;hist=(n.board,from,over,To)::n.hist}
let moves (p:hole[])=G|>List.fold(fun n g->match g with from,over,To when p[over]=X&&p[from]=X&&p[To]=O->(from,over,To)::n |To,over,from when p[over]=X&&p[from]=X&&p[To]=O->(from,over,To)::n |_->n)[]
let rec fs=function []->None |n::g when n.p2go=0->Some((n.board,-1,-1,-1)::n.hist) |n::g->fs(((moves n.board)|>List.map(fun g->move n g))@g)
let solve n=fs [{board=n; p2go=13; hist=[]}]
let fN(g:hole[])=printfn " %A\n %A %A\n %A %A %A\n %A %A %A %A\n%A %A %A %A %A" g[0] g[1] g[2] g[3] g[4] g[5] g[6] g[7] g[8] g[9] g[10] g[11] g[12] g[13] g[14]
match solve [|O;X;X;X;X;X;X;X;X;X;X;X;X;X;X|] with Some n->n|>List.rev|>List.iter(fun(g,from,over,To)->fN g; if from> -1 then printfn "\nmove from %A over %A to %A\n" from over To) |_->printfn "No solution found"
</syntaxhighlight>
{{out}}
<pre>
O
X X
X X X
X X X X
X X X X X
move from 5 over 2 to 0
X
X O
X X O
X X X X
X X X X X
move from 14 over 9 to 5
X
X O
X X X
X X X O
X X X X O
move from 7 over 8 to 9
X
X O
X X X
X O O X
X X X X O
move from 9 over 5 to 2
X
X X
X X O
X O O O
X X X X O
move from 1 over 4 to 8
X
O X
X O O
X O X O
X X X X O
move from 13 over 8 to 4
X
O X
X X O
X O O O
X X X O O
move from 11 over 12 to 13
X
O X
X X O
X O O O
X O O X O
move from 2 over 4 to 7
X
O O
X O O
X X O O
X O O X O
move from 6 over 3 to 1
X
X O
O O O
O X O O
X O O X O
move from 0 over 1 to 3
O
O O
X O O
O X O O
X O O X O
move from 3 over 7 to 12
O
O O
O O O
O O O O
X O X X O
move from 13 over 12 to 11
O
O O
O O O
O O O O
X X O O O
move from 10 over 11 to 12
O
O O
O O O
O O O O
O O X O O
</pre>
=={{header|Go}}==
{{trans|Kotlin}}
<syntaxhighlight lang="go">package main
import "fmt"
type solution struct{ peg, over, land int }
type move struct{ from, to int }
var emptyStart = 1
var board [16]bool
var jumpMoves = [16][]move{
{},
{{2, 4}, {3, 6}},
{{4, 7}, {5, 9}},
{{5, 8}, {6, 10}},
{{2, 1}, {5, 6}, {7, 11}, {8, 13}},
{{8, 12}, {9, 14}},
{{3, 1}, {5, 4}, {9, 13}, {10, 15}},
{{4, 2}, {8, 9}},
{{5, 3}, {9, 10}},
{{5, 2}, {8, 7}},
{{9, 8}},
{{12, 13}},
{{8, 5}, {13, 14}},
{{8, 4}, {9, 6}, {12, 11}, {14, 15}},
{{9, 5}, {13, 12}},
{{10, 6}, {14, 13}},
}
var solutions []solution
func initBoard() {
for i := 1; i < 16; i++ {
board[i] = true
}
board[emptyStart] = false
}
func (sol solution) split() (int, int, int) {
return sol.peg, sol.over, sol.land
}
func (mv move) split() (int, int) {
return mv.from, mv.to
}
func drawBoard() {
var pegs [16]byte
for i := 1; i < 16; i++ {
if board[i] {
pegs[i] = fmt.Sprintf("%X", i)[0]
} else {
pegs[i] = '-'
}
}
fmt.Printf(" %c\n", pegs[1])
fmt.Printf(" %c %c\n", pegs[2], pegs[3])
fmt.Printf(" %c %c %c\n", pegs[4], pegs[5], pegs[6])
fmt.Printf(" %c %c %c %c\n", pegs[7], pegs[8], pegs[9], pegs[10])
fmt.Printf(" %c %c %c %c %c\n", pegs[11], pegs[12], pegs[13], pegs[14], pegs[15])
}
func solved() bool {
count := 0
for _, b := range board {
if b {
count++
}
}
return count == 1 // just one peg left
}
func solve() {
if solved() {
return
}
for peg := 1; peg < 16; peg++ {
if board[peg] {
for _, mv := range jumpMoves[peg] {
over, land := mv.split()
if board[over] && !board[land] {
saveBoard := board
board[peg] = false
board[over] = false
board[land] = true
solutions = append(solutions, solution{peg, over, land})
solve()
if solved() {
return // otherwise back-track
}
board = saveBoard
solutions = solutions[:len(solutions)-1]
}
}
}
}
}
func main() {
initBoard()
solve()
initBoard()
drawBoard()
fmt.Printf("Starting with peg %X removed\n\n", emptyStart)
for _, solution := range solutions {
peg, over, land := solution.split()
board[peg] = false
board[over] = false
board[land] = true
drawBoard()
fmt.Printf("Peg %X jumped over %X to land on %X\n\n", peg, over, land)
}
}</syntaxhighlight>
{{out}}
<pre>
Same as Kotlin entry
</pre>
=={{header|J}}==
<syntaxhighlight lang="j">
NB. This is a direct translation of the python program,
NB. except for the display which by move is horizontal.
Line 516 ⟶ 1,237:
NB. Solution NB. return Solution however Solution is global.
)
</syntaxhighlight>
Example linux session with program in file CrackerBarrel.ijs
<pre>
Line 549 ⟶ 1,270:
ubuntu$
</pre>
=={{header|Java}}==
Print the number of solutions for each start and end combination.
Print one possible solution.
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
public class IQPuzzle {
public static void main(String[] args) {
System.out.printf(" ");
for ( int start = 1 ; start < Puzzle.MAX_PEGS ; start++ ) {
System.out.printf(" %,6d", start);
}
System.out.printf("%n");
for ( int start = 1 ; start < Puzzle.MAX_PEGS ; start++ ) {
System.out.printf("%2d", start);
Map<Integer,Integer> solutions = solve(start);
for ( int end = 1 ; end < Puzzle.MAX_PEGS ; end++ ) {
System.out.printf(" %,6d", solutions.containsKey(end) ? solutions.get(end) : 0);
}
System.out.printf("%n");
}
int moveNum = 0;
System.out.printf("%nOne Solution:%n");
for ( Move m : oneSolution ) {
moveNum++;
System.out.printf("Move %d = %s%n", moveNum, m);
}
}
private static List<Move> oneSolution = null;
private static Map<Integer, Integer> solve(int emptyPeg) {
Puzzle puzzle = new Puzzle(emptyPeg);
Map<Integer,Integer> solutions = new HashMap<>();
Stack<Puzzle> stack = new Stack<Puzzle>();
stack.push(puzzle);
while ( ! stack.isEmpty() ) {
Puzzle p = stack.pop();
if ( p.solved() ) {
solutions.merge(p.getLastPeg(), 1, (v1,v2) -> v1 + v2);
if ( oneSolution == null ) {
oneSolution = p.moves;
}
continue;
}
for ( Move move : p.getValidMoves() ) {
Puzzle pMove = p.move(move);
stack.add(pMove);
}
}
//System.out.println("Puzzles tested = " + puzzlesTested);
return solutions;
}
private static class Puzzle {
public static int MAX_PEGS = 16;
private boolean[] pegs = new boolean[MAX_PEGS]; // true : peg in hole. false : hole is empty.
private List<Move> moves;
public Puzzle(int emptyPeg) {
for ( int i = 1 ; i < MAX_PEGS ; i++ ) {
pegs[i] = true;
}
pegs[emptyPeg] = false;
moves = new ArrayList<>();
}
public Puzzle() {
for ( int i = 1 ; i < MAX_PEGS ; i++ ) {
pegs[i] = true;
}
moves = new ArrayList<>();
}
private static Map<Integer,List<Move>> validMoves = new HashMap<>();
static {
validMoves.put(1, Arrays.asList(new Move(1, 2, 4), new Move(1, 3, 6)));
validMoves.put(2, Arrays.asList(new Move(2, 4, 7), new Move(2, 5, 9)));
validMoves.put(3, Arrays.asList(new Move(3, 5, 8), new Move(3, 6, 10)));
validMoves.put(4, Arrays.asList(new Move(4, 2, 1), new Move(4, 5, 6), new Move(4, 8, 13), new Move(4, 7, 11)));
validMoves.put(5, Arrays.asList(new Move(5, 8, 12), new Move(5, 9, 14)));
validMoves.put(6, Arrays.asList(new Move(6, 3, 1), new Move(6, 5, 4), new Move(6, 9, 13), new Move(6, 10, 15)));
validMoves.put(7, Arrays.asList(new Move(7, 4, 2), new Move(7, 8, 9)));
validMoves.put(8, Arrays.asList(new Move(8, 5, 3), new Move(8, 9, 10)));
validMoves.put(9, Arrays.asList(new Move(9, 5, 2), new Move(9, 8, 7)));
validMoves.put(10, Arrays.asList(new Move(10, 6, 3), new Move(10, 9, 8)));
validMoves.put(11, Arrays.asList(new Move(11, 7, 4), new Move(11, 12, 13)));
validMoves.put(12, Arrays.asList(new Move(12, 8, 5), new Move(12, 13, 14)));
validMoves.put(13, Arrays.asList(new Move(13, 12, 11), new Move(13, 8, 4), new Move(13, 9, 6), new Move(13, 14, 15)));
validMoves.put(14, Arrays.asList(new Move(14, 13, 12), new Move(14, 9, 5)));
validMoves.put(15, Arrays.asList(new Move(15, 14, 13), new Move(15, 10, 6)));
}
public List<Move> getValidMoves() {
List<Move> moves = new ArrayList<Move>();
for ( int i = 1 ; i < MAX_PEGS ; i++ ) {
if ( pegs[i] ) {
for ( Move testMove : validMoves.get(i) ) {
if ( pegs[testMove.jump] && ! pegs[testMove.end] ) {
moves.add(testMove);
}
}
}
}
return moves;
}
public boolean solved() {
boolean foundFirstPeg = false;
for ( int i = 1 ; i < MAX_PEGS ; i++ ) {
if ( pegs[i] ) {
if ( foundFirstPeg ) {
return false;
}
foundFirstPeg = true;
}
}
return true;
}
public Puzzle move(Move move) {
Puzzle p = new Puzzle();
if ( ! pegs[move.start] || ! pegs[move.jump] || pegs[move.end] ) {
throw new RuntimeException("Invalid move.");
}
for ( int i = 1 ; i < MAX_PEGS ; i++ ) {
p.pegs[i] = pegs[i];
}
p.pegs[move.start] = false;
p.pegs[move.jump] = false;
p.pegs[move.end] = true;
for ( Move m : moves ) {
p.moves.add(new Move(m.start, m.jump, m.end));
}
p.moves.add(new Move(move.start, move.jump, move.end));
return p;
}
public int getLastPeg() {
for ( int i = 1 ; i < MAX_PEGS ; i++ ) {
if ( pegs[i] ) {
return i;
}
}
throw new RuntimeException("ERROR: Illegal position.");
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for ( int i = 1 ; i < MAX_PEGS ; i++ ) {
sb.append(pegs[i] ? 1 : 0);
sb.append(",");
}
sb.setLength(sb.length()-1);
sb.append("]");
return sb.toString();
}
}
private static class Move {
int start;
int jump;
int end;
public Move(int s, int j, int e) {
start = s; jump = j; end = e;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{");
sb.append("s=" + start);
sb.append(", j=" + jump);
sb.append(", e=" + end);
sb.append("}");
return sb.toString();
}
}
}
</syntaxhighlight>
{{out}}
<pre>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 6,816 0 0 0 0 0 3,408 0 0 3,408 0 0 16,128 0 0
2 0 720 0 0 0 8,064 0 0 0 0 3,408 0 0 2,688 0
3 0 0 720 8,064 0 0 0 0 0 0 0 2,688 0 0 3,408
4 0 0 8,064 51,452 0 0 0 0 1,550 0 0 8,064 0 0 16,128
5 0 0 0 0 0 0 0 0 0 0 0 0 1,550 0 0
6 0 8,064 0 0 0 51,452 0 1,550 0 0 16,128 0 0 8,064 0
7 3,408 0 0 0 0 0 720 0 0 2,688 0 0 8,064 0 0
8 0 0 0 0 0 1,550 0 0 0 0 0 0 0 0 0
9 0 0 0 1,550 0 0 0 0 0 0 0 0 0 0 0
10 3,408 0 0 0 0 0 2,688 0 0 720 0 0 8,064 0 0
11 0 3,408 0 0 0 16,128 0 0 0 0 6,816 0 0 3,408 0
12 0 0 2,688 8,064 0 0 0 0 0 0 0 720 0 0 3,408
13 16,128 0 0 0 1,550 0 8,064 0 0 8,064 0 0 51,452 0 0
14 0 2,688 0 0 0 8,064 0 0 0 0 3,408 0 0 720 0
15 0 0 3,408 16,128 0 0 0 0 0 0 0 3,408 0 0 6,816
One Solution:
Move 1 = {s=6, j=3, e=1}
Move 2 = {s=15, j=10, e=6}
Move 3 = {s=8, j=9, e=10}
Move 4 = {s=10, j=6, e=3}
Move 5 = {s=2, j=5, e=9}
Move 6 = {s=14, j=9, e=5}
Move 7 = {s=12, j=13, e=14}
Move 8 = {s=7, j=4, e=2}
Move 9 = {s=3, j=5, e=8}
Move 10 = {s=1, j=2, e=4}
Move 11 = {s=4, j=8, e=13}
Move 12 = {s=14, j=13, e=12}
Move 13 = {s=11, j=12, e=13}
</pre>
=={{header|jq}}==
'''Works with jq, the C implementation of jq'''
'''Works with gojq, the Go implementation of jq'''
This entry presents functions for handling a triangular solitaire
board of arbitrary size.
More specifically, the triples defining the "legal moves" need not be
specified explicitly. These triples are instead computed by the
function `triples($depth)`, which emits the triples [$x, $over, $y]
corresponding to a peg at position $x being potentially able to jump
over a peg (at $over) to position $y, or vice versa, where $x < $over.
The `solve` function can be used to generate all solutions, as
illustrated below for the standard-size board.
The position of the initial "hole" can also be specified.
The holes in the board are numbered sequentially beginning from 1 at
the top of the triangle. Since jq arrays have an index origin of 0,
the array representing the board has a "dummy element" at index 0.
<syntaxhighlight lang="jq">
### General utilities
def array($n): . as $in | [range(0;$n)|$in];
def count(s): reduce s as $_ (0; .+1);
# Is . equal to the number of items in the (possibly empty) stream?
def countEq(s):
. == count(limit(. + 1; s));
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .;
### Solitaire
# Emit a stream of the relevant triples for a triangle of the given $height,
# specifically [$x, $over, $y] for $x < $y
def triples($height):
def triples: range(0; length - 2) as $i | .[$i: $i+3];
def stripes($n):
def next:
. as [$r1, $r2, $r3]
| ($r3[-1]+1) as $x
| [$r2, $r3, [range($x; $x + ($r3|length) + 1)]];
limit($n; recurse(next)) ;
def lefts:
. as [$r1, $r2, $r3]
| range(0; $r1|length) as $i
| [$r1[$i], $r2[$i], $r3[$i]];
def rights:
. as [$r1, $r2, $r3]
| range(0; $r1|length) as $i
| [$r1[$i], $r2[$i+1], $r3[$i+2]];
($height * ($height+1) / 2) as $max
| [[1], [2,3], [4,5,6]] | stripes($height)
| . as [$r1, $r2, $r3]
| ($r1|triples),
(if $r3[-1] <= $max then lefts, rights else empty end) ;
# For depth <= 10, use single characters to represent pegs, e.g. A for 10.
# Input: {depth, board}
def drawBoard:
def hex: [if . < 10 then 48 + . else 55 + . end] | implode;
def p: map(. + " ") | add;
# Generate the sequence [$i, $n] for the hole numbers of the left-hand side
def seq: recurse( .[1] += .[0] | .[0] += 1) | .[1] += 1;
.depth as $depth
| def tr: if $depth > 11 then lpad(3) elif . == "-" then . else hex end;
[range(0; 1 + ($depth * ($depth + 1) / 2)) as $i | if .board[$i] then $i else "-" end | tr]
| limit($depth; ([1,0] | seq) as [$n, $s] | ((1 + $depth - $n)*" ") + (.[$s:$s+$n] | p )) ;
# "All solutions"
# Input: as produced by init($depth; $emptyStart)
def solve:
def solved:
.board as $board
| 1 | countEq($board[] | select(.)) ;
[triples(.depth)] as $triples # cache the triples
| def solver:
# move/3 tries in both directions
# It is assumed that .board($over) is true
def move($peg; $over; $source):
if (.board[$peg] == false) and .board[$source]
then .board[$peg] = true
| .board[$source] = false
| .board[$over] = false
| .solutions += [ [$peg, $over, $source] ]
| solver
| if .emit == true then .
else # revert
.solutions |= .[:-1]
| .board[$peg] = false
| .board[$source] = true
| .board[$over] = true
end
end ;
if solved then .emit = true
else
foreach $triples[] as [$x, $over, $y] (.;
if .board[$over]
then move($x; $over; $y),
move($y; $over; $x)
else .
end )
| select(.emit)
end;
solver;
# .board[0] is a dummy position
def init($depth; $emptyStart):
{ $depth,
board: (true | array(1 + $depth * (1+$depth) / 2))
}
| .board[0] = false
| .board[$emptyStart] = false;
# Display the sequence of moves to a solution
def display($depth):
init($depth; 1)
| . as $init
| drawBoard,
" Original setup\n",
(first(solve) as $solve
| $init
| foreach ($solve.solutions[]) as [$peg, $over, $source] (.;
.board[$peg] = true
| .board[$over] = false
| .board[$source] = false;
drawBoard,
"Peg \($source) jumped over peg \($over) to land on \($peg)\n" ) ) ;
display(6),
"\nTotal number of solutions for a board of height 5 is \(init(5; 1) | count(solve))"
</syntaxhighlight>
{{output}}
<pre style="height:20lh;overflow:auto>
-
2 3
4 5 6
7 8 9 A
B C D E F
G H I J K L
Original setup
1
- 3
- 5 6
7 8 9 A
B C D E F
G H I J K L
Peg 4 jumped over peg 2 to land on 1
1
2 3
- - 6
7 8 - A
B C D E F
G H I J K L
Peg 9 jumped over peg 5 to land on 2
-
- 3
4 - 6
7 8 - A
B C D E F
G H I J K L
Peg 1 jumped over peg 2 to land on 4
1
- -
4 - -
7 8 - A
B C D E F
G H I J K L
Peg 6 jumped over peg 3 to land on 1
1
2 -
- - -
- 8 - A
B C D E F
G H I J K L
Peg 7 jumped over peg 4 to land on 2
-
- -
4 - -
- 8 - A
B C D E F
G H I J K L
Peg 1 jumped over peg 2 to land on 4
-
- -
4 5 -
- - - A
B - D E F
G H I J K L
Peg 12 jumped over peg 8 to land on 5
-
- -
- - 6
- - - A
B - D E F
G H I J K L
Peg 4 jumped over peg 5 to land on 6
-
- -
- - 6
7 - - A
- - D E F
- H I J K L
Peg 16 jumped over peg 11 to land on 7
-
- -
- - 6
7 - 9 A
- - - E F
- H - J K L
Peg 18 jumped over peg 13 to land on 9
-
- -
- - -
7 - - A
- - D E F
- H - J K L
Peg 6 jumped over peg 9 to land on 13
-
- -
- - 6
7 - - -
- - D E -
- H - J K L
Peg 15 jumped over peg 10 to land on 6
-
- -
- - 6
7 - - -
- - D E -
- H I - - L
Peg 20 jumped over peg 19 to land on 18
-
- -
- - 6
7 - - -
- - D E -
- - - J - L
Peg 17 jumped over peg 18 to land on 19
-
- -
- - 6
7 8 - -
- - - E -
- - - - - L
Peg 19 jumped over peg 13 to land on 8
-
- -
- - 6
- - 9 -
- - - E -
- - - - - L
Peg 7 jumped over peg 8 to land on 9
-
- -
- - -
- - - -
- - D E -
- - - - - L
Peg 6 jumped over peg 9 to land on 13
-
- -
- - -
- - - -
- - - - F
- - - - - L
Peg 13 jumped over peg 14 to land on 15
-
- -
- - -
- - - A
- - - - -
- - - - - -
Peg 21 jumped over peg 15 to land on 10
Total number of solutions for a board of depth 5: 13987
</pre>
=={{header|Julia}}==
{{trans|Raku}}
<syntaxhighlight lang="julia">moves = [[1, 2, 4], [1, 3, 6], [2, 4, 7], [2, 5, 9], [3, 5, 8], [3, 6, 10], [4, 5, 6],
[4, 7, 11], [4, 8, 13], [5, 8, 12], [5, 9, 14], [6, 9, 13], [6, 10, 15],
[7, 8, 9], [8, 9, 10], [11, 12, 13], [12, 13, 14], [13, 14, 15]]
triangletext(v) = join(map(i -> " "^([6,4,3,1,0][i]) * join(map(x -> rpad(x, 3),
v[div(i*i-i+2,2):div(i*(i+1),2)]), ""), 1:5), "\n")
const solutiontext = ["Starting board:\n" * triangletext([0; ones(Int, 14)]) * "\n"]
function solve(mv, turns=1, bd=[0; ones(Int, 14)])
if turns + 1 == length(bd)
return true
elseif bd[mv[2]] == 0 || (bd[mv[1]] == 0 && bd[mv[3]] == 0) || (bd[mv[3]] == 1 && bd[mv[1]] == 1)
return false
else
movetext = "\nmove " * (bd[mv[1]] == 0 ? "$(mv[3]) to $(mv[1])" : "$(mv[1]) to $(mv[3])")
newboard = deepcopy(bd)
map(i -> newboard[i] = 1 - newboard[i], mv)
for move in moves
if solve(move, turns + 1, newboard)
push!(solutiontext, (movetext * "\n" * triangletext(newboard) * "\n"))
return true
end
end
end
false
end
for (i, move) in enumerate(moves)
if solve(move)
println(join([solutiontext[1]; reverse(solutiontext[2:end])], ""))
break
elseif i == length(moves)
println("No solution found.")
end
end
</syntaxhighlight>{{out}}
<pre style="height:20lh;overflow:auto>
Starting board:
0
1 1
1 1 1
1 1 1 1
1 1 1 1 1
move 4 to 1
1
0 1
0 1 1
1 1 1 1
1 1 1 1 1
move 9 to 2
1
1 1
0 0 1
1 1 0 1
1 1 1 1 1
move 11 to 4
1
1 1
1 0 1
0 1 0 1
0 1 1 1 1
move 2 to 7
1
0 1
0 0 1
1 1 0 1
0 1 1 1 1
move 12 to 5
1
0 1
0 1 1
1 0 0 1
0 0 1 1 1
move 3 to 8
1
0 0
0 0 1
1 1 0 1
0 0 1 1 1
move 10 to 3
1
0 1
0 0 0
1 1 0 0
0 0 1 1 1
move 1 to 6
0
0 0
0 0 1
1 1 0 0
0 0 1 1 1
move 7 to 9
0
0 0
0 0 1
0 0 1 0
0 0 1 1 1
move 14 to 12
0
0 0
0 0 1
0 0 1 0
0 1 0 0 1
move 6 to 13
0
0 0
0 0 0
0 0 0 0
0 1 1 0 1
move 12 to 14
0
0 0
0 0 0
0 0 0 0
0 0 0 1 1
move 15 to 13
0
0 0
0 0 0
0 0 0 0
0 0 1 0 0
</pre>
=={{header|Kotlin}}==
{{trans|Python}}
<syntaxhighlight lang="scala">// version 1.1.3
data class Solution(val peg: Int, val over: Int, val land: Int)
var board = BooleanArray(16) { if (it == 0) false else true }
val jumpMoves = listOf(
listOf(),
listOf( 2 to 4, 3 to 6),
listOf( 4 to 7, 5 to 9),
listOf( 5 to 8, 6 to 10),
listOf( 2 to 1, 5 to 6, 7 to 11, 8 to 13),
listOf( 8 to 12, 9 to 14),
listOf( 3 to 1, 5 to 4, 9 to 13, 10 to 15),
listOf( 4 to 2, 8 to 9),
listOf( 5 to 3, 9 to 10),
listOf( 5 to 2, 8 to 7),
listOf( 9 to 8),
listOf(12 to 13),
listOf( 8 to 5, 13 to 14),
listOf( 8 to 4, 9 to 6, 12 to 11, 14 to 15),
listOf( 9 to 5, 13 to 12),
listOf(10 to 6, 14 to 13)
)
val solutions = mutableListOf<Solution>()
fun drawBoard() {
val pegs = CharArray(16) { '-' }
for (i in 1..15) if (board[i]) pegs[i] = "%X".format(i)[0]
println(" %c".format(pegs[1]))
println(" %c %c".format(pegs[2], pegs[3]))
println(" %c %c %c".format(pegs[4], pegs[5], pegs[6]))
println(" %c %c %c %c".format(pegs[7], pegs[8], pegs[9], pegs[10]))
println(" %c %c %c %c %c".format(pegs[11], pegs[12], pegs[13], pegs[14], pegs[15]))
}
val solved get() = board.count { it } == 1 // just one peg left
fun solve() {
if (solved) return
for (peg in 1..15) {
if (board[peg]) {
for ((over, land) in jumpMoves[peg]) {
if (board[over] && !board[land]) {
val saveBoard = board.copyOf()
board[peg] = false
board[over] = false
board[land] = true
solutions.add(Solution(peg, over, land))
solve()
if (solved) return // otherwise back-track
board = saveBoard
solutions.removeAt(solutions.lastIndex)
}
}
}
}
}
fun main(args: Array<String>) {
val emptyStart = 1
board[emptyStart] = false
solve()
board = BooleanArray(16) { if (it == 0) false else true }
board[emptyStart] = false
drawBoard()
println("Starting with peg %X removed\n".format(emptyStart))
for ((peg, over, land) in solutions) {
board[peg] = false
board[over] = false
board[land] = true
drawBoard()
println("Peg %X jumped over %X to land on %X\n".format(peg, over, land))
}
}</syntaxhighlight>
{{out}}
<pre>
-
2 3
4 5 6
7 8 9 A
B C D E F
Starting with peg 1 removed
1
- 3
- 5 6
7 8 9 A
B C D E F
Peg 4 jumped over 2 to land on 1
1
- 3
4 - -
7 8 9 A
B C D E F
Peg 6 jumped over 5 to land on 4
-
- -
4 - 6
7 8 9 A
B C D E F
Peg 1 jumped over 3 to land on 6
-
2 -
- - 6
- 8 9 A
B C D E F
Peg 7 jumped over 4 to land on 2
-
2 -
- 5 6
- - 9 A
B - D E F
Peg C jumped over 8 to land on 5
-
2 -
- 5 6
- - 9 A
B C - - F
Peg E jumped over D to land on C
-
2 -
- 5 -
- - - A
B C D - F
Peg 6 jumped over 9 to land on D
-
- -
- - -
- - 9 A
B C D - F
Peg 2 jumped over 5 to land on 9
-
- -
- - -
- - 9 A
B - - E F
Peg C jumped over D to land on E
-
- -
- - 6
- - 9 -
B - - E -
Peg F jumped over A to land on 6
-
- -
- - -
- - - -
B - D E -
Peg 6 jumped over 9 to land on D
-
- -
- - -
- - - -
B C - - -
Peg E jumped over D to land on C
-
- -
- - -
- - - -
- - D - -
Peg B jumped over C to land on D
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[Showstate]
Showstate[state_List, pos_] := Module[{p, e},
p = {#, FirstPosition[pos, #, Missing[], {2}]} & /@ state;
e = Complement[Flatten[pos], state];
e = {"_", FirstPosition[pos, #, Missing[], {2}]} & /@ e;
p = Join[p, e];
p = DeleteMissing[p, 1, \[Infinity]];
p[[All, 2]] //= Map[Reverse];
p[[All, 2, 2]] *= -1;
p[[All, 2, 1]] += p[[All, 2, 2]] 0.5;
Graphics[Text @@@ p, ImageSize -> 150]
]
pos = TakeList[Range[15], Range[5]];
moves1 = Catenate[If[Length[#] >= 3, Partition[#, 3, 1], {}] & /@ pos];
moves2 = Catenate[If[Length[#] >= 3, Partition[#, 3, 1], {}] & /@ Flatten[pos, {{2}, {1}}]];
moves3 = Catenate[If[Length[#] >= 3, Partition[#, 3, 1], {}] & /@ Flatten[Reverse /@ pos, {{2}, {1}}]];
moves = Join[moves1, moves2, moves3];
moves = Join[moves, Reverse /@ moves];
moves = <|Sort[{#1, #2} -> #3 & @@@ moves]|>;
ClearAll[SolvePuzzle]
SolvePuzzle[{state_List, history_List}, goal_] := Module[{k, newstate},
If[continue,
k = Keys[moves];
k = Select[k, ContainsAll[state, #] &];
k = Select[k, FreeQ[state, moves[#]] &];
k = {#, moves[#]} & /@ k;
Do[
newstate = state;
newstate = DeleteCases[newstate, Alternatives @@ move[[1]]];
AppendTo[newstate, move[[2]]];
If[newstate =!= goal,
SolvePuzzle[{newstate, Append[history, state]}, goal]
,
Print[FlipView[Showstate[#, pos] & /@ Append[Append[history, state], goal]]];
continue = False;
]
,
{move, k}
]
]
]
x = 1;
y = 13;
state = DeleteCases[Range[15], x];
continue = True;
SolvePuzzle[{state, {}}, {y}]</syntaxhighlight>
{{out}}
Outputs a graphical overview, by clicking one can go through the different states.
=={{header|Nim}}==
{{trans|Go}}
<syntaxhighlight lang="nim">import sequtils, strutils
type
Solution = tuple[peg, over, land: int]
Board = array[16, bool]
const
EmptyStart = 1
JumpMoves = [@[],
@[(2, 4), (3, 6)],
@[(4, 7), (5, 9)],
@[(5, 8), (6, 10)],
@[(2, 1), (5, 6), (7, 11), (8, 13)],
@[(8, 12), (9, 14)],
@[(3, 1), (5, 4), (9, 13), (10, 15)],
@[(4, 2), (8, 9)],
@[(5, 3), (9, 10)],
@[(5, 2), (8, 7)],
@[(9, 8)],
@[(12, 13)],
@[(8, 5), (13, 14)],
@[(8, 4), (9, 6), (12, 11), (14, 15)],
@[(9, 5), (13, 12)],
@[(10, 6), (14, 13)]]
func initBoard(): Board =
for i in 1..15: result[i] = true
result[EmptyStart] = false
proc draw(board: Board) =
var pegs: array[16, char]
for peg in pegs.mitems: peg = '-'
for i in 1..15:
if board[i]:
pegs[i] = i.toHex(1)[0]
echo " $#".format(pegs[1])
echo " $# $#".format(pegs[2], pegs[3])
echo " $# $# $#".format(pegs[4], pegs[5], pegs[6])
echo " $# $# $# $#".format(pegs[7], pegs[8], pegs[9], pegs[10])
echo " $# $# $# $# $#".format(pegs[11], pegs[12], pegs[13], pegs[14], pegs[15])
func solved(board: Board): bool = board.count(true) == 1
proc solve(board: var Board; solutions: var seq[Solution]) =
if board.solved: return
for peg in 1..15:
if board[peg]:
for (over, land) in JumpMoves[peg]:
if board[over] and not board[land]:
let saveBoard = board
board[peg] = false
board[over] = false
board[land] = true
solutions.add (peg, over, land)
board.solve(solutions)
if board.solved: return # otherwise back-track.
board = saveBoard
discard solutions.pop()
var board = initBoard()
var solutions: seq[Solution]
board.solve(solutions)
board = initBoard()
board.draw()
echo "Starting with peg $# removed\n".format(EmptyStart.toHex(1))
for (peg, over, land) in solutions:
board[peg] = false
board[over] = false
board[land] = true
board.draw()
echo "Peg $1 jumped over $2 to land on $3\n".format(peg.toHex(1), over.toHex(1), land.toHex(1))</syntaxhighlight>
{{out}}
<pre> -
2 3
4 5 6
7 8 9 A
B C D E F
Starting with peg 1 removed
1
- 3
- 5 6
7 8 9 A
B C D E F
Peg 4 jumped over 2 to land on 1
1
- 3
4 - -
7 8 9 A
B C D E F
Peg 6 jumped over 5 to land on 4
-
- -
4 - 6
7 8 9 A
B C D E F
Peg 1 jumped over 3 to land on 6
-
2 -
- - 6
- 8 9 A
B C D E F
Peg 7 jumped over 4 to land on 2
-
2 -
- 5 6
- - 9 A
B - D E F
Peg C jumped over 8 to land on 5
-
2 -
- 5 6
- - 9 A
B C - - F
Peg E jumped over D to land on C
-
2 -
- 5 -
- - - A
B C D - F
Peg 6 jumped over 9 to land on D
-
- -
- - -
- - 9 A
B C D - F
Peg 2 jumped over 5 to land on 9
-
- -
- - -
- - 9 A
B - - E F
Peg C jumped over D to land on E
-
- -
- - 6
- - 9 -
B - - E -
Peg F jumped over A to land on 6
-
- -
- - -
- - - -
B - D E -
Peg 6 jumped over 9 to land on D
-
- -
- - -
- - - -
B C - - -
Peg E jumped over D to land on C
-
- -
- - -
- - - -
- - D - -
Peg B jumped over C to land on D</pre>
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl">@start = qw<
0
1 1
1 1 1
1 1 1 1
1 1 1 1 1
>;
@moves = (
[ 0, 1, 3], [ 0, 2, 5], [ 1, 3, 6],
[ 1, 4, 8], [ 2, 4, 7], [ 2, 5, 9],
[ 3, 4, 5], [ 3, 6,10], [ 3, 7,12],
[ 4, 7,11], [ 4, 8,13], [ 5, 8,12],
[ 5, 9,14], [ 6, 7, 8], [ 7, 8, 9],
[10,11,12], [11,12,13], [12,13,14]
);
$format .= (" " x (5-$_)) . ("%d " x $_) . "\n" for 1..5;
sub solve {
my ($move, $turns, @board) = @_;
$turns = 1 unless $turns;
return "\nSolved" if $turns + 1 == @board;
return undef if $board[$$move[1]] == 0;
my $valid = do {
if ($board[$$move[0]] == 0) {
return undef if $board[$$move[2]] == 0;
"\nmove $$move[2] to $$move[0]\n";
} else {
return undef if $board[$$move[2]] == 1;
"\nmove $$move[0] to $$move[2]\n";
}
};
my $new_result;
my @new_layout = @board;
@new_layout[$_] = 1 - @new_layout[$_] for @$move;
for $this_move (@moves) {
$new_result = solve(\@$this_move, $turns + 1, @new_layout);
last if $new_result
}
$new_result ? "$valid\n" . sprintf($format, @new_layout) . $new_result : $new_result}
$result = "Starting with\n\n" . sprintf($format, @start), "\n";
for $this_move (@moves) {
$result .= solve(\@$this_move, 1, @start);
last if $result
}
print $result ? $result : "No solution found";
</syntaxhighlight>
{{out}}
<pre style="height:60ex;overflow:scroll;">Starting with
0
1 1
1 1 1
1 1 1 1
1 1 1 1 1
move 3 to 0
1
0 1
0 1 1
1 1 1 1
1 1 1 1 1
move 8 to 1
1
1 1
0 0 1
1 1 0 1
1 1 1 1 1
move 10 to 3
1
1 1
1 0 1
0 1 0 1
0 1 1 1 1
move 1 to 6
1
0 1
0 0 1
1 1 0 1
0 1 1 1 1
move 11 to 4
1
0 1
0 1 1
1 0 0 1
0 0 1 1 1
move 2 to 7
1
0 0
0 0 1
1 1 0 1
0 0 1 1 1
move 9 to 2
1
0 1
0 0 0
1 1 0 0
0 0 1 1 1
move 0 to 5
0
0 0
0 0 1
1 1 0 0
0 0 1 1 1
move 6 to 8
0
0 0
0 0 1
0 0 1 0
0 0 1 1 1
move 13 to 11
0
0 0
0 0 1
0 0 1 0
0 1 0 0 1
move 5 to 12
0
0 0
0 0 0
0 0 0 0
0 1 1 0 1
move 11 to 13
0
0 0
0 0 0
0 0 0 0
0 0 0 1 1
move 14 to 12
0
0 0
0 0 0
0 0 0 0
0 0 1 0 0
Solved</pre>
=={{header|Phix}}==
{{libheader|Phix/basics}}
Twee brute-force string-based solution. Backtracks a mere 366 times, whereas starting with the 5th peg missing backtracks 19388 times (all in 0s, obvs).
<!--(phixonline)-->
<syntaxhighlight lang="phix">
-- demo\rosetta\IQpuzzle.exw
with javascript_semantics
function solve(string board, integer left)
if left=1 then return "" end if
for i=1 to length(board) do
if board[i]='1' then
for mj in {-11,-9,2,11,9,-2} do
integer over = i+mj, tgt = i+2*mj
if tgt>=1 and tgt<=length(board)
and board[tgt]='0' and board[over]='1' then
board = reinstate(board,{i,over,tgt},"001")
string res = solve(board,left-1)
if length(res)!=4 then return board&res end if
board = reinstate(board,{i,over,tgt},"110")
end if
end for
end if
end for
return "oops"
end function
sequence start = """
----0----
---1-1---
--1-1-1--
-1-1-1-1-
1-1-1-1-1
"""
puts(1,substitute(join_by(split(start&solve(start,14),'\n'),5,7),"-"," "))
</syntaxhighlight>
{{out}}
<pre>
0 1 1 0 0 0 0
1 1 0 1 0 1 0 0 1 0 1 1 1 1
1 1 1 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 0 0 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
0 0 0 0 0 0 0
1 1 0 1 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 0 1 0 0
</pre>
Adapted to the English game (also in demo\rosetta\IQpuzzle.exw):
<syntaxhighlight lang="phix">
function solveE(string board, integer left)
if left=1 then
-- return "" -- (leaves it on the edge)
if board[3*15+8]='.' then return "" end if
return "oops"
end if
for i=1 to length(board) do
if board[i]='.' then
for mj in {-2,15,2,-15} do
integer over = i+mj, tgt = i+2*mj
if tgt>=1 and tgt<=length(board)
and board[tgt]='o' and board[over]='.' then
board = reinstate(board,{i,over,tgt},"oo.")
string res = solveE(board,left-1)
if length(res)!=4 then return board&res end if
board = reinstate(board,{i,over,tgt},"..o")
end if
end for
end if
end for
return "oops"
end function
string estart = """
-----.-.-.----
-----.-.-.----
-.-.-.-.-.-.-.
-.-.-.-o-.-.-.
-.-.-.-.-.-.-.
-----.-.-.----
-----.-.-.----
"""
puts(1,substitute(join_by(split(estart&solveE(estart,32),'\n'),7,8),"-"," "))
</syntaxhighlight>
{{out}}
<pre style="font-size: 12px">
. . . . . . . . . o . . . o o . o o . o o . o .
. . . . o . . o . o o . o o . o o . o o . o o o
. . . . . . . . . . o . . . . o o . . . . . o . . . . . . o . . . . . . . o o . . . o o . o . . . o o . o o . .
. . . o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. o . . o . o o . o o . o o . o o . o o . o o .
o o o . o o o o o o o o . o o . o o . o o . o .
o o . o . o o o o o o . o o o o . o . o o o o . o . o o o o o o . o o o o o o . o o o o o o . o o o o o o o o o
. . . . . . . . . o . . . . . . o . . . . o o . . . . . o o o . . . . o o . o o . . o o . o . o o o o . o o o o
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
o o o o o o o o o o o o o o o o o o o o o o o o
. o o . o o o o o o o o o o o o o o o o o o o o
o o o o . o o o o . o . o o o o o o . o o o o o o . o o o o o o . o o o o o o . o o o o o o . o o o o o o . o o
o o . o o o o o o o o o o o o o . o o o o o o . o o o o o o . o o o o o o . o . o o o o . o . o o o o . o . o o
. . . . . . . . . o . . . . . . o . . . . o o . . . . . o . o o . . . o . o o o . . o . o o . o o o . . o . o o
. . . . . . . . . . . . . . . . . o . . o o . o
. . . . . . . . . . . . . . . . . . . . . o . .
o o o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o o o o o
o o o o . o o o o o o . o o o o o o . o o o o o o . o o o o o o . o o o o o o o o o o o o o o o o o o o o o o o
o o o o . o o o o o o . o o o o o o . o o o o o o . o o o o o o . o o o o o o o o o o o o o o o o o o o . o o o
o . o o . o o o . o o . o o o . . o . o o o o o . . o o o o o o o . o o o o o . . o o o o . o o o o o o o o o o
. . o . . o o . o o . o o . o o . o o . o o o o
o . . . o o o o o o o o o o o o o o o o o o o o
</pre>
=={{header|Picat}}==
This version use the constraint solver (cp).
<syntaxhighlight lang="picat">import cp.
go =>
% Solve the puzzle
puzzle(1,N,NumMoves,X,Y),
println("Show the moves (Move from .. over .. to .. ):"),
foreach({From,Over,To} in X)
println([from=From,over=Over,to=To])
end,
nl,
println("Show the list at each move (0 is an empty hole):"),
foreach(Row in Y)
foreach(J in 1..15)
printf("%2d ", Row[J])
end,
nl
end,
nl,
println("And an verbose version:"),
foreach(Move in 1..NumMoves)
if Move > 1 then
printf("Move from %d over %d to %d\n",X[Move-1,1],X[Move-1,2],X[Move-1,3])
end,
nl,
print_board([Y[Move,J] : J in 1..N]),
nl
end,
nl,
% fail, % uncomment to see all solutions
nl.
puzzle(Empty,N,NumMoves,X,Y) =>
N = 15,
% Peg 1 can move over 2 and end at 4, etc
% (for table_in/2)
moves(Moves),
ValidMoves = [],
foreach(From in 1..N)
foreach([Over,To] in Moves[From])
ValidMoves := ValidMoves ++ [{From,Over,To}]
end
end,
NumMoves = N-1,
% which move to make
X = new_array(NumMoves-1,3),
X :: 1..N,
% The board at move Move
Y = new_array(NumMoves,N),
Y :: 0..N,
% Initialize for row
Y[1,Empty] #= 0,
foreach(J in 1..N)
if J != Empty then
Y[1,J] #= J
end
end,
% make the moves
foreach(Move in 2..NumMoves)
sum([Y[Move,J] #=0 : J in 1..N]) #= Move,
table_in({From,Over,To}, ValidMoves),
% Get this move and update the rows
element(To,Y[Move-1],0),
element(From,Y[Move-1],FromVal), FromVal #!= 0,
element(Over,Y[Move-1],OverVal), OverVal #!= 0,
element(From,Y[Move],0),
element(To,Y[Move],To),
element(Over,Y[Move],0),
foreach(J in 1..N)
(J #!= From #/\ J #!= Over #/\ J #!= To) #=>
Y[Move,J] #= Y[Move-1,J]
end,
X[Move-1,1] #= From,
X[Move-1,2] #= Over,
X[Move-1,3] #= To
end,
Vars = Y.vars() ++ X.vars(),
solve($[split],Vars).
%
% The valid moves:
% Peg 1 can move over 2 and end at 4, etc.
%
moves(Moves) =>
Moves = [
[[2,4],[3,6]], % 1
[[4,7],[5,9]], % 2
[[5,8],[6,10]], % 3
[[2,1],[5,6],[7,11],[8,13]], % 4
[[8,12],[9,14]], % 5
[[3,1],[5,4],[9,13],[10,15]], % 6
[[4,2],[8,9]], % 7
[[5,3],[9,10]], % 8
[[5,2],[8,7]], % 9
[[6,3],[9,8]], % 10
[[7,4],[12,13]], % 11
[[8,5],[13,14]], % 12
[[8,4],[9,6],[12,11],[14,15]], % 13
[[9,5],[13,12]], % 14
[[10,6],[14,13]] % 15
].
%
% Print the board:
%
% 1
% 2 3
% 4 5 6
% 7 8 9 10
% 11 12 13 14 15
%
print_board(B) =>
printf(" %2d\n", B[1]),
printf(" %2d %2d\n", B[2],B[3]),
printf(" %2d %2d %2d\n", B[4],B[5],B[6]),
printf(" %2d %2d %2d %2d\n",B[7],B[8],B[9],B[10]),
printf(" %2d %2d %2d %2d %2d\n",B[11],B[12],B[13],B[14],B[15]),
nl.</syntaxhighlight>
{{out}}
<pre>Show the moves (Move from .. over .. to .. ):
[from = 4,over = 2,to = 1]
[from = 6,over = 5,to = 4]
[from = 1,over = 3,to = 6]
[from = 12,over = 8,to = 5]
[from = 14,over = 13,to = 12]
[from = 6,over = 9,to = 13]
[from = 12,over = 13,to = 14]
[from = 15,over = 10,to = 6]
[from = 7,over = 4,to = 2]
[from = 2,over = 5,to = 9]
[from = 6,over = 9,to = 13]
[from = 14,over = 13,to = 12]
[from = 11,over = 12,to = 13]
Show the list at each move (0 is an empty hole):
0 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 0 3 0 5 6 7 8 9 10 11 12 13 14 15
1 0 3 4 0 0 7 8 9 10 11 12 13 14 15
0 0 0 4 0 6 7 8 9 10 11 12 13 14 15
0 0 0 4 5 6 7 0 9 10 11 0 13 14 15
0 0 0 4 5 6 7 0 9 10 11 12 0 0 15
0 0 0 4 5 0 7 0 0 10 11 12 13 0 15
0 0 0 4 5 0 7 0 0 10 11 0 0 14 15
0 0 0 4 5 6 7 0 0 0 11 0 0 14 0
0 2 0 0 5 6 0 0 0 0 11 0 0 14 0
0 0 0 0 0 6 0 0 9 0 11 0 0 14 0
0 0 0 0 0 0 0 0 0 0 11 0 13 14 0
0 0 0 0 0 0 0 0 0 0 11 12 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 13 0 0
And an verbose version:
0
2 3
4 5 6
7 8 9 10
11 12 13 14 15
Move from 4 over 2 to 1
1
0 3
0 5 6
7 8 9 10
11 12 13 14 15
Move from 6 over 5 to 4
1
0 3
4 0 0
7 8 9 10
11 12 13 14 15
Move from 1 over 3 to 6
0
0 0
4 0 6
7 8 9 10
11 12 13 14 15
Move from 12 over 8 to 5
0
0 0
4 5 6
7 0 9 10
11 0 13 14 15
Move from 14 over 13 to 12
0
0 0
4 5 6
7 0 9 10
11 12 0 0 15
Move from 6 over 9 to 13
0
0 0
4 5 0
7 0 0 10
11 12 13 0 15
Move from 12 over 13 to 14
0
0 0
4 5 0
7 0 0 10
11 0 0 14 15
Move from 15 over 10 to 6
0
0 0
4 5 6
7 0 0 0
11 0 0 14 0
Move from 7 over 4 to 2
0
2 0
0 5 6
0 0 0 0
11 0 0 14 0
Move from 2 over 5 to 9
0
0 0
0 0 6
0 0 9 0
11 0 0 14 0
Move from 6 over 9 to 13
0
0 0
0 0 0
0 0 0 0
11 0 13 14 0
Move from 14 over 13 to 12
0
0 0
0 0 0
0 0 0 0
11 12 0 0 0
Move from 11 over 12 to 13
0
0 0
0 0 0
0 0 0 0
0 0 13 0 0</pre>
=={{header|Prolog}}==
Works with SWI-Prolog and module(lambda).
<
iq_puzzle :-
Line 649 ⟶ 3,032:
select(End, Free, F1),
display(Tail, [Start, Middle | F1]).
</syntaxhighlight>
Output :
<pre> ?- iq_puzzle.
Line 771 ⟶ 3,154:
=={{header|Python}}==
<syntaxhighlight lang="python">#
# Draw board triangle in ascii
#
Line 866 ⟶ 3,249:
AddPeg(board,land) # board order changes!
DrawBoard(board)
print "Peg %X jumped over %X to land on %X\n" % (peg,over,land)</
{{out}}
Line 963 ⟶ 3,346:
=={{header|Racket}}==
{{incorrect|Racket|Should the output start 6 jumps 3, then 15 jumps 10 ... rather than 1 jumps 3, then 6 jumps 10 ... ?
<br/>
Not so fast... The output is correct if one reads the statement differently. The first number is the arrival<br/>position, the second number is the position where the peg is "jumped over" and is to be removed.<br/><br/>The position of where the peg jumps <b><i>from</i></b> is not indicated - but it can only be a single possibility in each case.}}
* This includes the code to generate the list of available hops (other implementations seem to have the table built in)
* It produces a full has containing all the possible results from all possible start positions (including ones without valid hops, and unusual starts). It takes no time... and once this is pre-calculated then some of the questions you might want answered about this puzzle can be more easily answered!
Line 969 ⟶ 3,354:
Oh and there are some useful triangle numbers functions thrown in for free!
<
(define << arithmetic-shift)
(define bwbs? bitwise-bit-set?)
Line 1,047 ⟶ 3,432:
;; Solve #1 missing -> #13 left alone
(for-each display-board (find-path (flip-peg 1 full-board) (flip-peg 13 empty-board)))</
{{out}}
Line 1,128 ⟶ 3,513:
[ ] [ ] [ ] [ ]
[ ] [ ] [13] [ ] [ ]</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2017.05}}
{{trans|Sidef}}
<syntaxhighlight lang="raku" line>
constant @start = <
0
1 1
1 1 1
1 1 1 1
1 1 1 1 1
>».Int;
constant @moves =
[ 0, 1, 3],[ 0, 2, 5],[ 1, 3, 6],
[ 1, 4, 8],[ 2, 4, 7],[ 2, 5, 9],
[ 3, 4, 5],[ 3, 6,10],[ 3, 7,12],
[ 4, 7,11],[ 4, 8,13],[ 5, 8,12],
[ 5, 9,14],[ 6, 7, 8],[ 7, 8, 9],
[10,11,12],[11,12,13],[12,13,14];
my $format = (1..5).map: {' ' x 5-$_, "%d " x $_, "\n"};
sub solve(@board, @move) {
return " Solved" if @board.sum == 1;
return Nil if @board[@move[1]] == 0;
my $valid = do given @board[@move[0]] {
when 0 {
return Nil if @board[@move[2]] == 0;
"move {@move[2]} to {@move[0]}\n ";
}
default {
return Nil if @board[@move[2]] == 1;
"move {@move[0]} to {@move[2]}\n ";
}
}
my @new-layout = @board;
@new-layout[$_] = 1 - @new-layout[$_] for @move;
my $result;
for @moves -> @this-move {
$result = solve(@new-layout, @this-move);
last if $result
}
$result ?? "$valid\n " ~ sprintf($format, |@new-layout) ~ $result !! $result
}
print "Starting with\n ", sprintf($format, |@start);
my $result;
for @moves -> @this-move {
$result = solve(@start, @this-move);
last if $result
};
say $result ?? $result !! "No solution found";</syntaxhighlight>
{{out}}
<pre style="height:60ex;overflow:scroll;">Starting with
0
1 1
1 1 1
1 1 1 1
1 1 1 1 1
move 3 to 0
1
0 1
0 1 1
1 1 1 1
1 1 1 1 1
move 8 to 1
1
1 1
0 0 1
1 1 0 1
1 1 1 1 1
move 10 to 3
1
1 1
1 0 1
0 1 0 1
0 1 1 1 1
move 1 to 6
1
0 1
0 0 1
1 1 0 1
0 1 1 1 1
move 11 to 4
1
0 1
0 1 1
1 0 0 1
0 0 1 1 1
move 2 to 7
1
0 0
0 0 1
1 1 0 1
0 0 1 1 1
move 9 to 2
1
0 1
0 0 0
1 1 0 0
0 0 1 1 1
move 0 to 5
0
0 0
0 0 1
1 1 0 0
0 0 1 1 1
move 6 to 8
0
0 0
0 0 1
0 0 1 0
0 0 1 1 1
move 13 to 11
0
0 0
0 0 1
0 0 1 0
0 1 0 0 1
move 5 to 12
0
0 0
0 0 0
0 0 0 0
0 1 1 0 1
move 11 to 13
0
0 0
0 0 0
0 0 0 0
0 0 0 1 1
move 14 to 12
0
0 0
0 0 0
0 0 0 0
0 0 1 0 0
Solved
</pre>
=={{header|Ruby}}==
<
G = [[0,1,3],[0,2,5],[1,3,6],[1,4,8],[2,4,7],[2,5,9],[3,4,5],[3,6,10],[3,7,12],[4,7,11],[4,8,13],[5,8,12],[5,9,14],[6,7,8],[7,8,9],[10,11,12],[11,12,13],[12,13,14],
FORMAT = (1..5).map{|i| " "*(5-i)+"%d "*i+"\n"}.join+"\n"
def solve n,i,g
return "Solved" if i == 1
return false unless n[g[0]]==0 and n[g[1]]==1 and n[g[2]]==1
return l
end
puts FORMAT % (N=[0,1,1,1,1,1,1,1,1,1,1,1,1,1,1])
l=false; G.each{|g| l=solve(N,
puts l ? l : "No solution found"
</syntaxhighlight>
{{out}}
<pre style="height:64ex;overflow:scroll">
Line 1,256 ⟶ 3,792:
=={{header|Sidef}}==
{{trans|Ruby}}
<
const G = [
Line 1,267 ⟶ 3,803:
]
const format = (
func solve(n, i, g) is cached {
Line 1,295 ⟶ 3,831:
var r = ''
G.each {|g| (r = solve(N, 1, g)) && break }
say (r ? r : "No solution found")</
{{out}}
Line 1,398 ⟶ 3,934:
Solved
</pre>
=={{header|Visual Basic .NET}}==
'''Notes:'''
This program uses a brute-force method with a string of 25 characters to internally represent the 15 spots on the peg board. One can set the starting removed peg and intended last remaining peg by editing the header variable declarations named '''''Starting''''' and '''''Target'''''. If one doesn't care which spot the last peg lands on, the '''''Target''''' variable can be set to 0. The constant '''''n''''' can be changed for different sized peg boards, for example with '''''n = 6''''' the peg board would have 21 positions.
<syntaxhighlight lang="vbnet">
Imports System, Microsoft.VisualBasic.DateAndTime
Public Module Module1
Const n As Integer = 5 ' extent of board
Dim Board As String ' the peg board
Dim Starting As Integer = 1 ' position on board where first peg has been removed
Dim Target As Integer = 13 ' final peg position, use 0 to solve for any postion
Dim Moves As Integer() ' possible offset moves on grid
Dim bi() As Integer ' string position to peg location index
Dim ib() As Integer ' string position to peg location reverse index
Dim nl As Char = Convert.ToChar(10) ' newline character
' expands each line of the board properly
Public Function Dou(s As String) As String
Dou = "" : Dim b As Boolean = True
For Each ch As Char In s
If b Then b = ch <> " "
If b Then Dou &= ch & " " Else Dou = " " & Dou
Next : Dou = Dou.TrimEnd()
End Function
' formats the string representaion of a board into a viewable item
Public Function Fmt(s As String) As String
If s.Length < Board.Length Then Return s
Fmt = "" : For i As Integer = 1 To n : Fmt &= Dou(s.Substring(i * n - n, n)) &
If(i = n, s.Substring(Board.Length), "") & nl
Next
End Function
' returns triangular number of n
Public Function Triangle(n As Integer) As Integer
Return (n * (n + 1)) / 2
End Function
' returns an initialized board with one peg missing
Public Function Init(s As String, pos As Integer) As String
Init = s : Mid(Init, pos, 1) = "0"
End Function
' initializes string-to-board position indices
Public Sub InitIndex()
ReDim bi(Triangle(n)), ib(n * n) : Dim j As Integer = 0
For i As Integer = 0 To ib.Length - 1
If i = 0 Then
ib(i) = 0 : bi(j) = 0 : j += 1
Else
If Board(i - 1) = "1" Then ib(i) = j : bi(j) = i : j += 1
End If
Next
End Sub
' brute-force solver, returns either the steps of a solution, or the string "fail"
Public Function solve(brd As String, pegsLeft As Integer) As String
If pegsLeft = 1 Then ' down to the last one, see if it's the correct one
If Target = 0 Then Return "Completed" ' don't care where the last one is
If brd(bi(Target) - 1) = "1" Then Return "Completed" Else Return "fail"
End If
For i = 1 To Board.Length ' for each possible position...
If brd(i - 1) = "1" Then ' that still has a peg...
For Each mj In Moves ' for each possible move
Dim over As Integer = i + mj ' the position to jump over
Dim land As Integer = i + 2 * mj ' the landing spot
' ensure landing spot is on the board, then check for a valid pattern
If land >= 1 AndAlso land <= brd.Length _
AndAlso brd(land - 1) = "0" _
AndAlso brd(over - 1) = "1" Then
setPegs(brd, "001", i, over, land) ' make a move
' recursively send it out to test
Dim Res As String = solve(brd.Substring(0, Board.Length), pegsLeft - 1)
' check result, returing if OK
If Res.Length <> 4 Then _
Return brd & info(i, over, land) & nl & Res
setPegs(brd, "110", i, over, land) ' not OK, so undo the move
End If
Next
End If
Next
Return "fail"
End Function
' returns a text representation of peg movement for each turn
Function info(frm As Integer, over As Integer, dest As Integer) As String
Return " Peg from " & ib(frm).ToString() & " goes to " & ib(dest).ToString() &
", removing peg at " & ib(over).ToString()
End Function
' sets three pegs as once, used for making and un-doing moves
Sub setPegs(ByRef board As String, pat As String, a As Integer, b As Integer, c As Integer)
Mid(board, a, 1) = pat(0) : Mid(board, b, 1) = pat(1) : Mid(board, c, 1) = pat(2)
End Sub
' limit an integer to a range
Sub LimitIt(ByRef x As Integer, lo As Integer, hi As Integer)
x = Math.Max(Math.Min(x, hi), lo)
End Sub
Public Sub Main()
Dim t As Integer = Triangle(n) ' use the nth triangular number for bounds
LimitIt(Starting, 1, t) ' ensure valid parameters for staring and ending positions
LimitIt(Target, 0, t)
Dim stime As Date = Now() ' keep track of start time for performance result
Moves = {-n - 1, -n, -1, 1, n, n + 1} ' possible offset moves on a nxn grid
Board = New String("1", n * n) ' init string representation of board
For i As Integer = 0 To n - 2 ' and declare non-existent spots
Mid(Board, i * (n + 1) + 2, n - 1 - i) = New String(" ", n - 1 - i)
Next
InitIndex() ' create indicies from board's pattern
Dim B As String = Init(Board, bi(Starting)) ' remove first peg
Console.WriteLine(Fmt(B & " Starting with peg removed from " & Starting.ToString()))
Dim res As String() = solve(B.Substring(0, B.Length), t - 1).Split(nl)
Dim ts As String = (Now() - stime).TotalMilliseconds.ToString() & " ms."
If res(0).Length = 4 Then
If Target = 0 Then
Console.WriteLine("Unable to find a solution with last peg left anywhere.")
Else
Console.WriteLine("Unable to find a solution with last peg left at " &
Target.ToString() & ".")
End If
Console.WriteLine("Computation time: " & ts)
Else
For Each Sol As String In res : Console.WriteLine(Fmt(Sol)) : Next
Console.WriteLine("Computation time to first found solution: " & ts)
End If
If Diagnostics.Debugger.IsAttached Then Console.ReadLine()
End Sub
End Module</syntaxhighlight>
{{out}}
'''A full solution:'''
<pre style="height:64ex;overflow:scroll">
0
1 1
1 1 1
1 1 1 1
1 1 1 1 1 Starting with peg removed from 1
1
0 1
0 1 1
1 1 1 1
1 1 1 1 1 Peg from 4 goes to 1, removing peg at 2
1
0 1
1 0 0
1 1 1 1
1 1 1 1 1 Peg from 6 goes to 4, removing peg at 5
0
0 0
1 0 1
1 1 1 1
1 1 1 1 1 Peg from 1 goes to 6, removing peg at 3
0
1 0
0 0 1
0 1 1 1
1 1 1 1 1 Peg from 7 goes to 2, removing peg at 4
0
1 1
0 0 0
0 1 1 0
1 1 1 1 1 Peg from 10 goes to 3, removing peg at 6
0
1 1
0 1 0
0 0 1 0
1 0 1 1 1 Peg from 12 goes to 5, removing peg at 8
0
1 1
0 1 1
0 0 0 0
1 0 0 1 1 Peg from 13 goes to 6, removing peg at 9
0
0 1
0 0 1
0 0 1 0
1 0 0 1 1 Peg from 2 goes to 9, removing peg at 5
0
0 0
0 0 0
0 0 1 1
1 0 0 1 1 Peg from 3 goes to 10, removing peg at 6
0
0 0
0 0 1
0 0 1 0
1 0 0 1 0 Peg from 15 goes to 6, removing peg at 10
0
0 0
0 0 0
0 0 0 0
1 0 1 1 0 Peg from 6 goes to 13, removing peg at 9
0
0 0
0 0 0
0 0 0 0
1 1 0 0 0 Peg from 14 goes to 12, removing peg at 13
0
0 0
0 0 0
0 0 0 0
0 0 1 0 0 Peg from 11 goes to 13, removing peg at 12
Completed
Computation time to first found solution: 15.6086 ms.
</pre>
'''A failed solution:'''
<pre>
1
0 1
1 1 1
1 1 1 1
1 1 1 1 1 Starting with peg removed from 2
Unable to find a solution with last peg left at 13.
Computation time: 1656.2754 ms.
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./fmt" for Conv, Fmt
var board = List.filled(16, true)
board[0] = false
var jumpMoves = [
[ ],
[ [ 2, 4], [ 3, 6] ],
[ [ 4, 7], [ 5, 9] ],
[ [ 5, 8], [ 6, 10] ],
[ [ 2, 1], [ 5, 6], [ 7, 11], [ 8, 13] ],
[ [ 8, 12], [ 9, 14] ],
[ [ 3, 1], [ 5, 4], [ 9, 13], [10, 15] ],
[ [ 4, 2], [ 8, 9] ],
[ [ 5, 3], [ 9, 10] ],
[ [ 5, 2], [ 8, 7] ],
[ [ 9, 8] ],
[ [12, 13] ],
[ [ 8, 5], [13, 14] ],
[ [ 8, 4], [ 9, 6], [12, 11], [14, 15] ],
[ [ 9, 5], [13, 12] ],
[ [10, 6], [14, 13] ]
]
var solutions = []
var drawBoard = Fn.new {
var pegs = List.filled(16, "-")
for (i in 1..15) if (board[i]) pegs[i] = Conv.Itoa(i, 16)
Fmt.print(" $s", pegs[1])
Fmt.print(" $s $s", pegs[2], pegs[3])
Fmt.print(" $s $s $s", pegs[4], pegs[5], pegs[6])
Fmt.print(" $s $s $s $s", pegs[7], pegs[8], pegs[9], pegs[10])
Fmt.print(" $s $s $s $s $s", pegs[11], pegs[12], pegs[13], pegs[14], pegs[15])
}
var solved = Fn.new { board.count { |peg| peg } == 1 } // just one peg left
var solve // recursive so need to pre-declare
solve = Fn.new {
if (solved.call()) return
for (peg in 1..15) {
if (board[peg]) {
for (ol in jumpMoves[peg]) {
var over = ol[0]
var land = ol[1]
if (board[over] && !board[land]) {
var saveBoard = board.toList
board[peg] = false
board[over] = false
board[land] = true
solutions.add([peg, over, land])
solve.call()
if (solved.call()) return // otherwise back-track
board = saveBoard
solutions.removeAt(-1)
}
}
}
}
}
var emptyStart = 1
board[emptyStart] = false
solve.call()
board = List.filled(16, true)
board[0] = false
board[emptyStart] = false
drawBoard.call()
Fmt.print("Starting with peg $X removed\n", emptyStart)
for (sol in solutions) {
var peg = sol[0]
var over = sol[1]
var land = sol[2]
board[peg] = false
board[over] = false
board[land] = true
drawBoard.call()
Fmt.print("Peg $X jumped over $X to land on $X\n", peg, over, land)
}</syntaxhighlight>
{{out}}
<pre>
Same as Kotlin entry.
</pre>
=={{header|Yabasic}}==
{{trans|Phix}}
<syntaxhighlight lang="yabasic">// Rosetta Code problem: http://rosettacode.org/wiki/Solve_triangle_solitare_puzzle
// by Galileo, 04/2022
dim moves$(1)
nmov = token("-11,-9,2,11,9,-2", moves$(), ",")
sub solve$(board$, left)
local i, j, mj, over, tgt, res$
if left = 1 return ""
for i = 1 to len(board$)
if mid$(board$, i, 1) = "1" then
for j = 1 to nmov
mj = val(moves$(j)) : over = i + mj : tgt = i + 2 * mj
if tgt >= 1 and tgt <= len(board$) and mid$(board$, tgt, 1) = "0" and mid$(board$, over, 1) = "1" then
mid$(board$, i, 1) = "0" : mid$(board$, over, 1) = "0" : mid$(board$, tgt, 1) = "1"
res$ = solve$(board$, left - 1)
if len(res$) != 4 return board$+res$
mid$(board$, i, 1) = "1" : mid$(board$, over, 1) = "1" : mid$(board$, tgt, 1) = "0"
end if
next
end if
next
return "oops"
end sub
start$ = "\n\n 0 \n 1 1 \n 1 1 1 \n 1 1 1 1 \n1 1 1 1 1"
print start$, solve$(start$, 14)</syntaxhighlight>
{{out}}
<pre>
0
1 1
1 1 1
1 1 1 1
1 1 1 1 1
1
0 1
0 1 1
1 1 1 1
1 1 1 1 1
1
0 1
1 0 0
1 1 1 1
1 1 1 1 1
0
0 0
1 0 1
1 1 1 1
1 1 1 1 1
0
1 0
0 0 1
0 1 1 1
1 1 1 1 1
0
1 1
0 0 0
0 1 1 0
1 1 1 1 1
0
1 1
0 1 0
0 0 1 0
1 0 1 1 1
0
1 1
0 1 1
0 0 0 0
1 0 0 1 1
0
0 1
0 0 1
0 0 1 0
1 0 0 1 1
0
0 0
0 0 0
0 0 1 1
1 0 0 1 1
0
0 0
0 0 1
0 0 1 0
1 0 0 1 0
0
0 0
0 0 0
0 0 0 0
1 0 1 1 0
0
0 0
0 0 0
0 0 0 0
1 1 0 0 0
0
0 0
0 0 0
0 0 0 0
0 0 1 0 0
---Program done, press RETURN---</pre>
=={{header|zkl}}==
{{trans|D}}
{{Trans|Ruby}}
<
var G=T( T(0,1, 3), T(0,2, 5), T(1,3, 6), T( 1, 4, 8), T( 2, 4, 7), T( 2, 5, 9),
T(3,4, 5), T(3,6,10), T(3,7,12), T( 4, 7,11), T( 4, 8,13), T( 5, 8,12),
Line 1,436 ⟶ 4,412:
reg l;
foreach g in (G){ if(l=solve(N,1,g)) break; }
println(l and l or "No solution found.");</
{{out}}
<pre style="height:32ex;overflow:scroll">
| |||