스도쿠 해결기

문제설명

스도쿠를 풀어버리자.

입력설명

첫번째줄에 첫번째 줄에 있는 숫자가 들어간다.

둘번째줄에 두번째 줄에 있는 숫자가 들어간다.

n번째줄에 n번째 줄에 있는 숫자가 들어간다.

출력설명

해답을 출력한다.

입력예시

103450000

400709123

789023056

201064089

564000231

890201504

312645000

645900012

000312045

출력예시

123456789

456789123

789123456

231564897

564897231

897231564

312645978

645978312

978312645

backtracking for replace
이상하네요 4번째 라인의 문제가 '201064089' 인데 풀이는 '231564897' 입니다. 끝에 089 부분이 풀었더니 897이 되면서 문제에 있던 숫자가 변경됐네요 - 안 준환, 2015/06/11 22:27 M D
제가 풀어낸 답은 [1, 2, 3, 4, 5, 6, 8, 9, 7] [4, 5, 6, 7, 8, 9, 1, 2, 3] [7, 8, 9, 1, 2, 3, 4, 5, 6] [2, 3, 1, 5, 6, 4, 7, 8, 9] [5, 6, 4, 8, 9, 7, 2, 3, 1] [8, 9, 7, 2, 3, 1, 5, 6, 4] [3, 1, 2, 6, 4, 5, 9, 7, 8] [6, 4, 5, 9, 7, 8, 3, 1, 2] [9, 7, 8, 3, 1, 2, 6, 4, 5] 입니다. - 안 준환, 2015/06/11 22:28 M D
[1, 2, 3, 4, 5, 6, (9), (7), (8)] [4, 5, 6, 7, 8, 9, 1, 2, 3] [7, 8, 9, 1, 2, 3, 4, 5, 6] [2, 3, 1, 5, 6, 4, 7, 8, 9] [5, 6, 4, 8, 9, 7, 2, 3, 1] [8, 9, 7, 2, 3, 1, 5, 6, 4] [3, 1, 2, 6, 4, 5, (8), (9), (7)] [6, 4, 5, 9, 7, 8, 3, 1, 2] [9, 7, 8, 3, 1, 2, 6, 4, 5] 위 분의 답 말고도 이것도 저 문제의 답이 될 수 있네요(윗분하고 다른 부분만 괄호로 표기) 위 스도쿠는 잘못된 예시입니다. 스도쿠 책이나 인터넷에서 스도쿠 생성기를 찾아서 다른 예시를 찾아보세요 저 문제 안풀린다고 알고리즘 잘못 짜신게 아닙니다;; 다만 답이 2개인 경우에 답을 하나로 만드는 알고리즘도 있다 하더군요 - Graed, 2015/09/18 21:01 M D
Gread님의 의견에 동의합니다 - Noh Hun, 2015/11/11 15:09 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

10개의 풀이가 있습니다.

간만에 python을하니 또 문법이 기억이 잘 안나네요; 막 풀었는데 다음분들께 깔끔한 코드 부탁드리겠습니다.

test.txt의 내용은

003000000
040006002
007050080
004008030
030100070
060000400
090010200
500700010
000000600

이고

그때 실행결과는

[0, 0, 3, 0, 0, 0, 0, 0, 0]
[0, 4, 0, 0, 0, 6, 0, 0, 2]
[0, 0, 7, 0, 5, 0, 0, 8, 0]
[0, 0, 4, 0, 0, 8, 0, 3, 0]
[0, 3, 0, 1, 0, 0, 0, 7, 0]
[0, 6, 0, 0, 0, 0, 4, 0, 0]
[0, 9, 0, 0, 1, 0, 2, 0, 0]
[5, 0, 0, 7, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 6, 0, 0]
solved
[9, 5, 3, 2, 8, 1, 7, 6, 4]
[1, 4, 8, 3, 7, 6, 5, 9, 2]
[6, 2, 7, 4, 5, 9, 1, 8, 3]
[7, 1, 4, 6, 2, 8, 9, 3, 5]
[2, 3, 9, 1, 4, 5, 8, 7, 6]
[8, 6, 5, 9, 3, 7, 4, 2, 1]
[4, 9, 6, 8, 1, 3, 2, 5, 7]
[5, 8, 2, 7, 6, 4, 3, 1, 9]
[3, 7, 1, 5, 9, 2, 6, 4, 8]

입니다.

#텍스트파일에서 문제 로딩
def load(filename):
    ret = []
    f = open(filename, 'r')
    while True:
        l=f.readline()
        if not l:
            break
        l = map(lambda x:int(x), l.strip())
        ret.append(list(l))
    f.close()
    return ret

#현재 스도쿠 보드 상태를 출력
def printBoard(board):
    for row in board:
        print(row)

#현재 상태에서 풀지 못한 부분에 1~9 어떤 수도 넣지 못하는 곳이 있다면 False, 아직 가능성이 있다면 True 반환
def validationCheck(board, exceptBoard):
    for y in range(len(board)):
        for x in range(len(board[y])):
            if board[y][x] <= 0 and findAnswer(board, exceptBoard, x, y)<0:
                return False
    return True;

