Sudoku in C++ < C/C++ < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 17:23 Di 19.02.2008 | | Autor: | Antivirus |
| Aufgabe | Ich soll ein Sudokulöser erstellen.
Die Dateien vorgP4.2.h und vorgP4.2.c++ sind vorgaben die ich nicht verändern darf.
In aufgP4.2.c++ hab das mein Programm reingeschrieben, nur funktioniert das nicht ganz...
es sagt bei einem vollen Sudoku zwar, ob das richtig ist oder nicht, aber sobald ich eine 0 (= also kein Eintrag) funktioniert es nicht mehr...
|
Hat da einer eine Idee.
Hier sind die Quelltexte:
vorgP4.2.h:
typedef unsigned char SD [9][9][10];
//SD[j][0] ist Anzahl der offenen Möglichkeiten
auf Position (i,j)
//SD[i][j][k]==true genau dann wenn die Zahl k eine
offene Möglichkeit ist
char sudoku(SD);
vorgP4.2.c++ :
#include<stdio.h>
#include<stdlib.h>
#include"vorgP4.2.h"
#include<iostream.h>
void lese_SD(SD sd){
unsigned c;
for(unsigned i=0;i<9;++i)
for(unsigned j=0;j<9;++j)
{ scanf("%u",&c);
for(unsigned k=1;k<10;++k)
sd[i][j][k]=(c?0:1);
sd[i][j][0]=(c?1:9);
if(c) sd[i][j][c]=1;
}
}
void drucke_SD(SD sd){
for(unsigned i=0;i<9;++i)
{
for(unsigned j=0;j<9;++j)
{
if(sd[i][j][0]!=1)
{ printf("%u ",0); continue; }
for(unsigned k=1;k<10;++k)if(sd[i][j][k])
printf("%u ",k);
}
[mm] printf("\n");
[/mm]
}
}
SD sd;
main(){
lese_SD(sd);
drucke_SD(sd);
[mm] printf("\n");
[/mm]
if(sudoku(sd)) drucke_SD(sd);
else printf("unloesbar");
system("PAUSE");
}
und schließlich das wichtigste...
aufgP4.2.c++ :
#include "vorgP4.2.h"
char voll(SD sd1)
{ int rueck=1;
for(unsigned i=0;i<9;++i)
{
for(unsigned j=0;j<9;++j)
{
if(sd1[i][j][0]>1)
rueck = 0;
}
}
return rueck;}
int welche_zahl(SD sd2, int zeile, int spalte)
{ int rueck=0;
for (unsigned k=0;k<10;++k)
if (sd2[zeile][spalte][k]==1)
rueck=k;
return rueck;}
char teste(SD sd3)
{ int rueck=1;
//zeilentest:
for(unsigned i=0;i<9;++i)
{
for(unsigned j=0;j<9;++j)
{
for(unsigned l=0;l<9;++l)
{
if ((welche_zahl(sd3,i,j)==welche_zahl(sd3,i,l))&&(j!=l))
rueck = 0;
}
}
}
//spaltentest
for(unsigned j=0;j<9;++j)
{
for(unsigned i=0;i<9;++i)
{
for(unsigned l=0;l<9;++l)
{
if ((welche_zahl(sd3,i,j)==welche_zahl(sd3,l,j))&&(i!=l))
rueck = 0;
}
}
}
//boxtest
for(unsigned i=0;i<9;++i)
{
for(unsigned j=0;j<9;++j)
{
for(unsigned k=((i/3)*3);k<(((i/3)*3)+3);++k)
{
for(unsigned l=((j/3)*3);l<(((j/3)*3)+3);++l)
{
if ((welche_zahl(sd3,i,j)==welche_zahl(sd3,k,l))&&((i!=k)||(j!=l)))
rueck = 0;
}
}
}
}
return rueck;
}int freiezeile(SD sd4)
{
int rueck;
for(unsigned i=0;i<9;++i)
{
for(unsigned j=0;j<9;++j)
{
if(sd4[i][j][0]>1)
rueck = i;
}
}
return rueck;
}
int freiespalte(SD sd5, int zeile)
{
int rueck;
for(unsigned j=0;j<9;++j)
{
if(sd5[zeile][j][0]>1)
rueck = j;
}
return rueck;
}
char sudoku(SD sd)
{
SD sdx;int wert=0;
// sd auf sdx zuweisen:for(unsigned i=0;i<9;++i)
{
for(unsigned j=0;j<9;++j)
{
for(unsigned k=0;k<10;++k)
sdx[i][j][k]=sd[i][j][k];
}
}
// sind alle einträge im sudoku drin?
// wenn ja dann prüfe ob diese Lösung so geht
if (voll(sd)==1)
{
if(teste(sd)==1)
{
return 1;
}
else return 0;
}
else
{
// suche nächsten freien Platzint zeile = freiezeile(sd);
int spalte = freiespalte(sd,zeile);
for(unsigned zahl=0;zahl<9;++zahl)
//trage zahl ein und löse dann
{
for(unsigned i=1;i<10;++i)
{
sdx[zeile][spalte][i]=0;
}
sdx[zeile][spalte][zahl]=1;
sdx[zeile][spalte][0]=1;
if (sudoku(sdx)==1)
{
for(unsigned i=0;i<9;++i)
{
for(unsigned j=0;j<9;++j)
{
for(unsigned k=0;k<10;++k)
sd[i][j][k]=sdx[i][j][k];
}
}
return 1;
}
else
return 0;
}
}
}
Kann wer Helfen??
Bitte,Bitte,...
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:36 Mi 20.02.2008 | | Autor: | Zneques |
Hallo,
> // suche nächsten freien Platzint zeile = freiezeile(sd);
Dort sind zwei Zeilen in einem.
> char sudoku(SD sd)
Da du sd verändern möchtest, müsstest du es doch als Referenz übergeben :
char sudoku(SD& sd)
Bin mir da aber nicht so sicher, da ich kein c++ verwende.
Ciao.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:42 Mi 20.02.2008 | | Autor: | Antivirus |
Oh nein, daran liegt es nicht bzw. darf ich dies nicht ändern, da es vorgegeben war...
der Fehler muss in der Implementierung sein, aber weis einfach nicht wo...
????
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 03:23 Do 21.02.2008 | | Autor: | Zneques |
Ok, da sd ein Array ist, wird es, glaube ich, immer als Referenz übergeben. Daran liegt es also nicht.
Was macht denn das Programm ? Stürzt es ab ? Beendet es ohne Lösung ?
Füge doch vor deinem if (sudoku(sdx)==1) mal eine Ausgabe ein, so dass man sehen kann welche Stellen er verändert.
Möglicherweise ist auch die Laufzeit einfach zu hoch.
Wenn er in 10 Positionen alle 9 Ziffern versucht hat er bereits [mm] 9^{10}\approx3.5 [/mm] Mrd. Fälle zu bearbeiten.
Ciao.
|
|
|
|
