Programmieranstoß oder hat wer das schon programmiert?

N

napsi

Erfahrenes Mitglied
Hallo an Alle!

Vorweg muss ich sagen, dass ich nur im VBA ein wenig versiert bin.

Vielleicht hat jemand so ewas auch schon programmiert und kann es mir zur Verfügung stellen.

Hier die Problemstellung:

Ich habe ein Quadrat mit 5x5 Feldern. Es stehen auch 25 Zahlen zur Verfügung (1-25). In jedes Feld wird eine Zahl eingetragen und darf nur einmal vorkommen. Dazu kommt noch, dass in jeder Zeile und Spalte es eine Summe gibt, die vorgegeben ist. Es sind auch einige Zahlen vorausgefüllt.

Anbei findet Ihr auch einen Screen, der das verdeutlichen soll.

Ich bitte um Eure Hilfe, da ich nicht weiß, wo ich mich hinwenden könnte.

lg.

Napsi
 

Anhänge

  • GC2A1NH.jpg
    GC2A1NH.jpg
    103,6 KB · Aufrufe: 5
Hi

ich hab sowas zwar nicht fertig, aber:
Würdest du es mit Hilfe auch selbst versuchen oder willst du nur fertige Lösungen?

Sind die 25 Felder teilweise vorbelegt, oder sind nur die Summen gegeben
(oder können die Summen evt. auch teilweise nicht vorhanden sein, dafür Vorbelegung)?

Es gibt Fälle mit mehreren möglichen Lösungen. Reicht dann eine oder sind alle nötig?

Und haben die grünen Felder im Bild irgendeine Bedeutung?
 
Hallo!

Prinzipiell bin ich natürlich daran interessiert, es selber zusammen zu bringen, aber wie gesagt, ausser ein wenig vba bin ich eher unwissend. die felder, die ausgefüllt sind, sind bereits richtig positioniert, somit sollte es nur eine lösung geben. weiters ist eben die zeilen und spaltensumme vorgegeben.

die grünen felder sind für das beispiel weniger von bedeutung, die werte darin werden nur dann weiterverwendet.

Bin auf Lösungen und vorschläge gespannt.

lg.

Gerald
 
napsi hat gesagt.:
Bin auf Lösungen und vorschläge gespannt.
Zum Vergrößern anklicken....

Hallo,

eine sehr einfache mögliche Implementierung wäre die Lösung über Backtracking zu finden D.h. oben links die kleinste möglich Zahl einsetzen, im Feld danach die zweite kleinst mögliche Zahl usw. Nach jedem einsetzen überprüfst du ob das zu einem gültigen Feld führt. Falls ein Fehler auftritt, weil die Summe nicht passt, gehst du ein Schritt zurück und nimmst die nächst höhere Zahl, falls schon alle Zahlen getestet, wieder einen Schritt zurück. So kann man nebenbei auch ganz schnell Sudokus lösen.

Das Verfahren sollte bei der vorhandenen Größe recht schnell gehen, aber denk daran, das mit der Größe des Feldes der notwendige Rechenaufwand sehr schnell ansteigt, da es ja keine auf Logik basierende Methode ist.
 
Ich habe gerade ein 60-Zeilen PHP-Skript geschrieben, welches das Problem mit Bruteforce löst. Ist aber gerade noch am Rechnen ;)

Falls es jemanden interessiert - es sollte nicht allzu schwer zu C(++) portierbar sein:
PHP: 
function validateField($field, $sums) {
	$colSums = [];
	foreach ($field as $rowNr => $row) {
		if (array_sum($row) != $sums['rows'][$rowNr]) {
			return false;
		}
	}
	
	$colCount = count($field[0]);
	for ($i = 0; $i < $colCount; $i++) {
		if (array_sum( array_column($field, $i) ) != $sums['cols'][$i]) {
			return false;
		}
	}
	return true;
}

function fillField($field, $numbers) {
	array_walk_recursive($field, function (&$val) use (&$numbers) {
		if ($val == -1) {
			$val = array_shift($numbers);
		}
	});
	return $field;
}

