---

Hej alle

Jeg er mystificeret.

Jeg har et program der fungerede fint indtil jeg lavede den
sidste tilføjelse - en ekstra blok i en funktion. Programmet kan
løse sudokuer (p.t. op til midterste sværhedgrad) og den blok i
rutinen skal undersøge om der findes en kandidat der kun må stå
ét sted i et 3*3-felt. Hvert enkeltfelt har et array hvor der
starter med at stå 1-taller ved hvert af de 9 cifre, og så
fjerner jeg efterhånden de umulige kandidater.

Programmet arbejder med et array af structs:

enum { SIZE=3, STRIPE=SIZE*SIZE };

struct field_struct {
   int value;
   int candidates[STRIPE+1]; // 0-pladsen går til spilde.
};

struct field_struct field[STRIPE][STRIPE]; // 81 små felter.


Den problematiske rutine er her med velfungerende kode klippet væk:

bool check_candidates (struct field_struct field[STRIPE][STRIPE]) {
   int X, Y, x, y, x0, y0, candidate, sum;
   bool change=0;

   // Er der en kandidat der kun må være ét sted?
   // Store felter
   for (X=0; X<STRIPE; X+=SIZE)
      for (Y=0; Y<STRIPE; Y+=SIZE)
         for (candidate=1; candidate<=STRIPE; ++candidate) {
            sum=0;
            for (x=X; x<X+SIZE; ++x)
               for (y=Y; y<Y+SIZE; ++y)
      if (field[x][y].candidates[candidate]) {
                     x0=x;
                     y0=y;
                     ++sum;
                  }
            if (sum==1) {
               field[x][y].value=candidate;
               change=1;
            }
         }
   return change;
}

Det mærkelige er at hvis jeg remmer linjen ud med "++sum;", så
forsvinder problemet. Det viser sig i øvrigt ved en balladeboks
i stil med den man ser ved pointerfejl.

Jeg har prøvet at lade værdien af variablerne udskrives, og der er
ikke nogen uventede værdier at se.

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

Bertel Lund Hansen wrote:

> Programmet kan
> løse sudokuer (p.t. op til midterste sværhedgrad) og den blok i
> rutinen skal undersøge om der findes en kandidat der kun må stå
> ét sted i et 3*3-felt.

[...]

> bool check_candidates (struct field_struct field[STRIPE][STRIPE]) {
>    int X, Y, x, y, x0, y0, candidate, sum;
>    bool change=0;

>    // Er der en kandidat der kun må være ét sted?
>    // Store felter
>    for (X=0; X<STRIPE; X+=SIZE)
>       for (Y=0; Y<STRIPE; Y+=SIZE)
>          for (candidate=1; candidate<=STRIPE; ++candidate) {
>             sum=0;
>             for (x=X; x<X+SIZE; ++x)
>                for (y=Y; y<Y+SIZE; ++y)
>       if (field[x][y].candidates[candidate]) {
>                      x0=x;
>                      y0=y;
>                      ++sum;
>                   }
>             if (sum==1) {
>                field[x][y].value=candidate;

Burde dette ikke vaere:

               field[x0][y0].value=candidate;

>                change=1;
>             }
>          }
>    return change;
> }

> Det mærkelige er at hvis jeg remmer linjen ud med "++sum;", så
> forsvinder problemet. Det viser sig i øvrigt ved en balladeboks
> i stil med den man ser ved pointerfejl.

Saa vidt jeg kan bedoemme vil du under vejs gemme din kandidat i
field[4][10], field[7][10] og field[10][10].

Preben
--
se nocp cpo=BceFsx!$ hid bs=2 ls=2 hls ic " P. Guldberg /bin/vi@wielders.org
se scs ai isf-== fdo-=block cino=t0,:0 hi=100 ru so=4 noea lz|if has('unix')
se sh=/bin/sh|en|syn on|filetype plugin indent on|ono S V/\n^-- $\\|\%$/<CR>
cno <C-A> <C-B>|au FileType vim,mail se sw=4 sts=4 et|let&tw=72+6*(&ft=~'v')

---

Preben 'Peppe' Guldberg skrev:

> Burde dette ikke vaere:
>
>                field[x0][y0].value=candidate;

JO! ... [afsikring_click.wav] ... Tak!

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

Bertel Lund Hansen wrote:
>    for (X=0; X<STRIPE; X+=SIZE)
>       for (Y=0; Y<STRIPE; Y+=SIZE)
>          for (candidate=1; candidate<=STRIPE; ++candidate) {
>             sum=0;
>             for (x=X; x<X+SIZE; ++x)
>                for (y=Y; y<Y+SIZE; ++y)
>       if (field[x][y].candidates[candidate]) {
>                      x0=x;
>                      y0=y;
>                      ++sum;
>                   }
>             if (sum==1) {
>                field[x][y].value=candidate;
>                change=1;
>             }
>          }

