Anonymous user
Solve triangle solitaire puzzle: Difference between revisions
→{{header|J}}
m (→{{header|Julia}}: add starting position display) |
|||
Line 673:
</pre>
=={{header|Java}}==
Print the number of solutions for each start and end combination.
Print one possible solution.
<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();
}
}
}
</lang>
{{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|Julia}}==
| |||