#지정된 위치의 해답을 찾아냄, 단, force가 True라면 현재 위치에 넣을 수 있는 첫번째 숫자를 강제로 넣어버림
def findAnswer(board, exceptBoard, x, y, force=False):
    #candidate를 1~9로 잡고 제거 해 나감
    candidates={1,2,3,4,5,6,7,8,9}
    candidates=candidates-exceptBoard[y][x]
    #check col
    for y2 in range(len(board)):
        if board[y2][x] in candidates:
            candidates.remove(board[y2][x])
    #check row
    for x2 in range(len(board[y])):
        if board[y][x2] in candidates:
            candidates.remove(board[y][x2])
    #check box
    xstart=x//3*3
    ystart=y//3*3
    for y2 in range(ystart, ystart+3):
        for x2 in range(xstart, xstart+3):
            if board[y2][x2] in candidates:
                candidates.remove(board[y2][x2])
    if len(candidates)==0:
        return -1
    elif len(candidates)==1:
        return candidates.pop()
    elif force:
        while len(candidates)>0:
            candidate=candidates.pop()
            board[y][x]=candidate
            #강제로 넣은뒤에는 validiationCheck를 해서 계속 진행가능한지 판단하고 불가능하다면 다른 candidate를 넣어봄
            if validationCheck(board, exceptBoard):
                board[y][x]=0
                return candidate
            board[y][x]=0
        return 0
    else:
        return 0

CMD_PUT = 0
CMD_FORCE_PUT = 1
CMD_EXCEPT = 2

def solve(board, exceptBoard, cmdHistory):
    oldEmptyCount=0
    force = False
    while True:
        emptyCount=0
        for y in range(len(board)):
            for x in range(len(board[y])):
                if board[y][x] == 0:
                    answer=findAnswer(board, exceptBoard, x, y, force)
                    if answer>0:
                        if force:
                            cmdHistory.append((CMD_FORCE_PUT, x,y,answer))
                        else:
                            cmdHistory.append((CMD_PUT, x,y,answer))
                        board[y][x]=answer
                        force=False
                    if board[y][x]==0:
                        emptyCount+=1
        if emptyCount==0:
            break
        elif (oldEmptyCount == emptyCount and force) or (not validationCheck(board, exceptBoard)):
            #need to UNDO until last force
            while True:
                #force로 강제로 넣다보면 수가 막히는때가 있는데 이때는 그 전 force로 넣을 때로 되돌려서 다른 숫자로 다시 시도
                cmd = cmdHistory.pop()
                if cmd[0]==CMD_PUT or cmd[0]==CMD_FORCE_PUT:
                    board[cmd[2]][cmd[1]]=0
                if cmd[0]==CMD_FORCE_PUT:#forced
                    exceptBoard[cmd[2]][cmd[1]].add(cmd[3])
                    cmdHistory.append((CMD_EXCEPT, cmd[1],cmd[2],cmd[3]))
                    break
                elif cmd[0]==CMD_EXCEPT:
                    exceptBoard[cmd[2]][cmd[1]].remove(cmd[3])
                if len(cmdHistory)==0:
                    break
            force = True
        elif oldEmptyCount == emptyCount:
            force = True
        else:
            oldEmptyCount = emptyCount
        #printBoard(board)
        #printBoard(exceptBoard)
        #input()

def main():
    board = load('test.txt')
    exceptBoard = []
    for i in range(len(board)):
        exceptRow = []
        for i in range(len(board[0])):
            exceptRow.append(set())
        exceptBoard.append(exceptRow)
    cmdHistory = []# list of (CMD_PUT, CMD_FORCE_PUT or CMD_EXCEPT,x,y,number)
    #force로 숫자를 넣었다가 수를 되돌릴때 cmdHistory를 참고하여 undo함
    #이때 보드에 입력했던 숫자 뿐만 아니라 exceptBoard에 넣었던 특정칸에 넣어서는 안되는 숫자 리스트도 함께 undo 함께
    #CMD_PUT:정답을 찾은명령, CMD_FORCE_PUT:정답이 없어 force로 입력하는 명령, CMD_EXCEPT: undo도중 exceptBoard에 숫자 추가하는 명령
    printBoard(board)
    solve(board, exceptBoard, cmdHistory)
    print('solved')
    printBoard(board)

if __name__ == '__main__':
    main()
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

pandas를 사용하여 만들어 보았습니다.

엄청 어렵네요 ㅜㅜ

import numpy as np
from pandas import DataFrame, Series
import itertools
from copy import deepcopy

class Block():
    def __init__(self, value = 0, candidate = set(range(1,10))):
        self.candidate = candidate
        if isinstance(value, str):
            self.value = int(value)
        else:
            self.value = value

    def __repr__(self):
        if self.value:
            return str(self.value)
        else:
            return 'Candidate = {}'.format(self.candidate)

    def del_candidate(self, valueset):
        if self.value: return False

        tempset = self.candidate - valueset
        if not tempset:
            raise ValueError("Candidate can't be empty.")
        elif len(tempset) == 1:
            self.value = list(tempset)[0]
            return True
        else:
            self.candidate = tempset
            return False