Så vidt jeg kan se kan x blive op til X + SIZE - 1, hvilket er det samme
som op til STRIPE + SIZE -1, og du har kun til STRIPE -1.

Hvis ikke du tæller sum op, vil du kun læse unden for arrayet
(sum == 1 bliver ikke sandt), og programmet går ikke ned.

Jeg har i øvrigt lavet et program til at løse sudoko i C++,
hvis det har interesse.

--
Absolutely not the best homepage on the net:
http://home20.inet.tele.dk/midgaard
But it's mine - Bertel

---

Bertel Brander skrev:

> Jeg har i øvrigt lavet et program til at løse sudoko i C++,
> hvis det har interesse.

Ja, det har det. Jeg er ved at løbe tør for ideer (har én endnu),
og programmet kan ikke knække den svære sudoku jeg bruger.

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/

---

Bertel Lund Hansen wrote:
> Bertel Brander skrev:
>
>> Jeg har i øvrigt lavet et program til at løse sudoko i C++,
>> hvis det har interesse.
>
> Ja, det har det. Jeg er ved at løbe tør for ideer (har én endnu),
> og programmet kan ikke knække den svære sudoku jeg bruger.

#include <iostream>

typedef unsigned char uint8_t;

uint8_t Maze[9][9] = // This is the sudoko to solve
{
{7,8,0,0,0,5,9,0,0},
{0,4,0,2,0,7,0,3,0},
{0,5,9,0,0,8,2,4,0},
{0,2,0,0,0,9,3,1,0},
{0,0,7,3,0,4,6,0,0},
{0,3,4,1,0,0,0,9,0},
{0,6,5,7,0,0,8,2,0},
{0,7,0,9,0,6,0,5,0},
{0,0,3,5,0,0,0,7,6}
};

bool IsValid(uint8_t aSudoko[9][9], int aX, int aY, uint8_t aVal)
{ // Will the sudoko be valid if we put aVal into [aX][aY]
int a;
for(a = 0; a < 9; a++)
if(aSudoko[aX][a] == aVal)
return false;
for(a = 0; a < 9; a++)
if(aSudoko[a][aY] == aVal)
return false;
int y = aY/3;
int x = aX/3;
if(aSudoko[x*3][y*3 + 0] == aVal || aSudoko[x*3 + 1][y*3 + 0] ==
aVal || aSudoko[x*3 + 2][y*3 + 0] == aVal ||
aSudoko[x*3][y*3 + 1] == aVal || aSudoko[x*3 + 1][y*3 + 1] ==
aVal || aSudoko[x*3 + 2][y*3 + 1] == aVal ||
aSudoko[x*3][y*3 + 2] == aVal || aSudoko[x*3 + 1][y*3 + 2] ==
aVal || aSudoko[x*3 + 2][y*3 + 2] == aVal)
{
return false;
}
return true;
}

bool Solve(uint8_t aSudoko[9][9])
{
int x, y;
uint8_t Val;
for(y = 0; y < 9; y++)
{
for(x = 0; x < 9; x++)
{
if(aSudoko[x][y] == 0)
{ // Have found a empty index, check all values
for(Val = 1; Val <= 9; Val++)
{
if(IsValid(aSudoko, x, y, Val))
{
aSudoko[x][y] = Val;
if(Solve(aSudoko))
return true;
}
}
aSudoko[x][y] = 0;
return false;
}
}
}
return true;
}

int main()
{
if(Solve(Maze))
{
std::cout << "Success" << std::endl;
int x, y;
for(y = 0; y < 9; y++)
{
for(x = 0; x < 9; x++)
std::cout << int(Maze[y][x]);
std::cout << std::endl;
}
}
else
{
std::cout << "Failed" << std::endl;
}
}

--
Absolutely not the best homepage on the net:
http://home20.inet.tele.dk/midgaard
But it's mine - Bertel

---

Bertel Lund Hansen <nospamfilius@lundhansen.dk> writes:

> Bertel Brander skrev:
>
> > Jeg har i øvrigt lavet et program til at løse sudoko i C++,
> > hvis det har interesse.
>

> Ja, det har det. Jeg er ved at løbe tør for ideer (har én endnu),
> og programmet kan ikke knække den svære sudoku jeg bruger.

Der er en rimelig god vejledning på wikipedia:
<http://da.wikipedia.org/wiki/Sudoku>

--
// Wegge
Weblog: http://blog.wegge.dk
Wiki: http://wiki.wegge.dk

---

Anders Wegge Jakobsen skrev:

> Der er en rimelig god vejledning på wikipedia:

Det var kun den sidste fidus jeg ikke kendte.

--
Bertel
http://bertel.lundhansen.dk/      http://fiduso.dk/