quadrato di puzzle soluzione

Question

Domanda: dato un numero intero n, stampare i numeri da 1 a n come questo:

n = 4

risultato è:

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

Come lo risolvi (a parte la soluzione fornita nel link sottostante)?

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

sto guardando in un'altra direzione. Finora, sto cercando di capire se posso ottenere l'elenco ordinato delle posizioni che devo compilare.

Ecco cosa sto cercando: c'è un modo per ottenere il "fdisp" in modo da risolvere il problema problema in questo modo, invece di "camminare" nella matrice?

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

Anche se il vostro esempio è in python e questo è in Java, penso che si dovrebbe essere in grado di seguire la logica:

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

Un altro modo per farlo, questa volta in 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

Ho trovato un modo. Ora devo migliorare un po ', soprattutto devo trovare un modo più semplice per creare "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

Ecco un approccio diverso. Fa affidamento sul localizzare che i movimenti che fai scorrono ciclicamente: a destra, in basso, a sinistra, in alto, a destra, .... Inoltre, il numero di volte che ti muovi va: 3 a destra, 3 in basso, 3 a sinistra, 2 in alto, 2 a destra , 1 in basso, 1 a sinistra. Quindi, senza ulteriori indugi, lo codificherò in Python.

In primo luogo, userò alcuni itertools e alcuni NumPy:

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

Il ciclo direzioni tra: a destra, giù, sinistra, su, a destra, ...:

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

(I Sto usando gli array di numpy qui, quindi posso facilmente aggiungere direzioni insieme. Le tuple non si aggiungono bene.)

successivo, il numero di volte in cui mi muovo il conto alla rovescia da n-1 a 1, ripetendo ogni numero due volte, e il primo numero per tre volte:

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

Così ora la mia sequenza di direzioni può essere creato ripetendo ogni direzione successiva per il numero abbinato nel conto alla rovescia:

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

per ottenere la mia sequenza di indici, posso solo riassumere questa sequenza, ma (per quanto ne so) Python non fornisce un tale metodo, quindi cerchiamo di fretta gettare uno insieme:

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

Ora per generare la matrice originale, posso effettuare le seguenti operazioni:

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 

Il che, per n = 4, dà:

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

e, per n = 5, dà :

[[ 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]] 

Questo approccio può essere generalizzato alle griglie rettangolari; Lascio questo come esercizio per il lettore;)

Answer 5

Ho risolto il problema usando C++. Non so se ti sarà d'aiuto. Ma pubblicandolo. Se funziona per te sarà un piacere.

Ecco il codice:

#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; 
    } 

Ecco l'output dove 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 

Grazie.