Eight Queens Problem

유명한 프로그래밍 퀴즈.

8-queens 문제는 Queen이 다른 Queen를 공격할 수 없는 8 X 8개의 체스 판에서 8개의 Queen을 체스판 위에 놓이게하는 문제이다. 체스 판에서 Queen은 똑같은 행렬(가로와 세로)/대각선방향에 대해서 공격이 가능하다. 그러므로 이 문제에 대한 solution은 자기 자신(Queen)을 보호하면서 새로운 위치에 Queen을 놓게 하는 것이다.

  1. 각 열에는 오직 하나의 퀸만 존재해야 한다.
  2. 각 행에는 오직 하나의 퀸만 존재해야 한다.
  3. 각각의 퀸의 대각선에 다른 퀸이 존재해서는 안 된다.

예를들어 다음과 같이 퀸을 위치할 수 있다.

8 x 8 체스판에 8개의 Queen을 놓을 수 있는 방법은 모두 몇 가지인가?

재귀호출

2014/02/14 00:28

길가의풀

대각선도 행/열과 마찬가지로 한 퀸의 대각선 선상에서는 인접하지 않더라도 다른 퀸을 놓을 수 없다는거죠? 어휴 문제를 잘못 이해하고 풀었네요. 행,열과 달리 한 퀸과 바로 인접한 대각선방향에서만 퀸을 놓을 수 없는 걸로 이해하고 코드를 짰어요;ㅎㅎㅎ 나중에 시간나면 다시 풀어봐야겠네요 어릴 때 분명히 체스를 해 본 기억이 있는데.. 체스 룰이 기억이 잘 안나네요;;ㅎㅎ - Katherine, 2014/03/11 17:00 M D
@Katherine님, 네 맞습니다. 대각선상으로 움직일때도 부딫히면 안됩니다. - 길가의풀, 2014/03/11 17:18 M D
back-tracking에서 가장 유명한 문제 - Noname, 2017/07/06 02:34 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

37개의 풀이가 있습니다. 4 / 4 Page

#!/usr/bin/python3

import copy

class Board():
    col = 8
    row = 8

    def __init__(self):
        self.board = [[None for col in range(self.row)] for j in range(self.col)]
        self.queen_arr = []

    def __str__(self):
        s = ''
        for c in range(self.col):
            for r in range(self.row):
                if self.board[c][r] == 2:
                    s += "%4s " % 'Q'
                else:
                    s += "%4s " % self.board[c][r]
            s += '\n'
        return s

    def clean(self):
        self.board = [[None for col in range(self.row)] for j in range(self.col)]

    def ableQ(self,col,row):
        col -= 1
        row -= 1
        if self.board[col][row] == None:
            return True
        else :
            return False

    def queen(self, col, row):
        if (col < 1 or col > 9) or (row < 1 or row > 9):
            return False
        col -= 1
        row -= 1

        for i in range(8):
            self.board[col][i] = 1
            self.board[i][row] = 1

        for i in range(8):
            if col+i > 7 or row+i > 7:
                break
            self.board[col+i][row+i] = 1

        for i in range(8):  
            if col-i < 0 or row-i < 0:
                break
            self.board[col-i][row-i] = 1

        for i in range(8):
            if col-i < 0 or row+i > 7:
                break
            self.board[col-i][row+i] = 1

        for i in range(8):
            if col+i > 7 or row-i < 0:
                break
            self.board[col+i][row-i] = 1


        self.queen_arr.append(str(col)+str(row))
        self.queen_set()

        return True

    def queen_set(self):
        for arr in self.queen_arr:
            self.board[int(arr[0])][int(arr[1])] = 2

def queen_recursive(board,num):
    b = None
    count = 0
    for i in range(1,9):
        b = copy.deepcopy(board)
        if b.ableQ(num,i):
            b.queen(num,i)
            if num > 1 :
                count += queen_recursive(b,num-1)
            else:
                count += 1
    return count

b = Board()
print(queen_recursive(b, 8))

2016/11/23 16:07

바바

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬3

#!/usr/bin/env python3
# 검사배열
cols = [0 for _ in range(10)] # cols[10]
inc  = [0 for _ in range(20)] # inc[20], 증가하는 대각선, 좌표합은 일정, 4x4에서 2~8
dec  = [0 for _ in range(20)] # dec[20], 감소하는 대각선, 좌표차는 일정
                              # 인덱스가 음수가 되면 안되므로 안정범위로 조절
                              # 4x4에서 -3~3이므로 증가하는 대각선과 맞추기
                              # 위해 5를 더하면 되는데, 이는 N+1임.
