Опытный
Профиль
Группа: Участник
Сообщений: 345
Регистрация: 25.11.2006
Репутация: нет
Всего: 1
|
| Код |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define NCAR 200+1
#define N 9
#define CAJA 3
typedef struct
{
int fila;
int columna;
} TPosicion;
int calcularEtapaFinal(int[][N], int);
int sudokuBT(int[][N],int,int,int,int,TPosicion);
void comprobarLinea(int[],int,int[]);
void comprobarColumna(int[][N],int,int,int[]);
void comprobarCaja(int[][N],TPosicion,int,int[]);
void imprimirSudoku(int[][N],int,int);
int main()
{
//с этим судоко не пашет
int sudoku[N][N] =
{
{5,3,0, 0,7,0, 0,0,0},
{6,0,0, 1,9,5, 0,0,0},
{0,9,8, 0,0,0, 0,6,0},
{8,0,0, 0,6,0, 0,0,3},
{4,0,0, 8,0,3, 0,0,1},
{7,0,0, 0,2,6, 0,0,6},
{0,6,0, 0,0,0, 2,8,0},
{0,0,0, 4,1,9, 0,0,5},
{0,0,0, 0,8,0, 0,7,9}
};
//с этим судоко ПАШЕТ ))
/*int sudoku[N][N] =
{
{8,0,0,0,0,0,6,0,0},
{0,2,9,6,7,0,0,1,0},
{0,0,0,0,1,4,0,5,0},
{6,0,0,3,9,1,5,0,2},
{0,5,1,0,0,0,9,0,0},
{9,0,2,0,0,6,0,0,0},
{0,6,0,4,3,0,0,0,0},
{0,9,0,0,8,7,1,6,0},
{0,0,7,0,0,0,0,0,3}
};*/
int booleanSudokuSolucion;
int etapaFinal;
//распечатка
imprimirSudoku(sudoku,N,CAJA);
//сколько всего этапов будет, тойсть сколько пустых ячеек столько и этапов
etapaFinal=calcularEtapaFinal(sudoku,N);
//сам бэктрак
booleanSudokuSolucion=sudokuBT(sudoku,N,CAJA,1,etapaFinal);
printf("\n\n\n Sudoku %s esta resuelto!\n", !booleanSudokuSolucion ? "no": "");
imprimirSudoku(sudoku,N,CAJA);
return 0;
}
int calcularEtapaFinal(int sudoku[][N], int size)
{
int x,y;
int etapas=0;
for(x=0; x<size; x++)
for(y=0; y<size; y++)
if(!sudoku[x][y])
etapas++;
return etapas;
}
int sudokuBT(int sudoku[][N],int sizeSudoku,int sizeCaja,int etapaActual,int etapaFinal)
{
int numerosCandidatos[] = {1,2,3,4,5,6,7,8,9};//возможные комбинации
int exito=0;
int elementoVacio=0;
int x,y;
for(x=0; x<sizeSudoku && !elementoVacio; x++)
for(y=0; y<sizeSudoku && !elementoVacio; y++)
if(!sudoku[x][y])
{
posActual.fila=x;
posActual.columna=y;
elementoVacio=1;
}
if(elementoVacio)//если мы нашли пустой элемент, ячейку с нуликом
{
comprobarLinea(sudoku[posActual.fila],sizeSudoku,numerosCandidatos);//проверка линии
comprobarColumna(sudoku,posActual.columna,sizeSudoku,numerosCandidatos);//проверка колонки
comprobarCaja(sudoku,posActual,sizeCaja,numerosCandidatos);//проверка 3х3
for(x=0; x<sizeSudoku && !exito; x++) // пробуем все числа которые остались в списке кандидатов после 3 последних проверок
if(numerosCandidatos[x])
{
//***************************************//
/*imprimirSudoku(sudoku,N,CAJA);
puts("\n");
int z;
for(z=0; z<sizeSudoku; z++)
printf("\n$%i...%i.%i:%i -> %i,",etapaActual,posActual.fila,posActual.columna,z,numerosCandidatos[z]);
printf("\n%i -> %i,",x,numerosCandidatos[x]);
puts("\n");
system("pause");*/
//***************************************//
sudoku[posActual.fila][posActual.columna]=numerosCandidatos[x];
if(etapaActual==etapaFinal) // если последний этап,То на выход
exito=1;
else // если нет, то дальше в глубь
{
exito=sudokuBT(sudoku,sizeSudoku,sizeCaja,etapaActual+1,etapaFinal);
if(!exito)
sudoku[posActual.fila][posActual.columna]=0;
}
}
}
return exito;
}
void comprobarLinea(int v[], int size,int numerosCandidatos[])
{
int i;
for(i=0; i<size; i++)
if(v[i])
numerosCandidatos[ v[i] - 1 ]=0;
}
void comprobarColumna(int v[][N], int columna,int size,int numerosCandidatos[])
{
int i;
for(i=0; i<size; i++)
if(v[i][columna])
numerosCandidatos[ v[i][columna] - 1 ]=0;
}
void comprobarCaja(int v[][N], TPosicion p,int sizeCaja,int numerosCandidatos[])
{
int x,y;
while(p.fila%sizeCaja && p.fila) p.fila--;
while(p.columna%sizeCaja && p.columna) p.columna--;
for(x=0; x<sizeCaja; x++)
{
for(y=0; y<sizeCaja; y++)
{
//printf("%i ",v[p.fila+x][p.columna+y]);
if(v[p.fila+x][p.columna+y])
numerosCandidatos[ v[p.fila+x][p.columna+y] - 1 ]=0;
}
//printf("\n");
}
}
void imprimirSudoku(int sudoku[][N],int sizeSudoku,int sizeCaja)
{
puts("\n");
int x,y,i;
for(x=0; x<sizeSudoku; x++)
{
if(!x || !(x%sizeCaja))
for(i=0; i<sizeSudoku; i++)
printf("------");
printf("\n");
for(y=0; y<sizeSudoku; y++)
{
if(!y || !(y%sizeCaja))
printf(" |");
printf(" %i ",sudoku[x][y]);
}
printf("|\n");
}
for(i=0; i<sizeSudoku; i++)
printf("------");
}
|
вообщем не знаю где ошибка моя, уже устал спать хочу, помогите плиз  да и вообще как вам алгоритм? похоже на бэктракинг? или нет? можно лучше сделать? спасибо всем за помощь |
Sudoku Backtracking, бро хелп мы ) 
Загрузка ...
