rompecabezas cuadrado solución

Question

Pregunta: dado un número entero n, imprimir los números de 1 hasta n como esto:

n = 4

resultado es:

01 02 03 04 
12 13 14 05 
11 16 15 06 
10 09 08 07 

Cómo ¿Lo resuelve (aparte de la solución proporcionada en el siguiente enlace)?

http://www.programmersheaven.com/mb/CandCPP/81986/81986/problem-in-making-ap-c++-program/?S=B20000

estoy mirando en otra dirección. Hasta ahora, estoy tratando de averiguar si puedo obtener la lista ordenada de posiciones que tengo que completar.

Esto es lo que estoy buscando: ¿hay alguna manera de obtener el "fdisp" para resolver el problema de esa manera, en lugar de "caminar" en la matriz?

matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]] 
n = len(matrix) 

# final disposition wrote by hand: how to get it for arbitrary n? 
fdisp = [(0,0), (0,1), (0,2), (0,3), (1,3), (2,3), (3,3), (3,2), 
     (3,1), (3,0), (2,0), (1,0), (1,1), (1,2), (2,2), (2,1)] 

for val,i in enumerate(fdisp): 
    matrix[i[0]][i[1]] = val + 1 

def show_matrix(matrix, n): 
    for i,l in enumerate(matrix): 
     for j in range(n): 
      print "%d\t" % matrix[i][j], 
     print 

show_matrix(matrix, n) 

Answer 1

Aunque el ejemplo está en pitón y esto es en Java, creo que debería ser capaz de seguir la lógica:

public class SquareTest { 

public static void main(String[] args) { 
    SquareTest squareTest = new SquareTest(4); 
    System.out.println(squareTest); 
} 

private int squareSize; 
private int[][] numberSquare; 
private int currentX; 
private int currentY; 
private Direction currentDirection; 

private enum Direction { 
    LEFT_TO_RIGHT, RIGHT_TO_LEFT, TOP_TO_BOTTOM, BOTTOM_TO_TOP; 
}; 

public SquareTest(int squareSize) { 
    this.squareSize = squareSize; 
    numberSquare = new int[squareSize][squareSize]; 
    currentY = 0; 
    currentX = 0; 
    currentDirection = Direction.LEFT_TO_RIGHT; 
    constructSquare(); 
} 

private void constructSquare() { 
    for (int i = 0; i < squareSize * squareSize; i = i + 1) { 
     numberSquare[currentY][currentX] = i + 1; 
     if (Direction.LEFT_TO_RIGHT.equals(currentDirection)) { 
      travelLeftToRight(); 
     } else if (Direction.RIGHT_TO_LEFT.equals(currentDirection)) { 
      travelRightToLeft(); 
     } else if (Direction.TOP_TO_BOTTOM.equals(currentDirection)) { 
      travelTopToBottom(); 
     } else { 
      travelBottomToTop(); 
     } 
    } 
} 

private void travelLeftToRight() { 
    if (currentX + 1 == squareSize || numberSquare[currentY][currentX + 1] != 0) { 
     currentY = currentY + 1; 
     currentDirection = Direction.TOP_TO_BOTTOM; 
    } else { 
     currentX = currentX + 1; 
    } 
} 

private void travelRightToLeft() { 
    if (currentX - 1 < 0 || numberSquare[currentY][currentX - 1] != 0) { 
     currentY = currentY - 1; 
     currentDirection = Direction.BOTTOM_TO_TOP; 
    } else { 
     currentX = currentX - 1; 
    } 
} 

private void travelTopToBottom() { 
    if (currentY + 1 == squareSize || numberSquare[currentY + 1][currentX] != 0) { 
     currentX = currentX - 1; 
     currentDirection = Direction.RIGHT_TO_LEFT; 
    } else { 
     currentY = currentY + 1; 
    } 
} 

private void travelBottomToTop() { 
    if (currentY - 1 < 0 || numberSquare[currentY - 1][currentX] != 0) { 
     currentX = currentX + 1; 
     currentDirection = Direction.LEFT_TO_RIGHT; 
    } else { 
     currentY = currentY - 1; 
    } 
} 

@Override 
public String toString() { 
    StringBuilder builder = new StringBuilder(); 
    for (int i = 0; i < squareSize; i = i + 1) { 
     for (int j = 0; j < squareSize; j = j + 1) { 
      builder.append(numberSquare[i][j]); 
      builder.append(" "); 
     } 
     builder.append("\n"); 
    } 

    return builder.toString(); 
} 
} 