class Grid():
    def __init__(self, filename):
        with open(filename) as f:
            board = [list(x) for x in f.read().splitlines()]
        grid = DataFrame(board)
        self.grid = grid.applymap(Block)
        self.del_candidate()

    def del_candidate(self):
        ans = []
        while True:
            row = self.grid.apply(self.del_candidates_by_obj, axis = 1).sum()
            col = self.grid.apply(self.del_candidates_by_obj).sum()
            subgrid = [self.grid.ix[x:y, z:w] for (x,y), (z,w) in \
                       itertools.product([(x,y) for x,y in zip(range(0,9,3), range(2,9,3))],
                                         repeat = 2)]
            subgrid_result = sum((map(self.del_candidates_by_obj, subgrid)))
            change = sum([row, col, subgrid_result])
            if change:
                ans.append(change)
            else:
                break
        return ans

    @staticmethod
    def del_candidates_by_obj(obj):
        if isinstance(obj, DataFrame):
            valueset = set(obj.applymap(lambda x:x.value).values.reshape(9))
            return obj.applymap(lambda x:x.del_candidate(valueset)).sum().sum()
        if isinstance(obj, Series):
            valueset = set(obj.map(lambda x:x.value))
            return obj.map(lambda x:x.del_candidate(valueset)).sum()

    def evaluate(self, row, col):
        first_state = deepcopy(self.grid)
        result = {}
        changes = {}
        candidate = self.grid.at[row, col].candidate
        for i in candidate:
            self.grid = deepcopy(first_state)
            self.grid.ix[row, col].value = i
            try:
                x = self.del_candidate()
                result[i] = self.grid.copy()
                changes[i] = sum(x)
            except ValueError as e:
                result[i] = 'Error'
                changes[i] = None

        self.grid = deepcopy(first_state)
        changes = Series(changes)
        return result, changes

    def recursive_evaluate(self):
        first_state = deepcopy(self.grid)
        len_candidates = self.grid.applymap(lambda x: np.nan if x.value else len(x.candidate))
        if not len_candidates.any().any():
            return self.grid 
        assumetable = DataFrame(len_candidates.T.idxmax()).reset_index().dropna()
        assumetable.columns = ['row','col']
        # assumetable['candidates'] = [self.grid.at[row,col].candidate for row, col in assumetable.values] 
        assumetable['len_candidates'] = len_candidates.max(axis = 1)
        while len(assumetable.index) > 0:
            best_assume_index = assumetable.len_candidates.argmax()
            best_assume = assumetable.ix[best_assume_index].astype(int)
            assumetable.drop(best_assume_index, inplace=True)
            result, changes = self.evaluate(best_assume.row,best_assume.col)

            if changes.notnull().any():
                self.grid = result[changes.idxmax()]
                ans = self.recursive_evaluate()
                if isinstance(ans, DataFrame):
                    return ans
                else:
                    continue
            else:
                self.grid = deepcopy(first_state)
        return False

a=Grid('파일이름') a.recursive_evaluate() 하면되는거죠? 샘플문제 외에 다른 문제도 풀어보세요~ - 안 준환, 2015/06/15 08:54 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

저는 또 답이 다르게 나오네요...

123456978

456789123

789123456

231564789

564897231

897231564

312645897

645978312

978312645

하도 오래전에 짠 거라 컴파일하다가 fopen_s를 쓰라고 하네요. 컴파일할때 무시하라고 했습니다 --

// Sudoku.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

#include "stdafx.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <process.h>
#include <conio.h>
#include <iostream>

#define _CRT_SECURE_NO_WARNINGS

using namespace std;
using std::ostream;

#define MAX_BUFFER 100

int g_Count = 0;

class Sudoku
{
private:
    char cKey;
    char cIndex;
    char a_cVal[9];
    char cValid;
public:
    int SetIndex(int index) { cIndex = (char)index; return index; };
    int SetValue(int index, int value);
    int GetValue() { return (int)cKey; };
    int GetValid() { return (int)cValid; };
    int GetCandidate(int index);
    Sudoku();
    ~Sudoku() {};
    Sudoku& operator=(const Sudoku & b)
    {
        cValid = b.cValid;
        cIndex = b.cIndex;
        cKey = b.cKey;
        for (int i = 0; i<9; ++i)
            a_cVal[i] = b.a_cVal[i];
        return *this;
    }

    friend ostream & operator<<(ostream & os, const Sudoku & Sud)
    {
        os << (int)Sud.cKey;
        return os;
    }
};

class SudokuCompute{
private:
    class Sudoku * MySud;
    class Sudoku * YesterSud[MAX_BUFFER];
    int iStackEnd;
    int iStackBegin;

public:
    int SetValue(int row, int col, int value);
    int SetValue(Sudoku * Sud, int row, int col, int value);
    int Calc();
    void PrintOut();
    SudokuCompute();
    ~SudokuCompute() {};

};

SudokuCompute::SudokuCompute()
{
    MySud = NULL;
    MySud = new Sudoku[9 * 9];
    for (int k = 0; k<MAX_BUFFER; ++k) YesterSud[k] = NULL;
    iStackEnd = iStackBegin = 0;
    for (int i = 0; i<9; ++i)
    for (int j = 0; j<9; ++j)
        MySud[i * 9 + j].SetIndex(i * 10 + j);
}

int SudokuCompute::SetValue(int row, int col, int value)
{
    int result = 1;
    for (int i = 0; i<9; ++i)
    for (int j = 0; j<9; ++j)
    {
        result = result * (int)MySud[i * 9 + j].SetValue(row * 10 + col, value);
    }
    return result;
}

int SudokuCompute::SetValue(Sudoku * Sud, int row, int col, int value)
{
    int result = 1;
    for (int i = 0; i<9; ++i)
    for (int j = 0; j<9; ++j)
    {
        result = result * (int)Sud[i * 9 + j].SetValue(row * 10 + col, value);
    }
    return result;
}

