15 puzzle solver: Difference between revisions
Add solution on C#
Hendursaga (talk | contribs) m (Fixed spelling error, bumped tested version.) |
(Add solution on C#) |
||
Line 2,655:
The program takes about 12 seconds to solve the puzzle on my machine. I sacrificed efficiency for readability and extensibility.
=={{header|C sharp|C#}}==
{{libheader|System.Windows.Forms}}
{{libheader|System.Drawing}}
{{works with|C sharp|3+}}
Note 1: The program does not output a text solution. It's solvig step by step in grafical interface.<br>
Note 2: Rosetta task avaiable from UI. Click "Task" button and run slover. The solution is obtained for 164 moves.
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;
public static class Program
{
public static void Main(string[] args)
{
FifteenPuzzle Game = new FifteenPuzzle();
Application.Run(Game.Form);
}
}
public class Puzzle
{
private int mOrderedNumer;
public int OrderedNumer
{
get { return mOrderedNumer; }
}
public int CurrentNumber;
public bool IsPined = false;
public int X;
public int Y;
public int InvX
{
get { return (FifteenPuzzle.GridSize - 1) - X; }
}
public int InvY
{
get { return (FifteenPuzzle.GridSize - 1) - Y; }
}
public Puzzle(int OrderedNumer)
{
mOrderedNumer = OrderedNumer;
CurrentNumber = OrderedNumer;
X = OrderedNumer % FifteenPuzzle.GridSize;
Y = OrderedNumer / FifteenPuzzle.GridSize;
}
public bool IsEmptyPuzzle
{
get { return CurrentNumber >= (FifteenPuzzle.BlockCount - 1); }
}
public bool IsTruePlace
{
get { return (CurrentNumber == mOrderedNumer); }
}
public bool NearestWith(Puzzle OtherPz)
{
int dx = (X - OtherPz.X);
int dy = (Y - OtherPz.Y);
if ((dx == 0) && (dy <= 1) && (dy >= -1)) return true;
if ((dy == 0) && (dx <= 1) && (dx >= -1)) return true;
return false;
}
public int MHDistance(Puzzle OtherPz)
{
int dx = (X - OtherPz.X);
int dy = (Y - OtherPz.Y);
if (dx < 0) dx = -dx;
if (dy < 0) dy = -dy;
return dx + dy;
}
public override string ToString()
{
return (CurrentNumber + 1).ToString();
}
public void UpdateView(Button V)
{
V.Visible = true;
V.Text = ToString();
if (IsEmptyPuzzle) V.Visible = false;
}
}
public class FifteenPuzzle
{
public const int GridSize = 4; //Standard 15 puzzle is 4x4
public const int BlockCount = 16;
static readonly Random R = new Random();
private Form mForm;
public Form Form
{
get { return mForm; }
}
private List<Button> Puzzles = new List<Button>();
private int Moves = 0;
private DateTime Start;
private SolverPuzzle Solver;
private Button SolverButton;
private Timer SolverClock;
public FifteenPuzzle()
{
this.mForm = CreateForm();
this.Solver = new SolverPuzzle(Puzzles.ConvertAll<Puzzle>(Bt => (Puzzle)Bt.Tag));
}
private Form CreateForm()
{
int ButtonSize = 50;
int ButtonMargin = 3;
int FormEdge = 9;
Font ButtonFont = new Font("Arial", 15.75F, FontStyle.Regular);
Button StartButton = CreateButton("New Game", NewGameWithRandomBoard);
StartButton.Location = new Point(FormEdge, (GridSize * (ButtonMargin + ButtonSize)) + FormEdge);
int FormWidth = (GridSize * ButtonSize) + ((GridSize - 1) * ButtonMargin) + (FormEdge * 2);
int FormHeigth = FormWidth + StartButton.Height;
Form Form = new Form();
Form.Text = "Fifteen";
Form.ClientSize = new Size(FormWidth, FormHeigth);
Form.FormBorderStyle = FormBorderStyle.FixedSingle;
Form.MaximizeBox = false;
Form.SuspendLayout();
for (int i = 0; i < BlockCount; i++)
{
Button Bt = new Button();
Puzzle Pz = new Puzzle(i);
int PosX = FormEdge + (Pz.X) * (ButtonSize + ButtonMargin);
int PosY = FormEdge + (Pz.Y) * (ButtonSize + ButtonMargin);
Bt.Location = new Point(PosX, PosY);
Bt.Size = new Size(ButtonSize, ButtonSize);
Bt.Font = ButtonFont;
Bt.Tag = Pz;
Bt.UseVisualStyleBackColor = true;
Bt.TabStop = false;
Bt.Enabled = false;
Pz.UpdateView(Bt);
Bt.Click += new EventHandler(MovePuzzle);
Puzzles.Add(Bt);
Form.Controls.Add(Bt);
}
// solver controls
SolverClock = new Timer();
SolverClock.Interval = 300;
SolverClock.Tick += new EventHandler(SolverStep);
SolverButton = CreateButton("Run Solver", RunOrStopSolver);
SolverButton.Location = new Point(FormWidth - FormEdge - SolverButton.Width, StartButton.Location.Y);
SolverButton.Enabled = false;
Button TaskButton = CreateButton("Task", NewGameWithTask);
TaskButton.Location = new Point(StartButton.Location.X + StartButton.Width + ButtonMargin, StartButton.Location.Y);
TaskButton.Size = new Size((SolverButton.Location.X - ButtonMargin) - TaskButton.Location.X, 23);
Form.Controls.Add(StartButton);
Form.Controls.Add(TaskButton);
Form.Controls.Add(SolverButton);
Form.ResumeLayout();
return Form;
}
private Button CreateButton(string Text, EventHandler ClickHandler)
{
Button Bt = new Button();
Bt.Size = new Size(80, 23);
Bt.Text = Text;
Bt.Font = new Font("Arial", 9.75F, FontStyle.Regular);
Bt.UseVisualStyleBackColor = true;
Bt.TabStop = false;
Bt.Click += ClickHandler;
return Bt;
}
private void NewGameWithRandomBoard(object Sender, EventArgs E)
{
do
{
for (int i = 0; i < Puzzles.Count; i++)
{
Button Bt1 = Puzzles[R.Next(i, Puzzles.Count)];
Button Bt2 = Puzzles[i];
Swap(Bt1, Bt2);
}
}
while (!IsSolvable());
NewGameBase();
}
private void NewGameWithTask(object Sender, EventArgs E)
{
int[] RosettaTask = new int[]
{
15, 14, 1, 6,
9, 11, 4, 12,
0, 10, 7, 3,
13, 8, 5, 2,
};
for (int i = 0; i < Puzzles.Count; i++)
{
Button Bt = Puzzles[i];
Puzzle Pz = (Puzzle)Bt.Tag;
Pz.CurrentNumber = RosettaTask[i] - 1;
if (Pz.CurrentNumber < 0) Pz.CurrentNumber = BlockCount - 1;
Pz.UpdateView(Bt);
}
NewGameBase();
}
private void NewGameBase()
{
Solver.Clear();
for (int i = 0; i < Puzzles.Count; i++)
{
Puzzles[i].Enabled = true;
}
SolverButton.Enabled = true;
Moves = 0;
Start = DateTime.Now;
}
private void MovePuzzle(object Sender, EventArgs E)
{
Button Bt1 = (Button)Sender;
Puzzle Pz1 = (Puzzle)Bt1.Tag;
Button Bt2 = Puzzles.Find(Bt => ((Puzzle)Bt.Tag).IsEmptyPuzzle);
Puzzle Pz2 = (Puzzle)Bt2.Tag;
if (Pz1.NearestWith(Pz2))
{
Swap(Bt1, Bt2);
Moves++;
}
CheckWin();
}
private void CheckWin()
{
Button WrongPuzzle = Puzzles.Find(Bt => !((Puzzle)Bt.Tag).IsTruePlace);
bool UWin = (WrongPuzzle == null);
if (UWin)
{
for (int i = 0; i < Puzzles.Count; i++)
{
Puzzles[i].Enabled = false;
}
SolverClock.Enabled = false;
SolverButton.Enabled = false;
SolverButton.Text = "Run Solver";
TimeSpan Elapsed = DateTime.Now - Start;
Elapsed = TimeSpan.FromSeconds(Math.Round(Elapsed.TotalSeconds, 0));
MessageBox.Show(String.Format("Solved in {0} moves. Time: {1}", Moves, Elapsed));
}
}
private void Swap(Button Bt1, Button Bt2)
{
if (Bt1 == Bt2) return;
Puzzle Pz1 = (Puzzle)Bt1.Tag;
Puzzle Pz2 = (Puzzle)Bt2.Tag;
int g = Pz1.CurrentNumber;
Pz1.CurrentNumber = Pz2.CurrentNumber;
Pz2.CurrentNumber = g;
Pz1.UpdateView(Bt1);
Pz2.UpdateView(Bt2);
}
private bool IsSolvable()
{
// WARNING: size of puzzle board MUST be even(like 4)!
// For explain see: https://www.geeksforgeeks.org/check-instance-15-puzzle-solvable/
int InvCount = 0;
for (int i = 0; i < Puzzles.Count - 1; i++)
{
for (int j = i + 1; j < Puzzles.Count; j++)
{
Puzzle Pz1 = (Puzzle)Puzzles[i].Tag;
if (Pz1.IsEmptyPuzzle) continue;
Puzzle Pz2 = (Puzzle)Puzzles[j].Tag;
if (Pz2.IsEmptyPuzzle) continue;
if (Pz1.CurrentNumber > Pz2.CurrentNumber) InvCount++;
}
}
Button EmptyBt = Puzzles.Find(Bt => ((Puzzle)Bt.Tag).IsEmptyPuzzle);
Puzzle EmptyPz = (Puzzle)EmptyBt.Tag;
bool Result = false;
// even + odd
if (((EmptyPz.InvY + 1) % 2 == 0) && (InvCount % 2 != 0)) Result = true;
// odd + even
if (((EmptyPz.InvY + 1) % 2 != 0) && (InvCount % 2 == 0)) Result = true;
return Result;
}
private void RunOrStopSolver(object Sender, EventArgs E)
{
SolverClock.Enabled = !SolverClock.Enabled;
if (SolverClock.Enabled)
{
SolverButton.Text = "Stop Solver";
}
else
{
SolverButton.Text = "Run Solver";
Solver.Clear();
}
}
private void SolverStep(object Sender, EventArgs E)
{
Point NextMove = Solver.AnalysisPosition();
Button NextBt = Puzzles.Find(Bt => (((Puzzle)Bt.Tag).X == NextMove.X && ((Puzzle)Bt.Tag).Y == NextMove.Y));
if (NextBt != null) MovePuzzle(NextBt, EventArgs.Empty);
}
}
public class SolverPuzzle
{
static readonly int[] SolvingSecuence = new int[] { 0, 1, 2, 3, 4, 8, 12, 5, 6, 7, 9, 13, 10, 11, 14 };
static readonly Point[] GameSteps = new Point[] { new Point(0, 1), new Point(1, 0), new Point(-1, 0), new Point(0, -1) };
private List<Puzzle> Puzzles;
private PathSearch Navigator;
private Queue<Point> PlanedMoves = new Queue<Point>();
private class DeadLock
{
public int[] BoardMask;
public int EntryOrderedNumber;
public Point[] StepToSolve;
public bool InBoard(List<Puzzle> Puzzles)
{
bool HasDeadLock = true;
for (int i = 0; i < BoardMask.Length; i++)
{
if (BoardMask[i] < 0) continue;
if (BoardMask[i] != Puzzles[i].CurrentNumber)
{
HasDeadLock = false;
break;
}
}
return HasDeadLock;
}
}
private static List<DeadLock> DeadLocks = new List<DeadLock>();
static SolverPuzzle()
{
// create deadlocks
DeadLock D;
// top line
D = new DeadLock();
D.EntryOrderedNumber = 0;
D.BoardMask = new int[] { 0, 1, 2, -1, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, };
D.StepToSolve = new Point[]
{
new Point(1, 0), new Point(2, 0), new Point(3, 0), new Point(3, 1), new Point(2, 1),
new Point(2, 0), new Point(1, 0), new Point(0, 0), new Point(0, 1),
};
DeadLocks.Add(D);
// left line
D = new DeadLock();
D.EntryOrderedNumber = 1;
D.BoardMask = new int[] { 0, -1, -1, -1, 4, -1, -1, -1, 8, -1, -1, -1, -1, 12, -1, -1, };
D.StepToSolve = new Point[]
{
new Point(0, 0), new Point(0, 1), new Point(0, 2), new Point(0, 3), new Point(1, 3),
new Point(1, 2), new Point(0, 2), new Point(0, 1), new Point(0, 0), new Point(1, 0),
new Point(1, 1),
};
DeadLocks.Add(D);
// second from top line
D = new DeadLock();
D.EntryOrderedNumber = 5;
D.BoardMask = new int[] { -1, -1, -1, -1, -1, 5, 6, -1, -1, -1, -1, 7, -1, -1, -1, -1, };
D.StepToSolve = new Point[]
{
new Point(2, 1), new Point(3, 1), new Point(3, 2), new Point(2, 2), new Point(2, 1),
new Point(1, 1), new Point(1, 2),
};
DeadLocks.Add(D);
// second from left line
D = new DeadLock();
D.EntryOrderedNumber = 7;
D.BoardMask = new int[] { -1, -1, -1, -1, -1, 5, -1, -1, -1, 9, -1, -1, -1, -1, 13, -1, };
D.StepToSolve = new Point[]
{
new Point(2, 1), new Point(1, 1), new Point(1, 2), new Point(1, 3), new Point(2, 3),
new Point(2, 2), new Point(1, 2), new Point(1, 1), new Point(2, 1), new Point(3, 1),
new Point(3, 2),
};
DeadLocks.Add(D);
}
public SolverPuzzle(List<Puzzle> Puzzles)
{
this.Puzzles = Puzzles;
Navigator = new PathSearch(Puzzles, GameSteps);
}
public Point AnalysisPosition()
{
// just do exist plan
if (PlanedMoves.Count > 0) return PlanedMoves.Dequeue();
bool AllPined = PinTruePuzzles();
// already solved
if (AllPined) return new Point(-1, -1);
Puzzle EmptyPz = Puzzles.Find(Pz => Pz.IsEmptyPuzzle);
Puzzle WrongPz = FindWrongPuzzle();
// get path (empty puzzle => wrong puzle) if a far!
if (EmptyPz.MHDistance(WrongPz) > 1)
{
PlanedPath(EmptyPz, WrongPz);
// do path!
if (PlanedMoves.Count > 0) return PlanedMoves.Dequeue();
}
else // empty puzzle near
{
// move empty puzzle around!
WrongPz.IsPined = true;
Puzzle BestPz = FindBestPuzzleToSwap(WrongPz);
// if already in place - click on target
if (BestPz == EmptyPz) return new Point(WrongPz.X, WrongPz.Y);
PlanedPath(EmptyPz, BestPz);
// do path!
if (PlanedMoves.Count > 0) return PlanedMoves.Dequeue();
}
// if we are here SPEC CASE AHEAD
for (int i = 0; i < DeadLocks.Count; i++)
{
DeadLock Lock = DeadLocks[i];
if (Lock.InBoard(Puzzles))
{
// unpin dest
Puzzle DestPz = Puzzles.Find(Pz => Pz.OrderedNumer == Lock.EntryOrderedNumber);
DestPz.IsPined = false;
PlanedPath(EmptyPz, DestPz);
PlanedPath(Lock.StepToSolve);
// do path!
if (PlanedMoves.Count > 0) return PlanedMoves.Dequeue();
}
}
// never throw on normal state
throw new Exception("Wtf?");
}
private void PlanedPath(Point[] Steps)
{
// add to plan
for (int i = 0; i < Steps.Length; i++)
{
PlanedMoves.Enqueue(Steps[i]);
}
}
private void PlanedPath(Puzzle StartPz, Puzzle TargetPz)
{
List<Point> Path = Navigator.FindPath(StartPz, TargetPz);
// add to plan
for (int i = 0; i < Path.Count; i++)
{
PlanedMoves.Enqueue(Path[i]);
}
}
private Puzzle FindBestPuzzleToSwap(Puzzle CentrPz)
{
Puzzle TruePlacePz = Puzzles.Find(Pz => Pz.OrderedNumer == CentrPz.CurrentNumber);
Puzzle BestPz = null;
int BestDistance = 0;
for (int i = 0; i < GameSteps.Length; i++)
{
Puzzle NierPz = Puzzles.Find(Pz => ((Pz.X == CentrPz.X + GameSteps[i].X) && (Pz.Y == CentrPz.Y + GameSteps[i].Y)));
if (NierPz == null) continue;
if (NierPz.IsPined) continue;
int Distance = TruePlacePz.MHDistance(NierPz);
if (BestPz == null)
{
BestDistance = Distance;
BestPz = NierPz;
continue;
}
if (Distance < BestDistance)
{
BestDistance = Distance;
BestPz = NierPz;
}
}
return BestPz;
}
private Puzzle FindWrongPuzzle()
{
for (int i = 0; i < SolvingSecuence.Length; i++)
{
Puzzle SecPz = Puzzles.Find(Pz => Pz.CurrentNumber == SolvingSecuence[i]);
// first unpined in solving sec
if (!SecPz.IsPined) return SecPz;
}
return null;
}
private bool PinTruePuzzles()
{
// unpin all
for (int i = 0; i < Puzzles.Count; i++)
{
Puzzles[i].IsPined = false;
}
// pin
bool AllPined = true;
for (int i = 0; i < SolvingSecuence.Length; i++)
{
Puzzle SecPz = Puzzles.Find(Pz => Pz.OrderedNumer == SolvingSecuence[i]);
// stop pining on first wrong puzzle
if (!SecPz.IsTruePlace)
{
AllPined = false;
break;
}
SecPz.IsPined = true;
}
return AllPined;
}
public void Clear()
{
PlanedMoves.Clear();
}
}
public class PathSearch
{
// AStar path search. Extremely naive realization for one task.
private Stack<NodeSearch> OpenedNodes = new Stack<NodeSearch>();
private List<NodeSearch> Nodes = new List<NodeSearch>();
private Point[] Steps;
private const float StepCost = 1f;
private enum NodeState { Unknown, Open, Closed }
private class NodeSearch
{
public Puzzle Puzzle;
public Point Location
{
get { return new Point(Puzzle.X, Puzzle.Y); }
}
public int X
{
get { return Puzzle.X; }
}
public int Y
{
get { return Puzzle.Y; }
}
public bool IsWalkable
{
get { return !Puzzle.IsPined; }
}
public float G = 0f;
public NodeState State = NodeState.Unknown;
public NodeSearch ParentNode;
public NodeSearch(Puzzle Puzzle)
{
this.Puzzle = Puzzle;
}
public void Clear()
{
G = 0f;
State = NodeState.Unknown;
ParentNode = null;
}
}
public PathSearch(List<Puzzle> Puzzles, Point[] GameSteps)
{
this.Steps = GameSteps;
// bind puzzles to search nodes
for (int i = 0; i < Puzzles.Count; i++)
{
Nodes.Add(new NodeSearch(Puzzles[i]));
}
}
public List<Point> FindPath(Puzzle StartPz, Puzzle TargetPz)
{
List<Point> Path = new List<Point>();
NodeSearch Start = Nodes.Find(Ns => (Ns.Puzzle == StartPz));
if (Start == null) return Path;
NodeSearch Target = Nodes.Find(Ns => (Ns.Puzzle == TargetPz));
if (Target == null) return Path;
Start.State = NodeState.Open;
OpenedNodes.Push(Start);
bool PathFound = false;
while (OpenedNodes.Count > 0)
{
NodeSearch CurrentNode = OpenedNodes.Pop();
if (CurrentNode == Target)
{
PathFound = true;
break;
}
for (int i = 0; i < Steps.Length; i++)
{
NodeSearch NextNode = Nodes.Find(Ns => ((Ns.X == CurrentNode.X + Steps[i].X) && (Ns.Y == CurrentNode.Y + Steps[i].Y)));
if (NextNode == null) continue;
if (!NextNode.IsWalkable) continue;
if (NextNode.State == NodeState.Closed) continue;
if (NextNode.State == NodeState.Open)
{
float NewG = CurrentNode.G + StepCost;
if (NewG < NextNode.G)
{
NextNode.ParentNode = CurrentNode;
NextNode.G = NewG;
OpenedNodes.Push(NextNode);
}
}
else
{
// unknow node
NextNode.State = NodeState.Open;
NextNode.ParentNode = CurrentNode;
NextNode.G = CurrentNode.G + StepCost;
OpenedNodes.Push(NextNode);
}
}
CurrentNode.State = NodeState.Closed;
}
// restore path
if (PathFound)
{
NodeSearch CurentNode = Target;
while (CurentNode != Start)
{
Path.Add(CurentNode.Location);
CurentNode = CurentNode.ParentNode;
}
Path.Reverse();
}
// clear state
OpenedNodes.Clear();
for (int i = 0; i < Nodes.Count; i++)
{
Nodes[i].Clear();
}
return Path;
}
}</syntaxhighlight>
=={{header|C++}}==
| |||