// 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.
//
// Copyright
// This work is licensed under the
// Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.
// To view a copy of this license, visit
// http://creativecommons.org/licenses/by-nc-nd/3.0/
// 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
// Start with 5 empty, then:
// (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]])
{
availableMoves.Add(new Move((byte)i, (byte)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.
//
//------------------------------------------------------------------------------
public static readonly
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.history.Add(move);
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");
Console.WriteLine("Start with {0} empty, then:",
state.history[0].to);
foreach (Move move in state.history)
{
Console.Write(" ({0},{1})", move.from, move.to);
}
Console.WriteLine();
return 0;
}
}
}
return 1;
}
}