[Fortran] 포트란 퇴각검색을 이용한 스도쿠 풀이 알고리즘

 정보

• 업무명    : 포트란 퇴각검색을 이용한 스도쿠 풀이 알고리즘

• 작성자    : 박진만

• 작성일    : 2019-09-05

• 설   명    : 퇴각검색 (backtracking)을 통해서 스도쿠 퍼즐을 푸는 프로그램

• 수정이력 :

 

 

 내용

[특징]

• 깊이 우선 탐색에서 퇴각 검색 (backtracking) 방법을 고안하여 전역 해로 스도쿠를 해결하는 알고리즘

 

[기능]

• 스도쿠 해결

 

[활용 자료]

• 입력자료로서  grid 설정이 필요

 

[자료 처리 방안 및 활용 분석 기법]

• 깊이 우선 탐색

 

[사용법]

• grid 입력 후 소스코드 컴파일 후 실행

 

[사용 OS]

• Window 10

 

[사용 언어]

• Fortran

 

 소스 코드

[전체]

program sudoku
 
  implicit none
  integer, dimension (9, 9) :: grid
  integer, dimension (9, 9) :: grid_solved
  grid = reshape ((/               &
    & 0, 0, 3, 0, 2, 0, 6, 0, 0,   &
    & 9, 0, 0, 3, 0, 5, 0, 0, 1,   &
    & 0, 0, 1, 8, 0, 6, 4, 0, 0,   &
    & 0, 0, 8, 1, 0, 2, 9, 0, 0,   &
    & 7, 0, 0, 0, 0, 0, 0, 0, 8,   &
    & 0, 0, 6, 7, 0, 8, 2, 0, 0,   &
    & 0, 0, 2, 6, 0, 9, 5, 0, 0,   &
    & 8, 0, 0, 2, 0, 3, 0, 0, 9,   &
    & 0, 0, 5, 0, 1, 0, 3, 0, 0/), &
    & shape = (/9, 9/),            &
    & order = (/2, 1/))
  call pretty_print (grid)
  call solve (1, 1)
  write (*, *)
  call pretty_print (grid_solved)
 
contains
 
  recursive subroutine solve (i, j)
    implicit none
    integer, intent (in) :: i
    integer, intent (in) :: j
    integer :: n
    integer :: n_tmp
    if (i > 9) then
      grid_solved = grid
    else
      do n = 1, 9
        if (is_safe (i, j, n)) then
          n_tmp = grid (i, j)
          grid (i, j) = n
          if (j == 9) then
            call solve (i + 1, 1)
          else
            call solve (i, j + 1)
          end if
          grid (i, j) = n_tmp
        end if
      end do
    end if
  end subroutine solve
 
  function is_safe (i, j, n) result (res)
    implicit none
    integer, intent (in) :: i
    integer, intent (in) :: j
    integer, intent (in) :: n
    logical :: res
    integer :: i_min
    integer :: j_min
    if (grid (i, j) == n) then
      res = .true.
      return
    end if
    if (grid (i, j) /= 0) then
      res = .false.
      return
    end if
    if (any (grid (i, :) == n)) then
      res = .false.
      return
    end if
    if (any (grid (:, j) == n)) then
      res = .false.
      return
    end if
    i_min = 1 + 3 * ((i - 1) / 3)
    j_min = 1 + 3 * ((j - 1) / 3)
    if (any (grid (i_min : i_min + 2, j_min : j_min + 2) == n)) then
      res = .false.
      return
    end if
    res = .true.
  end function is_safe
 
  subroutine pretty_print (grid)
    implicit none
    integer, dimension (9, 9), intent (in) :: grid
    integer :: i
    integer :: j
    character (*), parameter :: bar = '+-----+-----+-----+'
    character (*), parameter :: fmt = '(3 ("|", i0, 1x, i0, 1x, i0), "|")'
    write (*, '(a)') bar
    do j = 0, 6, 3
      do i = j + 1, j + 3
        write (*, fmt) grid (i, :)
      end do
      write (*, '(a)') bar
    end do
  end subroutine pretty_print
 
end program sudoku

 

[GitHub GIST]

 

[결과]

|4 8 3|9 2 1|6 5 7| 
|9 6 7|3 4 5|8 2 1| 
|2 5 1|8 7 6|4 9 3| 
+-----+-----+-----+ 
|5 4 8|1 3 2|9 7 6| 
|7 2 9|5 6 4|1 3 8| 
|1 3 6|7 9 8|2 4 5| 
+-----+-----+-----+ 
|3 7 2|6 8 9|5 1 4| 
|8 1 4|2 5 3|7 6 9| 
|6 9 5|4 1 7|3 8 2|

 

 참고 문헌

[논문]

• 없음

[보고서]

• 없음

[URL]

• 없음

 

 문의사항

[기상학/프로그래밍 언어]

• sangho.lee.1990@gmail.com

[해양학/천문학/빅데이터]

• saimang0804@gmail.com