int SudokuCompute::Calc()
{
    int iRightCount = 0;
    int i, j;

    for (i = 0; i<9; ++i)
    for (j = 0; j<9; ++j)
    {
        if (MySud[i * 9 + j].GetValue() > 0)
        {
            ++iRightCount;
        }
        if (MySud[i * 9 + j].GetValue() == 0 && (MySud[i * 9 + j].GetValid() == 1))
        {
            if (SetValue(i, j, MySud[i * 9 + j].GetCandidate(0)))
            {
                return 1;
            }
            else
            {
                printf("\nWrong Pass");
                delete[] MySud;
                MySud = YesterSud[--iStackEnd];
                return 1;
            }
        }
    }
    for (i = 0; i<9; ++i)
    for (j = 0; j<9; ++j)
    {
        if (MySud[i * 9 + j].GetValue() == 0 && (MySud[i * 9 + j].GetValid() == 2))
        {
            printf("\nCase 2 Get : count(%d) StackBegin(%d) StackEnd(%d) ", g_Count++, iStackBegin, iStackEnd);
            if (iStackEnd == 100)
            {
                printf("\nCan't Solve!");
                return 0;
            }
            YesterSud[iStackEnd] = MySud;

            MySud = new Sudoku[9 * 9];
            for (int ii = 0; ii<9; ++ii)
            for (int jj = 0; jj<9; ++jj)
                MySud[ii * 9 + jj] = YesterSud[iStackEnd][ii * 9 + jj];
            SetValue(YesterSud[iStackEnd], i, j, YesterSud[iStackEnd][i * 9 + j].GetCandidate(0));
            SetValue(i, j, MySud[i * 9 + j].GetCandidate(1));
            iStackEnd++;
            return 1;
        }
    }

    if (iRightCount != 9 * 9)
    {
        printf("\nWrong Pass");
        delete[] MySud;
        MySud = YesterSud[--iStackEnd];
        if (iStackBegin > iStackEnd)
        {
            printf("\nCan't Solve!");
            return 0;
        }
        return 1;
    }
    else
    {
        printf("\nThe Right Thing!\n");
        return 0;
    }
}

void SudokuCompute::PrintOut()
{
    for (int i = 0; i<9; ++i)
    {
        for (int j = 0; j<9; ++j)
        {
            cout << MySud[i * 9 + j];
        }
        cout << endl;
    }
}

Sudoku::Sudoku()
{
    cKey = 0;
    cValid = 9;
    for (int i = 0; i<9; ++i)
        a_cVal[i] = 0;
}

int Sudoku::SetValue(int index, int value)
{
    if (value == 0) return 1;
    if (index == cIndex)
    {
        if (cKey != 0) return 0;

        if (a_cVal[value - 1] == -1) return 0;

        cKey = value;

        return 1;
    }
    else
    {
        if (index / 10 == cIndex / 10) // 행이 같을 때
        {
            a_cVal[value - 1] = -1;
        }

        if (index % 10 == cIndex % 10) // 열이 같을 때 
        {
            a_cVal[value - 1] = -1;
        }

        if (((index / 10) / 3 == (cIndex / 10) / 3)
            && ((index % 10) / 3 == (cIndex % 10) / 3)) // 인근
        {
            a_cVal[value - 1] = -1;
        }

        if (a_cVal[value - 1] != -1)
            ++a_cVal[value - 1];

        cValid = 0;

        for (int i = 0; i<9; ++i)
        if (a_cVal[i] != -1) ++cValid;

        return 1;
    }
}

int Sudoku::GetCandidate(int index)
{
    int iIndex = 0;
    for (int i = 0; i<9; ++i)
    {
        if (a_cVal[i] > 0)
        {
            if (iIndex++ == index)
                return i + 1;
        }
    }
    return 0;
}

void main()
{
    SudokuCompute MySudCompute;
    FILE * fp;
    //fopen_s(&fp, "..\\Sudoku\\Sudoku.txt", "rt");
    //fopen_s(&fp, "Sudoku.txt", "rt");
    fp = fopen( "Sudoku.txt", "rt");

    if (fp == NULL)
    {
        char a;
        cout << "Can't find sudoku.txt file! ";
        cin >> a;
        return;

    }

    char String1[9 * 9 + 1];
    String1[9 * 9] = 0;
    for (int ii = 0; ii<9; ++ii)
    {
        //fscanf_s(fp, "%s", (char *)(String1 + ii * 9));
        fscanf(fp, "%s", (char *)(String1 + ii * 9));       
    }
    fclose(fp);

    for (int i = 0; i<9; ++i)
    for (int j = 0; j<9; ++j)
        MySudCompute.SetValue(i, j, (int)String1[i * 9 + j] - '0');

    do
    {
        printf("\nSudoku\n");
        //MySudCompute.PrintOut();
        //if (g_Count > 1000 ) getch();
    } while (MySudCompute.Calc());
    MySudCompute.PrintOut();
}


※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
def rotate(str_list):
    str_questionRotate=["" for i in str_list]
    for i in range(len(str_list)):
        for j in range(len(str_list)):
            str_questionRotate[i]+=str_list[j][i]
    return  str_questionRotate

def answer_sdoqu(str_question,blank=81):
    str_questionRotate=rotate(str_question)
    set_0to9=set(map(lambda a: str(a),range(10)))
    str_poscol=list(map(lambda temp_str: set_0to9 - set(list(temp_str)),str_questionRotate))
    str_posrow=list(map(lambda temp_str: set_0to9 - set(list(temp_str)),str_question))
    str_answer=["" for i in str_question]

    str_box=[set() for i in range(len(str_question))]
    for i in range(len(str_question)):
        for j in range(len(str_question)):
            if str_question[i][j]!='0':
                str_box[3*int(i/3)+int(j/3)].add(str_question[i][j])
    for i,temp in enumerate(str_box):
        str_box[i]=set_0to9-temp

    for i in range(len(str_question)):
        for j in range(len(str_question)):
            if str_question[i][j]=='0':
                if len(str_posrow[i]&str_poscol[j]&str_box[3*int(i/3)+int(j/3)])==1:
                    s=(str_posrow[i]&str_poscol[j]&str_box[3*int(i/3)+int(j/3)]).pop()
                    str_posrow[i].discard(s)
                    str_poscol[j].discard(s)
                    str_box[3*int(i/3)+int(j/3)].discard(s)
                    str_answer[i]+=s
                else:
                    str_answer[i]+='0'
            else:
                str_answer[i]+=str_question[i][j]
    # 재귀부분
    count_blank=0
    for i in str_question:
        count_blank+=i.count('0')

    if blank==count_blank:
        return str_answer
    elif count_blank>0:
        return answer_sdoqu(str_answer,count_blank)
    else:
        return str_answer

