# Tricky Triangle

```// Written by Grant Jenks
// http://www.grantjenks.com/
//
// DISCLAIMER
// THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE
// LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR
// OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND,
// EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE
// ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU.
// SHOULD THE PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY
// SERVICING, REPAIR OR CORRECTION.
//
// To view a copy of this license, visit
// or send a letter to Creative Commons, 171 Second Street, Suite 300,
// San Francisco, California, 94105, USA.
//
// The Tricky Triangle
//
// The tricky triangle is a game played with pegs in a wood cut-out like so:
//
//                                    o
//                                   o o
//                                  o o o
//                                 o o o o
//                                o o o o o
//
// Initially, all the holes are filled with pegs. I'll number the pegs like so:
//
//                                     1
//                                  2     3
//                               4     5     6
//                            7     8     9    10
//                         11   12    13    14    15
//
// Now the goal of the game is to eliminate all the pegs but one. Pegs are
// eliminated when they are 'jumped', that is, when another peg moves two steps
// in the same diagonal direction over an occupied hole. So in the following
// situation:
//
//                                    x
//                                   o x
//                                  o o o
//                                 o o o o
//                                o o o o o
//
// The peg at 1 may jump to 6 and eliminate the peg at 3.
//
// At the start of the game all holes are filled and the player is permitted
// to remove one peg.
//
// The following program solves the tricky triangle puzzle and outputs a sequence
// of moves that are denoted by (start,end) pairs. Output:
//
// Solution:
// Board Numbering:             1
//                           2     3
//                        4     5     6
//                     7     8     9    10
//                  11   12    13    14    15
//  (14,5) (12,14) (7,9) (6,13) (14,12) (2,7) (11,4) (1,6) (10,3) (3,8) (4,13)
// (12,14) (15,13)
//

using System;
using System.Linq;
using System.Collections.Generic;

//------------------------------------------------------------------------------
//
// A move is from one hole to another.
//
//------------------------------------------------------------------------------

struct Move
{
public byte from;
public byte to;

public Move(byte aFrom, byte aTo)
{
from = aFrom;
to = aTo;
}
}

//------------------------------------------------------------------------------
//
// The board class simply wraps an array of booleans and provides useful
// constructors.
//
//------------------------------------------------------------------------------

class Board
{
public bool[] holes;

public Board()
{
holes = new bool[16];
for (int i = 1; i < 16; i++)
{
holes[i] = true;
}
}
public Board(Board board)
{
holes = new bool[16];
Array.Copy(board.holes, holes, 16);
}
}

//------------------------------------------------------------------------------
//
// The state class represents a board and a history of moves that got us to the
// board state. The initial missing peg can be inferred from the first move:
// the first move always has a destination of the initial missing peg.
//
//------------------------------------------------------------------------------

class State
{
public Board board;
public List<Move> history;

public State()
{
board = new Board();
history = new List<Move>();
}
public State(State state)
{
board = new Board(state.board);
history = new List<Move>(state.history);
}

//------------------------------------------------------------------------------
//
// Return a list of available moves.
//
//------------------------------------------------------------------------------

public List<Move> GetAvailableMoves()
{
List<Move> availableMoves = new List<Move>();

for (int i = 0; i < 16; i++)
{
if (board.holes[i])
{
for (int j = 0; j < 16; j++)
{
if (TrickyTriangle.board[i,j] > 0 && !board.holes[j]
&& board.holes[TrickyTriangle.board[i,j]])
{
}
}
}
}
return availableMoves;
}
}

class TrickyTriangle
{
//------------------------------------------------------------------------------
//
// The board is represented as an adjacency matrix. A non-zero position means,
// given board[x, y], that a peg at x may move to y. The value given at that
// position is the number of the hole that is 'jumped'. 0 is reserved both as a
// value in the matrix and as a row / column.
//
//------------------------------------------------------------------------------

byte[,] board = new byte[,] { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 2, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 4, 0, 5, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 6, 0, 0, 0, 0, 0 },
{ 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 8, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 9, 0 },
{ 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0,10 },
{ 0, 0, 4, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0 },
{ 0, 0, 5, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 6, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0,12, 0, 0 },
{ 0, 0, 0, 0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0,13, 0 },
{ 0, 0, 0, 0, 8, 0, 9, 0, 0, 0, 0,12, 0, 0, 0,14 },
{ 0, 0, 0, 0, 0, 9, 0, 0, 0, 0, 0, 0,13, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0,10, 0, 0, 0, 0, 0, 0,14, 0, 0 } };

//------------------------------------------------------------------------------
//
// Returns 0 on success, a sequence of moves found such that only one peg remains,
// or 1 on failure.
//
//------------------------------------------------------------------------------

static int Main(String[] args)
{
Stack<State> games = new Stack<State>();

// Reduce the search space based on symmetry.

foreach (int hole in (new int[] { 1, 2, 4, 5 }))
{
State state = new State();
state.board.holes[hole] = false;
games.Push(state);
}

// This is an iterative implementation of a depth-first-search more commonly
// implemented using recursion.

while (games.Count > 0)
{
State state = games.Pop();

List<Move> availableMoves = state.GetAvailableMoves();

if (availableMoves.Count > 0)
{
// Simulate each available move and put it on our stack.

foreach (Move move in availableMoves)
{
State newState = new State(state);

newState.board.holes[move.from] = false;
newState.board.holes[board[move.from, move.to]] = false;
newState.board.holes[move.to] = true;

games.Push(newState);
}
}
else
{
int pegs = state.board.holes.Count(h => h);

if (pegs == 1)
{
Console.WriteLine("Solution:");
Console.WriteLine("Board Numbering:             1");
Console.WriteLine("                          2     3");
Console.WriteLine("                       4     5     6");
Console.WriteLine("                    7     8     9    10");
Console.WriteLine("                 11   12    13    14    15");
state.history[0].to);

foreach (Move move in state.history)
{
Console.Write(" ({0},{1})",  move.from, move.to);
}

Console.WriteLine();

return 0;
}
}
}

return 1;
}
}```