Java로 스도쿠 게임 만들기(스도쿠 문제)

인터넷에서 스도쿠를 풀수 있는 곳이 있다. 스도쿠 앱도 있다.

스도쿠는 어떻게 만드는지, 궁금하다면, 여기 소개하는 Java로 스도쿠 문제를 만들어 내는 방법을 알아 보는 것도 좋을 것이다.

 

출처는 다음과 같다.

https://www.geeksforgeeks.org/program-sudoku-generator/ 

Program for Sudoku Generator - GeeksforGeeks

 

위의 사이트에 자세한 설명이 있는데, 아래의 녹색 부분만 먼저 숫자를 임으로 채운다. 그 다음에 나머지 부분을 채운다.

9개의 칸이 9개 있는 형상이다. 그 중에서 대각선 부분(녹색 부분)을 채우고, 나머지는 컴퓨터가 풀어 나가듯이 완성을

시키는 것으로 설명이 되어 있다. 전부 완성한 후에는 몇 개의 숫자를 0 으로 만든다. 0으로 된 부분을 우리가 맞추어 나가는 것이다. 이렇게 해서 Sudoku 문제를 만들어 내는 것이 아래의 프로그램이다.

//
// https://www.geeksforgeeks.org/program-sudoku-generator/
//
/* Java program for Sudoku generator */
import java.lang.*;
public class Sudoku
{
int[] mat[];
int N; // number of columns/rows.
int SRN; // square root of N
int K; // No. Of missing digits

// Constructor
Sudoku(int N, int K)
{
this.N = N;
this.K = K;

// Compute square root of N
Double SRNd = Math.sqrt(N);
SRN = SRNd.intValue();

mat = new int[N][N];
}

// Sudoku Generator
public void fillValues()
{
// Fill the diagonal of SRN x SRN matrices
fillDiagonal();

// Fill remaining blocks
fillRemaining(0, SRN);
// Remove Randomly K digits to make game
removeKDigits();
}

// Fill the diagonal SRN number of SRN x SRN matrices
void fillDiagonal()
{

for (int i = 0; i<N; i=i+SRN)

// for diagonal box, start coordinates->i==j
fillBox(i, i);
}

// Returns false if given 3 x 3 block contains num.
boolean unUsedInBox(int rowStart, int colStart, int num)
{
for (int i = 0; i<SRN; i++)
for (int j = 0; j<SRN; j++)
if (mat[rowStart+i][colStart+j]==num)
return false;

return true;
}

// Fill a 3 x 3 matrix.
void fillBox(int row,int col)
{
int num;
for (int i=0; i<SRN; i++)
{
for (int j=0; j<SRN; j++)
{
do
{
num = randomGenerator(N);
}
while (!unUsedInBox(row, col, num));

mat[row+i][col+j] = num;
}
}
}

// Random generator
int randomGenerator(int num)
{
return (int) Math.floor((Math.random()*num+1));
}

// Check if safe to put in cell
boolean CheckIfSafe(int i,int j,int num)
{
return (unUsedInRow(i, num) &&
unUsedInCol(j, num) &&
unUsedInBox(i-i%SRN, j-j%SRN, num));
}

// check in the row for existence
boolean unUsedInRow(int i,int num)
{
for (int j = 0; j<N; j++)
if (mat[i][j] == num)
return false;
return true;
}

// check in the row for existence
boolean unUsedInCol(int j,int num)
{
for (int i = 0; i<N; i++)
if (mat[i][j] == num)
return false;
return true;
}

// A recursive function to fill remaining
// matrix
boolean fillRemaining(int i, int j)
{
// System.out.println(i+" "+j);
if (j>=N && i<N-1)
{
i = i + 1;
j = 0;
}
if (i>=N && j>=N)
return true;

if (i < SRN)
{
if (j < SRN)
j = SRN;
}
else if (i < N-SRN)
{
if (j==(int)(i/SRN)*SRN)
j = j + SRN;
}
else
{
if (j == N-SRN)
{
i = i + 1;
j = 0;
if (i>=N)
return true;
}
}

for (int num = 1; num<=N; num++)
{
if (CheckIfSafe(i, j, num))
{
mat[i][j] = num;
if (fillRemaining(i, j+1))
return true;

mat[i][j] = 0;
}
}
return false;
}

// Remove the K no. of digits to
// complete game
public void removeKDigits()
{
int count = K;
while (count != 0)
{
int cellId = randomGenerator(N*N)-1;

// System.out.println(cellId);
// extract coordinates i and j
int i = (cellId/N);
int j = cellId%9;
if (j != 0)
j = j - 1;

// System.out.println(i+" "+j);
if (mat[i][j] != 0)
{
count--;
mat[i][j] = 0;
}
}
}

// Print sudoku
public void printSudoku()
{
for (int i = 0; i<N; i++)
{
for (int j = 0; j<N; j++)
System.out.print(mat[i][j] + " ");
System.out.println();
}
System.out.println();
}

// Driver code
public static void main(String[] args)
{
int N = 9, K = 20;
Sudoku sudoku = new Sudoku(N, K);
sudoku.fillValues();
sudoku.printSudoku();
}
}

위의 프로그램을 Sudoku.java에 저장한다.

그리고 다음 명령을 사용하여 컴파일하고 실행한다.

javac Sudoku.java (컴파일 명령, 한 번만 실행하면 됨.)

java Sudoku        (실행 명령, 필요시 매 번 실행)

 

다음은 실행 결과이다. 실행시마다 다른 스도쿠 게임이 만들어져 나온다.

0으로 된 부분을 사람이 채워 알맞은 숫자로 바꾸어 넎으면, 게임 하는 사람이 문제를 풀게 되는 것이다.

 

 

아래는 위의 파일을 Sudoku.Java 파일에 저장한 것이다.

Sudoku.zip

0.00MB