스도쿠 해결 코드입니다.

해결 방법은 answer_sdoqu 첫 부분에 각 행과 열, 그리고 3x3영역에서 사용되지 않은 숫자들의 집합을 만들었습니다. 이게 바로 str_posrow, str_poscol, str_box 변수입니다.

이후 for문을 2번 사용해서 매개변수로 넘어온 스도쿠 맵을 살펴보며 만약 0인 부분이 있다면 그 부분에서 해당되는 str_posrow, str_poscol, str_box 의 요소를 얻어 교집합을 구합니다(str_posrow, str_poscol, str_box는 각각 set이 저장된 list라 파이선의 교집합 연산이 가능합니다)그리고 그 위치에서 교집합이 1이라면 새로 만드는 str_answer에 비어있던 부분을 하나의 원소만을 가지는 교집합에서 넣어주면 스도쿠 풀이를 한 과정 진행하게 됩니다.

이후 계속해서 str_answer를 매겨변수로 재귀함수 호출로 계속해서 빈칸을 채워나갑니다.

다만 재귀식이라 답이 없다면 오류가 생기므로 blank변수를 사용합니다 blank는 이전의 함수가 호출되었을 때의 스도쿠 빈 칸의 크기로 만약 지난번에 있었던 빈칸하고 이번에 푼 스도쿠에서의 빈칸의 크기가 같다면 그건 더이상 풀 수 있는 방법이 없다는 의미임으로 재귀 호출을 종료하고 푸는게 가능한 데까지를 반환하도록 하였습니다.

rotate함수는 간단합니다. 그냥 열과 행을 바꾸는 코드입니다.

실제로 이 함수를 이용하려면 이런식으로 하면 됩니다.

q1=['704080906','500320008','080700300','040009060','260400051','050670040','006007090','900062004','405010607']
r=answer_sdoqu(q1)
print_sdoqu(r)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
a1= [1,0,3,4,5,0,8,0,0] #sudoku to solve 파이썬 입니다.
a2= [4,0,0,7,0,9,1,2,3]
a3= [7,8,9,0,2,3,0,5,6]
a4= [2,0,1,0,6,4,0,8,9]
a5= [5,6,4,0,0,0,2,3,1]
a6= [8,9,0,2,0,1,5,0,4]
a7= [3,1,2,6,4,5,0,0,0]
a8= [6,4,5,9,0,0,0,1,2]
a9= [0,0,0,3,1,2,0,4,5]
Li= [a1,a2,a3,a4,a5,a6,a7,a8,a9]

def search_vertical(x):
    for i in range(len(Li)):
        if Li[i][x]!= 0:
            possibleRow.remove(Li[i][x])
def is0inLi():                             #0이 하나라도 남아있으면 True
    for i in Li:
        if 0 in i:
            return True

while is0inLi():                   #0이 없어질때까지 반복
    for solve in range(8):
        for i in Li:
            col=[]
            indexToFill=[0,1,2,3,4,5,6,7,8]
            for j in i:
                if j!= 0:
                    col.append(j)    #이미 사용된 가로 숫자 리스트
                    indexToFill.remove(i.index(j))
            for k in indexToFill:
                possibleRow=[1,2,3,4,5,6,7,8,9]               
                search_vertical(k)               #세로줄에서 사용가능한 숫자 목록 만들기
                s1,s2=set(possibleRow),set(col)
                finalSet=s1-s2                   # 가로,세로 훑어본 결과 0인 자리에 넣을 수 있는 숫자들
                if len(finalSet)==1:             # 입력 가능 숫자가 1개면 즉시 그 숫자로 0을 대체 
                    i[k]=list(finalSet)[0]

그저 제가 머릿속으로 수도쿠 푸는 과정을 그대로 구현했어요. 가로, 세로 훑어서 넣을 수 있는 숫자가 하나면 바로 넣고 아니면 일단 패스~ 그 과정을 반복~ 음 윗분 말씀대로 엄밀히 따지면 첫줄 897, 987 두개로 나오니 기존 문제인 103450000 대신 103450(8)00로 8을 채워넣고 돌렸습니다. 물론 897, 987 남은 상황에서 랜덤으로 돌려서 풀어도 되긴 하겠지요. 파이썬 독학한 비전공자 백수입니다. 누가 저좀 데려가주세요ㅠ.ㅠ

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

스도쿠를 풀다보면 더이상 안풀려서, 여러가지 가능성중에 한가지로 가정해놓고 풀어야 하는 경우가 생기는데요, 그걸 스택으로 구현해보았습니다.

좀 무식할 수도 있는데, 1에서 9까지의 배열을 81개를 만들어서 각 자리에 하나씩 숫자가 정해질때마다 그 행과 그 열, 그리구 그 자리가 속해있는 3x3 사각형을 찾아서 거기에 속해있는 모든 리스트들에서 그 숫자를 제거하는 방법을 썼습니다.

