Hallo zusammen muss ein Spiel namens "Str8ts" programmieren. Um einen Einblick was ich meine, hier die Funktionsweise des Spiels:
Str8ts ist ein Zahlenrätsel, ähnlich dem Sudoku, welches aus einem quadratischen Spielfeld mit 9 × 9 Teilfeldern besteht. Die insgesamt 81 Felder sind zunächst nur teilweise mit Zahlen von 1 bis 9 belegt. Zusätzlich sind einige Felder schwarz und teilweise ebenfalls mit Zahlen von 1 bis 9 belegt.
Das Ziel des Spiels besteht darin, die noch freien weißen Felder so zu belegen, dass
• in jeder Zeile des Gitterfeldes jede der Zahlen von 1 bis 9 höchstens einmal vorkommt.
• in jeder Spalte des Gitterfeldes jede der Zahlen von 1 bis 9 höchstens einmal vorkommt.
• zusammenhängende weiße Felder in einer Zeile oder Spalte eine Straße bilden, d.h. aus lückenlos aufeinanderfolgenden Zahlen bestehen, allerdings nicht notwendigerweise in der richtigen Reihenfolge (z.B. 6,2,4,5,3).
Für die ersten zwei Punkte zählen auch die Zahlen in den schwarzen Feldern. Ein schwarzes Feld mit einer Zahl blockiert also die Verwendung dieser Zahl in der entsprechenden Zeile und Spalte des Gitterfeldes. Schwarze Felder, ob mit oder ohne Zahl, trennen Straßen voneinander, gehören selbst aber nicht zu einer Straße.
Ich hab einen Teil des Codes schon geschrieben, nur ich weiß nicht unter
was ich reinschreiben soll.
hier der Code:
Dankeschön im Voraus
Gruß Justin09
Str8ts ist ein Zahlenrätsel, ähnlich dem Sudoku, welches aus einem quadratischen Spielfeld mit 9 × 9 Teilfeldern besteht. Die insgesamt 81 Felder sind zunächst nur teilweise mit Zahlen von 1 bis 9 belegt. Zusätzlich sind einige Felder schwarz und teilweise ebenfalls mit Zahlen von 1 bis 9 belegt.
Das Ziel des Spiels besteht darin, die noch freien weißen Felder so zu belegen, dass
• in jeder Zeile des Gitterfeldes jede der Zahlen von 1 bis 9 höchstens einmal vorkommt.
• in jeder Spalte des Gitterfeldes jede der Zahlen von 1 bis 9 höchstens einmal vorkommt.
• zusammenhängende weiße Felder in einer Zeile oder Spalte eine Straße bilden, d.h. aus lückenlos aufeinanderfolgenden Zahlen bestehen, allerdings nicht notwendigerweise in der richtigen Reihenfolge (z.B. 6,2,4,5,3).
Für die ersten zwei Punkte zählen auch die Zahlen in den schwarzen Feldern. Ein schwarzes Feld mit einer Zahl blockiert also die Verwendung dieser Zahl in der entsprechenden Zeile und Spalte des Gitterfeldes. Schwarze Felder, ob mit oder ohne Zahl, trennen Straßen voneinander, gehören selbst aber nicht zu einer Straße.
Ich hab einen Teil des Codes schon geschrieben, nur ich weiß nicht unter
Code:
int loese(int feld[N][N], int i, int j)was ich reinschreiben soll.
hier der Code:
Code:
#include <stdio.h>
#include <string.h>
#define N 9
#define MIN(X,Y) ((X)<(Y))?(X):(Y)
#define MAX(X,Y) ((X)>(Y))?(X):(Y)
/* Liest ein Str8ts ein. */
void lese(int feld[N][N]){
int i, j;
for(i = 0; i < N; i++){
for(j = 0; j < N; j++){
scanf("%d", &(feld[i][j]));
}
getchar(); /* Newline */
}
}
/* Gibt ein Str8ts aus. */
void ausgabe(int feld[N][N]){
int i, j;
printf("\e[0;90;107m\n");
printf("+---+---+---+---+---+---+---+---+---+\n");
for(i = 0; i < N; i++){
printf("|");
for(j = 0; j < N; j++){
if(feld[i][j] == 0){
printf(" |");
}else if(feld[i][j] == -N-1){
printf("\e[40m \e[107m|");
}else if(feld[i][j] < 0){
printf("\e[0;97;40m %1d \e[0;90;107m|", -feld[i][j]);
}else{
printf(" %1d |", feld[i][j]);
}
}
printf("\n");
printf("+---+---+---+---+---+---+---+---+---+\n");
}
printf("\e[0m\n");
}
/* Prueft, ob zeile i oder spalte i keine gueltigen Straßen enthaelt. */
int strasse(int feld[N][N], int i){
int dummy[N];
int li, lj, k;
int s, e, max;
/* Durchlaufe Zeile */
lj = 0;
while(lj < N){
/* Finde weißes teilstueck in zeile i. */
while(feld[i][lj] < 0 && lj < N) lj++; /* Erlaube auch komplett schwarze Zeilen. */
s = lj;
while(feld[i][lj] > 0 && lj < N) lj++; /* Erlaube auch komplett schwarze Zeilen. */
e = lj - 1;
/* Wenn der Bereich gueltig ist */
if(s <= e){
memset(dummy, 0x00, N * sizeof(int));
max = 0;
/* Markiere im Bereich vorkommende Zahlen und merke das Maximum. */
for(k = s; k <= e; k++){
dummy[feld[i][k]-1]++;
max = MAX(feld[i][k], max);
}
/* Wenn vom Maximum abwaerts e-s+1 Zahlen genau einmal vorkommen, ist alles okay. */
for(k = 0; k < e-s+1; k++)
if(dummy[max-k-1] != 1) return 0;
}
}
/* Durchlaufe Spalte */
li = 0;
while(li < N){
/* Finde weißes teilstueck in zeile i. */
while(feld[li][i] < 0 && li < N) li++; /* Erlaube auch komplett schwarze Zeilen. */
s = li;
while(feld[li][i] > 0 && li < N) li++; /* Erlaube auch komplett schwarze Zeilen. */
e = li - 1;
/* Wenn der Bereich gueltig ist */
if(s <= e){
memset(dummy, 0x00, N * sizeof(int));
max = 0;
/* Markiere im Bereich vorkommende Zahlen und merke das Maximum. */
for(k = s; k <= e; k++){
dummy[feld[k][i]-1]++;
max = MAX(feld[k][i], max);
}
/* Wenn vom Maximum abwaerts e-s+1 Zahlen genau einmal vorkommen, ist alles okay. */
for(k = 0; k < e-s+1; k++)
if(dummy[max-k-1] != 1) return 0;
}
}
return 1;
}
/* Prueft, ob feld eine gueltige Loesung enthaelt. */
int loesung(int feld[N][N]){
int zeile[N];
int spalte[N];
int i, j, k;
/* Pruefe doppelte Belegungen in Zeilen und Spalten */
for(i = 0; i < N; i++){
memset(zeile, 0x00, N * sizeof(int));
memset(spalte, 0x00, N * sizeof(int));
for(j = 0; j < N; j++){
if(feld[i][j] == 0) return 0;
if(feld[j][i] == 0) return 0;
if(feld[i][j] > 0) zeile[feld[i][j]-1]++;
if(feld[j][i] > 0) spalte[feld[j][i]-1]++;
}
for(k = 0; k < N; k++){
if(zeile[k] > 1) return 0;
if(spalte[k] > 1) return 0;
}
/* Pruefe Straßen */
if(!strasse(feld, i)) return 0;
}
return 1;
}
/* Diese Funktion sucht die naechste freie Stelle im Str8ts (bzw. in der Zwischenloesung),
welches im Array b gespeichert ist.
Hierbei geht die Funktion zeilenweise vor.
Der Funktion werden Zeiger auf die aktuelle Zeile i und die aktuelle Spalte j uebergeben.
Nach Aufruf der Funktion enthalten i und j die Koordinaten des naechsten freien Feldes
im Str8ts.
Diese Funktion arbeitet mit Pointern, damit die Aenderungen der Parameter i und j
fuer die aufrufende Funktion "sichtbar" sind.
Beim Aufruf der Funktion daher unbedingt auf die Adressoperatoren ("&") achten!
Diese Funktion liefert 1 zurueck falls es keine freien Stellen mehr gibt,
ansonsten liefert die Funktion 0 zurueck */
int naechstesfeld(int feld[N][N], int* i, int* j){
while(feld[*i][*j] != 0){
if (*j < N - 1){
(*j)++;
}else{
(*i)++;
*j = 0;
if (*i == N) return 1;
}
}
return 0;
}
/* Diese Funktion muessen Sie noch ergaenzen.
(d.h. an einer Stelle ruft loese sich selbst auf) Sie duerfen
(und sollten auch) fuer die Implementierung alle oben definierten
Funktionen verwenden ....
Diese Funktion liefert als Rueckgabewert 1,
wenn alle Felder erfolgreich belegt worden sind
(d.h. es gibt keine freien Felder mehr)
Ansonsten liefert die Funktion 0 zurueck. */
int loese(int feld[N][N], int i, int j){
/* HIER ERGAENZEN */
}
int main(void){
int feld[N][N];
memset(feld, 0x00, N * N * sizeof(int));
lese(feld);
ausgabe(feld);
loese(feld, 0, 0);
ausgabe(feld);
if(loesung(feld))
printf("Das ist eine Loesung!\n");
else
printf("Das ist KEINE Loesung!\n");
return 0;
}Dankeschön im Voraus
Gruß Justin09
Zuletzt bearbeitet:
