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
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
}
}
}
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?
Moze jakis algo genetyczny?
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;
}
Dziękuję wszystkim za pomoc :)
Jakby kogoś to bardziej kręciło to publikacja moich kolegów:
http://www.itl.waw.pl/czasopisma/JTIT/2013/2/49.pdf ;)
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)?
Wystarczy że podmienisz bool can_insert(int x, int y, int value) {
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
To najpierw przeanalizuj (przynajmniej pobieżnie) odpowiedź a potem ewentualnie "nie wiedz" czy się rozumiemy i to pod warunkiem że coś nie pasuje.
@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");
}
}
}
}
Cześć, czy mógłbyś opisać pod komentarzami co się dzieje w kodzie krok po kroku?