Code: Alles auswählen
#include <stdio.h>
#include <stdlib.h>
const int BOARD_SIZE = 9;
#define TRUE 1
#define FALSE 0
void writeBoard(int *board)
{
int i, j, v;
printf("+-");
for (i=0; i<BOARD_SIZE * 2; i++)
printf("-");
printf("+\n");
for (j=0; j<BOARD_SIZE; j++)
{
printf("| ");
for (i=0; i<BOARD_SIZE; i++)
{
v = board[j * BOARD_SIZE + i];
if (v<0)
{
printf("+ ");
}
else
{
printf("X ");
}
}
printf("|\n");
}
printf("+-");
for (i=0; i<BOARD_SIZE * 2; i++)
printf("-");
printf("+\n");
}
void initBoard(int *board, int value)
{
int i;
for (i=0; i<BOARD_SIZE * BOARD_SIZE; i++)
board[i] = value;
}
void copyBoard(int *board, int *target)
{
int i;
for (i=0; i<BOARD_SIZE * BOARD_SIZE; i++)
target[i] = board[i];
}
void setBoard(int *board, int x, int y, int value)
{
board[y * BOARD_SIZE + x] = value;
}
int getBoard(int *board, int x, int y)
{
return board[y * BOARD_SIZE + x];
}
int getRowCount(int *board, int y)
{
int i, mpr = 0;
for (i=0; i<BOARD_SIZE; i++)
{
if (getBoard(board, i, y)>0) mpr++;
}
return mpr;
}
int getColumnCount(int *board, int x)
{
int i, mpc = 0;
for (i=0; i<BOARD_SIZE; i++)
{
if (getBoard(board, x, i)>0) mpc++;
}
return mpc;
}
int getRowMenDistance(int *board, int y)
{
int i, men = 0, distance = 0;
for (i=0; i<BOARD_SIZE; i++)
{
if (men==1)
{
distance+=1;
}
if (getBoard(board, i, y)>0)
{
men+=1;
}
}
return (men==2) ? distance : -1;
}
int getColumnMenDistance(int *board, int x)
{
int i, men = 0, distance = 0;
for (i=0; i<BOARD_SIZE; i++)
{
if (men==1)
{
distance+=1;
}
if (getBoard(board, x, i)>0)
{
men+=1;
}
}
return (men==2) ? distance : -1;
}
int canSetMan(int *board, int x, int y)
{
// feld selbst besetzt
if (getBoard(board, x, y)>0)
return FALSE;
// links besetzt?
if (x>0 && getBoard(board, x-1, y)>0)
return FALSE;
// rechts besetzt?
if (x<BOARD_SIZE-1 && getBoard(board, x+1, y)>0)
return FALSE;
// oben besetzt?
if (y>0 && getBoard(board, x, y-1)>0)
return FALSE;
// unten besetzt?
if (y<BOARD_SIZE-1 && getBoard(board, x, y+1)>0)
return FALSE;
// men per row
if (getRowCount(board, y)>1)
return FALSE;
// men per column
if (getColumnCount(board, x)>1)
return FALSE;
// strassenblock li-ob
if (x>0 && y>0 && getBoard(board, x-1, y-1)>0)
return FALSE;
// strassenblock re-ob
if (x<BOARD_SIZE-1 && y>0 && getBoard(board, x+1, y-1)>0)
return FALSE;
// strassenblock li-un
if (x>0 && y<BOARD_SIZE-1 && getBoard(board, x-1, y+1)>0)
return FALSE;
// strassenblock re-un
if (x<BOARD_SIZE-1 && y<BOARD_SIZE-1 && getBoard(board, x+1, y+1)>0)
return FALSE;
return TRUE;
}
int checkEndConditions(int *board)
{
int i;
int distance;
int dist_4 = 0;
for(i=0; i<BOARD_SIZE; i++)
{
// check rows
distance = getRowMenDistance(board, i);
if (distance <= 0)
return FALSE;
if (distance == 5)
{
dist_4+=1;
}
// check columns
distance = getColumnMenDistance(board, i);
if (distance <= 0)
return FALSE;
if (distance == 5)
{
dist_4+=1;
}
}
if (dist_4 != 3)
return FALSE;
return TRUE;
}
void trySetManRecursive(int *board, int pos, int level)
{
int x, y;
do
{
y = pos / BOARD_SIZE;
x = pos % BOARD_SIZE;
if (canSetMan(board, x, y))
{
int current_board[ BOARD_SIZE * BOARD_SIZE ];
copyBoard(board, current_board);
setBoard(current_board, x, y, 1);
if (level==0)
{
printf("ROOT LEVEL MOVE\n");
writeBoard(current_board);
}
if (pos<BOARD_SIZE*BOARD_SIZE)
{
trySetManRecursive(current_board, pos+1, level+1);
}
if (checkEndConditions(current_board))
{
printf("\nSOLUTION!\n\n");
writeBoard(current_board);
printf("\n\n");
}
}
pos++;
}
while (pos<BOARD_SIZE*BOARD_SIZE);
}
int main (int argc, const char * argv[]) {
int board[ BOARD_SIZE * BOARD_SIZE ];
// setup
initBoard(board, -1);
setBoard(board, 0, 0, 1);
setBoard(board, 3, 4, 1);
trySetManRecursive(board, 2, 0);
printf("END STATE!\n");
writeBoard(board);
return 0;
}
