quadratische Puzzle Lösung

Question

Frage: eine ganze Zahl n, drucken die Zahlen von 1 bis n wie folgt gegeben:

n = 4

Ergebnis ist:

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

Wie Löst man es (abgesehen von der Lösung, die im unten stehenden Link angegeben ist)?

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

Ich bin in einer anderen Richtung. Bisher versuche ich herauszufinden, ob ich die geordnete Liste der Positionen, die ich ausfüllen muss, bekommen kann.

Hier ist was ich im Auge: gibt es eine Möglichkeit, die "fdisp" zu erhalten, um die zu lösen Problem auf diese Weise, anstatt "in der Matrix" zu gehen?

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

Obwohl Ihr Beispiel in Python ist, und dies ist in Java, ich glaube, Sie sollten die Logik folgen können:

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

Eine andere Möglichkeit, es zu tun, diesmal 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

Ich fand einen Weg. Jetzt muss ich es ein bisschen verbessern, vor allem muss ich einen saubereren Weg finden, um "fdisp" zu bauen. 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

Hier ist ein anderer Ansatz. Es hängt davon ab, zu erkennen, dass die Bewegungen, die Sie machen, zwischen den Modi "rechts", "unten", "links", "oben", "rechts", "weiter" und "rechts", "3 nach unten", "3 nach links", "2 nach oben" und "nach rechts" gehen , 1 nach unten, 1 nach links. Also werde ich das ohne weiteres in Python programmieren.

Zuerst werde ich einige itertools verwenden und einige numpy:

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

Die Richtungen Zyklus zwischen: rechts, unten, links, oben, rechts, ...:

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

(I verwende numpy's arrays hier, damit ich einfach Richtungen addieren kann. Tupel fügen nicht schön hinzu.)

Als nächstes werden die Anzahl, wie oft ich zählt von n-1 bis 1 bewegen, zweimal jede Zahl zu wiederholen, und die erste Zahl dreimal:

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

So nun meine Folge von Richtungen erstellt werden kann durch jede aufeinanderfolgende Richtung durch die paarigen Zahl in Countdown wiederholen:

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

zu meiner Sequenz von Indizes, kann ich nur diese Sequenz zusammenzufassen, aber (AFAIK) Python liefert nicht, ein solches Verfahren, also lassen Sie uns schnell ein Wurf zusammen:

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

nun das Original-Array zu erzeugen, kann ich folgendes tun:

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 

Which, für n = 4, ergibt sich:

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

und für n = 5, gibt :

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

Dieser Ansatz kann zu rechteckigen Gittern verallgemeinert werden; Ich lasse dies als eine Übung für den Leser;)

Answer 5

ich Ihr Problem mit C++ gelöst haben. Ich weiß nicht, ob es für dich hilfreich ist. Aber es posten. Wenn es für Sie funktioniert, wird es ein Vergnügen sein. Hier

ist der Code:

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

Hier ist die Ausgabe, wobei 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 

Danke.