Tag 12 - Die Lösung ist 0

Das härteste Rätsel der Adventure-Welt
Benutzeravatar
Bluecat
Hobby-Archäologe
Hobby-Archäologe
Beiträge: 123
Registriert: 18.07.2005, 20:41

Re: Tag 12 - Die Lösung ist 0

Beitrag 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;
}
Benutzeravatar
muetze86
Hobby-Archäologe
Hobby-Archäologe
Beiträge: 208
Registriert: 04.12.2008, 11:15

Re: Tag 12 - Die Lösung ist 0

Beitrag 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:
"Und die Mächte der Dunkelheit werden mir applaudieren, wenn ich durch die Tore der Hölle SCHREITE und deinen aufgespießten Kopf bei mir habe."........."'Schreite'?"........"Dann eben 'ROLLE! Durch die Tore der Hölle ROLLE'."
Benutzeravatar
Andro19
Komplettlösungsnutzer
Komplettlösungsnutzer
Beiträge: 24
Registriert: 15.12.2009, 22:02

Re: Tag 12 - Die Lösung ist 0

Beitrag von Andro19 »

@ Bluecat und ollipolli

Vielen lieben Dank :-D
Zuletzt geändert von Andro19 am 13.12.2010, 00:19, insgesamt 1-mal geändert.
ollipolli
Komplettlösungsnutzer
Komplettlösungsnutzer
Beiträge: 24
Registriert: 06.12.2006, 16:29

Re: Tag 12 - Die Lösung ist 0

Beitrag 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;
					}
				}
			}
		}
	}
}
Benutzeravatar
Roger7520
Süßwasserpirat
Süßwasserpirat
Beiträge: 266
Registriert: 07.03.2008, 20:52
Wohnort: Dinslaken

Re: Tag 12 - Die Lösung ist 0

Beitrag 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
Alles Roger?
Benutzeravatar
elfant
Zombiepirat
Zombiepirat
Beiträge: 10090
Registriert: 03.12.2010, 16:35
Wohnort: Sylt
Kontaktdaten:

Re: Tag 12 - Die Lösung ist 0

Beitrag von elfant »

Ich danke Dir für das Programm, Bluecat.
Worte sind die mächtigste Droge, welche die Menschheit benutzt. - Joseph Rudyard Kipling (1865 - 1936)

Bitte nicht für geistig normal ansehen. Entweder versuche ich gerade humorvoll zu sein oder der Hammer hat wieder einmal den Dachstuhl beschädigt.

Tobacco Mackenthun
Friedrichstraße 33
25980 Sylt OT Westerland
Benutzeravatar
Nikioko
Adventure-Gott
Adventure-Gott
Beiträge: 4513
Registriert: 18.06.2008, 21:46
Wohnort: Bonn
Kontaktdaten:

Re: Tag 12 - Die Lösung ist 0

Beitrag 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
How much wood would a woodchuck chuck if a woodchuck could chuck wood?
The only saw I saw was the saw I saw with.
Benutzeravatar
Bluecat
Hobby-Archäologe
Hobby-Archäologe
Beiträge: 123
Registriert: 18.07.2005, 20:41

Re: Tag 12 - Die Lösung ist 0

Beitrag 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 ;)
Benutzeravatar
Einzelkämpfer
Argonaut
Argonaut
Beiträge: 8534
Registriert: 08.12.2007, 01:43

Re: Tag 12 - Die Lösung ist 0

Beitrag 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.
Die kostenlosen Adventures der "Argonauts":
Me and the Robot (2020), Welcome to the Funky Fair (2020), IMAGinE (2021), MVEM: A Druidic Adventure (2021), Oh My God (2022), Under the Sea (2023)
Benutzeravatar
Antarael
Tastatursteuerer
Tastatursteuerer
Beiträge: 703
Registriert: 04.12.2008, 01:17
Wohnort: Twisted Heart
Kontaktdaten:

Re: Tag 12 - Die Lösung ist 0

Beitrag von Antarael »

"Wir haben nichts, das uns eint,
keine zwei Dinge, die sich gleichen,
kein drittes Auge,
keine Hoffnung in der vierten Himmelsrichtung.
Im Fünften begründet sich der Ort des Herzens.
Lebt wohl, unbeschwerte Zeiten!"
Shootingstar
Riesiger Roboteraffe
Riesiger Roboteraffe
Beiträge: 9402
Registriert: 24.08.2006, 22:03

Re: Tag 12 - Die Lösung ist 0

Beitrag 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:
Jetzt sind die guten alten Zeiten, nach denen wir uns in zehn Jahren zurücksehnen.
(Sir Peter Ustinov)
Benutzeravatar
Orlando
Logik-Lord
Logik-Lord
Beiträge: 1107
Registriert: 11.12.2008, 13:02
Wohnort: Rheinhessen

Re: Tag 12 - Die Lösung ist 0

Beitrag von Orlando »

Jan ist mittlerweile Ehrenpräsident in der "Vereinigung subtiler Andeutungen und doppeldeutiger Botschaften e.V." :mrgreen:
I'm crying out in fury to the gods of fate
Come on, get me if you can
Benutzeravatar
Stumpfi
Süßwasserpirat
Süßwasserpirat
Beiträge: 361
Registriert: 14.12.2007, 22:28

Re: Tag 12 - Die Lösung ist 0

Beitrag von Stumpfi »

Erklärt jetzt noch jemand die Überschrift, bitte? Und bin ich die einzige, die keine Bestätigungsmails mehr bekommt?
Benutzeravatar
S-Made
Rätselmeister
Rätselmeister
Beiträge: 1531
Registriert: 31.10.2003, 11:13

Re: Tag 12 - Die Lösung ist 0

Beitrag 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.
DasKlapptSoNicht.de
Eure Wohlfühloase für Artikel über Computer- und Videospiele. Kostenlos und werbefrei für alle.
Benutzeravatar
Nikioko
Adventure-Gott
Adventure-Gott
Beiträge: 4513
Registriert: 18.06.2008, 21:46
Wohnort: Bonn
Kontaktdaten:

Re: Tag 12 - Die Lösung ist 0

Beitrag 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.
How much wood would a woodchuck chuck if a woodchuck could chuck wood?
The only saw I saw was the saw I saw with.
Antworten