Solve triangle solitaire puzzle: Difference between revisions
m
→{{header|Phix}}: use pygments, simplified by using reinstate, which also fixes a couple of p2js violations
No edit summary Tags: Mobile edit Mobile web edit |
m (→{{header|Phix}}: use pygments, simplified by using reinstate, which also fixes a couple of p2js violations) |
||
| (10 intermediate revisions by 6 users not shown) | |||
Line 118:
{{out}}
<pre>
1
. 3
Line 209 ⟶ 210:
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>
Line 386 ⟶ 639:
brd$[pos + dir] = "·"
brd$[pos + 2 * dir] = "●"
brd$[pos] = "●"
brd$[pos + dir] = "●"
Line 392 ⟶ 645:
if solution$ <> ""
solution$ = strjoin brd$[] & solution$
.
.
Line 402 ⟶ 655:
.
.
print solution$
</syntaxhighlight>
Line 553 ⟶ 806:
</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}}
Line 1,120 ⟶ 1,498:
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>
Line 1,161 ⟶ 1,843:
end
</syntaxhighlight>{{out}}
<pre style="height:20lh;overflow:auto>
Starting board:
0
Line 1,842 ⟶ 2,524:
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 for
end if
end for
return "oops"
end function
sequence start = """
1-1-1-1-1
"""
puts(1,substitute(join_by(split(start&solve(start,14),'\n'),5,7),"-"," "))
</syntaxhighlight>
{{out}}
Line 1,890 ⟶ 2,573:
Adapted to the English game (also in demo\rosetta\IQpuzzle.exw):
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 = """
-----.-.-.----
"""
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
Line 3,488 ⟶ 4,170:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
var board = List.filled(16, true)
| |||