import copy
def isSolved(sdk):#풀린 스도쿠인지 확인
    return all(len(sdk[j][i]) == 1  for i in range(9) for j in range(9))
def fixOnePoint(sdk, row, col, n):
    '''
    스도쿠의 한자리를 n으로 픽스했을때 n이 들어갈 수 없는 자리를 찾아서
    그 자리에 해당하는 리스트에서 n을 제거함.
    n을 제거했을 때 리스트에 한개만 남는다면,
    재귀적으로 그 자리에서도 이 함수를 호출
    '''
    sdk[row][col] = [n]
    for i in range(9): #가로줄
        if i==col : continue #자기자리는 제외
        if n in sdk[row][i] :
            sdk[row][i].remove(n)
            if len(sdk[row][i])==0 : return False #잘못된 풀이이므로 중단
            if len(sdk[row][i])==1 : fixOnePoint(sdk, row, i, sdk[row][i][0])
    for j in range(9): #세로줄
        if j==row : continue
        if n in sdk[j][col] :
            sdk[j][col].remove(n)
            if len(sdk[j][col])==0 : return False
            if len(sdk[j][col])==1 : fixOnePoint(sdk, j, col, sdk[j][col][0])
    for j in range(row/3*3, row/3*3+3):
        for i in range(col/3*3, col/3*3+3):
            if i==col and j==row : continue
            if n in sdk[j][i] :
                sdk[j][i].remove(n)
                if len(sdk[j][i])==0 : return False
                if len(sdk[j][i])==1 : fixOnePoint(sdk, j, i, sdk[j][i][0])
    return True
def printOut(sdk):#화면에 결과 출력
    for line in sdk: print ''.join(str(x[0]) for x in line)
def translateProblem(problem): #문제를 적절한 배열구조로 바꿈
    sdk = []
    for j in range(9): #[1~9]의 배열을 81개 만듬.
        line=[]
        for i in range(9):
            line.append(list(range(1,10)))
        sdk.append(line)
    problem = problem.split()
    for row,line in enumerate(problem):
        for col, c in enumerate(line):
            if int(c)>0:fixOnePoint(sdk, row, col, int(c))
    return sdk

problem='''\
103450000
400709123
789023056
201064089
564000231
890201504
312645000
645900012
000312045'''

sdk_list=[translateProblem(problem)] #문제풀이 스택
'''
스도쿠를 풀다보면
답을 가정하고 풀어야 하는 경우가 생기는데
그걸 스택으로 구현했다.
스도쿠를 스택에서 꺼내서
여러 가능성을 입력해서 나오는 결과들을 다시 스택에 넣음
'''

while sdk_list:
    s=sdk_list.pop()#스택에서 가져옴
    for j,i in [(j,i) for j in range(9) for i in range(9)]:
        if len(s[j][i])>1:break
    possible_list = s[j][i]
    for c in possible_list:
        s_copy = copy.deepcopy(s) #리스트의 내부를 조작해야 하면서
                                    # 함수를 같은 리스트로 여러번 호출해야 하므로
                                    # deepcopy를 사용해야 함.
        if fixOnePoint(s_copy, j, i, c):#c값이 잘못된 가정이 아니라면
            if isSolved(s_copy) : 
                printOut(s_copy)
                break
            sdk_list.append(s_copy) #스택에 추가

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

Python 2.7

빈 칸의 리스트를 만들고 인덱스 변수를 넣어 이동시켰습니다.

class Sudoku:
    def __init__(self, s):
        self.board = [map(int, list(line)) for line in s.split()]
        self.empty = [(x,y) for x in xrange(9)\
                      for y in xrange(9) if self.board[y][x]==0]
        self.i = len(self.empty)-1

    def output(self):
        for line in self.board:
            print ''.join(map(str,line))
        print

    def grid(self, gn):
        x = 3*(gn%3)+1
        y = 3*(gn/3)+1
        pos = zip([x-1,x,x+1]*3, [y-1,y-1,y-1,y,y,y,y+1,y+1,y+1])
        return [self.board[p[1]][p[0]] for p in pos]

    def addable(self, x, y):
        res = set([1,2,3,4,5,6,7,8,9])
        # Horizontal
        res-= set(self.board[y])
        # Vertical
        res-= set(self.board[i][x] for i in xrange(9))
        # Grid
        gn = 3*(y/3)+x/3
        res-= set(self.grid(gn))
        return res

    def add(self, n):
        x,y = self.empty[self.i]
        self.board[y][x] = n
        self.i-= 1

    def remove(self):
        self.i+= 1
        x,y = self.empty[self.i]
        self.board[y][x] = 0

    def solve(self):
        if self.i == -1:
            self.output()
            return
        x,y = self.empty[self.i]
        for n in self.addable(x,y):
            self.add(n)
            self.solve()
            self.remove()

Sudoku('\n'.join([raw_input() for i in xrange(9)])).solve()
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

예전에 프로젝트 오일러 풀면서 작성했던 LiveScript 코드입니다. 어떤 칸에 채울 수 있는 숫자들을 하나씩 넣어보면서 진행하고, 데드엔드를 만나면 돌아와서 다음 숫자로 재시도합니다. 별다른 휴리스틱이나 제약조건전파는 무시했습니다.

i2c = (i) -> [i % 9, Math.floor i / 9]
zone = (i) -> 
  [x, y] = i2c i
  (Math.floor y / 3) * 3 + (Math.floor x / 3)
in-zone = (i) ->
  z = zone i
  zi = (z % 3) * 3 + (Math.floor z / 3) * 27
  [zi + m * 9 for m in [0 til 2]].map ->
    [it + n for n in [0 til 2]]
  .reduce (++), []