Answer 2

Otra manera de hacerlo, esta vez en C#:

int number = 9; 
var position = new { x = -1, y = 0 }; 
var directions = new [] { 
    new { x = 1, y = 0 }, 
    new { x = 0, y = 1 }, 
    new { x = -1, y = 0 }, 
    new { x = 0, y = -1 } 
}; 

var sequence = (
    from n in Enumerable.Range(1, number) 
    from o in Enumerable.Repeat(n, n != number ? 2 : 1) 
    select o 
).Reverse().ToList(); 

var result = new int[number,number]; 

for (int i = 0, current = 1; i < sequence.Count; i++) 
{ 
    var direction = directions[i % directions.Length];  

    for (int j = 0; j < sequence[i]; j++, current++) 
    { 
     position = new { 
      x = position.x + direction.x, 
      y = position.y + direction.y 
     }; 

     result[position.y, position.x] = current; 
    } 
} 

Answer 3

Encontré una manera. Ahora tengo que mejorarlo un poco, especialmente tengo que encontrar una manera más limpia de construir "fdisp". n = 5

dim = n 
pos = (0, -1) 
fdisp = [] 
squares = n % 2 == 0 and n/2 or n/2 + 1 

for _ in range(squares): 
    pos = (pos[0], pos[1] + 1) 
    fdisp.append(pos) 

    fdisp += [(pos[0],pos[1]+i) for i in range(1, dim)] 
    pos = fdisp[-1] 
    fdisp += [(pos[0]+i,pos[1]) for i in range(1, dim)] 
    pos = fdisp[-1] 
    fdisp += [(pos[0],pos[1]-i) for i in range(1, dim)] 
    pos = fdisp[-1] 
    fdisp += [(pos[0]-i,pos[1]) for i in range(1, dim - 1)] 
    pos = fdisp[-1] 
    dim = dim - 2 

matrix = [[0] * n for i in range(n)] 

for val,i in enumerate(fdisp): 
    matrix[i[0]][i[1]] = val + 1 

def show_matrix(matrix, n): 
    for i,l in enumerate(matrix): 
     for j in range(n): 
      print "%d\t" % matrix[i][j], 
     print 

show_matrix(matrix, n) 

Answer 4

Así es un enfoque diferente. Se basa en detectar que los movimientos que haces cambian de un ciclo a otro: derecha, abajo, izquierda, arriba, derecha, .... Además, el número de veces que te mueves es: 3 hacia la derecha, 3 hacia abajo, 3 hacia la izquierda, 2 hacia arriba, 2 hacia la derecha , 1 abajo, 1 izquierda. Así que sin más preámbulos, voy a codificar esto en Python.

En primer lugar, voy a utilizar algunos itertools y algunos numpy:

from itertools import chain, cycle, imap, izip, repeat 
from numpy import array 

El ciclo direcciones entre: derecha, abajo, izquierda, arriba, derecha, ...:

directions = cycle(array(v) for v in ((0,1),(1,0),(0,-1),(-1,0))) 

(I Estoy usando las matrices numpy aquí, así que puedo agregar direcciones fácilmente juntas. Las tuplas no se agregan bien.)

A continuación, el número de veces que me muevo una cuenta atrás de n-1 a 1, repitiendo cada número dos veces, y el primer número tres veces:

countdown = chain((n-1,), *imap(repeat, range(n-1,0,-1), repeat(2))) 