// from http://stackoverflow.com/a/13194803/603003
function pc_permute_callback($items, $callback, $perms = array()) {
	if (empty($items)) {
		$callback($perms);
	}
	else {
		$return = array();
		for ($i = count($items) - 1; $i >= 0; --$i) {
			$newitems = $items;
			$newperms = $perms;
			list($foo) = array_splice($newitems, $i, 1);
			array_unshift($newperms, $foo);
			pc_permute_callback($newitems, $callback, $newperms);
		}
	}
}

function solveField($field, $sums, $numberRange) {
	$usedNumbers = [];
	array_walk_recursive($field, function($val) use (&$usedNumbers) {
		if ($val != -1) {
			$usedNumbers[] = $val;
		}
	});
	$missingNumbers = array_diff($numberRange, $usedNumbers);
	pc_permute_callback($missingNumbers, function ($permutation) use ($field, $sums) {
		$newField = fillField($field, $permutation);
		if (validateField($newField, $sums)) {
			exit('SOLVED');
		}
	});
}
 
Haha, ja das habe ich mir auch schon ausgerechnet gehabt :D

Ich habe gerade allerdings ein riesen Problem: mein Skript beendet einfach mit exit('SOLVED');, ohne die Lösung auszugeben.
Jetzt muss ich es nochmal laufen lassen -.-


PS: sheel's Zahl errechnet sich so: 25 Felder - 9 benutzte Felder = 16 ==> 16!
 
Und ich hab zwar Lösungen, aber ab und zu wird gemeldet, dass es keine gültige gibt...
warum muss ich erst noch rausfinden :D

Und fertig.
Code etwas undokumentiert, aber vorerst egal:
C: 
#include <stdio.h>

char solve(char (*)[5], const char *, const char *);
void findNextField(const char (*)[5], const char *, const char *, char *, char *);
char solveRec(const char (*)[5], const char *, const char *,
	char *, char *, char *, char *, unsigned long, char, char);

void findNextField(const char (*data)[5], const char *rowcount,
const char *colcount, char *y, char *x)
{
	char roworcol, max, maxindex, i;
	
	if(*y >= 0 && *y < 5 && *x >= 0 && *x < 5)
	{
		if(rowcount[*y] < 5)
		{
			*x = 0;
			while(data[*y][*x])
				(*x)++;
			return;
		}
		if(colcount[*x] < 5)
		{
			*y = 0;
			while(data[*y][*x])
				(*y)++;
			return;
		}
	}

	max = -1;
	roworcol = -1;
	for(i = 0; i < 5; i++)
	{
		if(rowcount[i] > max && rowcount[i] < 5)
		{
			roworcol = 0;
			max = rowcount[i];
			maxindex = i;
			if(max == 4)
				break;
		}
	}
	if(max < 4)
	{
		for(i = 0; i < 5; i++)
		{
			if(colcount[i] > max && colcount[i] < 5)
			{
				roworcol = 1;
				max = colcount[i];
				maxindex = i;
			}
			if(max == 4)
				break;
		}
	}

	if(roworcol == 1)
	{
		*x = maxindex;
		*y = 0;
		while(data[*y][*x])
			(*y)++;
	}
	else if(roworcol == 0)
	{
		*y = maxindex;
		*x = 0;
		while(data[*y][*x])
			(*x)++;
	}
	return;
}

