Sudoku - jaki algorytm na rozwiązanie?

0

Witam,
poszukuję jakiegoś algorytmu pozwalającego rozwiązać sudoku. Jestem początkującym programistą, więc najlepszy byłby dla mnie pseudokod. Mimo to dziękuję za każdą formę pomocy.
Pozdrawiam

1
     Initialize 2D array with 81 empty grids(nx=9,ny=9)
     Fill in some empty grid with the known values
     Make an original copy of the array
     Start from top left grid(nx=0,ny=0), check if grid is empty
     if (grid is empty){
     assign the empty grid with values (i) 
       if (no numbers exists in same rows & same columns same as (i))
       fill in the number
       if (numbers exists in same rows & same columns same as (i))
       discard (i) and repick other values (i++)
     }else{
       while (nx<9){
         Proceed to next row grid(nx++,ny)
           if (nx equal 9){
           reset nx = 1
           proceed to next column grid(nx,ny++)
               if (ny equal 9){
               print solutions
               }
           }           
     }

http://en.wikipedia.org/wiki/Sudoku_solving_algorithms

0

Mam wrażenie, że to nie jest tak krotkie na jakie wygląda... Tam nie ma tylko kilka pętli i ifow, trzeba dodatkowe metody dorobić. Prawda?

0

Moze jakis algo genetyczny?

2

Mam wrażenie, że to nie jest tak krotkie na jakie wygląda... Tam nie ma tylko kilka pętli i ifow, trzeba dodatkowe metody dorobić. Prawda?

może coś takiego: http://www.thelearningpoint.ne[...]cience/c-program-sudoku-solver w porównaniu z innymi, które widziałam w C w internecie wydaje się prosty. - karolinaa dzisiaj, 15:24

Gotowiec rozwiązujący sudoku który niedawno dla kogoś innego na forum napisałem:

bool solve(int x, int y);

int sudoku[9][9] = { /* tu zadane sudoku... */ };
int curr[9][9];
bool can_insert(int x, int y, int value) {
    for(int i = 0; i < 9; i++) {
        if (value == curr[x][i] || value == curr[i][y] ||
            value == curr[x/3*3+i%3][y/3*3+i/3]) return false;
    } return true;
}

bool next(int x, int y) {
    if (x == 8 && y == 8) return true;
    else if (x == 8) return solve(0, y + 1);
    else return solve(x + 1, y);
}
 
bool solve(int x, int y) {
    if (sudoku[x][y] == 0) {
        for(int i = 1; i <= 9; i++) {
            if (can_insert(x, y, i)) {
                curr[x][y] = i;
                if (next(x, y)) return true;
            }
        } curr[x][y] = 0; return false;
    } return next(x, y);
}

Prosty? Prosty ;].
Zasadniczo dokładnie ten sam algorytm co na wikipedii.

Można poprawić trochę wydajność algorytmu (tzn. stałą w czasie wykonania), np. eliminując dzielenie w can_insert itd, ale starałem się jak najprostszy kod podać (zresztą jeśli przyjdzie tu Dragon to i tak mi to wypomni).

Żeby uruchomić algorytm z jakimiś testowymi danymi:

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

/* podany wyżej kod tutaj */

int main() {
    for(int i=0; i<9; i++)
        for(int j=0; j<9; j++)
            curr[i][j] = sudoku[i][j];
    if (solve(0,0)) {
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                cout<<curr[i][j];
            } cout<<endl;
        }
    } else {
        cout<<"impossible\n";
    }
    return 0;
}
0

Dziękuję wszystkim za pomoc :)

2

Jakby kogoś to bardziej kręciło to publikacja moich kolegów:
http://www.itl.waw.pl/czasopisma/JTIT/2013/2/49.pdf ;)

0

Jeszcze jedno pytanko. Chciałbym trochę podrasować program. Czy jest możliwość (w dosyć łatwy sposób) przemienić ten algorytm na taki, który rozwiąże sudoku z nieregularnymi kształtami, zamiast tych 9 kwadratów (3x3)?

0