cnt = 0

def solve(row):
    global cnt # 

    if row > N:
        cnt += 1
        return

    for col in range(1, N + 1):
        incN = row + col
        decN = N + (row - col) + 1
        # 검사배열 조건에 맞다면 
        if not cols[col] and not inc[incN] and not dec[decN]:
            cols[col] = inc[incN] = dec[decN] = 1 # 체크
            solve(row + 1)
            cols[col] = inc[incN] = dec[decN] = 0 # 백트랙킹

if __name__ == '__main__':
    N = 8 # 체스판 크기 및 퀸의 수
    solve(1) # 1 행에 퀸을 놓는다
    print(cnt)

# 보드는 1, 1 부터 시작한다고 가정
# 퀸은 한 행에 하나만 존재 할 수 있다
# 퀸을 1, 1부터 놓으면, 그 다음 퀸은 2행부터 놓아야한다
# 2행부터는 퀸이 놓일 자리를 대각선, 같은 열을 피해서 놓아야한다
# 놓아야 할 자리, 놓지 말아야 할 자리를 판단하기 위해 열, 증가대각선, 
# 감소대각선 별로 배열을 준비한다. 이를 검사배열이라고 하자
# 퀸을 임의의 위치에 놓았다면 각 검사배열에 맞는 인덱스를 찾아서 1로 채운다
# 퀸을 놓는 함수는 그 다음 행으로 호출한다
# 함수호출의 종료조건은 보드 크기보다 인자의 행이 더 클때 종료한다
# 종료된 함수는 그 전의 검사배열에 체크했던 인덱스를 찾아가 지워야한다
# 이를 백트랙킹이라고 한다
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

javascript

var queens = [];
var count = 0;

var place = function (row, col) {
    console.log(row, col, queens)
    for (let i = 0; i < row; i++) {
        if (queens[i] === col || queens[i] === col - (row - i) || queens[i] === col + (row - i)) {
            return false;
        }
    }
    return true;
};

var chess = function (row) {
    if (row == 8) count++;
    for (let col = 0; col < 8; col++) {
        if (place(row, col)) {
            queens[row] = col;
            chess(row + 1);
        }
    }
}

chess(0);

console.log(count);
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
# 이전에 놓인 퀸들queens과 충돌하는지 판단
def can_put(queens, nx, ny):
    for x, y in queens:
        if y == ny or abs(x-nx) == abs(y-ny):
            return False

    return True


##1줄에 하나씩 배치. 
# row-1 행까지 퀸들의 배치가 끝난 상태에서,
# row행의 몇 번째 열에 다음 퀸을 둘 것인가? 가능한 모든 경우를 탐색
def backtrack(queens, row):
    if row >= 8:
        return 1

    sum = 0    
    for col in range(8):
            if can_put(queens, row, col):
                sum += backtrack(queens+[(row, col)], row + 1)

    return sum


print(backtrack([], 0))  # 92

유명한 문젠데 제대로 풀어본 건 처음인 거 같네요.

굳이 8x8 보드를 만들 필요 없이 좌표만으로 계산 됩니다.

이미 행을 기준으로 삼았기 때문에, queens 리스트에 (x,y) 대신 y만 넣고 검사해도 되는데 오히려 더 복잡해질 거 같아서 패스했습니다.

can_put() 함수 역시, 코드를 줄일 수는 있겠지만 가독성을 떨어트린다 판단해서 그대로 두었습니다.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

JAVA입니다.

public class eX014 {
    static byte[][] screen = new byte[8][8];
    static int caseCount = 0;


    public static void main(String[] args) {
        // TODO Auto-generated method stub

        //
        long start = System.nanoTime();

        count(0);
        System.out.println("경우의수: "+ String.valueOf(caseCount));

        long stop = System.nanoTime();
        System.out.println(stop - start + " ns");
        System.out.println((stop - start) / 1000000 + " ms");
        System.out.println((stop - start) / 1000000 / 1000 + " sec");
    }


    static void count(int row) {
        //해당 행의 모든 열을 탐색하여 퀸이 놓일 수 있는 위치의 개수를 구한다.
        for(int i=0; i<screen[0].length; i++) {
                 //해당 위치에 퀸을 놓는다.(1대입)
            screen[row][i] = 1;
            //해당 위치에 퀸을 놓을 수 있으면 true, 아니면 false
            if(canSet(row,i)) {
                if(row == screen.length-1) {
                    caseCount += 1;
                    screen[row][i] = 0;
                    continue;
                }
                count(row+1);
            }
            //해당 위치에 놓아져있는 퀸을 뺀다!
            screen[row][i] = 0;
        }
    }