sub = (xs, ys) -> [x for x in xs when x not in ys]

class Node
  (@value, @order) ->
    @color = if @value == 0 then \white else \black

class Sudoku
  (str-data) ->
    @data = str-data.split '' .map (c, i) ->
      new Node (parseInt c), i
  avaiables: (i) ->
    [x, y] = i2c i
    ar = [0 til 9].map (e) ~> @data[9 * y + e].value
    ac = [0 til 9].map (e) ~> @data[9 * e + x].value
    az = in-zone i .map (e) ~> @data[e].value
    sub [1 to 9], ar++ac++az
  run: ->
    nv = @data.filter (.color == \white)
    if nv.length == 0 then return yes
    cv = nv[0]
    for a in @avaiables cv.order
      cv <<< color:\gray, value:a
      if @run! then return yes
    cv <<< color:\white, value:0
    no
  description: ->
    [0 til 9].map (r)~>
      [0 til 9].map (c)~>
        @data[c + r * 9].value.to-string!
      .join '|'
    .join '\n' + '-' * 17 + '\n'

a = new Sudoku \103450000400709123789023056201064089564000231890201504312645000645900012000312045 
a.run!
a.description! |> console.log

출력은 아래와 같습니다.

1|2|3|4|5|6|8|9|7
-----------------
4|5|6|7|8|9|1|2|3
-----------------
7|8|9|1|2|3|4|5|6
-----------------
2|3|1|5|6|4|7|8|9
-----------------
5|6|4|8|9|7|2|3|1
-----------------
8|9|7|2|3|1|5|6|4
-----------------
3|1|2|6|4|5|9|7|8
-----------------
6|4|5|9|7|8|3|1|2
-----------------
9|7|8|3|1|2|6|4|5
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

#include <stdio.h>
#include <stdlib.h>

#define MAX_COLS 10000
#define size 9

struct Matrix{
    bool flag[size+1];
    int value;
} matrix[size][size];

bool verdict();
void setFlag();

void main() {
    int input[size][size] = {{1,0,3,4,5,0,0,0,0},{4,0,0,7,0,9,1,2,3},{7,8,9,0,2,3,0,5,6},{2,0,1,0,6,4,0,8,9},
    {5,6,4,0,0,0,2,3,1},{8,9,0,2,0,1,5,0,4},{3,1,2,6,4,5,0,0,0},{6,4,5,9,0,0,0,1,2},{0,0,0,3,1,2,0,4,5}};
    for(int i=0;i<size;i++) {
        for(int j=0;j<size;j++) {
            matrix[i][j].value = input[i][j];
            for(int k=0;k<=size;k++)
                matrix[i][j].flag[k] = false;
        }
    }

    printf("Input\n");
    for(int i=0;i<size;i++) {
        for(int j=0;j<size;j++) {
            printf("%d ", matrix[i][j].value);
        }
        printf("\n");
    }

    while(verdict()){
        bool roop = true;
        while(roop) {
            setFlag();
            roop = false;
            for(int i=0;i<size;i++) {
                for(int j=0;j<size;j++) {
                    int count = 0;
                    int index = 0;
                    for(int k=1;k<=size;k++) {
                        if(matrix[i][j].flag[k] == false) {
                            count++;
                            index = k;
                        }
                    }
                    if(count==1 && matrix[i][j].value==0) {
                        matrix[i][j].value = index;
                        roop = true;
                    }
                }
            }
        }


        for(int i=0;i<size;i++) {
            for(int j=0;j<size;j++) {
                int count = 0;
                int index = 0;
                for(int k=1;k<=size;k++) {
                    if(matrix[i][j].flag[k] == false) {
                        count++;
                        index = k;
                    }
                }
                if(count==2 && matrix[i][j].value==0) {
                    matrix[i][j].value = index;
                    setFlag();
                }

            }
        }
    }
    printf("\nOutput\n");
    for(int i=0;i<size;i++) {
        for(int j=0;j<size;j++) {
            printf("%d ", matrix[i][j].value);
        }
        printf("\n");
    }
}

bool verdict() {
    for(int i=0;i<size;i++) {
        for(int j=0;j<size;j++) {
            if(matrix[i][j].value == 0)
                return true;
        }
    }
    return false;
}

