Sudoku X v C, ignoruje poslední prvek v poli – C / C++ – Fórum – Programujte.com

Zdravím, mám sudoku X v C

 Program mi ignoruje poslední prvek v sudoku, tj. pokud budu řešit aktuální zadání, vyjde v poli [0][8] a [8][0] stejné číslo. Věděl by někdo, kde je chyba? Snažil jsem se projít kontrolu diagonál tam i zpátky. Ve výsledku je to zcela zbytečné, bylo to spíš zoufalost.

#include <stdio.h>

int isAvailable(int sudoku[9][9], int row, int col, int num)
{
    //checking in the grid
    int rowStart = (row/3) * 3;
    int colStart = (col/3) * 3;

    int i, j, a, d;
    for(i=0; i<9; ++i)
    {
        if (sudoku[row][i] == num)                             return 0;
        if (sudoku[i][col] == num)                             return 0;

              for(a=8; a>0; --a) {
                if (sudoku[a][a] == 0 ) continue;
                if (sudoku[a][8-a] == 0 ) continue;

              for (j = a - 1; j >=0; j--) {
                if (sudoku[j][j]  == sudoku[a][a]) return 0;
                if (sudoku[a][8-a] == sudoku[j][8-j]) return 0;

            }
              }

            for(a=0; a<8; ++a) {
            if (sudoku[a][a] == 0 || sudoku[8][8] == 0) continue;
            if (sudoku[a][8-a] == 0 || sudoku[8][0] == 0) continue;

		    for (j = a + 1; j < 9; j++) {
                if (sudoku[j][j]  == sudoku[a][a]) return 0;
                if (sudoku[a][8-a] == sudoku[j][8-j]) return 0;

            }

            }

        if (sudoku[rowStart + (i%3)][colStart + (i/3)] == num) return 0;
    }

    return 1;
}

int fillsudoku(int sudoku[9][9], int row, int col)
{
    int i;
    if( row<9 && col<9 )
    {
        if( sudoku[row][col] != 0 )//pre filled
        {
            if( (col+1)<9 )
                return fillsudoku(sudoku, row, col+1);
            else if( (row+1)<9 )
                return fillsudoku(sudoku, row+1, 0);
            else
                return 1;
        }
        else
        {
            for(i=0; i<9; ++i)
            {
                if( isAvailable(sudoku, row, col, i+1) )
                {
                    sudoku[row][col] = i+1;

                    if( (col+1)<9 )
                    {
                    if( fillsudoku(sudoku, row, col +1) )
                        return 1;
                        else
                            sudoku[row][col] = 0;
                    }
                    else if( (row+1)<9 )
                    {
                        if( fillsudoku(sudoku, row+1, 0) )
                            return 1;
                        else
                            sudoku[row][col] = 0;
                    }
                    else
                        return 1;
                }
            }
        }
        return 0;
    }
    else
    {
        return 1;
    }
}

int main()
{
int i, j;
    int sudoku[9][9]={{0, 2, 0, 0, 0, 0, 4, 0, 0},
                      {1, 0, 0, 0, 0, 0, 0, 0, 0},
                      {0, 3, 8, 5, 0, 4, 0, 0, 1},
                      {0, 0, 0, 0, 0, 0, 7, 0, 8},
                      {0, 0, 0, 0, 6, 0, 0, 0, 0},
                      {2, 0, 5, 0, 0, 0, 0, 0, 0},
                      {4, 0, 0, 7, 0, 9, 2, 3, 0},
                      {0, 0, 0, 0, 0, 0, 0, 0, 5},
                      {0, 0, 6, 0, 0, 0, 0, 4, 0}};

    if( fillsudoku(sudoku, 0, 0) )
    {

        for(i=0; i<9; ++i)
        {
            for(j=0; j<9; ++j)
                printf("%d ", sudoku[i][j]);
            printf("\n");
        }
        printf("\a");
    }
    else
    {
        printf("\n\nNO SOLUTION\n\n");
    }

    return 0;
}

Funkci fillsudoku voláš rekurzívně. Zkus odkrokovat program a podívat se, jestli je ukončovací podmínka správně nastavena.

hu

