#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;
                    }
                }
            }
        }
    }
}

# 9x9 sdoku
class sdoku:
  def __init__(self, inp):
    self.board = [[*map(int,i)] for i in inp.split('\n')]
    self.x = [(i,j) for i in range(9)
                    for j in range(9) if self.board[i][j] == 0]

  def solve(self):
    stc = [self.__solver(self.x[0])]
    while stc:
      try:
        tx, ty = self.x[len(stc)-1]
        self.board[tx][ty] = next(stc[-1])
      except:
        stc.pop()
        tx, ty = self.x[len(stc)]
        self.board[tx][ty] = 0
        continue
      if len(stc) == len(self.x):
        self.__printans()
        return
      stc.append(self.__solver(self.x[len(stc)]))
    print('정답을 찾을 수 없습니다')

  def __solver(self, v):
    ret = set(self.board[v[0]])
    ret |= set(self.board[i][v[1]] for i in range(9))
    ret |= set(self.board[i][j] for i in range(3*(v[0]//3), 3*(v[0]//3)+3)
                                for j in range(3*(v[1]//3), 3*(v[1]//3)+3))
    ret = set(range(10)) - ret
    yield from ret

  def __printans(self):
    for i in self.board:
      print(''.join(map(str,i)))
    print()



if __name__ == '__main__':
  inp = ['''\
530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079''',
'''\
040000000
001034620
603000070
000483507
000050060
000009040
005000001
800547396
000021000''']

  for j in (sdoku(i) for i in inp): j.solve()

결과

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

248675139
751934628
693218475
926483517
184752963
537169842
475396281
812547396
369821754

간만에 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

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

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;
                    }
                }
            }
        }
    }
}

재밌네요 흐. 그냥 하면 어려울 거 없는데.

일단 기본 접근 방법은 소거법입니다.

• 각 칸마다 들어갈 수 있는 숫자('후보'라고 합시다)들을 저장해 놓습니다.

• 처음 숫자가 주어진 칸은 후보가 하나 뿐이고, 숫자가 없는 칸은 후보가 123456789 전부입니다.

• 특정 칸을 뽑아서 그 칸의 숫자를 후보 중 하나인 k로 확정하고, 확정한 칸을 기준으로 가로/세로/3x3의 다른 칸들에게서 후보 k를 제외합니다.

• 위 과정을 모든 칸이 확정될 때까지 반복합니다.

.

첫 번째 고민: 백트래킹

사람이 풀라고 만들어진 문제라면 선택지가 두 개 이상인 경우가 그리 많지 않습니다.

백트래킹을 할 때 일일이 롤백하면 한 수마다 20칸 이상을 뒤져야 하기 때문에 배보다 배꼽이 클 것 같고.

대신 분기가 생길 때마다 자료 구조를 통째로 복사하도록 했습니다.

메모리가 낭비될 거 같지만 실제로 돌려 보니 분기하는 경우가 몇 번 안 되네요.

구현은 앞서 어느 분처럼 큐를 사용했습니다.

.

두 번째 고민: 후보 개수가 가장 적은 칸부터 확정한다.

후보 개수가 가장 적은 칸을 골라낼 때 그냥 9x9 칸을 전부 검사해도 81번 밖에 안 됩니다. 하지만 뭔가 마음에 안 들지요...

여기서 뭔가 효율을 추구하려면 오버헤드가 81번 검사하는 거보다 작아야 한다는 제약이 붙는데,

원래의 9x9 배열과 최소값을 뽑기 위한 자료 구조를 동기화시켜야 해서 만만치 않습니다.

힙을 써볼까 하다가(뒤져봤더니 heapq 라는 게 있네요) 엄청 지저분해져서 포기하고, priority array를 사용했습니다.

참고: http://ptgmedia.pearsoncmg.com/images/chap4_9780321968975/elementLinks/04fig05_alt.jpg

'후보 개수'를 배열의 인덱스(priority)로 사용하고 각 배열 원소는 (x, y) 좌표들의 집합입니다.

