!This program is designed to calculate a possible next move in a game of
!Connect 5.  It reads in the size of the board, and then the board itself, 
!with each line containing consecutive rows of the board.  A zero represents
!an empty place on the board.  menum represents the players piece, and hisnum
!represents the opponents piece

program connect
  implicit none
! max= the largest possible playing board
! n= the size of this particular board
! row = the current row being annalized
! col = the current column being annalized
! Board = the array containing the read in board
! Value = the array containing the value of each possible move in its
!     respective location
! i= a counter
! temp = temporary vector to hold the value of a diagonal
! x,y = the coordinates of the move with the highest value that is legal
! diag = temporarily holds the pieces in each diagonal set of 5
! startr = the first row which contains an empty space
! done = if an empty spot has been found 

  integer, parameter :: max=20
  integer ::  n, row, col
  integer :: Board (max,max)
  real ::  value(max,max)
  integer :: i, temp (0:4), x, y, diag(0:4)
  integer :: startr
  logical :: done
  
  read *, n              !input n
  do row=1,n
     read *, Board (row,1:n) !input each line of the board
  end do
  value=0
  do row=1,n  !loop over every possible horizontal set of five and call check5 
     do col=1,n-4 !add the value returned by check5 to the corresponding set
                  !   of five in value
        value(row, col:col+4)=value(row, col:col+4) + check5(Board (row, col:col+4))
     end do
  end do
  do col=1,n  !loop over every possible vertical set of five and call check5 
     do row=1,n-4 !add the value returned by check5 to the corresponding set
                  !   of five in value
        value(row:row+4, col)=value(row:row+4, col) + check5(Board (row:row+4, col))
     end do
  end do
  do row=5,n  !loop over every possible +sloped diag set of five and call check5 
     do col=1,n-4 !add the value returned by check5 to the corresponding set
                  !   of five in value
        do i=0,4
           diag(i)=(board(row-i,col+i))
        end do
        temp= check5(diag)
        do i=0,4
           value(row-i, col+i)=value(row-i,col+i) + temp(i)
        end do
     end do
  end do
  do row=1, n-4 !loop over every possible +sloped diag set of five and call check5 
     do col=1,n-4 !add the value returned by check5 to the corresponding set
                  !   of five in value
        do i=0,4
           diag(i)=(board(row+i,col+i))
        end do
        temp= check5(diag)
        do i=0,4
           value(row+i, col+i)=value(row+i,col+i) + temp(i)
        end do
     end do
  end do
  done=.false.
  do row=1,n     !Find the first empty square
     do col=1,n
        if (Board(row,col)==0) then
           x=row
           y=col
           done=.true.
           exit
        end if
     end do
     if (done) exit
  end do
  startr=x  !set startr to the first empty row
  do row=startr,n !loop through all values and find the maximum value
                  !for an empty square
     do col=1,n  
        if (value(x,y)<value(row,col) .and. Board(row,col)==0) then
           x=row
           y=col
        end if
     end do
  end do
  print "(I4,I4)", y-1, x-1 !return the best move in the proper format

contains
  !This function takes in a vector of five pieces on a board and returns a 
  !value for each spot depending on what is in the set
  function check5 (group) result (val)
     !group = the inputted five pieces
     !val = the vector of the value coresponding to this set
     !i = a counter
     !me = the number of the players pieces
     !him = the number of the opponents pieces
     !menum = the number corresponding to the players piece
     !himnum = the number corresponding to the opponents piece
      integer :: group(5), i, me, him
      real :: val(5)
      integer, parameter :: menum=1, himnum=-1
      me = 0
      him =0
      do i= 1,5 !count the number of each persons pieces in group
         if (group(i)==menum) me=me+1
         if (group(i)==himnum) him=him+1
      end do
      if ((me/=0) .and. (him/=0)) then !if both pieces are present
         val=0
      else
         if ((me==0) .and. (him==0)) then !if no pieces are present
            val=21
         else
            if (me==1) val=401   !set respective values to the board dependent
            if (me==2) val=8001  !on the number of pieces, and if they are 
            if (me==3) val=3200001.  !the players or the opponents
            if (me==4) val=1280000000.
            if (him==1) val=400
            if (him==2) val=8000
            if (him==3) val=160000
            if (him==4) val=64000000.
         end if
      end if
    end function check5
end program