| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
 Posted: Mon Jun 19, 2006 10:42 pm Post subject: Generate any N^2 x N^2 grid by a construction |
 |
|
Further to my other posting for even N, it is, of course, perfectly possible to produce a grid by construction also for odd N. The method is even simpler:
Step 1: Fill first row with the digits 1 to N, in any order.
Step 2: Fill each row of the remainder of the first row of boxes (chute) with a copy of the previous row, circularly shifted right by N columns.
Step 3: Fill all the remaining rows of boxes (chutes) with a copy of the previous row of boxes (chute), shifted right by 1 column.
For N=3, and an ordered first row, this gives:
| Code: |
1 2 3 4 5 6 7 8 9
7 8 9 1 2 3 4 5 6
4 5 6 7 8 9 1 2 3
9 1 2 3 4 5 6 7 8
6 7 8 9 1 2 3 4 5
3 4 5 6 7 8 9 1 2
8 9 1 2 3 4 5 6 7
5 6 7 8 9 1 2 3 4
2 3 4 5 6 7 8 9 1
|
and a symmetric puzzle generated from the basic N=5 grid looks like:
| Code: |
. . . . . . 7 . . . . . 13 . . . . . 19 . . . . . .
. . 23 24 . . . . . 5 6 . 8 . 10 11 . . . . . 17 18 . .
. . . . 20 21 22 23 24 . . . . . . . 7 8 9 10 11 . . . .
. . . . 15 16 17 18 19 . . . . . . . 2 3 4 5 6 . . . .
. . . 9 10 11 . . 14 15 16 17 18 19 20 21 22 . . 25 1 2 . . .
. 1 . . 4 . . . . . . . . . . . . . . . 20 . . 23 .
. 21 . . . . . 2 . . 5 6 7 8 9 . . 12 . . . . . 18 .
15 16 17 18 19 . 21 . 23 . . . . . . . 6 . 8 . 10 11 12 13 14
10 . . . . 15 16 17 18 . 20 21 22 23 24 . 1 2 3 4 . . . . 9
5 6 . 8 . 10 . 12 . 14 . . . . . 20 . 22 . 24 . 1 . 3 4
. . 1 . . 4 5 6 7 8 . . . . . 14 15 16 17 18 . . 21 . .
. 20 21 . 23 . . . 2 3 4 5 . 7 8 9 10 . . . 14 . 16 17 .
. 15 . . . 19 . . . . . . . . . . . . . 8 . . . 12 .
. 10 11 . 13 . . . 17 18 19 20 . 22 23 24 25 . . . 4 . 6 7 .
. . 6 . . 9 10 11 12 13 . . . . . 19 20 21 22 23 . . 1 . .
23 24 . 1 . 3 . 5 . 7 . . . . . 13 . 15 . 17 . 19 . 21 22
18 . . . . 23 24 25 1 . 3 4 5 6 7 . 9 10 11 12 . . . . 17
13 14 15 16 17 . 19 . 21 . . . . . . . 4 . 6 . 8 9 10 11 12
. 9 . . . . . 15 . . 18 19 20 21 22 . . 25 . . . . . 6 .
. 4 . . 7 . . . . . . . . . . . . . . . 23 . . 1 .
. . . 25 1 2 . . 5 6 7 8 9 10 11 12 13 . . 16 17 18 . . .
. . . . 21 22 23 24 25 . . . . . . . 8 9 10 11 12 . . . .
. . . . 16 17 18 19 20 . . . . . . . 3 4 5 6 7 . . . .
. . 9 10 . . . . . 16 17 . 19 . 21 22 . . . . . 3 4 . .
. . . . . . 8 . . . . . 14 . . . . . 20 . . . . . .
|
Surely this tessalation result is well known?
Below is the full program for both odd and even N. (It can be compiled with the free compiler from www.g95.org.) It reads N from standard input. If N is negative, the first row is randomized.
Regards,
Mike Metcalf
| Code: |
program massive
! (c) Michael Metcalf, 2006.
! A free Fortran 95 compiler for most systems is available
! at www.g95.org.
implicit none
integer, allocatable, dimension(:, :) :: sudoku
integer :: i, N, N2, add_rows, row, spin, k, itemp
logical :: random = .false.
real, allocatable, dimension(:) :: numbers
!
! Read square-root of size of grid, N. For large N, a stack limit
! might be reached and require extension. Negative N implies
! random start.
!
write(*, '(" Input size: ")', advance='no')
read(*, *) N
N2 = N**2
if (N < 0) then
N = -N
random = .true.
allocate(numbers(N2))
end if
!
! Allocate required storage.
!
allocate(sudoku(N2, N2))
!
! Fill first row with the digits 1 to N, in any order.
!
sudoku(1, :) = (/ (i, i = 1, N2) /)
if(random) then
call random_seed( )
call random_number(numbers)
do i = 1, N2
k = int(numbers(i)*(N2-i+1)) + i ! based on H. D. Knoble's `RPERM'
itemp = sudoku(1, i)
sudoku(1, i) = sudoku(1, k)
sudoku(1, k) = itemp
end do
end if
!
select case(mod(N, 2))
!
! FOR EVEN N
case(0)
!
! Fill the second row with a copy of the first in reverse order.
!
sudoku(2, :) = sudoku(1, N2:1:-1)
row = 2
!
! Fill each pair of rows of the remainder of the first row of boxes (chute)
! with a copy of the previous two rows, circularly shifted right by N+N
! columns.
!
do add_rows = 1, N/2 - 1
sudoku(row+1:row+2, :) = cshift(sudoku(row-1:row, :), -2*N, dim=2)
row = row +2
end do
!
! Fill the second row of boxes (chute) with a copy of the first, circularly
! shifted right by N columns.
!
sudoku(row+1:row+N, :) = cshift(sudoku(row-N+1:row, :), -N, dim=2)
row = row + N
!
! Fill all the remaining rows of boxes (chutes) two at a time with a copy
! of the two previous rows of boxes (chutes).
!
do add_rows = 1, N/2 - 1
sudoku(row+1:row+2*N, :) = sudoku(row-2*N+1:row, :)
!
! In each of the copied pairs of rows of boxes (chutes), divide the N columns
! in each box into two equal groups, and for each group circularly shift
! the columns one position right.
!
do spin = 1, N2, N/2
sudoku(row+1:row+2*N, spin:spin+N/2-1) = &
cshift(sudoku(row+1:row+2*N, spin:spin+N/2-1), -1, dim=2)
end do
row = row + 2*N
end do
!
! FOR ODD N
case(1)
!
! Fill each row of the remainder of the first row of boxes (chute)
! with a copy of the previous row, circularly shifted right by N columns.
!
row = 1
do add_rows = 2, N
row = row + 1
sudoku(row, :) = cshift(sudoku(row-1, :), -N)
end do
!
! Fill all the remaining rows of boxes (chutes) with a copy
! of the previous row of boxes (chute), shifted right by 1 column.
!
do add_rows = 1, N - 1
sudoku(row+1:row+N, :) = cshift(sudoku(row-N+1:row, :), -1, dim=2)
row = row + N
end do
end select
!
! Write the finished grid to a file.
!
open(3, file='grid.txt')
do row = 1, N2
print '(196i4)', sudoku(row, :)
write(3, '(196i3)') sudoku(row, :)
end do
end program massive
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