class PriorityArray:
    def __init__(self, N = 1):
        self.arr = [set() for pri in range(N)]

    def isempty(self):
        return sum(map(len, self.arr)) == 0

    def pop(self):  # 가장 높은 우선순위 집합에서 한 개를 뽑음
        for s in self.arr:
            if s:
                return s.pop()

    def insert(self, x, y, key):
        self.arr[len(key) - 1] |= {(x, y)}

    def update(self, x, y, key, nkey):
        if (x, y) in self.arr[len(key) - 1]:
            self.arr[len(key) - 1] -= {(x, y)}
            self.arr[len(nkey) - 1] |= {(x, y)}

    def clone(self):
        parr = PriorityArray()
        parr.arr = self.arr
        return parr

    def print(self):  # 디버깅용
        for i in range(len(self.arr)):
            if self.arr[i]:
                print(i + 1, self.arr[i])

입출력 코드:

def print_brd(brd):
    if brd:
        for row in brd:
            print(list(map(lambda x: ''.join(sorted(list(x))), row)))


# 입력 data -> 9x9 배열, priority array 준비
def init(data):
    data = data.split('\n')
    N = len(data)
    brd = [list(line) for line in data]
    parr = PriorityArray(N)

    for i in range(N):
        for j in range(N):
            brd[i][j] = set(brd[i][j].replace('0', '123456789'))
            parr.insert(i, j, brd[i][j])

    return N, brd, parr


data = '103450000\n400709123\n789023056\n201064089\n564000231\n890201504\n312645000\n645900012\n000312045'
sudoku(data)

알고리즘:

brd 에는 각 칸의 후보 숫자들을 저장하고, parr 에는 '숫자가 확정되지 않은' 칸들의 좌표를 저장합니다.

sudoku(): parr에서 가장 후보 개수가 적은 칸을 하나 뽑아서,

• 후보가 1개(s)이면 그대로 확정, 가로/세로/3x3 다른 칸들에서 s를 제거합니다(remove_candidates)

• 후보가 2개 이상이면 각 후보 숫자에 대해 분기(branches)한 상태를 que에 집어넣고, que에서 다음 (brd, parr)을 뽑아서 계속합니다.

• 위 과정을 반복하다가 parr이 비었으면 성공하고 종료

def sudoku(data):    
    N, brd, parr = init(data)

    que = [(brd, parr)]
    while que:
        brd, parr = que.pop(0)

        while True:
            if parr.isempty():  # 성공
                print_brd(brd)
                return

            (x, y) = parr.pop()
            #print_brd(brd); print(x, y, brd[x][y]); print(); parr.print(); print(); input()
            if len(brd[x][y]) == 1:
                remove_candidates(brd, parr, N, x, y, brd[x][y])
            else:
                que += branches(brd, parr, x, y)
                break

    print('No answer')


# brd[x][y]의 각 후보 숫자마다 (brd, parr)를 새로 만듬
def branches(brd, parr, x, y):
    lst = []
    for n in brd[x][y]:
        brd2, parr2 = brd[:], parr.clone()
        brd2[x][y] = {n}
        parr2.insert(x, y, {n})
        lst.append((brd2, parr2))
    return lst


