關于什么是
PuzzleFifteen,參看WIKIPEDIA。
貼下我自己寫的代碼，現在只能是將倒著的順過來，還不知道如何初始化任意的可解的棋局及如何自動破解，歡迎大蝦能提點下。
/***************************************************************************
* fifteen.c
*
* Computer Science 50
* Problem Set 3
*
* Implements The Game of Fifteen (generalized to d x d).
*
* Usage: fifteen d
*
* whereby the board's dimensions are to be d x d,
* where d must be in [DIM_MIN,DIM_MAX]
*
* Note that usleep is obsolete, but it offers more granularity than
* sleep and is simpler to use than nanosleep; `man usleep` for more.
***************************************************************************/
#define _XOPEN_SOURCE 500
#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
// constants
#define DIM_MIN 3
#define DIM_MAX 9
// global board
int board[DIM_MAX][DIM_MAX];
int d;
// prototypes
void clear();
void greet();
void init();
void draw();
bool move();
bool won();
int
main(int argc, char *argv[])
{
// ensure proper usage
if (argc != 2)
{
printf("Usage: %s d\n", argv[0]);
return 1;
}
// greet user with instructions
greet();
// ensure valid dimensions
d = atoi(argv[1]);
if (d < DIM_MIN || d > DIM_MAX)
{
printf("Board must be between %d x %d and %d x %d, inclusive.\n",
DIM_MIN, DIM_MIN, DIM_MAX, DIM_MAX);
return 2;
}
// initialize the board
init();
// accept moves until game is won
while (true)
{
// clear the screen
clear();
// draw the current state of the board
draw();
// check for win
if (won())
{
printf("ftw!\n");
break;
}
// prompt for move
printf("Tile to move: ");
int tile = GetInt();
// move if possible, else report illegality
if (!move(tile))
{
printf("\nIllegal move.\n");
usleep(500000);
}
// sleep thread for animation's sake
usleep(500000);
}
// that's all folks
return 0;
}
/*
* void
* clear()
*
* Clears screen using ANSI escape sequences.
*/
void
clear()
{
printf("\033[2J");
printf("\033[%d;%dH", 0, 0);
}
/*
* void
* greet()
*
* Greets player.
*/
void
greet()
{
clear();
printf("WELCOME TO THE GAME OF FIFTEEN\n");
usleep(2000000);
}
/*
* void
* init()
*
* Initializes the game's board with tiles numbered 1 through d*d - 1
* (i.e., fills 2D array with values but does not actually print them).
*/
void
init()
{
// TODO
for(int i = 0; i < d; i++)
for(int j = 0; j < d; j++)
// do NOT initialize board[d-1][d-1]
if((i != d - 1) || (j != d - 1))
board[i][j] = (d - i) * d - j - 1;
if(d % 2 == 0)
{
board[d-1][d-2] = 2;
board[d-1][d-3] = 1;
}
}
/*
* void
* draw()
*
* Prints the board in its current state.
*/
void
draw()
{
// TODO
for(int i = 0; i < d; i++)
{
for(int j = 0; j < d; j++)
{
if((board[i][j] == 0))
printf(" \t");
else
printf("%2d\t",board[i][j]);
}
printf("\n");
}
}
/*
* bool
* move(int tile)
*
* If tile borders empty space, moves tile and returns true, else
* returns false.
*/
bool
move(int tile)
{
// TODO
//First found the 'tile'
for(int i = 0; i < d; i++)
for(int j = 0; j < d; j++)
if(board[i][j] == tile)
{
//validity check
//Check up
if(i - 1 >= 0)
if(board[i-1][j] == 0)
{
board[i-1][j] = board[i][j];
board[i][j] = 0;
return true;
}
//Check down
if(i + 1 < d)
if(board[i+1][j] == 0)
{
board[i+1][j] = board[i][j];
board[i][j] = 0;
return true;
}
//Check left
if(j - 1 >= 0)
if(board[i][j-1] == 0)
{
board[i][j-1] = board[i][j];
board[i][j] = 0;
return true;
}
//Check right
if(j + 1 < d)
if(board[i][j+1] == 0)
{
board[i][j+1] = board[i][j];
board[i][j] = 0;
return true;
}
}
return false;
}
/*
* bool
* won()
*
* Returns true if game is won (i.e., board is in winning configuration),
* else false.
*/
bool
won()
{
// TODO
static int solved[DIM_MAX][DIM_MAX];
static int once = 0;
if(once == 0)
{
for(int i = 0; i < d; i++)
for(int j = 0; j < d; j++)
// do NOT initialize board[d-1][d-1]
if((i != d - 1) || (j != d - 1))
solved[i][j] = i * d + j + 1;
once ++;
}
for(int i = 0; i < d; i++)
for(int j = 0; j < d; j++)
if(board[i][j] != solved[i][j])
return false;
return true;
}