    static boolean canSet(int row, int column) {
        //세로체크
        for(int i=0; i< screen.length; i++) {
            if(i == row)
                continue;
            if(screen[i][column] == 1)
                return false;
        }
        //가로체크
        for(int i=0; i<screen[0].length; i++) {
            if(i == column)
                continue;
            if(screen[row][i] == 1)
                return false;
        }


        int cRow,cColumn;
        //우상단대각 체크(우상단방향)
        for(cRow = row-1, cColumn=column+1; ( cRow >= 0 && cColumn < screen[0].length ); cRow-=1,cColumn+=1) {
            if(screen[cRow][cColumn] == 1)
                return false;
        }

        //우상단대각 체크(좌하단방향)
        for(cRow = row+1, cColumn=column-1; ( cRow < screen.length  && cColumn >= 0 ); cRow+=1,cColumn-=1) {
            if(screen[cRow][cColumn] == 1)
                return false;
        }

        //좌상단대각 체크(좌상단방향)
        for(cRow = row-1, cColumn=column-1; ( cRow >= 0  && cColumn >= 0 ); cRow-=1,cColumn-=1) {
            if(screen[cRow][cColumn] == 1)
                return false;
        }
        //좌상단대각 체크(우하단방향)
        for(cRow = row+1, cColumn=column+1; ( cRow < screen.length  && cColumn < screen[0].length ); cRow+=1,cColumn+=1) {
            if(screen[cRow][cColumn] == 1)
                return false;
        }

        return true;
    }

}

<결과 및 실행시간> 경우의수: 92 2639911 ns 2 ms 0 sec

8x8 byte배열을 만듭니다. 퀸이 놓여져 있는 부분은 1대입, 이외에 0(기본값) 맨처음 0번째 행부터 시작합니다. 0번째 행의 0~7번째 열을 반복문으로 탐색합니다. 반복문이 돌며 해당 위치에 퀸을 놓을 수 있는지 검사를 합니다.(canSet함수) 해당 위치에 퀸을 놓을 수 있다면 다음 행에 대해서 위의 과정을 반복합니다.(재귀) 마지막 행을 검사할 때, 퀸을 놓을 수 있는 위치가 발견된다면 case가 1개 발견되었으므로 변수에 +1을 해줍니다.

코드가 더럽다고 생각되네요... 비효율적인 부분이나, 코드를 깔끔히 정리할 수 있어 보이는 부분 지적 부탁드립니다.(__)

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

[Python 3.6]

import math

cnt = 0
def findQueenPosition(positionArray, line):
    global cnt
    if(line == 8):
        cnt += 1
        return
    for row in range(8):
        newPositionArray = ckeckQueenPosition(positionArray, line, row)
        if(newPositionArray):
            findQueenPosition(newPositionArray, line + 1)

def ckeckQueenPosition(positionArray, line, row):
    newPositionArray = positionArray[:]
    for position in newPositionArray:
        if (position[0] == line or position[1] == row or math.fabs(position[0] - line) == math.fabs(position[1] - row)): return
    newPositionArray.append((line, row))
    return newPositionArray

findQueenPosition([], 0)
print(cnt)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Python 3으로 풀었습니다.

def count_of_eight_queens():
    def can_choose(columns, new_c):
        new_r = len(columns)
        for r in range(len(columns)):
            c = columns[r]
            if new_c == c or abs(new_r - r) == abs(new_c - c):
                return False
        return True

    def choose_in(columns, items):
        if not items:
            nonlocal count
            count += 1
            # print(columns)
            return
        for col_idx in range(len(items)):
            col = items[col_idx]
            if can_choose(columns, col):
                columns.append(col)
                choose_in(columns, items[0:col_idx] + items[col_idx+1:])
                columns.remove(col)

    count = 0
    columns = []
    items = [i for i in range(8)]
    choose_in(columns, items)
    return count
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.

재귀호출 x 3
연관 문제
Eliya, 2017/07/22 13:23
Noname, 2017/08/19 01:34

언어별 풀이 현황
전 체 x 37
python x 16
ruby x 2
cpp x 6
matlab x 1
lisp x 1
java x 4
기 타 x 4
cs x 1
go x 1
javascript x 1