Así que ahora mi secuencia de direcciones se puede crear repitiendo cada dirección sucesiva por el número emparejado en cuenta regresiva:

dirseq = chain(*imap(repeat, directions, countdown)) 

para conseguir mi secuencia de índices, puedo resumir esta secuencia, pero (que yo sepa) Python no proporciona un procedimiento de este tipo, por lo que vamos rápidamente lanzar una juntos:

def sumseq(seq, start=0): 
    v = start 
    yield v 
    for s in seq: 
    v += s 
    yield v 

Ahora, para generar la matriz original, puedo hacer lo siguiente:

a = array(((0,)*n,)*n) # n-by-n array of zeroes 
for i, v in enumerate(sumseq(dirseq, array((0,0)))): 
    a[v[0], v[1]] = i+1 
print a 

Lo cual, para n = 4, da:

[[ 1 2 3 4] 
[12 13 14 5] 
[11 16 15 6] 
[10 9 8 7]] 

y, para n = 5, da :

[[ 1 2 3 4 5] 
[16 17 18 19 6] 
[15 24 25 20 7] 
[14 23 22 21 8] 
[13 12 11 10 9]] 

Este enfoque se puede generalizar a cuadrículas rectangulares; Dejo esto como ejercicio para el lector;)

Answer 5

He resuelto su problema usando C++. No sé si será útil para ti. Pero publicarlo. Si funciona para ti, será un placer.

Aquí está el código:

#include<iostream> 
    #include<string.h> 
    using namespace std; 

    bool valid(int n,int r,int c) 
    { 
     if(r>=1 && r<=n && c>=1 && c<=n) 
      return true; 
     return false; 
    } 


    int main() 
    { 
     pair<int,int>d1,d2,d3,d4,temp; 
     d1 = make_pair(0,1); 
     d2 = make_pair(1,0); 
     d3 = make_pair(0,-1); 
     d4 = make_pair(-1,0); 
     /**********************direction******************************/ 

     int n, i, j, counter=1, newR = 1, newC = 0, direction = 4; 
     bool changeDir=true; 
     /**************************variables*************************/ 

     cin>>n; 
     int arr[n+1][n+1]; 
     int visited[n+1][n+1]; 
     /*************************arrays********************************/ 

     memset(visited,0,sizeof(visited)); 
     memset(arr,0,sizeof(arr)); 
     /***************initializing the array**************************/ 

     while(counter<=n*n) 
     { 
      if(direction==1 && changeDir) 
      { 
       temp = make_pair(d2.first,d2.second); 
       direction=2; 
       changeDir=false; 
      } 
      else if(direction==2&& changeDir) 
      { 
       temp = make_pair(d3.first,d3.second); 
       direction=3; 
       changeDir=false; 
      } 
      else if(direction==3&& changeDir) 
      { 
       temp = make_pair(d4.first,d4.second); 
       direction=4; 
       changeDir=false; 
      } 
      else if(direction==4&& changeDir) 
      { 
       temp = make_pair(d1.first,d1.second); 
       direction=1; 
       changeDir=false; 
      } 
      while(counter<=(n*n) && !changeDir) 
      { 
       newR =newR+temp.first; 
       newC=newC+temp.second; 
       if(valid(n,newR,newC) && !visited[newR][newC]) 
       { 
        arr[newR][newC]=counter; 
        visited[newR][newC]=1; 
        counter++; 
       } 
       else 
       { 
        newR-=temp.first; 
        newC-=temp.second; 
        changeDir=true; 
        break; 
       } 
      } 
     } 
     for(i=1;i<=n;i++) 
     { 
      for(j=1;j<=n;j++) 
      { 
       if(arr[i][j]<10) 
        cout<<0; 
       cout<<arr[i][j]<<" "; 
      } 
      cout<<endl; 
     } 
     return 0; 
    } 

Aquí está la salida donde N = 5:

01 02 03 04 05 
16 17 18 19 06 
15 24 25 20 07 
14 23 22 21 08 
13 12 11 10 09 

Gracias.