Skip to content

Instantly share code, notes, and snippets.

@mattbasta
Created April 20, 2011 01:50
Show Gist options
  • Save mattbasta/930169 to your computer and use it in GitHub Desktop.
Save mattbasta/930169 to your computer and use it in GitHub Desktop.
tilegame.cpp
#include <cstdlib>
#include <iostream>
#include <cmath>
using namespace std;
int checkCompletion(int pos[3][3]);
int dist(int num, int x, int y);
int bestTile(int tiles[3][3], int & x, int & y);
void printBoard(int tiles[3][3]);
void cloneBoard(int board[3][3]);
/*
Returns a number. The closer to zero this number is, the more complete the
puzzle is. If the value of this number is zero, the puzzle is complete.
*/
int checkCompletion(int pos[3][3])
{
int total = 0;
for(int x=0;x<3;x++)
{
for(int y=0;y<3;y++)
{
if(pos[x][y]<0)
continue;
total += dist(pos[x][y], x, y);
}
}
return total;
}
/*
Determine the physical number of moves required to put a piece back where it
needs to be.
*/
int dist(int num, int x, int y)
{
int sXpos = 0, sYpos = 0; // The vars that will store where the num is
sXpos = ((num-1) % 3);
sYpos = ((num-1) / 3);
return abs(x - sXpos) + abs(y - sYpos);
}
/*
Determines the best tile to move.
*/
int bestTile(int tiles[3][3], int & x, int & y)
{
int bestX = -1, bestY = -1, bestDist = 0, curDist = 0, potentialDist = 0;
int px, py;
py = 0;
for(px=-1;px<=1;px+=2)
{
if(px + x < 0 || px + x > 2)
continue;
curDist = dist(tiles[y][px + x], px + x, y);
potentialDist = dist(tiles[y][px + x], x, y);
if(curDist-potentialDist<=0)
{
int tempBoard[3][3];
int tx,ty;
for(int ti=0;ti<3;ti++)
for(int tj=0;tj<3;tj++)
tempBoard[ti][tj] = tiles[ti][tj];
tempBoard[y][x] = tiles[y][px + x];
tempBoard[y][px + x] = -1;
tx = px+x;
ty = y;
curDist = bestTile(tiles, tx, ty);
}
if(curDist > bestDist)
{
bestX = px + x;
bestY = y;
bestDist = curDist;
}
}
px = 0;
for(py=-1;py<=1;py+=2)
{
if(py+y<0||py+y>2)
continue;
curDist = dist(tiles[y][px + x], x, py + y);
potentialDist = dist(tiles[py + y][x], x, y);
if(curDist-potentialDist<=0)
{
int tempBoard[3][3];
int ty, tx;
for(int ti=0;ti<3;ti++)
for(int tj=0;tj<3;tj++)
tempBoard[ti][tj] = tiles[ti][tj];
tempBoard[y][x] = tiles[py + y][x];
tempBoard[py + y][x] = -1;
ty = py + y;
tx = x;
curDist = bestTile(tiles, tx, ty);
}
if(curDist > bestDist)
{
bestX = x;
bestY = py + y;
bestDist = curDist;
}
}
x = bestX;
y = bestY;
return bestDist;
}
/*
Prints the game board to the screen.
*/
void printBoard(int tiles[3][3])
{
cout << endl << "-----" << endl;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(tiles[i][j]==-1)
cout << " ";
else
cout << tiles[i][j] << " ";
}
cout << endl;
}
cout << "-----" << endl;
}
int main(int argc, char *argv[])
{
int i[3][3] =
{
{1, 3, 6},
{4, -1, 7},
{2, 5, 8}
};
int x=1, y=1;
cout << bestTile(i,x,y) << endl;
printBoard(i);
system("PAUSE");
return EXIT_SUCCESS;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment