如何获得半幻方?

huangapple go评论112阅读模式
英文:

How I can get semimagic square?

问题

你的问题是你的程序修改了输入矩阵中已有的数字,而你希望它只修改点(.)。你可以通过修改你的代码来解决这个问题。在SimpleMatrix函数中,你可以添加一个条件来检查是否应该在当前位置插入数字。这里是修改后的代码:

  1. def SimpleMatrix(number, row, colum, size):
  2. """
  3. Distribution of the matrix by elements, for example
  4. our matrix:
  5. [2 2 5]
  6. [. . 0]
  7. [1 . .]
  8. for 2 in (0,0) => [2 0 0]
  9. [0 2 0]
  10. [0 0 2]
  11. for 2 in (0,1) => [2 3 0]
  12. [0 2 0]
  13. [0 0 2]
  14. """
  15. matrix = [[0 for _ in range(size)] for _ in range(size)]
  16. if matrix[row][colum] == 0: # Only insert if the current position is empty
  17. matrix[row][colum] = number
  18. for i in range(size):
  19. for j in range(size):
  20. if not (i == row or j == colum) and matrix[i][j] == 0 and RowAndColumEmpty(matrix, i, j):
  21. matrix[i][j] = number
  22. break
  23. return matrix

通过这个修改,你的程序将只在当前位置为空(值为0)的情况下插入数字,而不会覆盖已经存在的数字。这应该解决了你的问题。

英文:

How do I implement this in Python?

> Given is an input matrix like this one:
>
>
> ┌───┬───┬───┐
> │ 2 │ 2 │ 5 │
> ├───┼───┼───┤
> │ . │ . │ 0 │
> ├───┼───┼───┤
> │ 3 │ . │ . │
> └───┴───┴───┘
>

> Instead of dots, insert numbers so that the sum of the numbers in the rows and columns in the square is the same.

My code:

  1. def EnterMatr():
  2. matr = []
  3. n = int(input("Enter n: "))
  4. print("Enter a matrix:")
  5. for i in range(n):
  6. arr = input().split()
  7. for j in range(len(arr)):
  8. if arr[j] == ".": # Dots are replaced by None
  9. arr[j] = None
  10. else:
  11. arr[j] = int(arr[j])
  12. matr.append(arr)
  13. return matr
  14. def SimpleMatrix(number, row, colum, size):
  15. """
  16. Distribution of the matrix by elements, for example
  17. our matrix:
  18. [2 2 5]
  19. [. . 0]
  20. [1 . .]
  21. for 2 in (0,0) => [2 0 0]
  22. [0 2 0]
  23. [0 0 2]
  24. for 2 in (0,1) => [0 2 0]
  25. [2 0 0]
  26. [0 0 2]
  27. """
  28. matrix = [[0 for _ in range(size)] for _ in range(size)]
  29. matrix[row][colum] = number
  30. for i in range(size):
  31. for j in range(size):
  32. if not (i == row or j == colum) and RowAndColumEmpty(matrix, i, j):
  33. matrix[i][j] = number
  34. break
  35. return matrix
  36. def GenerateMultiSemiMetrix(matr):
  37. MultiMatrix = []
  38. for i in range(len(matr)):
  39. for j in range(len(matr)):
  40. if matr[i][j]:
  41. MultiMatrix.append(SimpleMatrix(matr[i][j], i,j,len(matr)))
  42. return MultiMatrix
  43. def RowAndColumEmpty(matr, row, colum):
  44. """
  45. Checking whether the row and column where we insert are empty
  46. """
  47. for i in range(len(matr)):
  48. if not matr[row][i] == 0:
  49. return False
  50. for i in range(len(matr)):
  51. if not matr[i][colum] == 0:
  52. return False
  53. return True
  54. def addMatr(first, second):
  55. matrix = [[0 for _ in range(len(first))] for _ in range(len(first))]
  56. for i in range(len(first)):
  57. for j in range(len(first)):
  58. matrix[i][j] = first[i][j] + second[i][j]
  59. return matrix
  60. def SumMatrix(MatrArr):
  61. matrix = [[0 for _ in range(len(MatrArr[0]))] for _ in range(len(MatrArr[0]))]
  62. for elem in MatrArr:
  63. matrix = addMatr(matrix, elem)
  64. return matrix
  65. matr = EnterMatr()
  66. matr = SumMatrix(GenerateMultiSemiMetrix(matr))
  67. for elem in matr:
  68. print(elem)

Here is the output of an execution of that code:

  1. Enter n: 3
  2. Enter a matrix:
  3. 2 2 5
  4. . . 0
  5. 1 . .
  6. [2, 3, 5]
  7. [7, 2, 1]
  8. [1, 5, 4]

The problem is that the result matrix has different numbers at places where already numbers were given in the input matrix:

  • The original 2 at (0, 1) becomes 3
  • The original 0 at (1, 2) becomes 1

This should not be possible.

How can I change the program such that it would only change the dots?

Is there any algorithm or something else that could solve my problem?

答案1

得分: 0

这可以表示为𝑛²矩阵的一组方程式以及求和变量的集合。然后剩下的是解决这组线性方程式。您可以使用a package来解决这个问题。

