스도쿠(개인 프로젝트)
아래 코드들이 실행되면 오른쪽 상단에는 실행시간, 중단에는 9x9빈칸, 그리그 그 아래에는 Start, Quit버튼이 위치된다.
하나의 9X9 사각형을 9개의 3X3사각형으로 나누는 선을 아래 코드로 이용해 그린다.
sudoku_easy.jsp
...
<script type="text/javascript">
...
$(document).ready(function()
{
...
//3x3의 작은 사각형으로 나누는 선 그리기
var row_add;
var col_add;
for(var i=2; i< 8; i+=3)
{
for(var j=0; j<9; j++)
{
row_add = "#"
col_add = "#"
row_add += (i+j*9);
col_add += (i*9+j);
//border-left: double 3px blue;
$(row_add).css("border-right","4px solid black");
$(col_add).css("border-bottom","4px solid black");
}
}
});
...
</script>
Start버튼을 누르면 sciprt태그 의 start 함수가 실행된다.
sudoku_easy.jsp
...
<script type="text/javascript">
...
function start()
{
sudoku_maker();
...
}
...
</script>
start함수에서 sudoku_maker함수가 실행되고, sudoku_maker클래스의 객체가 생성된다.
package games;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.TreeMap;
public class sudoku_maker
{
int cur_idx;
int cur_num;
Random rand = new Random();
ArrayList<Integer> nums;
ArrayList<Integer> including;
ArrayList<Integer> total = new ArrayList<Integer>();
ArrayList<ArrayList<Integer>> board =new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> rows = new ArrayList<ArrayList<Integer>>();;
ArrayList<ArrayList<Integer>> cols = new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> small_boards =new ArrayList<ArrayList<Integer>>();
TreeMap<Integer,Integer> blank = new TreeMap<Integer,Integer>();
long beforeTime;
long afterTime;
long secDiffTime;
long beforeTime_o;
long afterTime_o;
long secDiffTime_o;
boolean stop = false;
boolean back = false;
public sudoku_maker(int blank_size)
{
initializer();
...
}
...
}
initializer함수를 이용해 2차원 어레이리스트 board,row,cols,small_boards들의 모든 요소값들을 -1로 만들어 준다.
public class sudoku_maker
{
...
public void initializer()
{
total = new ArrayList<Integer>();
board =new ArrayList<ArrayList<Integer>>();
rows = new ArrayList<ArrayList<Integer>>();;
cols = new ArrayList<ArrayList<Integer>>();
small_boards =new ArrayList<ArrayList<Integer>>();
for(int i=0; i<9; i++)
{
board.add(new ArrayList<>(Arrays.asList(-1,-1,-1,-1,-1,-1,-1,-1,-1)));
rows.add(new ArrayList<>(Arrays.asList(-1,-1,-1,-1,-1,-1,-1,-1,-1)));
cols.add(new ArrayList<>(Arrays.asList(-1,-1,-1,-1,-1,-1,-1,-1,-1)));
small_boards.add(new ArrayList<>(Arrays.asList(-1,-1,-1,-1,-1,-1,-1,-1,-1)));
for(int j=0; j<9; j++)
{
total.add(j+i*9);
}
}
}
...
}
processing함수를 이용해 스도쿠 판을 채워줄 숫자를 규칙에 맞게 배열한다.
public class sudoku_maker
{
...
public sudoku_maker(int blank_size)
{
...
processing();
...
}
...
}
n_mix함수를 이용해 1~9까지 숫자를 무작위 순서로 배치한 어레이리스트를 받는다.
public class sudoku_maker
{
public void processing()
{
//초기 세팅
for(int i=0; i<9; i++)
{
outerloop:
while(true)
{
nums=n_mix(true);
...
}
}
}
}
public class sudoku_maker
{
...
//9개의 숫자 무작위로 배치하기
private ArrayList<Integer> n_mix(boolean init)
{
ArrayList<Integer> n_array;
if(init)
{
n_array = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9));
}
else
{
n_array = new ArrayList<Integer>(Arrays.asList(0,1,2,3,4,5,6,7,8));
}
ArrayList<Integer> n_mix = new ArrayList<Integer>();
int arr_size = 9;
for(int i=0; i<9; i++)
{
int cur_idx = rand.nextInt(arr_size);
int cur_val = n_array.get(cur_idx);
n_mix.add(cur_val);
n_array.remove(Integer.valueOf(cur_val));
arr_size -=1;
}
return n_mix;
}
}
스도쿠에 배치된 숫자는 아래와 같은 규칙을 따른다.
1.각각의 가로줄(row)과 세로줄(column)에 1~9가 중복 없이 하나씩 들어간다.
2.3×3칸(box) 안에는 1~9가 중복 없이 하나씩 들어간다.
예시를 가지고 위의 규칙하에 숫자를 배치하는 코드의 동작을 이해해보자.
첫번째 행에 숫자를 넣는것은 특별히 고려해야할 것이 없음으로, 두번째 줄에 숫자를
넣는 상황부터 설명해 보겠다.
두번째 행에 넣을 숫자들을 얻어온다.
nums=n_mix(true); // nums == [8, 7, 3, 6, 5, 1, 9, 2, 4]
두번재 행 첫번째 열에 들어갈 숫자cur_num(=nums.get(0))가 스도쿠 규칙에
적합한 값인지 판단한다.
board의 첫번째 열(=cols.get(0))에는 [-1,-1,-1, 4,-1,-1,-1,-1,-1]가 들어가 있다.
그리고 첫번째 3x3box(=small_boards.get(0))에는 [-1, 2, -1, 4, 5,-1,-1,-1,-1]가 들어있다.
cur_num(=8)이 cols.get(0)과 small_boards.get(0)에 들어있지 않으므로, 8은 이 두배열에
들어갈 수 있다.
두번째 행의 들어갈 나머지 숫자들(nums.get(1)~nums.get(8))에대해 앞서 살펴본 방법과
동일한 방식으로 판단한다.
nums의 모든 숫자들이 위의 조건을 만족했음으로, 아래의 반복문(화살표로 표시된 영역)을
이용해 rows, cols, small_boards, board에 nums값들을 넣어준다.
public class sudoku_maker
{
public void processing()
{
//초기 세팅
for(int i=0; i<9; i++)
{
outerloop:
while(true)
{
...
for(int j=0; j<9; j++)
{
cur_num = nums.get(j);
//자리가 비어있고, 이미 사용된 숫자가 아닌지 판별한다.
if(cols.get(j).indexOf(cur_num) <0)
{
if(small_boards.get(j/3 + 3*Integer.valueOf(i / 3)).indexOf(cur_num) <0)
{
if(j==8)
{
▲ for(int k=0; k<9; k++)
여 {
기 cur_num = nums.get(k);
가 rows.get(i).set(k, cur_num);
실 cols.get(k).set(i, cur_num);
행 small_boards.get(k/3 + 3*(i / 3)).set(cur_num-1, cur_num);
됨 board.get(i).set(k, cur_num);
▼ }
break outerloop;
}
}
else
{
...
}
}
else
{
...
}
}
}
}
}
}
세번째 행에 넣을 숫자들을 얻어온다.
nums=n_mix(true); // nums == [9, 6, 2, 4, 1, 8, 7, 5, 3]
세번재 행 세번재 열에 들어갈 숫자cur_num(=nums.get(2))가 cols.get(2)
(=[-1, 2, 3, -1, -1, -1, -1, -1, -1])에 들어있으므로 backtracking
(별로 표시한 부분, 이 때 i=2, j=2)를 실행한다.
public class sudoku_maker
{
public void processing()
{
//초기 세팅
for(int i=0; i<9; i++)
{
outerloop:
while(true)
{
nums=n_mix(true);
innerloop:
for(int j=0; j<9; j++)
{
cur_num = nums.get(j);
//자리가 비어있고, 이미 사용된 숫자가 아닌지 판별한다.
if(cols.get(j).indexOf(cur_num) <0)
{
if(small_boards.get(j/3 + 3*Integer.valueOf(i / 3)).indexOf(cur_num) <0)
{
...
}
else
{
i = backtracking(i, j);
break innerloop;
}
}
else
{
★ i =backtracking(i, j); //i=2, j=2
break innerloop;
}
}
}
}
}
}
public class sudoku_maker
{
...
public int backtracking(int i, int j)
{
//i=2, j=2
including = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9));
including.removeAll(rows.get(i)); //=> including = [1,2,3,4,5,6,7,8,9]
including.removeAll(cols.get(j)); //=> including = [1,4,5,6,7,8,9]
including.removeAll(small_boards.get(j/3 + 3*(i / 3))); //=> including = [1,6,9]
//board의 i행 j열에 들어갈 수 있는 숫자가 하나도 없는경우
if(including.size() == 0)
{
nums = new ArrayList<>(rows.get(i-1));
if(i > 0)
{
...
return i-1;
}
else
{
return 0;
}
}
//board의 i행 j열에 들어갈 수 있는 숫자가 하나 이상(1,6,9) 있는경우
else
{
return i;
}
}
...
}
processing()에서 backtracking(별로 표시된 부분)수행결과 i는 2가 된다.
그 결과 innerloop:로 표시한 반복문에서 탈출한다. 그 다음 while문이 반복되고 nums에
1~9까지 숫자를 새롭게 무작위로 배치한 값(=[9, 6, 1, 4, 2, 8, 7, 5, 3])들이 들어간다.
public class sudoku_maker
{
public void processing()
{
//초기 세팅
for(int i=0; i<9; i++)
{
outerloop:
while(true)
{
//nums = [9, 6, 1, 4, 2, 8, 7, 5, 3]
nums=n_mix(true);
innerloop:
for(int j=0; j<9; j++)
{
cur_num = nums.get(j);
//자리가 비어있고, 이미 사용된 숫자가 아닌지 판별한다.
if(cols.get(j).indexOf(cur_num) <0)
{
...
}
else
{
★ i =backtracking(i, j); //i=2, j=2
break innerloop;
}
}
}
}
}
}
세번째 행에 넣을 각각의 숫자들(nums=[9, 6, 1, 4, 2, 8, 7, 5, 3])이 3x3box과 숫자의 인덱스에
해당하는 열에 들어있지 않음으로, 아래의 반복문(화살표로 표시된 영역)을 이용해rows, cols,
small_boards, board에 nums값들을 넣어준다.
public class sudoku_maker
{
public void processing()
{
//초기 세팅
for(int i=0; i<9; i++)
{
outerloop:
while(true)
{
...
for(int j=0; j<9; j++)
{
cur_num = nums.get(j);
//자리가 비어있고, 이미 사용된 숫자가 아닌지 판별한다.
if(cols.get(j).indexOf(cur_num) <0)
{
if(small_boards.get(j/3 + 3*Integer.valueOf(i / 3)).indexOf(cur_num) <0)
{
if(j==8)
{
▲ for(int k=0; k<9; k++)
여 {
기 cur_num = nums.get(k);
가 rows.get(i).set(k, cur_num);
실 cols.get(k).set(i, cur_num);
행 small_boards.get(k/3 + 3*(i / 3)).set(cur_num-1, cur_num);
됨 board.get(i).set(k, cur_num);
▼ }
break outerloop;
}
}
else
{
...
}
}
else
{
...
}
}
}
}
}
}
네, 다섯번째 행들을 위에서의 과정을 반복해 채워준다.
이제 여섯번째 행에 대해서 아래의 반복문을 실행되고, j가 2일 때 backtracking(별로 표시됨)이
수행된다. (nums=[2, 3, 1, 4, 9, 8, 7, 5, 6])
public class sudoku_maker
{
public void processing()
{
//초기 세팅
for(int i=0; i<9; i++)
{
outerloop:
while(true)
{
...
for(int j=0; j<9; j++)
{
//(nums=[2, 3, 1, 4, 9, 8, 7, 5, 6])
cur_num = nums.get(j);
//자리가 비어있고, 이미 사용된 숫자가 아닌지 판별한다.
if(cols.get(j).indexOf(cur_num) <0)
{
if(small_boards.get(j/3 + 3*Integer.valueOf(i / 3)).indexOf(cur_num) <0)
{
...
}
else
{
★ i = backtracking(i, j); //i=5; j=2
break innerloop;
}
}
else
{
...
}
}
}
}
}
}
6행 3열에 넣을수 있는 숫자가 하나도 없음으로, 5행에 넣었던 숫자를 제거한다. 이 때, rows,
cols,small_boards의 관련된 값도 변경해준다. 위에서 'i = backtracking(i, j);'수행결과
i = 5-1이 수행되어 i엔 4가 들어간다. 즉 5행 새롭게 숫자를 넣는 과정을 반복해야 한다는 것이다.
public class sudoku_maker
{
...
public int backtracking(int i, int j)
{
//i=5, j=2
including = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9));
//including.removeAll(rows.get(i)); //=> including = [1,2,3,4,5,6,7,8,9]
including.removeAll(cols.get(j)); //=> including = [4, 6, 7, 8]
including.removeAll(small_boards.get(j/3 + 3*(i / 3))); //=> including = []
//board의 i행 j열에 들어갈 수 있는 숫자가 하나도 없는경우
if(including.size() == 0)
{
nums = new ArrayList<>(rows.get(i-1));
if(i > 0)
{
rows.set(i-1, new ArrayList<>(Arrays.asList(-1,-1,-1,-1,-1,-1,-1,-1,-1)));
board.set(i-1, new ArrayList<>(Arrays.asList(-1,-1,-1,-1,-1,-1,-1,-1,-1)));
for(int k=0; k<9; k++)
{
cols.get(k).set(i-1, -1);
cur_num = nums.get(k);
small_boards.get(k/3 + 3*Integer.valueOf((i-1) / 3)).set(cur_num-1, -1);
}
return i-1;
}
else
{
...
}
}
//board의 i행 j열에 들어갈 수 있는 숫자가 하나 이상(1,6,9) 있는경우
else
{
...
}
}
...
}
지금까지 예시에서 살펴본 동작을 반복하면 9X9스도쿠가 규칙에 맞게 만들어진다. 숫자가 전부
다 배치되었음으로, 아래 코드를 통해 빈칸이 될곳을 무작위로 선택한다.
public class sudoku_maker
{
...
ArrayList<Integer> total = new ArrayList<Integer>();
TreeMap<Integer,Integer> blank = new TreeMap<Integer,Integer>();
public sudoku_maker(int blank_size)
{
//빈칸이 될곳 선택
for(int i=0; i<blank_size; i++)
{
cur_idx = rand.nextInt(total.size());
cur_num = total.get(cur_idx);
blank.put(cur_num, board.get(cur_num/9).get(cur_num%9));
total.remove(Integer.valueOf(cur_num));
}
}
...
}
board에서 빈칸이 될곳의 값을 0으로 만든다.
public class sudoku_maker
{
...
public sudoku_maker(int blank_size)
{
//빈칸 만들기
for(int key : blank.keySet())
{
board.get(key/9).set(key%9, 0);
}
}
...
}
sudoku_easy.jsp에서 s_d.get_sudo_mix(), s_d.get_blank() 실행해 9X9 board에관한 정보들을 받는다.
public class sudoku_maker
{
...
ArrayList<ArrayList<Integer>> board =new ArrayList<ArrayList<Integer>>();
TreeMap<Integer,Integer> blank = new TreeMap<Integer,Integer>();
...
public TreeMap<Integer,Integer> get_blank(int blank_size)
{
return blank;
}
public ArrayList<ArrayList<Integer>> get_sudo_mix()
{
return board;
}
...
}
sudoku_easy.jsp에서 보드에관한 정보를 바탕으로 숫자 및 빈칸을 만들어주고 초시계 또한 시작된다.
sudoku_easy.jsp
...
<script type="text/javascript">
...
function start()
{
sudoku_maker();
$("#start").attr("disabled", true);
$("#difficulty").attr("disabled", true);
$("#end").attr("disabled", false);
timer = setInterval
(
function()
{
time++;
min = Math.floor(time/60);
hour = Math.floor(min/60);
sec = time%60;
min = min%60;
var th = hour;
var tm = min;
var ts = sec;
if(th<10){
th = "0" + hour;
}
if(tm < 10){
tm = "0" + min;
}
if(ts < 10){
ts = "0" + sec;
}
$('#time').html(th + ":" + tm + ":" + ts);
}, 1000);
}
...
</script>
위의 코드에서 보면 onkeypress=”Number_check()”라고 되어있다. 즉 빈칸에 키보드로 값을 입력하면 함수가 실행된다. 하나의 빈칸에 숫자가 새로 입력되거나 바뀔경우, 각 빈칸에 해당되는 행과, 열에 있는 숫자들의 합이 45인가 확인해 본다.
sudoku_easy.jsp
...
<script type="text/javascript">
...
var row_key = new Array(9);
var col_key = new Array(9);
var row_val = new Array(9);
var col_val = new Array(9);
for (var i = 0; i < row_key.length; i++)
{
// new Array() => 빈배열만 선언
row_key[i] = new Array();
col_key[i] = new Array();
row_val[i] = new Array();
col_val[i] = new Array();
}
var row;
var col;
var sum_r;
var sum_c;
var solv;
...
function Number_check(class_num)
{
//keyCode를 이용해 숫자만 입력 가능하도록 한다.
// 숫자 keyCode
// 0 => 48
// ...
// 9 => 57
//숫자가 아닌경우
if(event.keyCode<49 || event.keyCode>57)
{
//숫자가아닌 값을 입력란에서 지우는 역할을 한다.
event.returnValue=false;
}
else
{
//자바스크립트에서 나눗샘을 할 경우 소수점 단위로 표시하기에
//나눗샘의 몫을 얻기 원한다면 버림을 해야된다.
row = Math.floor((class_num)/9);
col = (class_num)%9;
solv = true;
good:
for(var i=0; i<9; i++)
{
//alert(i);
sum_r = 0;
sum_c = 0;
//row_c에 row_val[i]를 깊은복사 한다.
var row_c = row_val[i].slice();
for(var j=0; j<row_key[i].length; j++)
{
if(class_num != row_key[i][j])
{
//(event.keyCode-48)의 자료형이 Number가 아닌경우를 대비해 *1을 해준다.
sum_r += ($('.'+row_key[i][j]).val())*1;
//row_c.indexOf(($('.'+row_key[i][j]).val())*1)인 인데스에 해당하는 값을
//row_c에서 제거한다.
row_c.splice(row_c.indexOf(($('.'+row_key[i][j]).val())*1), 1);
}
//Number_check는 onKeyPress를 통해 실행된다.
//onKeyPress는 키를 누르면 이벤트 발생 후 문자가 입력되게 처리된다.
//다시말해, 현재 빈칸에 입력된 숫자는 ($('.'+row_sum_blank[i][j]).val())*1로
//가져오지 못한다. 이런 문제를 해결하기 위해선 아래와 같이 코딩해야 한다.
else
{
//blank에 들어갈수 있는 값들에 event.keyCode-48가 포함되었나
//확인한다.
if(row_c.includes(event.keyCode-48))
{
sum_r += (event.keyCode-48);
//row_c.indexOf(event.keyCode-48)인 인데스에 해당하는 값을
//row_c에서 제거한다.
row_c.splice(row_c.indexOf(event.keyCode-48), 1);
}
else
{
solv = false;
break good;
}
}
}
//col_c에 col_val[i]를 깊은복사 한다.
var col_c = col_val[i].slice();
for(var j=0; j<col_key[i].length; j++)
{
if(class_num != col_key[i][j])
{
sum_c += ($('.'+col_key[i][j]).val())*1;
//col_c.indexOf(($('.'+col_key[i][j]).val())*1)인 인데스에 해당하는 값을
//col_c에서 제거한다.
col_c.splice(col_c.indexOf(($('.'+col_key[i][j]).val())*1), 1);
}
else
{
if(col_c.includes(event.keyCode-48))
{
sum_c += (event.keyCode-48);
//col_c.indexOf(event.keyCode-48)인 인데스에 해당하는 값을
//col_c에서 제거한다.
col_c.splice(col_c.indexOf(event.keyCode-48), 1);
}
else
{
solv = false;
break good;
}
}
}
//가로행의 합이 45가 아닌경우(1~9까지의 합이 45)
if(sum_r + row_sum[i] != 45)
{
solv = false;
break good;
}
//세로열의 합이 45가 아닌경우(1~9까지의 합이 45)
if(sum_c + col_sum[i] != 45)
{
solv = false;
break good;
}
}
//스도쿠를 완성한 경우
if(solv)
{
...
}
}
}
...
</script>
스도쿠가 완성되었다면 ajax로 비동기 통신을 해주고 100ms후 결과를 보여주는 모달창을 실행한다.(숫저퍼즐 페이지에서 비동기 통신 참고)
모달창을 닫으면 end함수가 실행되고 화면이 초기화된다.
<script type="text/javascript">
...
function end()
{
//숫자가 없는 깨끗한 상태로 만든다.
//location.replace()를 이용해 현재 페이지로 이동하면,
//히스토리에 저장되지 않아 이전페이지 이동이 불가능하게 된다.
//location.href => 현재 페이지의 주소
clearInterval(timer);
location.replace(location.href);
}
...
</script>
마친가지로 스도쿠 완성전 Quit버튼을 누른다면, end()함수가 실행되고 화면이 초기화 된다.
동작영상
※전체 코드는 https://github.com/qlqlzh/Storage에서 my_project.zip과 my_project.z01를 다운받은 후 my_project_mybatis.zip의 압축을 풀으면 볼 수 있다.
댓글남기기