| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
 Posted: Fri May 26, 2006 1:49 pm Post subject: Generate a single N^2 x N^2 grid by a construction (N even) |
 |
|
Summary: I have devised a method by which a single N^2 x N^2 grid, for any even N, can be created by a construction. But perhaps this is already well known to experts in tiling?
Background: A common method to build a sudoku puzzle is first to generate a complete grid and then to find a suitable subset of the givens to form a valid puzzle. However, generating large grids becomes very time-consuming as N becomes larger than about 7. For instance, my own program can manage N=7 in times between 30 and 1900 seconds, but fails to complete for larger values, except for a limited class of grids for N=8 and 10 in which some of the randomness is replaced by a construction.
The full construction: While cycling along the East River this week, I realised that if a limited set of grids can be generated using a partial construction, it should be possible to construct a single grid, for any even N, using only a construction. I then tried it out for N = 2, 4 and 6 using pencil and paper, and for larger N (up to N=65  ) using a simple program (below). Of course, the single grid can then be permuted in the usual way to disguise its regularity, but this does not affect its underlying structure. The method is simple:
Step 1: Fill the first row with the digits 1 to N (in any order).
Step 2: Fill the second row with a copy of the first in reverse order.
Step 3: 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.
Step 4: Fill the second chute with a copy of the first, circularly shifted right by N columns.
Step 5a: Fill all the remaining chutes two at a time with a copy of the two previous chutes.
Step 5b: In each of the copied pairs of chutes, divide the N columns in each box into two equal groups, and for each group circularly shift the columns one position right.
The result for N=4 is listed below.
Question: Is this already a well-known result in tiling theory?
Regard,
Mike Metcalf
| Code: |
program massive
! (c) Michael Metcalf, 2006.
! A free Fortran 95 compiler for most systems is available at www.g95.com.
implicit none
integer, allocatable, dimension(:, :) :: sudoku
integer :: i, N, N2, add_rows, row, spin
!
! Read square-root of size of grid, N (N even). For large N, a stack limit
! might be reached and require extension.
write(*, '(" Input size: ")', advance='no')
read(*, *) N
N2 = N**2
!
! Allocate required storage.
allocate(sudoku(N2, N2))
!
! Fill first row with the digits 1 to N (in any order, here simply
! increasing).
sudoku(1, :) = (/ (i, i = 1, N2) /)
!
! 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
!
! Write the finished grid to a file.
open(3, file='grid.txt')
do row = 1, N2
write(3, '(99i5)') sudoku(row, :)
end do
end program massive
|
| Code: |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1 16 15 14 13 12 11 10 9
13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12
4 3 2 1 16 15 14 13 12 11 10 9 8 7 6 5
5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4
12 11 10 9 8 7 6 5 4 3 2 1 16 15 14 13
2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15
15 16 13 14 11 12 9 10 7 8 5 6 3 4 1 2
10 9 12 11 14 13 16 15 2 1 4 3 6 5 8 7
7 8 5 6 3 4 1 2 15 16 13 14 11 12 9 10
14 13 16 15 2 1 4 3 6 5 8 7 10 9 12 11
3 4 1 2 15 16 13 14 11 12 9 10 7 8 5 6
6 5 8 7 10 9 12 11 14 13 16 15 2 1 4 3
11 12 9 10 7 8 5 6 3 4 1 2 15 16 13 14
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
