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;
}
Re: Tag 12 - Die Lösung ist 0
Verfasst: 13.12.2010, 00:15
von Andro19
@ Bluecat und ollipolli
Vielen lieben Dank
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.
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
ASCII-Code?
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?
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."
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.
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.
Ja, aber fairerweise habe nicht ich das herausgefunden, sondern k0SH.