Snake, Snake, Snake
A. Fifth? Edition
This is the continued struggle for me to solve 15 puzzle. The most efforts of mine is to construct
a snake which can eat node and grow by swim around board. But I have to admit this idea is dead as
snake will be stuck when the dimension of board becomes too small. So, it is useless in solving 15
puzzle. I have given up this approach.
The 15 puzzle? Or the path for a node to move? Or the path for a cluster of number to move, like snake? Or the
number cluster itself?
Since I have to memorize all coordinate I have been in the labyrinth, there is no better way than a simple DFS. I would not
bother to find any algorithm, as all algorithms require you to memorize the position you have been to.
E.Further improvement
The next step is to implement the move a single node on board, then the whole cluster move.
F.File listing
1. node.h
2. node.cpp
3. cluster.h
4. cluster.cpp
5. board.h
6. board.cpp
7. main.cpp
file name: node.h
#ifndef NODE_H
#define NODE_H
#include <stdio.h>
#include <math.h>
const int BoardSize=4;
const int MaxNodesLength=BoardSize*4;
//const int MaxBoardSize=BoardSize*4;
const int MinimumRotateSize=2;
//#define abs(x) (x>=0?x:-x)
enum Direction
{
U, R , D , L, None
};
enum Position
{
Right, DownRight, Down, DownLeft, Left, UpLeft, Up, UpRight
};
//class Puzzle;
class Coord
{
friend class Board;
private:
int row;
int col;
public:
const Coord& operator=(const Coord& rhs);
bool operator==(const Coord& rhs) const;
bool operator!=(const Coord& rhs) const ;
bool neighbour(const Coord& rhs) const;
void move(Direction dir);
Coord(int r=-1, int c=-1);
};
#endif
file name: node.cpp
#include "node.h"
#include <stdio.h>
#include <math.h>
char dirStr[4]={'U', 'D' , 'L' , 'R'};
Coord::Coord(int r, int c)
{
row=r;
col=c;
}
void Coord::move(Direction dir)
{
switch (dir)
{
case U:
row--;
break;
case D:
row++;
break;
case L:
col--;
break;
case R:
col++;
break;
}
}
//assignment of coord
const Coord& Coord::operator =(const Coord& rhs)
{
row=rhs.row;
col=rhs.col;
return *this;
}
bool Coord::operator !=(const Coord& rhs) const
{
return !(this->operator==(rhs));
}
bool Coord::operator ==(const Coord& rhs) const
{
if (row==rhs.row&&col==rhs.col)
{
return true;
}
else
{
return false;
}
}
bool Coord::neighbour(const Coord& rhs) const
{
//next row
if (abs(row-rhs.row)==1)
{
return col==rhs.col;
}
else
{
//same row
if (row==rhs.row)
{
//next col
return abs(col-rhs.col)==1;
}
else
{
//nothing
return false;
}
}
}
file name: cluster.h
#include <stdio.h>
#include "node.h"
class Cluster
{
private:
int length;
Coord nodes[MaxNodesLength];
//bool ascending;
int head;//this is the head pos, as head is moving
void initialize();
public:
int getLength(){return length;}
void clear();
const Coord getHead();
bool step(const Coord& newPos);//must be a valid move
bool step(Direction dir);
bool addTail(const Coord& newTail);
bool isNode(const Coord& rhs);
bool addHead(const Coord& newHead);
bool removeHead();
bool removeTail();
bool setHead(const Coord& first);
void swapHeadTail();
Coord operator[](int index) const;
Coord& operator[](int index);
int index(const Coord& pos) const;
Cluster();
Cluster& operator=(const Cluster& dummy);
};
file name: cluster.cpp
#include "cluster.h"
#include <math.h>
const Coord Cluster::getHead()
{
return nodes[head];
}
Cluster& Cluster::operator =(const Cluster& dummy)
{
initialize();
for (int i=0; i<dummy.length; i++)
{
addTail(dummy[i]);
}
return *this;
}
void Cluster::swapHeadTail()
{
Coord hold;
int step=-1, headIndex, tailIndex;
do
{
step++;
if (step>length/2)
{
break;
}
headIndex=head-step>=0?head-step:head-step+MaxNodesLength;
tailIndex=(head+length-step)%MaxNodesLength;
hold=nodes[headIndex];
nodes[headIndex]=nodes[tailIndex];
nodes[tailIndex]=hold;
}while (nodes[headIndex]!=nodes[tailIndex]);
}
bool Cluster::removeTail()
{
if (length==0)
{
return false;
}
else
{
length--;
if (length==0)
{
head=-1;
}
}
return true;
}
bool Cluster::removeHead()
{
if (length==0)
{
return false;
}
else
{
length--;
if (length==0)
{
head=-1;
}
else
{
head=(head+1)%MaxNodesLength;
}
}
return true;
}
void Cluster::clear()
{
initialize();
}
bool Cluster::step(Direction dir)
{
Coord dummy;
dummy=nodes[head];
dummy.move(dir);
return step(dummy);
}
//valid for two meanings:
//1. not eat any node
//2. adjacent to head
bool Cluster::step(const Coord& newPos)
{
//don't bite your tail or body
if (isNode(newPos))
{
return false;
}
//can you bite too far?
if (!nodes[head].neighbour(newPos))
{
return false;
}
head--;
if (head<0)
{
head+=MaxNodesLength;
}
nodes[head]=newPos;
return true;
}
bool Cluster::isNode(const Coord& rhs)
{
for (int i=0; i<length; i++)
{
if (this->operator[](i)==rhs)
{
return true;
}
}
return false;
}
void Cluster::initialize()
{
head=-1;
length=0;
}
Cluster::Cluster()
{
initialize();
}
//unless it is first time or cleared, you cannot set head
//when it already has one
bool Cluster::setHead(const Coord& first)
{
if (head!=-1)
{
return false;
}
head=0;
length=1;
nodes[head]=first;
return true;
}
bool Cluster::addTail(const Coord& newTail)
{
if (length==0)
{
setHead(newTail);
return true;
}
int tail;
if (length==MaxNodesLength)
{
return false;
}
if (isNode(newTail))
{
return false;
}
/*
if (!nodes[tail].neighbour(newTail))
{
return false;
}
*/
tail=(head+length)%MaxNodesLength;
length++;
nodes[tail]=newTail;
return true;
}
int Cluster::index(const Coord& pos) const
{
for (int i=0; i<length; i++)
{
if (this->operator [](i)==pos)
{
return i;
}
}
return -1;
}
bool Cluster::addHead(const Coord& newHead)
{
if (length==0)
{
setHead(newHead);
return true;
}
if (length==MaxNodesLength)
{
return false;
}
if (isNode(newHead))
{
return false;
}
if (!nodes[head].neighbour(newHead))
{
return false;
}
length++;
head--;
if (head<0)
{
head+=MaxNodesLength;
}
nodes[head]=newHead;
return true;
}
Coord& Cluster::operator [](int index)
{
return nodes[(head+index)%MaxNodesLength];
}
Coord Cluster::operator [](int index) const
{
return nodes[(head+index)%MaxNodesLength];
}
file name: board.h
#include "cluster.h"
#include "node.h"
const MaxFrameLength=BoardSize*2-1;
class Board
{
friend class Cluster;
//friend class Solve;
private:
int board [BoardSize][BoardSize];
bool map[BoardSize][BoardSize];
bool restrict[BoardSize][BoardSize];
Cluster path;
int size;
void initialize();
bool valid(const Coord& pos);
Direction findDir(const Coord& start, const Coord& end);
//Direction findNextDir(const Coord& curr, Direction dir);
bool impasse(const Coord& curr, Direction dir);
bool doPathFinding(const Coord& curr, const Coord& end, Direction dir);
//the below are for puzzle
int frame[MaxFrameLength];
int frameLength;
Cluster spacePath;
Cluster nodePath;
Cluster snakePath;
Cluster snake;
Cluster framePath;
Coord space;
bool moveNode(Coord& current, const Coord& dest);
bool getSpacePath(const Coord& dest);
bool moveSpace(const Coord& dest);
void swapNode(Coord& target);//the other one is always the space
void snakeGrow(const Coord& newHead);
void setFrame(int level);//set number string
void makeSnake(int level);
Coord findNode(int value);
bool snakeSwim(const Coord& dest);
void snakeStep(const Coord& dest);
bool snakeBite(const Coord& dest);
bool snakeSwim();
bool canStep(const Coord& dest);
void showSnake(const Coord& dest);
public:
Board(int theSize=BoardSize);
bool solve();
void display();
void displayPath(bool showPath=true);
bool pathFinding(const Coord& start, const Coord& end);
//bool pathFinding(const Coord& end);
bool pathFinding2(const Coord& start, const Coord& end);
void setRestrict(const Coord& pos);
void resetRestrict(const Coord& pos);
};
file name: board.cpp
#include "board.h"
int settings[BoardSize][BoardSize]=
{
{1, 5, 7, 3 },
{4, 10, 0, 2 },
{8, 11, 14, 9},
{12, 13, 6, 15}
};
void Board::swapNode(Coord& target)
{
int hold;
bool bHold;
Coord temp;
bHold=restrict[target.row][target.col];
restrict[target.row][target.col]=restrict[space.row][space.col];
restrict[space.row][space.col]=bHold;
hold=board[space.row][space.col];//0
board[space.row][space.col]=board[target.row][target.col];
board[target.row][target.col]=hold;
temp=space;
space=target;
target=temp;
}
bool Board::getSpacePath(const Coord& dest)
{
if (pathFinding(space, dest))
{
spacePath=path;
spacePath.addHead(dest);
return true;
}
else
{
printf("error! cannot find space path for (%d,%d)\n", dest.row, dest.col);
return false;
}
}
bool Board::moveSpace(const Coord& dest)
{
Coord curr;
if (getSpacePath(dest))
{
for (int i=spacePath.getLength()-1; i>=0; i--)
{
curr=spacePath[i];
swapNode(curr);
}
//path does not include the start and dest
//swapNode(dest);
return true;
}
return false;
}
bool Board::moveNode(Coord& current, const Coord& dest)
{
Coord curr;
restrict[current.row][current.col]=true;
if (pathFinding(current, dest))
{
//pathFinding didn't give you the full path, it excludes the dest
nodePath=path;
nodePath.addHead(dest);
for (int i=nodePath.getLength()-1; i>=0; i--)
{
curr=nodePath[i];
moveSpace(curr);
swapNode(current);
}
return true;
}
return false;
}
void Board::setFrame(int level)
{
/*
int r=level, c=0;
Coord curr;
frameLength=size;
framePath.clear();
for (int i=0; i<frameLength; i++)
{
frame[i]=r*size+c;
curr.row=r;
curr.col=c;
framePath.addTail(curr);
}
*/
int r=0, c=level;
Coord curr;
//bool begin=false;
frameLength=(level+1)*2-1;
framePath.clear();
for (int i=0; i<frameLength; i++)
{
frame[i]=r*size+c;
curr.row=r;
curr.col=c;
framePath.addTail(curr);
if (r<level)
{
r++;
}
else
{
c--;
}
}
}
void Board::displayPath(bool showPath)
{
Coord curr;
int index;
for (int i=0; i<size; i++)
{
for (int j=0; j<size; j++)
{
if (restrict[i][j])
{
printf("%c%c\t", '@','@');
}
else
{
curr.row=i;
curr.col=j;
index=path.index(curr);
if (index!=-1)
{
if (showPath)
{
printf("%02d\t", index);
}
else
{
printf("%02d\t", board[i][j]);
}
}
else
{
printf("%c%c\t", '*', '*');
}
}
}
printf("\n");
}
}
Coord Board::findNode(int value)
{
Coord result;
for (int i=0; i<size; i++)
{
for (int j=0; j<size; j++)
{
if (board[i][j]==value)
{
result.row=i;
result.col=j;
break;
}
}
}
return result;
}
void Board::snakeGrow(const Coord& newHead)
{
snake.addHead(newHead);
restrict[newHead.row][newHead.col]=true;
}
bool Board::snakeBite(const Coord& dest)
{
Coord curr;
bool canMove=false;
restrict[dest.row][dest.col]=true;
if (!snakeSwim(dest))
{
while (true)
{
canMove=false;
for (int i=0; i<4; i++)
{
curr=snake[0];
curr.move((Direction)i);
if (!snake.isNode(curr))
{
canMove=true;
snakeStep(curr);
if (snakeSwim(dest))
{
snake.addHead(dest);
return true;
}
}
}
if (!canMove)
{
return false;
}
}
}
else
{
//swim ok
snake.addHead(dest);
return true;
}
//showSnake(dest);
}
void Board::showSnake(const Coord& dest)
{
printf("snake want to bite (%d,%d)\n", dest.row, dest.col);
display();
}
bool Board::solve()
{
makeSnake(size-1);
return true;
}
void Board::makeSnake(int level)
{
Coord curr, newHead, dest;
snake.clear();
setFrame(level);
curr=findNode(frame[0]);
//snake.addHead(curr);
snakeGrow(curr);
newHead=snake[0];//the head
//all other pieces must swim to head
for (int i=1; i<frameLength; i++)
{
curr=findNode(frame[i]);
//for test
showSnake(curr);
if (!snakeBite(curr))
{
printf("snake said,\"I am stuck\"\n");
}
/*
if (pathFinding(curr, newHead))
{
//nodePath=path;
//dest=nodePath[0];
dest=path[0];//only need the head which is the last pos
moveNode(curr, dest);//curr is moving
//snake.addHead(curr);
snakeGrow(curr);
}
else
{
//we may need to move snake a bit
//snakeSwim();//???where to
//printf("can this really happen? I mean the length of snake is reduced\n");
snakeSwim();
}
*/
}
}
bool Board::snakeSwim(const Coord& dest)
{
Coord theHead;
//showSnake(dest);
if (snake.isNode(dest))
{
printf("snake said :\"cannot bite myself!\"\n");
return false;
}
else
{
theHead=snake[0];
if (pathFinding(theHead, dest))
{
snakePath=path;
//snakePath.addHead(dest);
for (int i=snakePath.getLength()-1; i>=0; i--)
{
snakeStep(snakePath[i]);
}
return true;
}
return false;
}
}
void Board::snakeStep(const Coord& dest)
{
moveSpace(dest);
for (int i=0; i<snake.getLength(); i++)
{
swapNode(snake[i]);//restrict is changed
}
}
//this is the rather direct path
bool Board::pathFinding(const Coord& start, const Coord& end)
{
Coord curr;
Direction dir;
path.clear();
if (start==end)
{
return true;
}
//path.setHead(start);
//curr=path.getHead();
curr=start;
dir=findDir(curr, end);
curr.move(dir);
while (curr!=end)
{
if (valid(curr))
{
path.addHead(curr);
//curr=path.getHead();//??not necessary
}
else
{
//it must be something restricted and it is required
//a more generate way of finding path
for (int i=0; i<size; i++)
{
for (int j=0; j<size; j++)
{
map[i][j]=false;
}
}
map[start.row][start.col]=true;//I am here!!!
path.clear();//restart!!
//path.setHead(start);//do not include start itself
return pathFinding2(start, end);
}
dir=findDir(curr, end);
curr.move(dir);
}
return true;
}
bool Board::pathFinding2(const Coord& start, const Coord& end)
{
Coord curr;
for (int dir=0; dir<4; dir++)
{
curr=start;
curr.move((Direction)dir);
if (curr==end)
{
return true;
}
if (valid(curr))
{
if (!map[curr.row][curr.col])
{
path.addHead(curr);
map[curr.row][curr.col]=true;
if (pathFinding2(curr, end))
{
return true;
}
else
{
path.removeHead();
//anyway, I have been here before
//map[curr.row][curr.col]=false;
}
}
}
}
return false;
}
void Board::setRestrict(const Coord& pos)
{
restrict[pos.row][pos.col]=true;
}
void Board::resetRestrict(const Coord& pos)
{
restrict[pos.row][pos.col]=false;
}
bool Board::impasse(const Coord& curr, Direction dir)
{
Coord dummy;
dummy=curr;
dummy.move(dir);
return valid(dummy);
}
/*
//this way has a fatal problem of circling
Direction Board::findNextDir(const Coord& curr, Direction dir)
{
Direction result=dir, turnLeft;
//first try old direction,
while (impasse(curr, result))
{
//cannot advance, so turn right, or next dir
result=(Direction)((result+1)%4);
}
if (result!=dir)//means we already turned to right, so, return
{
return result;
}
else
{
//we must turn to left BEFORE we run into wall
turnLeft=result;//initialize
do
{
result=turnLeft;//must!!!
turnLeft=(Direction)(result-1<0?3:result-1);
}while (!impasse(curr, turnLeft));
return result;//result is the dir before turning left
}
}
bool Board::pathFinding(const Coord& end)
{
Coord curr;
Direction dir;
curr=path.getHead();
//in what case, should I return false? a dead end?
dir=findDir(curr, end);
while (curr!=end)
{
dir=findNextDir(curr, dir);
curr.move(dir);
path.addHead(curr);
curr=path.getHead();
}
return true;
}
*/
Direction Board::findDir(const Coord& start, const Coord& end)
{
int rOff, cOff;
rOff=end.row-start.row;
cOff=end.col-start.col;
if (abs(rOff)>abs(cOff))
{
return rOff>0?D:U;
}
else
{
return cOff>0?R:L;
}
}
Board::Board(int theSize)
{
size=theSize;
initialize();
}
bool Board::valid(const Coord& pos)
{
if (pos.col<0||pos.row<0||pos.col>=size||pos.row>=size)
{
return false;
}
return !restrict[pos.row][pos.col];
}
void Board::display()
{
Coord curr;
printf("the size of board is %d\n", size);
for (int i=0; i<size; i++)
{
for(int j=0; j<size; j++)
{
curr.row=i;
curr.col=j;
if (snake.isNode(curr))
{
printf("%6d%c", board[i][j], '*');
}
else
{
printf("%6d", board[i][j]);
}
}
printf("\n");
}
}
void Board::initialize()
{
for (int i=0; i<size; i++)
{
for (int j=0; j<size; j++)
{
board[i][j]=settings[i][j];
restrict[i][j]=false;
if (board[i][j]==0)
{
space.row=i;
space.col=j;
}
}
}
snake.clear();
path.clear();
nodePath.clear();
framePath.clear();
snakePath.clear();
}
file name: main.cpp
#include <stdio.h>
#include "board.h"
#include "node.h"
int main()
{
Board B;
Coord start(0,3), end(3,2), temp(2,2), temp1(3,3), temp2(1,2), temp3(1,1);
B.display();
/*
B.setRestrict(temp);
B.setRestrict(temp1);
B.setRestrict(temp2);
B.setRestrict(temp3);
if (B.pathFinding(start, end))
{
B.displayPath();
}
else
{
printf("no way!\n");
}
*/
B.solve();
return 0;
}
The result is like following:
The following is a part of debug result and pls note that when snake wants to bite node (0,1) which has
value of 13, it gets stuck because the '0' is at (0,0) and snake head is at (1,0). The head of snake and
its target together stop "0" from moving!
the size of board is 4
1 5 7 3
4 10 0 2
8 11 14 9
12 13 6 15
snake want to bite (0,2)
the size of board is 4
1 5 7 3*
4 10 0 2
8 11 14 9
12 13 6 15
snake want to bite (2,1)
the size of board is 4
1 5 7* 3*
4 10 0 2
8 11 14 9
12 13 6 15
snake want to bite (2,3)
the size of board is 4
5 10 0 2
1 7* 3* 9
4 11* 14 15
8 12 13 6
snake want to bite (3,2)
the size of board is 4
1 5 10 2
4 3* 0 9
8 7* 11* 15*
12 13 14 6
snake want to bite (0,1)
the size of board is 4
0 13 9 2
3* 12 10 5
7* 8 1 4
11* 15* 14* 6
error! cannot find space path for (2,2)
snake want to bite (1,0)
the size of board is 4
11* 13* 9 2
12 14* 15* 5
8 10 1 4
0 3* 7* 6