home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15075 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  1.6 KB
  1. Path: sparky!uunet!ogicse!network.ucsd.edu!ucsbcsl!iota!marcos
  2. From: marcos@iota.Berkeley.EDU (Marcos Valerio)
  3. Newsgroups: sci.math
  4. Subject: latin square-like problem
  5. Keywords: magic squares, latin squares
  6. Message-ID: <6722@ucsbcsl.ucsb.edu>
  7. Date: 16 Nov 92 19:38:44 GMT
  8. Article-I.D.: ucsbcsl.6722
  9. Sender: root@ucsbcsl.ucsb.edu
  10. Reply-To: marcos@iota.Berkeley.EDU (Marcos Valerio)
  11. Lines: 50
  12.  
  13. I have a nice little problem for you.
  14.  
  15. I need an algorithm to build n*n latin squares with two extra properties:
  16.  
  17. P1: All the elements in the main diagonal are different and equal to the row
  18.     (or column) which they belong.
  19.  
  20. P2: If for each row we select the element equals to row-1, they will all be in
  21.     different columns.
  22.  
  23. For example: 
  24.  
  25.  n=3: 
  26.  ----
  27.  
  28.   0 2 1
  29.   2 1 0
  30.   1 0 2 
  31.  
  32.  n=5:
  33.  ----
  34.  
  35.   0  2  4  1  3
  36.   4  1  3  0  2
  37.   3  0  2  4  1
  38.   2  4  1  3  0
  39.   1  3  0  2  4
  40.  
  41. Please observe that in both cases the elements in the main diagonal are:
  42. 0, 1, 2, ..., n-1 and also if we select the Aii-1 elements from each row,
  43. they are in different columns.
  44.  
  45. There is no solution for n=4.
  46.  
  47. In my solution there is a separate algorithm for odd and even numbers, but
  48. I don't think it is the best one. That's why I'm posting the problem to you.
  49.  
  50. I came across this problem when trying to simulate broadcast in a ring
  51. based network. Details can be given upon request.
  52.  
  53. Thanks,
  54.  
  55. -- 
  56. Marcos de Macedo Valerio
  57. Center for Distributed Systems
  58. Department of Computer Engineering
  59. University of California, Santa Barbara
  60. Phone : (805) 893-4461 office
  61.         (805) 685-9677 home
  62. email address : marcos@nu.ece.ucsb.edu
  63.