Zajímá se pouze o to, jestli je sudoku zaplněný. Tento problém není tak triviální jak vypadá, aspoň pro mě.

Zkusil jsem to takhle a přijde mi, že jsem pořád ve slepé uličce, že to tímto způsobem vůbec nelze.

#include <stdio.h>

int zkontroluj2(int sudoku[9][9], int radek, int sloupec)
{
  int k, j, l, m;


      for (k = 0; k < 9; ++k) {
            if (sudoku[k][k] == 0 ) continue;
		for (j = k + 1; j < 9; ++j) {
			if (sudoku[j][j] == sudoku[k][k]) return 0;

        }
    }

       for (l = 0; l < 9; ++l) {
            if (sudoku[8-l][l] == 0 ) continue;
		for (m = l + 1; m < 9; ++m) {
			if (sudoku[8-m][m] == sudoku[8-l][l]) return 0;

        }
    }

}

int zkontroluj(int sudoku[9][9], int radek, int sloupec, int cislo)
{
    int i, l , m, k , j;
    int poc_radek = (radek / 3) * 3;
    int poc_sloupec = (sloupec / 3) * 3;
    zkontroluj2(sudoku, radek, sloupec);

    for(i = 0; i < 9; ++i)
    {
        if (sudoku[radek][i] == cislo)                                   return 0;
        if (sudoku[i][sloupec] == cislo)                                 return 0;

        if (sudoku[poc_radek + (i % 3)][poc_sloupec + (i / 3)] == cislo) return 0;
    }

     return 1;

}

int reseni(int sudoku[9][9], int radek, int sloupec)
{
    int i;

    if( radek < 9 && sloupec < 9 )
    {
        if( sudoku[radek][sloupec] != 0 )
        {
            if( (sloupec + 1) < 9 )
                return reseni(sudoku, radek, sloupec + 1);
            else if( (radek + 1) < 9)
                return reseni(sudoku, radek + 1, 0);
            else
                return 1;
        }
        else
        {
            for(i = 0; i < 9; ++i)
            {
                if( zkontroluj(sudoku, radek, sloupec, i + 1) )
                {
                    sudoku[radek][sloupec] = i + 1;

                    if( (sloupec + 1) < 9 )
                    {
                    if( reseni(sudoku, radek, sloupec + 1) )
                        return 1;
                        else
                            sudoku[radek][sloupec] = 0;
                    }
                    else if( (radek + 1) < 9 )
                    {
                        if( reseni(sudoku, radek + 1, 0) )
                            return 1;
                        else
                            sudoku[radek][sloupec] = 0;
                    }
                    else

                          return 1;


                }
            }
        }
        return 0;
    }
    else
    {
        return 1;
    }
}

int main(void)
{
int i, j;

    int sudoku[9][9]={{0, 0, 0, 0, 0, 6, 5, 0, 9},
                      {0, 0, 1, 0, 0, 0, 0, 0, 0},
                      {0, 0, 2, 5, 0, 0, 0, 0, 0},
                      {0, 0, 4, 0, 0, 0, 8, 0, 1},
                      {0, 0, 0, 0, 8, 0, 0, 0, 0},
                      {7, 0, 8, 0, 0, 0, 9, 0, 0},
                      {0, 0, 0, 0, 0, 7, 4, 0, 0},
                      {0, 0, 0, 0, 0, 0, 2, 0, 0},
                      {5, 0, 6, 4, 0, 0, 0, 0, 0}};

    if( reseni(sudoku, 0, 0) )
    {
        printf("Reseni sudoku:\n\n");
        for(i = 0; i < 9; ++i)
        {
            for(j = 0; j < 9; ++j)
                printf("%d ", sudoku[i][j]);
            printf("\n");
        }
        printf("\a");
    }
    else
    {
        printf("\n\nReseni neexistuje\n\n");
    }

    return 0;
}

Jakou ten druhý kód dělá chybu? Jaké je správné řešení příkladu?

hu

Da se vzit libovolny priklad odsud http://sudokuonline.cz/diagonalni.html. Bud zcela ignoruje jednu diagonalu nebo druhou diagonalu a nekdy se zase stane, ze prvni a posledni prvek je stejny. Je to zcela nevyzpytatelne.