char solveRec(char (*data)[5], const char *rowsum, const char *colsum,
char *currentrowsum, char *currentcolsum, char *rowcount, char *colcount,
unsigned long usedmask, char y, char x)
{
	char nexty, nextx, minz, maxz;
	if((usedmask/2) == ((1<<25)-1))
		return 0;

	minz = 1;
	maxz = 25;
	if(rowcount[y] == 4)
	{
		minz = maxz = rowsum[y] - currentrowsum[y];
		if(colcount[x] == 4 && minz != (colsum[x] - currentcolsum[x]))
			maxz = 0;
	}
	else if(colcount[x] == 4)
	{
		minz = maxz = colsum[x] - currentcolsum[x];
	}
	else
	{
		while(usedmask&(1<<minz)) minz++;
		while(usedmask&(1<<maxz)) maxz--;
	}
	if(minz > maxz || minz < 1 || maxz > 25) return 1;

	nexty = y;
	nextx = x;
	rowcount[y]++;
	colcount[x]++;
	data[y][x] = -1;
	findNextField(data, rowcount, colcount, &nexty, &nextx);

	while(minz <= maxz)
	{
		if(usedmask&(1<<minz))
		{
			minz++;
			continue;
		}
  		data[y][x] = minz;
		currentrowsum[y] += minz;
		currentcolsum[x] += minz;
		usedmask |= (1<<minz);
		if(!solveRec(data, rowsum, colsum, currentrowsum, currentcolsum,
			rowcount, colcount, usedmask, nexty, nextx))
			return 0;
		usedmask &= ~(1<<minz);
		currentcolsum[x] -= minz;
		currentrowsum[y] -= minz;
		minz++;
	}
	data[y][x] = 0;
	rowcount[y]--;
	colcount[x]--;
	return 1;
}

char solve(char (*data)[5], const char *rowsum, const char *colsum)
{
	unsigned long usedmask = 0;
	char y, x;
	char rowcount[5], colcount[5];
	char currentrowsum[5], currentcolsum[5];
	for(y = 0; y < 5; y++)
	{
		rowcount[y] = 0;
		colcount[y] = 0;
		currentrowsum[y] = 0;
		currentcolsum[y] = 0;
	}
	for(y = 0; y < 5; y++)
	{
		if(rowsum[y] < 15 || rowsum[y] > 115 || colsum[y] < 15 || colsum[y] > 115)
			return -1;
		for(x = 0; x < 5; x++)
		{
			if(data[y][x] < 0 || data[y][x] > 25)
				return -1;
			if(data[y][x])
			{
				if(usedmask & (1<<data[y][x]))
					return -1;
				usedmask |= (1<<data[y][x]);
				rowcount[y]++;
				colcount[x]++;
				currentrowsum[y] += data[y][x];
				currentcolsum[x] += data[y][x];
			}
		}
	}
	if((usedmask/2) == ((1<<25)-1))
		return 0;
	y = -1;
	x = -1;
	findNextField(data, rowcount, colcount, &y, &x);
	return solveRec(data, rowsum, colsum, currentrowsum, currentcolsum,
		rowcount, colcount, usedmask, y, x);
}

int main(int argc, char *argv[])
{
	char data[5][5] = {
		{0,0,20,0,0},
		{2,17,0,10,0},
		{0,1,13,0,0},
		{0,0,0,24,0},
		{15,0,0,0,3},
	};
	char rowsum[5] = {78, 69, 73, 56, 49};
	char colsum[5] = {66, 54, 62, 77, 66};

	char y, x, r;

	r = solve(data, rowsum, colsum);

	if(r < 0)
		printf("Error\n");
	else if(r > 0)
		printf("No solution\n");
	else
	{
		for(y = 0; y < 5; y++)
		{
			for(x = 0; x < 5; x++)
				printf("%.2d ", data[y][x]);
			printf("\n");
		}
	}

	return 0;
}
Sowohl in Richtung einfach+schön als auch hässlich+schnell kann man noch optimieren :p

edit: Falls es mehrere Lösungen gibt wird bei mir nur eine ausgegeben.
Kann aber relativ einfach umgebaut werden
 
Zuletzt bearbeitet:
hallo an alle:

bin sehr überrascht, im positiven, wieviele sich mit meinem problem geschäftigt haben. danke mal im vorherein.

Der C-Code wirkt bis jetzt am komplettesten, wenn ich die kommentare so lese, allerdings wie kann dieser nun verwendet werden. welches programm brauche ich dafür? Werde mir den Code sicherlich ein wenig ansehen, um etwas lernen zu können.

Handelt es sich um C oder c++?
lg.

Gerald
 
Zuletzt bearbeitet:
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück