[컴퓨팅 사고력] 스도쿠

<위키백과>에서 스도쿠를 검색하면 다음과 같이 설명을 하고 있다.

스도쿠는 18세기 스위스 수학자 레온하르트 오일러가 창안한 Latin Square 를 기반으로 하여 1979년 당시 74세의 건축가였던 미국의 Howard Garns가 현재의 모습으로 변형하여 1979년 5월 미국의 '델 매거진즈'(Dell Magazines)가 잡지 《Dell Pencil Puzzles & Word Games》에 "Number Place"로 소개된 것이 시초이나, 1984년 4월 일본의 출판사인 '니코리'(ニコリ, Nikoli)가 출판한 잡지 《퍼즐 통신 니코리》(パズル通信ニコリ)[2]에 '스도쿠'라는 이름을 붙여 수록하면서 대중에게 보급되기 시작하여 2005년 무렵에 이르러 온 세계로 퍼져 나갔다.

 

이러한 스도쿠는 다음과 같은 규칙에 의해서 9*9칸의 퍼즐을 채워넣는다.

(1) 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

(2) 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

 

이러한 규칙을 이용해서 위의 빈칸을 채워 넣으시오.

 

정답)

위와 같은 문제를 풀때 한줄,혹은 한열, 또는 3*3 에서 1개 짜리를 먼저 채워주는 방법으로 하나씩 채워 주면 좀 더 효율적으로 채울 수 있다.

 

컴퓨팅사고력

스도쿠 문제와 같은 경우 컴퓨팅 과학에서는 자료구조의 이차원 배열을 생각 할 수 있다.

행과 열의 위치를 판단하는 방법을 확인하고 비어 있는 칸에 1~9까지 순차적으로 넣어 볼 수 있다.

또한 알고리즘 측면으로는 백트래킹 기법을 활용하여 풀수가 있는데 처음 만나는 빈칸에서 1부터 ~ 9 까지 넣을 수 있는지 하나씩 체크 하면서 넣을 수 있다고 하면 그 수를 넣어 보고 다음 빈칸을 찾아 떠난다.

그 다음 빈칸에서 1부터 9까지 넣을 수가 없다고 하면 다시 되돌아 와서 그 다음 수를 넣어 보는 방식으로 모든 경우를 다 계산해 보는 방법이 백트래킹 방법이며 C언어로 소스코드를 구현해 본다고 하면 다음과 같은 형식으로 구현이 가능하다.

bool check(int y,int x,int num)
{
    for(int i=0;i<9;i++)
    {
        if(num==arr[y][i]) return false; //같은행에 같은 숫자가 있다.
        if(num==arr[i][x]) return false; //같은열에 같은 숫자가 있다.
    }
    int num2=(y/3)*3; //3*3의 시작 위치를 구하기 위해 큰 블럭으로 나누자.
    int num1=(x/3)*3;
    for(int i=num2;i<num2+3;i++)
    {
        for(int j=num1;j<num1+3;j++)
        {
            if(num==arr[i][j]) return false; //3*3 구간안에 같은 숫자가 있다
        }
    }
    return true;
}

bool sdoku(int y,int x)
{
 
   if(x>=9)
   {
      y++;
      x=0;
   }
   if(y>=9)
   {
      ///sucess 출력한다.
      return true;
   }
   if(arr[y][x]) return stoku(y,x+1); //빈칸이 아니면 다음으로 진행
 
   for(int i=1;i<=9;i++) //1~9까지 숫자를 넣어 보자.
   {
      if(check(y,x,i)==false) continue; ///i를 놓지 못하면 다음 수로 바꾸자.
      arr[y][x]=i;
      if(sdoku(y,x+1) ==true) return true; ///만약 끝까지 모두 놓았다면 더 이상 진행하지 말자. 
      arr[y][x]=0;
   }
   return false;
 
}

 

[인천 서구 원당컴퓨터학원]

원당컴퓨터학원에서는?

1. 4차 산업 시대의 흐름은 컴퓨터를 얼마나 이해하느냐에 따라 삶의 질이 틀려 질 수 있다는 것을 항상 염두에 두고 있습니다.

2. 알고리즘은 프로그래밍의 근원이 되는 문제해결 능력이며, 머신러닝은 IoT등에 의해 모여진 데이터를 활용하는 기법입니다.

3. 이에 따라 초,중,고 학생들이 알기 쉽게 이해하는 인공지능 부터 알고리즘까지 학생들의 실력에 맞춰 수업을 진행중에 있습니다.

4. 현재 초등학생이 고등학생이 되는 때에는 고교학점제 도입에 따라 자신이 전공하고자 하는 특기가 크게 부각 될것입니다.

5. IT 업체중 규모가 큰 곳에서는 코딩테스트(알고리즘테스트)로 블라인드 면접을 수행하는곳이 늘고 있습니다.

6. 미래 IT를 꿈꾸는 학생들의 산실이 되기 위해 항상 최선을 다하는 원당컴퓨터학원이 되겠습니다.

 

※ 정보영재 혹은 인공지능 관련 수업에 관해 궁금하신 분은 문의(032-565-5497) 주세요.

 

 

원당컴퓨터학원 커리큘럼

- OA : 학교 수행 평가에 꼭 필요한 컴퓨터 활용능력 향상

- IT 자격증 과정 : 취업대비,대학생인증제,승진을 위한 국가공인 자격증 취득과정

- 정보영재 : 정보올림피아드 및 알고리즘 대회/소프트웨어특기자전형/디미고 특별전형 대비/코딩테스트 대비를 위한 알고리즘 과정

- 프로젝트반 : 응용프로그래밍/웹프로그래밍/앱프로그래밍 등을 통해 직접 만들어 보면서 컴퓨터 프로그래밍 이해(소프트웨어 학생부종합전형/특성화고(디미고,선린고등) 특별전형대비)

- 인공지능 : 인공지능의 이해 및 실습을 통해 빅데이터 가공(4차 산업 시대의 축이 되는 인공지능 시대를 대비)

- 일반고,과고,영재고,특성화고,컴퓨터학과(SW) 대학생을 위한 내신대비 : python,java,c++,자료구조,알고리즘,이산수학