Tengo un rompecabezas de 6 * 6 con 35 números (1 ~ 35) en una secuencia aleatoria. Use el en blanco como un 'registro' y mueva los números uno por uno para que estén en orden. Puedo lidiar con un rompecabezas 3 * 3, pero ¿cómo lidiar con un 6 * 6? ¿Podrías darme algunas pistas? 
6 * 6 algoritmo de rompecabezas
La idea es la misma, representar el problema como estados graph, y ejecutar el algoritmo shortest path.
Si la eficiencia del algoritmo es importante, es posible que desee un algoritmo informado -como A* algorithm, que se espera que sea bastante rápido (en relación a las alternativas) con un buen admissible heuristic function.
Una solución más lenta aunque más simple puede ejecutar un BFS.
Ambos algoritmos (A *, BFS) son a la vez completa (siempre encuentra una solutuion, si es que existe) y óptima (encuentra camino más corto).
También tenga en cuenta, puede utilizar macros para aprender "buena" serie de movimientos, para obtener el algoritmo más rápido. Ignore esta mejora hasta que implemente una solución de trabajo (aunque lenta).
EDIT: directrices de codificación:
mirar el problema como un gráfico: El gráfico será G=(V,E) donde V = { all possible states} y E = { (u,v) | can move from state u to state v within a single step }
Ahora, con este gráfico - que tienen una posición de partida (la fuente, que se da como entrada) y un objetivo (un rompecabezas ordenado). Inicie un BFS o A * (eche un vistazo al pseudo código de estos en los enlaces de wikipedia adjuntos), para encontrar una ruta desde el origen hasta el destino. Deberías comenzar con BFS, es más simple.
La ruta devuelta por el algoritmo de ruta más corta es idéntica a la serie de movimientos que tendrá que hacer para pasar del tablero inicial al objetivo.
Nota: ¡No es necesario crear el gráfico real! solo necesita mantener el nodo inicial (origen) y crear su vértice, y tener una función successors:V->2^V, que le proporciona los sucesores para cada vértice (formalmente: successors(v) = { (v,u) | (v,u) is in E }). De esta manera, puedes construir la parte relevante del gráfico sobre la marcha.
La eficiencia es probablemente un problema en una matriz tan pequeña, especialmente si se trata de una tarea o un problema de aprendizaje. –
Para ser sincero, no sé cómo resolver este problema y esta respuesta no ayuda. El pseudo código de muy alto nivel sería una buena forma de demostrar cómo se haría esto. –
@Tyler: esta respuesta supone que OP ya usa esta estrategia para 3x3, pero que no es lo suficientemente rápida para funcionar con 6x6. Sin más información de OP, realmente no podemos ahora cuál es el problema. –
Una simple estrategia para este juego es poner los números correctos en la fila superior (debería ser fácil porque no te importan otros números, los dos últimos números son un poco más difíciles de poner en el lugar correcto porque debe colocarlos a ambos en el mismo movimiento), congelar la fila superior y continuar con la columna izquierda y luego con la fila superior y luego con la columna izquierda ...
No es la estrategia óptima, pero es uno que funciona y es simple de codificar.
He estudiado este mismo problema/rompecabezas cuando estaba en la universidad y es un problema muy interesante que implica la IA y las técnicas heurísticas y la teoría de grafos. Como se indica en amit, se recomienda encarecidamente que marque A *, BFS y heurística.
Aquí está mi contribución: al tratar de resolver esto, puedes probar una división de para conquistar estrategia.Puedes pensar que esta cuadrícula de 6x6 es solo cuatro cuadrículas de 3x3 juntas, e intenta resolverlas como casos separados en un orden determinado.
Por ejemplo, se puede tratar el siguiente algoritmo:
La última cuestión que decir es que hay que prestar atención en qué esquina se va a dejar como espacio de trabajo como no se puede dejar que la esquina superior derecha de la cuadrícula superior derecha sea su espacio de trabajo " piezas faltantes "porque no será posible poner una pieza allí en el futuro;
Ps1: espacio de trabajo es la posición que temporalmente dejó pasar la pieza, para poder tener un espacio libre para maniobrar las piezas;
Ps2: en este contexto, la cuadrícula es una combinación de piezas NxN, que tienen todas las piezas correctas, no necesariamente en orden.
Espero haber ayudado de alguna manera. :-)
gracias, también. usted y amit ambos me dan mucha ayuda :-) – tmj
Creo que si recorremos toda la matriz 6 * 6 A la vez, podremos encontrar un solo número pequeño y moverlo a la siguiente matriz, que no es una solución relevante. Una mejor forma de resolver este problema es usar la búsqueda binaria en la matriz dada. Si aplicamos la búsqueda binaria, entonces habrá una alta complejidad de tiempo. Entonces, ¿cuál es la mejor manera de resolver este problema?
Le pedí que todos tengan un vistazo en el siguiente código. El código de abajo es la solución para el problema anterior. He resuelto el problema anterior utilizando Insertion Sort. No es necesario usar BFS o cualquier otro cosas –
He resuelto el problema anterior rompecabezas usando el algoritmo Inserting Sort. Me llevó casi 2 días resolver el rompecabezas anterior. Simplemente ejecute el código de .Net si tiene que preguntar algo, simplemente déjeme un mensaje. No he usado ninguna clase C# incorporada para resolver el problema anterior. Es una solución de código lógico pura c con el código
private static void MazePuzzle()
{
/****
* A typical C Problem for Maze puzzle has been solved by prince.It took almost 3 days.
* Problem is about Sorting a 2D Matrix with any number of row and column
* This problem is also known as Rat Maze puzzle
* It is also be a typical Backtracking Problem
* ***/
const int _row = 6;
const int _coloumn = 6;
//int _column1 = _coloumn;
int[,] _doubleArray = new int[_row, _coloumn] { { 19, 2, 4, 34, 23, 41 }, { 11, 63, 3, 93, 65, 98 }, { 12, 80, 15, 76, 71, 90 }, { 119, 32, 94, 84, 23, 41 }, { 129, 232, 124, 341, 253, 411 }, { 197, 289, 47, 343, 293, 401 } };
int [] _StoringArray1D=new int[_row*_coloumn];
int i = 0;
int j = 0;
int _comparingArrayElement = 0;
int _swipeTemp = 0;
for (; i < _row; i++)
{
int _trackrow = 0;
for (;j <_coloumn; j++)
{
_trackrow = 0;
if(i==0 && j==0)
{
_comparingArrayElement= _doubleArray[i, j + 1];
if(_comparingArrayElement<_doubleArray[i,j])
{
_swipeTemp = _doubleArray[i,j+1];
_doubleArray[i, j + 1] = _doubleArray[i, j];
_doubleArray[i, j] = _swipeTemp;
}//innerMost if
}//For First time
else
{
int k = 0;
do
{
if (_trackrow == i || _trackrow < i)
{
for (; k < _coloumn; k++)
{
if(k==j && i==_trackrow)
{
break;
}
else
{
if(_doubleArray[_trackrow,k]>_doubleArray[i,j])
{
int _swipetempPrevious=_doubleArray[_trackrow,k];
_doubleArray[_trackrow,k]=_doubleArray[i,j];
_doubleArray[i, j] = _swipetempPrevious;
}
else
{
//do nothing just traverse
}//swipe else
}//k==j else
}//inner for do while
_trackrow++;
k = 0;
}//trackrow if
else
{
break;
}//trackrow else
} while (true);
}//else
}//innner for
j = 0;
}//outer for
Console.WriteLine("End of Program");
}//Maze Puzzle Method
¿Es esta tarea? –
¿Cómo lidiar con la carcasa 3x3? –
* Cualquier * secuencia aleatoria? Incluso los insoportables? – harold