Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Generate any N^2 x N^2 grid by a construction

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message
m_b_metcalf

Joined: 13 Mar 2006
Posts: 210
:
Location: Berlin

Items
PostPosted: Mon Jun 19, 2006 10:42 pm    Post subject: Generate any N^2 x N^2 grid by a construction Reply with quote

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

Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron