Generating 'Magic Square' Algorithm (Algorithm is from a book)

Question

I've been having a problem with this magic square code for quite some time now. I've just been following a book's algorithm step by step but for some reasons it doesn't display it correctly.

int main(){
    int n;
    char temp[100];
    cout << "Enter an odd number: ";
    cin >> temp;
    n = atoi(temp);
    cout << endl;
    //error if its even
    if (n%2 == 0){
        cout << "Input Error!";
        return (-1);
        cout << endl;
    }

    int square[n][n];
    //places 0 inside
    for (int r = 0; r < n; r++){
        for (int c = 0; c < n; c++){
            square[r][c] = 0;
        }
    }
    //store 1 in middle of first row
    square[0][(n-1)/2] = 1;
    //current position
    int key = 2, i = 0, j = (n-1)/2;

    while(key <= n*n){
        int k = (i-1)%n, l = (j-1)%n; //look up and left
        //square occupied, move down
        if (square[k][l] != 0){
            i = (i+1)%n;
        }
        //square (k,l) needs to be assigned
        else{
            i = k;
            j = l;
        }
        square[i][j] = key; //assign it a value
        key++;
    }

    //display
    for (int r = 0; r < n; r++){
        for (int c = 0; c < n; c++){
            cout << setw(5) << square[r][c] << setw(5);
        }
        cout << endl;
    }

    return 0;
}

If I input 5 as an odd number, the display would be like this:

Enter an odd number: 5

    5   14   22   20   18
    6   15   23    0   19
   17   16   24    0    0
    0    0   25    0    0
    0    0    0    0    0

The output I'm expecting is:

Enter an odd number: 5

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

What seems to be the problem?

FYI, use of non constant array sizes is not supported by the standard: int square[n][n]; I'm surprised that you are allowed to dynamically set more than the outer dimension. — Gem Taylor, Sep 03 '19 at 13:29
Add the line `cout << "square[" << i << "][" << j << "] = " << key << endl;` just before updating the square to see where the missing numbers went. I suspect that your book could be relying on the result of negative moduluses (`%`), which is implementation-dependent, and C++ does not check to see if you're indexing outside of an array. — molbdnilo, Sep 03 '19 at 13:31
The error occurs at size three. Use as small test cases as possible to make debugging easier. — molbdnilo, Sep 03 '19 at 13:33
Yes, I'm blaming the negative modulus as well, I think. Try changing `(i-1)%n` to `(i+n-1)%n`, and similarly for others? — Gem Taylor, Sep 03 '19 at 13:33
Another problem is this: what if you find an occupied square and the square "below" it is also occupied? — molbdnilo, Sep 03 '19 at 13:38
This is the second time i've seen this exact problem. Which book is it again? it was a nightmare to find the error last time. — Owl, Sep 03 '19 at 13:47
I tried `cout << "square[" << i << "][" << j << "] = " << key << endl;` and it seems a lot of the numbers went out of bounds in the negative side. — Razna, Sep 03 '19 at 13:55
@Owl The book is called "Fundamentals of Data Structures by Ellis Horowitz and Sartaj Sahni. Here's the algorithm that I was following. https://i.imgur.com/6NEHn9L.jpg — Razna, Sep 03 '19 at 13:59
@GemTaylor i tried `(i+n-1)%n` and it seems to be displaying all the numbers but some are not the correct positions. Whenever it detects an occupied space, it seems to be going upward rather than downwards. — Razna, Sep 03 '19 at 14:04
possible duplicate of https://stackoverflow.com/questions/4372554/magic-square-program-c — Paul Baxter, Sep 03 '19 at 17:08

score 0 · Accepted Answer · answered Sep 03 '19 at 14:48

I ran your code and the result was following

Enter an odd number: 5

5    3    1   10   23
6    4    2   11   24
7   16   14   12   25
18   17   15   13   21
19    0    0    0    0

I guess it is some difference between compilers. Your problem is probably, that the modulo of a negative number is also negative: link

And indexing with negative values is undefined behaviour: link

Paul Baxter · Answer 2 · 2019-09-03T17:18:21.690

#include "stdafx.h"

#include<iostream>
#include<iomanip>
using namespace std;

int main()
{
    int n;

    cout << "Please enter an odd integer: ";
    cin >> n;

    int** MagicSquare = new int*[n];
    for (int i = 0; i < n; ++i)
        MagicSquare[i] = new int[n];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            MagicSquare[i][j] = 0;
        }
    }

    int newRow,
        newCol;

    // Set the indices for the middle of the bottom i
    int i = 0;
    int j = n / 2;

    // Fill each element of the array using the magic array
    for (int value = 0; value <= n*n; value++)
    {
        MagicSquare[i][j] = value;
        // Find the next cell, wrapping around if necessary.
        newRow = (i + 1) % n;
        newCol = (j + 1) % n;
        // If the cell is empty, remember those indices for the
        // next assignment.
        if (MagicSquare[newRow][newCol] == 0)
        {
            i = newRow;
            j = newCol;
        }
        else
        {
            // The cell was full. Use the cell above the previous one.
            i = (i - 1 + n) % n;
        }

    }


    for (int x = 0; x<n; x++)
    {
        for (int y = 0; y<n; y++)
            cout << MagicSquare[x][y] << " ";
        cout << endl;
    }
}

Generating 'Magic Square' Algorithm (Algorithm is from a book)

2 Answers2