void setFlag() {
    for(int i=0;i<size;i++) {
        for(int j=0;j<size;j++) { // 좌표
            for(int k=0;k<size;k++) { // 가로
                matrix[i][j].flag[matrix[i][k].value] = true;
            }
            for(int k=0;k<size;k++) { // 세로
                matrix[i][j].flag[matrix[k][j].value] = true;
            }

            // 1 2 3
            // 4 5 6
            // 7 8 9
            if(i>=0 && i<=2 && j>=0 && j<=2) {// 1번 block
                int w_high = 2;
                int w_low = 0;
                int h_high=2;
                int h_low=0;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=0 && i<=2 && j>=3 && j<=5) {// 2번 block
                int w_high = 5;
                int w_low = 3;
                int h_high=2;
                int h_low=0;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=0 && i<=2 && j>=6 && j<=8) {// 3번 block
                int w_high = 8;
                int w_low = 6;
                int h_high=2;
                int h_low=0;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=3 && i<=5 && j>=0 && j<=2) {// 4번 block
                int w_high = 2;
                int w_low = 0;
                int h_high=5;
                int h_low=3;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=3 && i<=5 && j>=3 && j<=5) {// 5번 block
                int w_high = 5;
                int w_low = 3;
                int h_high=5;
                int h_low=3;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=3 && i<=5 && j>=6 && j<=8) {// 6번 block
                int w_high = 8;
                int w_low = 6;
                int h_high=5;
                int h_low=3;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=6 && i<=8 && j>=0 && j<=2) {// 7번 block
                int w_high = 2;
                int w_low = 0;
                int h_high=8;
                int h_low=6;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=6 && i<=8 && j>=3 && j<=5) {// 8번 block
                int w_high = 5;
                int w_low = 3;
                int h_high=8;
                int h_low=6;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=6 && i<=8 && j>=6 && j<=8) {// 9번 block
                int w_high = 8;
                int w_low = 6;
                int h_high=8;
                int h_low=6;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
        }
    }
}

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

#include <stdio.h>
#include <stdlib.h>

#define MAX_COLS 10000
#define size 9

struct Matrix{
    bool flag[size+1];
    int value;
} matrix[size][size];

bool verdict();
void setFlag();

void main() {
    int input[size][size] = {{1,0,3,4,5,0,0,0,0},{4,0,0,7,0,9,1,2,3},{7,8,9,0,2,3,0,5,6},{2,0,1,0,6,4,0,8,9},
    {5,6,4,0,0,0,2,3,1},{8,9,0,2,0,1,5,0,4},{3,1,2,6,4,5,0,0,0},{6,4,5,9,0,0,0,1,2},{0,0,0,3,1,2,0,4,5}};
    for(int i=0;i<size;i++) {
        for(int j=0;j<size;j++) {
            matrix[i][j].value = input[i][j];
            for(int k=0;k<=size;k++)
                matrix[i][j].flag[k] = false;
        }
    }

    printf("Input\n");
    for(int i=0;i<size;i++) {
        for(int j=0;j<size;j++) {
            printf("%d ", matrix[i][j].value);
        }
        printf("\n");
    }

    while(verdict()){
        bool roop = true;
        while(roop) {
            setFlag();
            roop = false;
            for(int i=0;i<size;i++) {
                for(int j=0;j<size;j++) {
                    int count = 0;
                    int index = 0;
                    for(int k=1;k<=size;k++) {
                        if(matrix[i][j].flag[k] == false) {
                            count++;
                            index = k;
                        }
                    }
                    if(count==1 && matrix[i][j].value==0) {
                        matrix[i][j].value = index;
                        roop = true;
                    }
                }
            }
        }


        for(int i=0;i<size;i++) {
            for(int j=0;j<size;j++) {
                int count = 0;
                int index = 0;
                for(int k=1;k<=size;k++) {
                    if(matrix[i][j].flag[k] == false) {
                        count++;
                        index = k;
                    }
                }
                if(count==2 && matrix[i][j].value==0) {
                    matrix[i][j].value = index;
                    setFlag();
                }

            }
        }
    }
    printf("\nOutput\n");
    for(int i=0;i<size;i++) {
        for(int j=0;j<size;j++) {
            printf("%d ", matrix[i][j].value);
        }
        printf("\n");
    }
}

bool verdict() {
    for(int i=0;i<size;i++) {
        for(int j=0;j<size;j++) {
            if(matrix[i][j].value == 0)
                return true;
        }
    }
    return false;
}

void setFlag() {
    for(int i=0;i<size;i++) {
        for(int j=0;j<size;j++) { // 좌표
            for(int k=0;k<size;k++) { // 가로
                matrix[i][j].flag[matrix[i][k].value] = true;
            }
            for(int k=0;k<size;k++) { // 세로
                matrix[i][j].flag[matrix[k][j].value] = true;
            }

            // 1 2 3
            // 4 5 6
            // 7 8 9
            if(i>=0 && i<=2 && j>=0 && j<=2) {// 1번 block
                int w_high = 2;
                int w_low = 0;
                int h_high=2;
                int h_low=0;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=0 && i<=2 && j>=3 && j<=5) {// 2번 block
                int w_high = 5;
                int w_low = 3;
                int h_high=2;
                int h_low=0;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=0 && i<=2 && j>=6 && j<=8) {// 3번 block
                int w_high = 8;
                int w_low = 6;
                int h_high=2;
                int h_low=0;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=3 && i<=5 && j>=0 && j<=2) {// 4번 block
                int w_high = 2;
                int w_low = 0;
                int h_high=5;
                int h_low=3;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=3 && i<=5 && j>=3 && j<=5) {// 5번 block
                int w_high = 5;
                int w_low = 3;
                int h_high=5;
                int h_low=3;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=3 && i<=5 && j>=6 && j<=8) {// 6번 block
                int w_high = 8;
                int w_low = 6;
                int h_high=5;
                int h_low=3;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=6 && i<=8 && j>=0 && j<=2) {// 7번 block
                int w_high = 2;
                int w_low = 0;
                int h_high=8;
                int h_low=6;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=6 && i<=8 && j>=3 && j<=5) {// 8번 block
                int w_high = 5;
                int w_low = 3;
                int h_high=8;
                int h_low=6;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
            else if(i>=6 && i<=8 && j>=6 && j<=8) {// 9번 block
                int w_high = 8;
                int w_low = 6;
                int h_high=8;
                int h_low=6;
                for(int w=w_low;w <= w_high;w++) {
                    for(int h=h_low;h<=h_high;h++) {
                        matrix[i][j].flag[matrix[h][w].value] = true;
                    }
                }
            }
        }
    }
}

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

풀이 작성

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

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

for x 2
backtracking x 1
replace x 1
연관 문제
Jeong Hoon Lee, 2017/06/20 08:49

언어별 풀이 현황
전 체 x 10
python x 6
cpp x 1
기 타 x 3