#brd[x][y]의 숫자가 s로 정해졌을 때, 다른 칸들의 후보 숫자에서 s를 제거
def remove_candidates(brd, parr, N, x, y, s):    
    p = [(x, j) for j in range(N)]  # 가로줄
    p += [(i, y) for i in range(N)]  # 세로줄

    X, Y = (x // 3) * 3, (y // 3) * 3  # 3x3
    for i in range(3):
        for j in range(3):
            p.append((X + i, Y + j))

    for i, j in set(p) - {(x, y)}:
        parr.update(i, j, brd[i][j], brd[i][j] - s)
        brd[i][j] -= s

• haskell
• 초보적인 추론을 사용합니다:
• 특정 구획(가로, 세로, 3x3 사각형)에서 n 개의 칸이 n 개의 같은 후보 숫자를 가지고 있다면, 같은 구획의 모든 다른 칸에서는 해당 후보 숫자들이 배제됩니다.
• List 모나드를 이용한 백트래킹을 사용합니다.
• 분기 -> 추론 -> 분기 -> ... 방식으로 모든 가능한 해를 구하게 됩니다.

import Control.Monad (guard)
import Control.Monad.Loops (iterateUntilM)
import           Data.Map   (Map, (!))
import qualified Data.Map as Map
import Data.Ix (range)
import Data.List

type UnsolvedSudoku = Map (Int, Int) [Int]
type SolvedSudoku = Map (Int, Int) Int


-- accessory functions

aggregateOn :: (Eq k, Ord k) => (a -> k) -> [a] -> [[a]]
aggregateOn f = Map.elems . Map.fromListWith (++) . fmap ((,) <$> f <*> pure)

chunksOf :: Int -> [a] -> [[a]]
chunksOf _ [] = []
chunksOf n xs = take n xs : chunksOf n (drop n xs)

fromJust (Just x) = x
find' p = fromJust . find p

limit :: (Eq a) => (a -> a) -> a -> a
limit f a = fst $ find' (uncurry (==)) $ zip =<< tail $ iterate f a


-- sudoku-related definitions

sudokuBound = ((0,0), (8,8))

allCompartmnets = concat $ aggregateOn <$> [fst, snd, belongingSq] <*> [range sudokuBound]
    where
        belongingSq (x, y) = (x `div` 3) * 3 + (y `div` 3)

compartments idx = filter (idx `elem`) allCompartmnets

solved = all ((==1).length)
valid  = all ((/=0).length)


-- sudoku-solving algorithms

infer :: UnsolvedSudoku -> UnsolvedSudoku
infer sdk = Map.mapWithKey (\i v -> v \\ elliminated i) sdk
    where
        elliminated :: (Int, Int) -> [Int]
        elliminated idx = do
            comp <- delete idx <$> compartments idx
            family <- group $ sort $ (sdk!) <$> comp
            guard $ (==) <$> length . head <*> length $ family
            head family

guess :: UnsolvedSudoku -> [UnsolvedSudoku]
guess sdk = do
    let Just idx = find ((>1) . length . (sdk!)) $ Map.keys sdk
    val <- sdk ! idx
    return $ Map.insert idx [val] sdk

solutions :: UnsolvedSudoku -> [SolvedSudoku]
solutions = fmap (fmap head) . iterateUntilM solved (filter valid . fmap (limit infer) . guess) . limit infer


-- I/O

parse :: String -> UnsolvedSudoku
parse = Map.fromList . zip (range sudokuBound) . fmap toCell . filter (`elem` ['0'..'9'])
    where toCell '0' = [1..9]; toCell ch = [fromEnum ch - fromEnum '0']

unparse :: SolvedSudoku -> String
unparse sdk = unlines $ chunksOf 9 $ concat $ fmap (show . (sdk!)) $ range sudokuBound

main = parse <$> getContents >>= mapM_ (putStrLn . unparse) . solutions

$ cat input | runhaskell sudoku
123456897
456789123
789123456
231564789
564897231
897231564
312645978
645978312
978312645

123456978
456789123
789123456
231564789
564897231
897231564
312645897
645978312
978312645

library(stringr)
prob <- matrix(NA, nrow = 9, ncol = 9)

prob[1, ] <- strsplit('103450000', split = '')[[1]]
prob[2, ] <- strsplit('400709123', split = '')[[1]]
prob[3, ] <- strsplit('789023056', split = '')[[1]]
prob[4, ] <- strsplit('201064089', split = '')[[1]]
prob[5, ] <- strsplit('564000231', split = '')[[1]]
prob[6, ] <- strsplit('890201504', split = '')[[1]]
prob[7, ] <- strsplit('312645000', split = '')[[1]]
prob[8, ] <- strsplit('645900012', split = '')[[1]]
prob[9, ] <- strsplit('000312045', split = '')[[1]]

duprob <- prob

find_zero <- function(x){
  for (i in 1:9){
    if (sum(str_count(x[i, ], '0')) == 1){
      goal <- setdiff(c(1:9), as.numeric(x[i, ]))
      for (j in 1:9){
        if (x[i, j] == '0'){
          x[i, j] <- as.character(goal)
        }
      }
    }
  }
  for (i in 1:9){
    if (sum(str_count(x[, i], '0')) == 1){
      goal <- setdiff(c(1:9), as.numeric(x[, i]))
      for (j in 1:9){
        if (x[j, i] == '0'){
          x[j, i] <- as.character(goal)
        }
      }
    }
  }
  return(x)
}
find_blank <- function(x){
  for (i in 1:9){
    if (sum(str_count(x, as.character(i))) == 8){

      goal <- i

      for (j in 1:9){
        if (sum(str_count(x[, j], as.character(goal))) == 0){
          goal_col <- j
        }
      }
      for (j in 1:9){
        if (sum(str_count(x[j, ], as.character(goal))) == 0){
          goal_row <- j
        }
      }

      if (x[goal_row, goal_col] == '0'){
        x[goal_row, goal_col] <- as.character(goal)
      } else {
        print(goal)
      }
    }
  }
  return(x)
}
find_cross <- function(x){
  for (goal in 1:9){
    for (i in 1:9){ #search in row

      can_set <- NULL
      del_set <- NULL

      if (sum(str_count(x[i, ], as.character(goal))) == 0){

        goal_row <- i

        for (j in 1:9){
          if (x[i, j] == '0'){
            can_set <- c(can_set, j)
          }
          if (sum(str_count(x[, j], as.character(goal))) == 1){
            del_set <- c(del_set, j)
          }
        }

        goal_col <- setdiff(can_set, del_set)

        if (length(goal_col) == 1 & x[goal_row, goal_col] == '0'){
          x[goal_row, goal_col] <- as.character(goal)
        } 
      }
    }
  }
  for (i in 1:9){ #search in row

    can_set <- NULL
    del_set <- NULL

    if (sum(str_count(x[, i], as.character(goal))) == 0){

      goal_col <- i

      for (j in 1:9){
        if (x[j, i] == '0'){
          can_set <- c(can_set, j)
        }
        if (sum(str_count(x[j, ], as.character(goal))) == 1){
          del_set <- c(del_set, j)
        }
      }

      goal_row <- setdiff(can_set, del_set)

      if (length(goal_row) == 1 & x[goal_row, goal_col] == '0'){
        x[goal_row, goal_col] <- as.character(goal)
      } 
    }
  }
  return(x)
}


while (sum(str_count(duprob, '0')) == 0){
  duprob <- find_zero(duprob)
  duprob <- find_blank(duprob)
  duprob <- find_cross(duprob)
}

answer <- matrix(as.numeric(duprob), nrow = 9, ncol = 9)

서핑 중 본 페이지를 보게되었는데 Creator님의 파이썬 코드가 참 깔끔하네요. 비교해보기위하여 같은 로직으로 C로 작성하였습니다

#include <stdio.h>
#include <set>

using namespace std;

int input[9][9] = {
    { 5, 3, 0, 0, 7, 0, 0, 0, 0 },
    { 6, 0, 0, 1, 9, 5, 0, 0, 0 },
    { 0, 9, 8, 0, 0, 0, 0, 6, 0 },
    { 8, 0, 0, 0, 6, 0, 0, 0, 3 },
    { 4, 0, 0, 8, 0, 3, 0, 0, 1 },
    { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
    { 0, 6, 0, 0, 0, 0, 2, 8, 0 },
    { 0, 0, 0, 4, 1, 9, 0, 0, 5 },
    { 0, 0, 0, 0, 8, 0, 0, 7, 9 }
};

void print_sudoku()
{
    for( int y = 0 ; y < 9 ; y++ )
    {
        for( int x = 0 ; x < 9 ; x++ )  printf( "%d ", input[y][x] );
        printf("\r\n");
    }
    printf("\r\n\r\n");
}

bool solve( int x, int y )
{
    if( y > 8 ) return true;
    if( input[y][x] != 0 )  return ( x < 8 ) ? solve( x + 1, y ) : solve( 0, y + 1 );

    set<int> targetNo;
    set<int> findNo;

    for( int i = 1 ; i <= 9 ; i++ ) targetNo.insert(i);
    for( int i = 0 ; i < 9 ; i++ ) {
        findNo.insert( input[y][i] );
        findNo.insert( input[i][x] );
    }
    for( int iy = 3*(y/3) ; iy < 3*(y/3)+3 ; iy++ )
        for( int ix = 3*(x/3) ; ix < 3*(x/3)+3 ; ix++ )
            findNo.insert( input[iy][ix] );

    for( set<int>::iterator it = findNo.begin() ; it != findNo.end() ; it++ )
        targetNo.erase( *it );

    for( set<int>::iterator it = targetNo.begin() ; it != targetNo.end() ; it++ )
    {
        input[y][x] = *it;
        if( ( ( x < 8 ) ? solve( x + 1, y ) : solve( 0, y + 1 ) ) == true ) return true;
        input[y][x] = 0;
    }
    return false;
}

void main()
{
    print_sudoku();

    if( solve( 0, 0 ) == true )
    {
        print_sudoku();
    }
    else
    {
        printf("Not Found");
    }   
}

import re

inp = ['103450000', '400709123', '789023056', '201064089', '564000231', '890201504', '312645000', '645900012', '000312045']

zero_com = re.compile('[0]')
def in_col(string_list) :
    queue_1 = [string_list]
    for gyo in range(0, 9) : # 1행에서 9행까지 순서대로 탐색

        while '0' in queue_1[0][gyo] : # queue에 들어있는 첫 번째 경우의 수가 모두 채워질 때 까지 해당 행의 숫자를 채워넣음
            p_data = queue_1.pop(0) # 첫 번쨰 데이터를 꺼냄
            exi_nums = set(list(p_data[gyo])) # 행 내의 중복을 확인하기 위한 집합
            exi_nums_in_row = set([p_data[u][p_data[gyo].index('0')] for u in range(0, len(p_data))]) # 열 내의 중복을 확인하기 위한 집합
            raw = p_data[gyo]
            for alt in range(1, 10) : # 1부터 9까지 순서대로 넣을 수 있는지 확인
                if not str(alt) in exi_nums and not str(alt) in exi_nums_in_row : # 행과 열에 중복되지 않는다면 :
                    pp = zero_com.sub(str(alt), raw, count = 1) # alt와 0을 바꿈
                    if gyo == 0 :
                        p_data = [pp] + p_data[1:]
                    elif 0 < gyo < 8 :
                        p_data = p_data[:gyo]+[pp] + p_data[gyo+1:]
                    elif gyo == 8 :
                        p_data = p_data[:8] + [pp]
                    queue_1.append(p_data) # 갱신한 데이터를 queue의 마지막 요소로 추가
    return queue_1

in_col(inp)

1행부터 9행까지 순서대로 탐색하도록 하였고, 숫자를 채워넣을 때는 정규표현식을 활용하였습니다.

결과

[['123456897',
  '456789123',
  '789123456',
  '231564789',
  '564897231',
  '897231564',
  '312645978',
  '645978312',
  '978312645'],
 ['123456978',
  '456789123',
  '789123456',
  '231564789',
  '564897231',
  '897231564',
  '312645897',
  '645978312',
  '978312645']]

가능한 경우의 수를 모두 출력하도록 했습니다.

import numpy as np
inp="""103450000
400709123
789023056
201064089
564000231
890201504
312645000
645900012
000312045"""
grid=[]
for i in inp.split("\n"):
    grid.append(list(i))
print(np.matrix(grid)) #문제 출력
def numpossible(y,x,num):
    global grid
    for i in range(9): #세로 확인
        if grid[y][i]==str(num):
            return False
    for i in range(9): #가로 확인
        if grid[i][x]==str(num):
            return False
    for i in range(3): #3x3매트릭스 확인
        for j in range(3):
            if grid[(y//3)*3+i][(x//3)*3+j]==str(num):
                return False
    return True
def solve():
    global grid
    for y in range(9):
        for x in range(9):
            if grid[y][x]=="0":
                for num in range(1,10):
                    if numpossible(y,x,num):
                        grid[y][x]=str(num)
                        solve()
                        grid[y][x]="0"
                return
    print(np.matrix(grid))
solve()

inp = '''\
    530070000
    600195000
    098000060
    800060003
    400803001
    700020006
    060000280
    000419005
    000080079'''

board = [[*map(int, i)] for i in inp.split()]
zeroRC = [(r,c) for r in range(9) for c in range(9) if board[r][c] == 0]

while len(zeroRC) > 0:
    z = zeroRC.pop(0)
    usedN = [0]
    for i in range(9):
        if board[z[0]][i] not in usedN:
            usedN.append(board[z[0]][i])
        if board[i][z[1]] not in usedN:
            usedN.append(board[i][z[1]])
    for i in range(3):
        for j in range(3):
            if board[i + (z[0]//3)*3][j+(z[1]//3)*3] not in usedN:
                usedN.append(board[i + (z[0]//3)*3][j+(z[1]//3)*3])

    if len(usedN) == 9:
        for i in range(10):
            if i not in usedN:
                board[z[0]][z[1]] = i
    elif len(usedN) < 9:
        zeroRC.append(z)

print(board)