برنامه ی پازل به صورت برنامه نویسی back tracking :
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// N should be >= 3
#define N 4
int board[N][N];
int showBoard() {
int i,val;
int row,col;
for ( row=0; row<N ; row++)
{
for ( col=0; col<N; col++)
{
if (board[row][col] == N*N){
printf(" *");
}
else {
printf("% 4d", board[row][col]);
}
}
printf("\n");
}
return 0;
}
int findKey(int val, int *v_f, int *v_c) {
int row,col;
*v_f = 0;
*v_c = 0;
if (val >= (N*N))
{
return 1;
}
for ( row=0; row<N ; row++)
{
for ( col=0; col<N; col++)
{
if (board[row][col] == val){
*v_f = row + 1;
*v_c = col + 1;
return 0;
}
}
}
return 1;
}
int findEmpty(int *v_f, int *v_c) {
int row,col;
*v_f = 0;
*v_c = 0;
for ( row=0; row<N ; row++)
{
for ( col=0; col<N; col++)
{
if (board[row][col] == N*N){
*v_f = row + 1;
*v_c = col + 1;
return 0;
}
}
}
return 1;
}
int move(int val) {
int row,col,filv,colv;
int i;
i=findKey(val, &row, &col);
i=findEmpty(&filv, &colv);
if ((row + 1 == filv && col == colv) ||
(row - 1 == filv && col == colv) ||
(row == filv && col + 1 == colv) ||
(row == filv && col - 1 == colv) )
{
board[row - 1][col - 1] = N*N;
board[filv - 1][colv - 1] = val;
return 0;
}
return 1;
}
int loadOrderedBoard() {
int row,col;
srand( (unsigned)time( NULL ) );
for ( row=0; row<N ; row++)
{
for ( col=0; col<N; col++)
{
board[row][col] = row * N + col;
}
}
return 0;
}
int gameOver() {
int row,col;
for ( row=0; row<N ; row++)
{
for ( col=0; col<N; col++)
{
if (board[row][col] != row * N + col + 1)
{
return 1;
}
}
}
return 0;
}
int checkParity() {
int i,j,paridad,dato;
paridad = 0;
for (i=0; i<(N*N) -1; i++)
{
dato = board[i/N][i%N];
if (dato != 16)
{
for (j=i+1; j<(N*N); j++)
{
if (board[j/N][j%N] < dato )
{
paridad++;
}
}
}
else {
paridad += (i/N) + 1;
}
}
return paridad % 2;
}
int fixParity()
{
int buf;
if (board[0][0] != (N*N) && board[0][1] != (N*N))
{
buf = board[0][0];
board[0][0] = board[0][1];
board[0][1] = buf;
}
else {
buf = board[1][0];
board[1][0] = board[1][1];
board[1][1] = buf;
}
}
int cheat()
{
int buf;
buf = board[N-1][N-2];
board[N-1][N-2] = board[N-1][N-3];
board[N-1][N-3] = buf;
return 0;
}
int loadBoard()
{
int i,j;
int base[N][N];
for (i=0; i<N*N; i++)
{
base[i/N][i%N] = 0;
}
srand((unsigned)time(NULL));
i=0;
while (i < N*N)
{
j = (int) ((float) (N*N) * rand() / (RAND_MAX + 1.0));
if (base[j/N][j%N] == 0)
{
base[j/N][j%N] = j+1;
board[i/N][i%N] = j+1;
i++;
}
}
}
int main()
{
int i, moves, option, play;
printf("1- Load random Board\n");
printf("2- Load ordered Board\n");
scanf("%d", &option);
switch (option)
{
case 1: loadBoard();
break;
case 2: loadOrderedBoard();
break;
default:
printf("I don't get that option!\n");
return 0;
break;
}
showBoard();
if (checkParity() != 0)
{
printf("ODD parity - No solution Board!\n");
printf("1- Fix Parity\n");
printf("2- Leave it\n");
scanf("%d", &option);
switch (option)
{
case 1: fixParity();
break;
case 2:
break;
default:
printf("I don't get that option!\n");
return 0;
break;
}
showBoard();
}
moves = 0;
play = 0;
do
{
printf("1 - %d to move\n", N*N-1);
printf("0 to exit\n");
printf("%d to cheat\n", N*N);
printf("Option: ");
scanf("%d", &play);
if (play == N*N)
{
cheat();
}
else if (move(play) == 0)
{
moves ++;
};
showBoard();
if (gameOver() == 0)
{
printf("GAME COMPLETED IN %03d MOVES!\n", moves);
play = 0;
}
printf("\n");
}while (play != 0);
}
