Sudoku løsning

Jeg havde noget til at ligge:
#include <iostream>
#include <vector>

typedef unsigned char uint8_t;
struct SudokuT
{
  uint8_t Maze[9][9];
};

SudokuT Maze = // 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(const SudokuT &aSudoko, 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.Maze[aX][a] == aVal)
        return false;
  for(a = 0; a < 9; a++)
      if(aSudoko.Maze[a][aY] == aVal)
        return false;
  int y = aY/3;
  int x = aX/3;
  if(aSudoko.Maze[x*3][y*3 + 0] == aVal || aSudoko.Maze[x*3 + 1][y*3 + 0] == aVal || aSudoko.Maze[x*3 + 2][y*3 + 0] == aVal ||
      aSudoko.Maze[x*3][y*3 + 1] == aVal || aSudoko.Maze[x*3 + 1][y*3 + 1] == aVal || aSudoko.Maze[x*3 + 2][y*3 + 1] == aVal ||
      aSudoko.Maze[x*3][y*3 + 2] == aVal || aSudoko.Maze[x*3 + 1][y*3 + 2] == aVal || aSudoko.Maze[x*3 + 2][y*3 + 2] == aVal)
  {
      return false;
  }
  return true;
}

bool Solve(SudokuT &aSudoko)
{
  int x, y;
  uint8_t Val;
  for(y = 0; y < 9; y++)
  {
      for(x = 0; x < 9; x++)
      {
        if(aSudoko.Maze[x][y] == 0)
        {  // Have found a empty index, check all values
            for(Val = 1; Val <= 9; Val++)
            {
              if(IsValid(aSudoko, x, y, Val))
              {
                  aSudoko.Maze[x][y] = Val;
                  if(Solve(aSudoko))
                    return true;
              }
            }
            aSudoko.Maze[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.Maze[y][x]);
        std::cout << std::endl;
      }
  }
  else
  {
      std::cout << "Failed" << std::endl;
  }
}

Jeg ved godt det ikke er dette du søger, men måske du kan bruge det til ét eller andet alligevel.  c",)
http://www.di-mgt.com.au/sudoku.html

Mange tak. Jeg kigger på det her til aften. Er ikke hjemme.

Ohh. Det er c++ det er skrevet i - ØV. Havde håbet på noget c, da jeg ikke kan så meget c++.


Vejmand: Meget godt input du kom med. Kan godt være at jeg kan kigge lidt på hvordan excel løser problemet.

Det samme i C:

#include <stdio.h>

typedef unsigned char uint8_t;
typedef unsigned char bool;
enum
{
  false, true
};

typedef struct SudokuT
{
  uint8_t Maze[9][9];
}SudokuT;

SudokuT Maze =
{
  {
      {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(const SudokuT *aSudoko, int aX, int aY, uint8_t aVal)
{
  int a;
  int y = aY/3;
  int x = aX/3;
  for(a = 0; a < 9; a++)
      if(aSudoko->Maze[aX][a] == aVal)
        return false;
  for(a = 0; a < 9; a++)
      if(aSudoko->Maze[a][aY] == aVal)
        return false;
  if(aSudoko->Maze[x*3][y*3 + 0] == aVal || aSudoko->Maze[x*3 + 1][y*3 + 0] == aVal || aSudoko->Maze[x*3 + 2][y*3 + 0] == aVal ||
      aSudoko->Maze[x*3][y*3 + 1] == aVal || aSudoko->Maze[x*3 + 1][y*3 + 1] == aVal || aSudoko->Maze[x*3 + 2][y*3 + 1] == aVal ||
      aSudoko->Maze[x*3][y*3 + 2] == aVal || aSudoko->Maze[x*3 + 1][y*3 + 2] == aVal || aSudoko->Maze[x*3 + 2][y*3 + 2] == aVal)
  {
      return false;
  }
  return true;
}

bool Solve(SudokuT *aSudoko)
{
  int x, y;
  uint8_t Val;
  for(y = 0; y < 9; y++)
  {
      for(x = 0; x < 9; x++)
      {
        if(aSudoko->Maze[x][y] == 0)
        {
            for(Val = 1; Val <= 9; Val++)
            {
              if(IsValid(aSudoko, x, y, Val))
              {
                  aSudoko->Maze[x][y] = Val;
                  if(Solve(aSudoko))
                    return true;
              }
            }
            aSudoko->Maze[x][y] = 0;
            return false;
        }
      }
  }
  return true;
}

int main()
{
  if(Solve(&Maze))
  {
      int x, y;
      printf("Success\n");
      for(y = 0; y < 9; y++)
      {
        for(x = 0; x < 9; x++)
          printf("%d", Maze.Maze[y][x]);
        printf("\n");
      }
  }
  else
  {
      printf("Failed\n");
  }
  return 0;
}

Takker. Det virker kanon :-)

Er det sådan du kan forklar hvad disse linier gør ?

bool IsValid(const SudokuT *aSudoko, int aX, int aY, uint8_t aVal)
{
  int a;
  int y = aY/3;
  int x = aX/3;
  for(a = 0; a < 9; a++)
      if(aSudoko->Maze[aX][a] == aVal)
        return false;
  for(a = 0; a < 9; a++)
      if(aSudoko->Maze[a][aY] == aVal)
        return false;
  if(aSudoko->Maze[x*3][y*3 + 0] == aVal || aSudoko->Maze[x*3 + 1][y*3 + 0] == aVal || aSudoko->Maze[x*3 + 2][y*3 + 0] == aVal ||
      aSudoko->Maze[x*3][y*3 + 1] == aVal || aSudoko->Maze[x*3 + 1][y*3 + 1] == aVal || aSudoko->Maze[x*3 + 2][y*3 + 1] == aVal ||
      aSudoko->Maze[x*3][y*3 + 2] == aVal || aSudoko->Maze[x*3 + 1][y*3 + 2] == aVal || aSudoko->Maze[x*3 + 2][y*3 + 2] == aVal)
  {
      return false;
  }
  return true;
}



Smid lige et svar mens du er igang. Og mange tak for hjælpen

IsValid funktionen checker om man kan indætte aVal i Sudoku'en på plads aX,aY.
Den løber linien og kolonen igennem for at se om aVal står der. Til slut checker den firkanten.
Funktionen returnerer true hvis aVal kan passe, ellers false.

Jeg samler ikke på point.

Er det muligt, at brugeren kan indtaste tallen? Så de ikke er "kodet" ind i programmet. Så man fx indtaster første linie og trykker på enter og så næste linie.

Jeg har prøver med scanf(), men kan ikke få det til at virke

#include <stdio.h>

typedef enum
{
  false, true
}bool;

typedef struct SudokuT
{
  unsigned int Maze[9][9];
}SudokuT;

SudokuT Maze;

bool IsValid(const SudokuT *aSudoko, int aX, int aY, unsigned int aVal)
{
  int a;
  int y = aY/3;
  int x = aX/3;
  for(a = 0; a < 9; a++)
      if(aSudoko->Maze[aX][a] == aVal)
        return false;
  for(a = 0; a < 9; a++)
      if(aSudoko->Maze[a][aY] == aVal)
        return false;
  if(aSudoko->Maze[x*3][y*3 + 0] == aVal || aSudoko->Maze[x*3 + 1][y*3 + 0] == aVal || aSudoko->Maze[x*3 + 2][y*3 + 0] == aVal ||
      aSudoko->Maze[x*3][y*3 + 1] == aVal || aSudoko->Maze[x*3 + 1][y*3 + 1] == aVal || aSudoko->Maze[x*3 + 2][y*3 + 1] == aVal ||
      aSudoko->Maze[x*3][y*3 + 2] == aVal || aSudoko->Maze[x*3 + 1][y*3 + 2] == aVal || aSudoko->Maze[x*3 + 2][y*3 + 2] == aVal)
  {
      return false;
  }
  return true;
}

bool Solve(SudokuT *aSudoko)
{
  int x, y;
  unsigned int Val;
  for(y = 0; y < 9; y++)
  {
      for(x = 0; x < 9; x++)
      {
        if(aSudoko->Maze[x][y] == 0)
        {
            for(Val = 1; Val <= 9; Val++)
            {
              if(IsValid(aSudoko, x, y, Val))
              {
                  aSudoko->Maze[x][y] = Val;
                  if(Solve(aSudoko))
                    return true;
              }
            }
            aSudoko->Maze[x][y] = 0;
            return false;
        }
      }
  }
  return true;
}

int main()
{
  int x, y;
  for(y = 0; y < 9; y++)
  {
      printf("%d>", y);
      fflush(stdout);
      scanf("%d,%d,%d,%d,%d,%d,%d,%d,%d", &Maze.Maze[y][0], &Maze.Maze[y][1], &Maze.Maze[y][2],
                                          &Maze.Maze[y][3], &Maze.Maze[y][4], &Maze.Maze[y][5],
                                          &Maze.Maze[y][6], &Maze.Maze[y][7], &Maze.Maze[y][8]);
  }
  if(Solve(&Maze))
  {
      printf("Success\n");
      for(y = 0; y < 9; y++)
      {
        for(x = 0; x < 9; x++)
            printf("%d", Maze.Maze[y][x]);
        printf("\n");
      }
  }
  else
  {
      printf("Failed\n");
  }
  return 0;
}

Man skal indtaste en linie af gangen, efterfulgt af enter, f.ex:
7,8,0,0,0,5,9,0,0

ok. Hvis du ikke ønsker at få nogen point for din hjælp, så tager jeg dem selv og lukker spørgsmålet.