Seite 18 von 20

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 00:08
von Bluecat
Bitte sehr. Das Programm ist überhaupt nicht optimiert und daher recht übersichtlich... ;)

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;
}

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 00:10
von muetze86
Bluecat hat geschrieben:Bitte sehr. Das Programm ist überhaupt nicht optimiert und daher recht übersichtlich... ;)

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;
}





:shock:

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 00:15
von Andro19
@ Bluecat und ollipolli

Vielen lieben Dank :-D

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 00:16
von ollipolli

Code: Alles auswählen

<?php

$rows = array_fill(0,9,2);
$cols = array_fill(0,9,2);
$feld = array_fill(0,9,array_fill(0,9,0));
$feld[0][0] = 1;
$feld[4][3] = 1;
$cols[0] = 1;
$rows[0] = 1;
$cols[3] = 1;
$rows[4] = 1;

place(16,-1,-1,$feld,$rows,$cols,3);

function place($n,$minrow,$mincol,$feld,$rows,$cols,$dist4)
{
	for ($k = 0; $k < $minrow; $k++)
	{
		if ($rows[$k])
			return;
	}
	if ($n == 0)
	{
		if ($dist4 == 0)
		{
			$m = 1;
			for ($r=0; $r<9; $r++)
			{
				$c1 = -1;
				$c2 = -1;
				for ($c=0; $c<9; $c++)
				{
					if ($feld[$r][$c])
					{
						if ($c1 == -1)
						{
							$c1 = $c;
						}
						else
						{
							$c2 = $c;
						}
					}
					echo $feld[$r][$c] ? 'X' : '.';
				}
				$m *= ($c2-$c1-1);
				echo "\t" . ($c2-$c1-1) . "\n";
			}
			echo "\n" . $m . "\n";
		}
	}
	else
	{
		for ($r=0; $r<9; $r++)
		{
			for ($c=0; $c<9; $c++)
			{
				if ($r < $minrow) continue;
				if ($r == $minrow && $c < $mincol) continue;
				if ($rows[$r] && $cols[$c] && $feld[$r][$c] == 0)
				{
					$possible = true;
					$dist4decrease = 0;

					if ($r>0 && $feld[$r-1][$c]) $possible = false;
					if ($c>0 && $feld[$r][$c-1]) $possible = false;
					if ($r<8 && $feld[$r+1][$c]) $possible = false;
					if ($c<8 && $feld[$r][$c+1]) $possible = false;
					if ($r>0 && $c>0 && $feld[$r-1][$c-1]) $possible = false;
					if ($r>0 && $c<8 && $feld[$r-1][$c+1]) $possible = false;
					if ($r<8 && $c>0 && $feld[$r+1][$c-1]) $possible = false;
					if ($r<8 && $c<8 && $feld[$r+1][$c+1]) $possible = false;
					if ($r > 4 && $feld[$r-5][$c]) $dist4decrease++;
					if ($c > 4 && $feld[$r][$c-5]) $dist4decrease++;
					if ($r < 4 && $feld[$r+5][$c]) $dist4decrease++;
					if ($c < 4 && $feld[$r][$c+5]) $dist4decrease++;
					if ($dist4 < $dist4decrease) $possible = false;

					if ($possible)
					{
						$rows[$r]--;
						$cols[$c]--;
						$feld[$r][$c] = 1;
						place($n-1, $r, $c, $feld, $rows, $cols, $dist4 - $dist4decrease);
						$rows[$r]++;
						$cols[$c]++;
						$feld[$r][$c] = 0;
					}
				}
			}
		}
	}
}

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 00:16
von Roger7520
Tja ich hab mal einfach Excel (bzw. Calc vom Open Office) genommen, da konnte man die Regel 6 am besten sehen wie ich fand. Hatte es dann auch recht schnell raus und hatte auch nicht so einen hohen Papierverbrauch. :D

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 00:17
von elfant
Ich danke Dir für das Programm, Bluecat.

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 00:19
von Nikioko
Lösung:

X----X--- 4
--X----X- 4
X---X---- 3
------X-X 1
-X-X----- 1
-----X-X- 1
-X-X----- 1
------X-X 1
--X-X---- 1

116154333

Lösung: 48

http://de.wikipedia.org/wiki/American_S ... II-Tabelle

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 00:22
von Bluecat
elfant hat geschrieben:Ich danke Dir für das Programm, Bluecat.
Gern geschehen. Es gibt sicher -ähm- kompaktere Lösungen, aber so vertu ich mich nicht so leicht ;)

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 00:26
von Einzelkämpfer
Nikioko hat geschrieben: Lösung: 48

http://de.wikipedia.org/wiki/American_S ... II-Tabelle
ASCII-Code? #-o

Musste man nicht draufkommen, oder? Naja, war ja auch für die Lösung nicht wichtig.

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 00:46
von Antarael

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 00:59
von Shootingstar
Die Lösung, die ich eingeschickt habe, war zwar falsch, aber irgendwie taucht die jetzt in meiner Liste eingeschickter Lösungen gar nicht auf - die Bestätigungs-Mail habe ich aber erhalten. Hat da etwa jemand meine Idee geklaut? :wink:

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 08:37
von Orlando
Jan ist mittlerweile Ehrenpräsident in der "Vereinigung subtiler Andeutungen und doppeldeutiger Botschaften e.V." :mrgreen:

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 08:53
von Stumpfi
Erklärt jetzt noch jemand die Überschrift, bitte? Und bin ich die einzige, die keine Bestätigungsmails mehr bekommt?

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 10:12
von S-Made
Nikioko hat bereits oben den Titel erklärt, indem er auf die ASCII Tabelle verwiesen hat:
http://de.wikipedia.org/wiki/American_S ... II-Tabelle

Das ASCII-Zeichen 0 entspricht der Dezimalzahl 48.

Re: Tag 12 - Die Lösung ist 0

Verfasst: 13.12.2010, 10:29
von Nikioko
Roger7520 hat geschrieben:Tja ich hab mal einfach Excel (bzw. Calc vom Open Office) genommen, da konnte man die Regel 6 am besten sehen wie ich fand. Hatte es dann auch recht schnell raus und hatte auch nicht so einen hohen Papierverbrauch. :D
Und wenn man ein 9x9-Raster mit Würfeln belegt und darauf achtet, dass keine 2 Würfel mit den Kanten oder Ecken aneinander stoßen, hat man das auch recht schnell. ;-)
S-Made hat geschrieben:Nikioko hat bereits oben den Titel erklärt, indem er auf die ASCII Tabelle verwiesen hat:
http://de.wikipedia.org/wiki/American_S ... II-Tabelle

Das ASCII-Zeichen 0 entspricht der Dezimalzahl 48.
Ja, aber fairerweise habe nicht ich das herausgefunden, sondern k0SH.