这里我实现了Guassian elimination方法:

  1. def gaussian_elimination(table):
  2. height = len(table)
  3. width = len(table[0])
  4. h = 0
  5. for x in range(width):
  6. abspivot = max(abs(table[y][x]) for y in range(h, height))
  7. if abspivot:
  8. pivoty = next(y for y in range(h, height) if abs(table[y][x]) == abspivot)
  9. pivotrow = table[pivoty]
  10. pivot = pivotrow[x]
  11. table[h], table[pivoty] = pivotrow, table[h] # swap rows
  12. for j in range(x, width): # divide pivot row to get a 1
  13. pivotrow[j] /= pivot
  14. for y, row in enumerate(table): # subtract pivotrow from other rows
  15. if y != h:
  16. coeff = row[x]
  17. row[x] = 0
  18. for j in range(x + 1, width):
  19. row[j] -= coeff * pivotrow[j]
  20. h += 1
  21. if h >= height:
  22. break
  23. # 从表中提取解决的值
  24. values = [0] * (width - 1)
  25. for row in table:
  26. for i in range(width - 1):
  27. if row[i]:
  28. values[i] = row[-1]
  29. break
  30. return values
  31. def solve(matr):
  32. width = len(matr)
  33. size = width * width
  34. # 创建表示方程式的扩展矩阵
  35. table = []
  36. # 添加方程式以反映行的总和
  37. for y in range(width):
  38. eq = [0] * (size + 2)
  39. eq[y * width:(y+1) * width] = [1] * width
  40. eq[size] = -1
  41. table.append(eq)
  42. # 添加方程式以反映列的总和
  43. for x in range(width):
  44. eq = [0] * (size + 2)
  45. for i in range(x, size, width):
  46. eq[i] = 1
  47. eq[size] = -1
  48. table.append(eq)
  49. # 添加方程式以反映已知值
  50. for y, row in enumerate(matr):
  51. for x, val in enumerate(row):
  52. if val is not None:
  53. eq = [0] * (size + 2)
  54. eq[y * width + x] = 1
  55. eq[-1] = val
  56. table.append(eq)
  57. # 使用高斯消元法解决这组方程式
  58. values = gaussian_elimination(table)
  59. # 验证所有解决的值都是整数
  60. if any(val - int(val) for val in values):
  61. raise ValueError("解决方案中出现意外的非整数")
  62. values = list(map(int, values))
  63. # 将值转换回矩阵
  64. return [
  65. values[width * y: width * (y + 1)]
  66. for y in range(width)
  67. ]
  68. matr = [
  69. [2, 2, 5],
  70. [None, None, 0],
  71. [1, None, None]
  72. ]
  73. print(solve(matr))

这将输出:

  1. [[2, 2, 5], [6, 3, 0], [1, 4, 4]]
英文:

This can be represented as a set of equations on the 𝑛² variables of the 𝑛x𝑛 matrix and a variable for the sum. Then remains to solve this set of linear equations. You can use a package for that.

Here I have implemented the Guassian elimination method:

  1. def gaussian_elimination(table):
  2. height = len(table)
  3. width = len(table[0])
  4. h = 0
  5. for x in range(width):
  6. abspivot = max(abs(table[y][x]) for y in range(h, height))
  7. if abspivot:
  8. pivoty = next(y for y in range(h, height) if abs(table[y][x]) == abspivot)
  9. pivotrow = table[pivoty]
  10. pivot = pivotrow[x]
  11. table[h], table[pivoty] = pivotrow, table[h] # swap rows
  12. for j in range(x, width): # divide pivot row to get a 1
  13. pivotrow[j] /= pivot
  14. for y, row in enumerate(table): # subtract pivotrow from other rows
  15. if y != h:
  16. coeff = row[x]
  17. row[x] = 0
  18. for j in range(x + 1, width):
  19. row[j] -= coeff * pivotrow[j]
  20. h += 1
  21. if h >= height:
  22. break
  23. # Extract the resolved values from the table
  24. values = [0] * (width - 1)
  25. for row in table:
  26. for i in range(width - 1):
  27. if row[i]:
  28. values[i] = row[-1]
  29. break
  30. return values
  31. def solve(matr):
  32. width = len(matr)
  33. size = width * width
  34. # Create an augemented matrix representing equations
  35. table = []
  36. # Add equations to reflect sum of rows
  37. for y in range(width):
  38. eq = [0] * (size + 2)
  39. eq[y * width:(y+1) * width] = [1] * width
  40. eq[size] = -1
  41. table.append(eq)
  42. # Add equations to reflect sum of columns
  43. for x in range(width):
  44. eq = [0] * (size + 2)
  45. for i in range(x, size, width):
  46. eq[i] = 1
  47. eq[size] = -1
  48. table.append(eq)
  49. # Add equations to reflect the known values
  50. for y, row in enumerate(matr):
  51. for x, val in enumerate(row):
  52. if val is not None:
  53. eq = [0] * (size + 2)
  54. eq[y * width + x] = 1
  55. eq[-1] = val
  56. table.append(eq)
  57. # Solve this set of equations with the Gaussian elimination method
  58. values = gaussian_elimination(table)
  59. # Verify that all resolved values are integers
  60. if any(val - int(val) for val in values):
  61. raise ValueError("Unexpected non-integer in solution")
  62. values = list(map(int, values))
  63. # Turn the values back into a matrix
  64. return [
  65. values[width * y: width * (y + 1)]
  66. for y in range(width)
  67. ]
  68. matr = [
  69. [2, 2, 5],
  70. [None, None, 0],
  71. [1, None, None]
  72. ]
  73. print(solve(matr))

This outputs:

  1. [[2, 2, 5], [6, 3, 0], [1, 4, 4]]

huangapple
  • 本文由 发表于 2023年5月20日 20:21:53
  • 转载请务必保留本文链接:https://go.coder-hub.com/76295209.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定