Wystarczy że podmienisz bool can_insert(int x, int y, int value) {

0

Nie wiem czy się do końca zrozumieliśmy. Chodzi mi o sudoku z kształtami w takim stylu: http://penszko.blog.polityka.pl/wp-content/uploads/2012/10/Pesu_2.jpg

1

To najpierw przeanalizuj (przynajmniej pobieżnie) odpowiedź a potem ewentualnie "nie wiedz" czy się rozumiemy i to pod warunkiem że coś nie pasuje.

0

@msm: Cześć, dzięki za Twój algorytm :). Bardzo mi pomógł. Uczę się obecnie języka C# i w ramach ćwiczenia przepisałem Twój algorytm właśnie do tego języka.
Nie jest to może mistrzostwo świata ale zamieszczam poniżej kod, być może komuś się przyda :). Jako że jest to mój pierwszy post na forum to chciałem się również przywitać :). Zatem ... Witajcie :).
W stosunku do zamieszczonego oryginału dodałem 2 drobne zmiany. Pierwsza z nich to podział wyniku na dziewięć dziewięciocyfrowych pól (tak jak w zwykłym Sudoku). Druga zmiana to prosta metoda wypisująca nierozwiązane Sudoku.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sudoku
{
    class Program
    {

        static void Main(string[] args)
        {

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

            Sudoku sudo = new Sudoku(sudoku);

            sudo.WypiszNierozwiazane();
            Console.WriteLine();
            sudo.WypiszRozwiazane();

            Console.ReadLine();

        }
    }

    class Sudoku
    {

        private int[,] TablicaDanych { get; set; }

        private readonly int[,] Curr = new int[9, 9];

        public Sudoku(int[,] tablicaDanych)
        {
            this.TablicaDanych = tablicaDanych;
        }

        private bool Can_insert(int x, int y, int value)
        {
            for (int i = 0; i < 9; i++)
            {
                if (value == Curr[x, i] || value == Curr[i, y] || value == Curr[x / 3 * 3 + i % 3, y / 3 * 3 + i / 3])
                {
                    return false;
                }
            }
            return true;
        }

        private bool Next(int x, int y)
        {
            if (x == 8 && y == 8)
            {
                return true;
            }
            else if (x == 8)
            {
                return Solve(0, y + 1);
            }
            else
            {
                return Solve(x + 1, y);
            }
        }

        private bool Solve(int x, int y)
        {
            if (TablicaDanych[x, y] == 0)
            {
                for (int i = 1; i <= 9; i++)
                {
                    if (Can_insert(x, y, i))
                    {
                        Curr[x, y] = i;

                        if (Next(x, y))
                        {
                            return true;
                        }
                    }
                }
                Curr[x, y] = 0; return false;
            }
            return Next(x, y);
        }

        public void WypiszNierozwiazane()
        {
            for (int a = 0; a < 9; a++)
            {
                for (int b = 0; b < 9; b++)
                {
                    Console.Write(TablicaDanych[a, b]);

                    if (b == 2 || b == 5)
                    {
                        Console.Write(" | ");
                    }
                }

                Console.WriteLine();
                if (a == 2 || a == 5)
                {
                    Console.WriteLine("---------------");
                }
            }
        }

        public void WypiszRozwiazane()
        {

            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    Curr[i, j] = TablicaDanych[i, j];
                }
            }

            if (Solve(0, 0))
            {
                for (int i = 0; i < 9; i++)
                {
                    for (int j = 0; j < 9; j++)
                    {
                        Console.Write(Curr[i, j]);

                        if (j == 2 || j == 5)
                        {
                            Console.Write(" | ");
                        }
                    }

                    Console.WriteLine();
                    if (i == 2 || i == 5)
                    {
                        Console.WriteLine("---------------");
                    }

                }
            }
            else
            {
                Console.WriteLine("impossible\n");
            }
        }

    }

}

0

@mario_wu:

Cześć, czy mógłbyś opisać pod komentarzami co się dzieje w kodzie krok po kroku?

1 użytkowników online, w tym zalogowanych: 0, gości: 1