Autor Tema: [Reto] Sudoku (backtracking 3)  (Leído 1534 veces)

Desconectado good

  • PHPerit@
  • *
  • Mensajes: 49
  • Karma: 0
  • Nuev@ PHPer@
    • Ver Perfil
[Reto] Sudoku (backtracking 3)
« en: 13 de Agosto de 2011, 22:01:49 pm »
Hola,

Podrías hacer un programa sencillo que resuelva un sueoku?

Entrada:

Un sudoku, 9 filas de 9 columnas cada una inidicando con 0 las casillas vacías.

Salida:

Una solución al sudoku pasado por la entrada



Ejemplo de entrada:

0 0 7 0 0 0 0 0 2
0 0 0 1 3 0 0 8 6
2 0 0 0 8 4 0 0 5
0 3 1 8 0 0 0 0 4
0 7 0 9 0 0 0 0 0
5 9 0 0 7 0 0 3 0
3 0 4 0 0 1 0 5 0
0 0 0 5 0 0 0 0 0
0 0 0 0 0 0 8 0 0

Ejemplo de Salida:

8 1 7 6 5 9 3 4 2
9 4 5 1 3 2 7 8 6
2 6 3 7 8 4 1 9 5
6 3 1 8 2 5 9 7 4
4 7 2 9 1 3 5 6 8
5 9 8 4 7 6 2 3 1
3 8 4 2 9 1 6 5 7
7 2 9 5 6 8 4 1 3
1 5 6 3 4 7 8 2 9



El truco de este problema es saber qué números se pueden poner, es decir, no sería eficiente probar todos los número [1,9] inclusive, el programa tardaría demasiado tiempo. Yo recomendaría hacer alguna(s) funciones para saber qué números pueden encajar en cada casilla (teniendo en cuenta la fila en la que estamos, la columna y el cuadrado de 3x3)

Fuente: Olimpiada informática española
« Última modificación: 13 de Agosto de 2011, 22:15:02 pm por good »

Comunidad PHPeros

[Reto] Sudoku (backtracking 3)
« en: 13 de Agosto de 2011, 22:01:49 pm »

Desconectado good

  • PHPerit@
  • *
  • Mensajes: 49
  • Karma: 0
  • Nuev@ PHPer@
    • Ver Perfil
Re:[Reto] Sudoku (backtracking 3)
« Respuesta #1 en: 13 de Agosto de 2011, 22:26:15 pm »
Lo que yo hice para éste fue crear tres funciones booleanas: una que me dijera si un número estaba en una fila dada, otra que me decía si lo estaba en una columna y la otra si lo estaba en un cierto cuadrado de 3x3

El backtracking funcionaba de la siguiente manera:

Empezaba en la primera casilla con un 0, y probaba allí todas los números posibles en este orden:

Primero probaba un número y llamaba a la función para que hiciera el backtracking, y cuando ésta terminaba (si es que lo hacia), volvía a poner la casilla en valor 0

El Código no es muy largo, talvez cuesta entender, yo tardé un tiempo en comprender el backtracking xDD pero bueno, si quereis puedo poner una solución

Desconectado good

  • PHPerit@
  • *
  • Mensajes: 49
  • Karma: 0
  • Nuev@ PHPer@
    • Ver Perfil
Re:[Reto][Solución] Sudoku (backtracking 3)
« Respuesta #2 en: 15 de Agosto de 2011, 14:43:09 pm »
Una solución posible (hay una manera más eficiente pero no la sé xD) es ésta:

Código: [Seleccionar]
#include <iostream>
#include <vector>
using namespace std;

typedef vector<vector<int> > VVI;
typedef vector<pair<int, int> > VPII;

bool se_puede (VVI& v, int xx, int y, int numero) {
for (int i = 0; i < 9; ++i) {
if (v[xx][i] == numero) return false;
else if (v[i][y] == numero) return false;
}

int fil = 3*(xx/3);
int col = 3*(y/3);
for (int i = fil; i < fil+3; ++i) {
for (int x = col; x < col+3; ++x) {
if (v[i][x] == numero) return false;
}
}
return true;
}

void backtrack (VVI& sudoku, VPII& pos, int count) {
if (count == pos.size()) {
for (int i = 0; i < 9; ++i) {
for (int x = 0; x < 8; ++x) cout << sudoku[i][x] << " ";
cout << sudoku[i][8];
cout << endl;
}
} else {
pair<int, int> p = pos[count];
int posX = p.first;
int posY = p.second;
for (int i = 0; i < 9; ++i) {
if (se_puede(sudoku, posX, posY, i+1)) {
sudoku[posX][posY] = i+1;
backtrack(sudoku, pos, count+1);
sudoku[posX][posY] = 0;
}
}
}
}

int main () {
VVI sudoku(9, vector<int>(9));
VPII blank;
for (int i = 0; i < 9; ++i) {
for (int x = 0; x < 9; ++x) {
cin>>sudoku[i][x];
if (sudoku[i][x] == 0) blank.push_back(make_pair(i, x));
}
}
backtrack(sudoku, blank, 0);
}

la función se_puede devuelve true sí un número (int numero) se puede poner en una casilla específica para un tablero dado.