class rikudo:
    def __init__(self,data):
        self.board = [ [ int(i[j:j+2]) if i[j:j+2].isdigit() else i[j:j+2] for j,k in enumerate(i) if not j&1 ] for i in data.split('\n') ]
        self.row, self.clm = len(self.board), len(self.board[0])
        self.nums = { self.board[i][j]:(i,j) for i in range(self.row)
                                             for j in range(self.clm) if self.board[i][j] not in (0,'--') }

    def answer(self):
        flag = False
        stc,stc2,cun = [self.nums[1]],[0],1

        nib = ( (0,2),(1,1),(1,-1),(0,-2),(-1,-1),(-1,1) )

        while cun < 36:
            if cun+1 in self.nums:
                if (self.nums[cun+1][0]-stc[-1][0], self.nums[cun+1][1]-stc[-1][1]) in nib:
                    stc.append(self.nums[cun+1])
                    stc2.append(0)
                    cun += 1
                    continue
                else: stc.pop(); stc2.pop(); cun -= 1; continue

            while 1:
                if stc2[-1] == 6: flag = True; break
                dx,dy = nib[stc2[-1]]
                stc2[-1] += 1
                if 0<=stc[-1][0]+dx<self.row and 0<=stc[-1][1]+dy<self.clm and self.board[stc[-1][0]+dx][stc[-1][1]+dy] == 0 and (stc[-1][0]+dx,stc[-1][1]+dy) not in stc: break

            if flag: flag=False; stc.pop(); stc2.pop(); cun -= 1; continue

            stc.append((stc[-1][0]+dx,stc[-1][1]+dy))
            stc2.append(0)
            cun += 1
        return stc

    def print_ans(self):
        for i,j in enumerate(self.answer()): self.board[j[0]][j[1]] = i+1
        for i in range(self.row):
            for j in range(self.clm):
                print('{:0>2}'.format(self.board[i][j]),end='')
            print()


sample = '''\
------24--00--00--00------
----00--00--26--36--00----
--00--21--00--00--28--32--
18--00--15------00--00--00
--00--00--00--08--01--00--
----00--10--00--00--03----
------12--00--00--05------'''

x = rikudo(sample)
x.print_ans()

------24--25--35--34------
----20--23--26--36--33----
--19--21--22--27--28--32--
18--16--15------29--30--31
--17--14--09--08--01--02--
----13--10--07--04--03----
------12--11--06--05------

Python

1) 주어진 예에서 처음에 보드에 적혀 있는 수들을 정렬하면 [1, 3, 5, 8, 10, 12, 15, 18, 21, 24, 26, 28, 32, 36] 인데,

여기서 가장 차이가 작은 수 두 개를 찾습니다: closest_nums()

그래서 제일 먼저 찾는 게 [1, 3], 즉 1과 3이 가장 가까우니 먼저 연결해 보겠다는 뜻. (이 과정에서, 이미 앞뒤로 연결된 수는 볼 필요가 없으므로 제외합니다).

2) 가장 가까운 두 수 [1, 3]을 찾았으니 이제 1~~>3 경로들을 찾습니다: find_paths() => [경로1, 경로2, ...]

1~~>3은 2개의 경로가 존재하는데, 찾은 경로들을 각각 그려본 후(draw()) 백트래킹을 사용하면서(erase()) 1)과 2)를 반복합니다.

1~~>3 다음에는

[1, 2, 3, 5, 8, 10, 12, 15, 18, 21, 24, 26, 28, 32, 36]

이렇게 되니까 3~~>5, 8~~>10, 10~~>12, 24~~>26, 26~~>28 순서로 찾게 됩니다.

class Rikudo:
    brd, inv_brd, size = {}, {}, 0

    def __init__(self, data):
        # arr <- 2차원 배열(data)
        arr = [[int(s) for s in row.split('-') if s.isdigit()] for row in data.split('\n')]
        arr[len(arr) // 2].insert(len(arr) // 2, -1)  # 가운데 안 쓰는 한 칸
        self.size = len(arr)

        # self.brd <- {(i, j):숫자, ... }
        for i in range(len(arr)):
            for j in range(len(arr[i])):
                if arr[i][j] >= 0:
                    self.brd[(i, j)] = arr[i][j]

        # inv_brd <- {숫자:(i, j), ... }, brd 와 inv_brd는 동기화되어야 함
        self.inv_brd = {v : k for k, v in self.brd.items() if v > 0}

    def closest_nums(self):
        nums = sorted(self.inv_brd.keys())  # 현재 보드에 적힌 숫자들을 정렬
        return min(
                    [[ x[0], x[1], x[1] - x[0] ] for x in zip(nums[:-1], nums[1:]) if x[1] - x[0] > 1],
                    key = lambda x:x[2]
                )[:2]   # 연속하지 않으면서 간격이 최소인 [nums[i], nums[i+1]을 리턴

    # 좌표 cbase와 인접하면서 유효한 좌표들을 리턴
    def adjacent(self, cbase, dest):
        def writable(c): return c == dest or c in self.brd.keys() and self.brd[c] == 0
        x, y = cbase
        if x < self.size // 2:    result = {(x, y-1), (x, y+1), (x-1, y-1), (x-1, y), (x+1, y), (x+1, y+1)}
        elif x > self.size // 2:  result = {(x, y-1), (x, y+1), (x-1, y), (x-1, y+1), (x+1, y-1), (x+1, y)}
        else:                      result = {(x, y-1), (x, y+1), (x-1, y-1), (x-1, y), (x+1, y-1), (x+1, y)}

        return {c for c in result if writable(c)}

    # path[-1]에서 dest에 이르는 길이 plen인 경로를 찾는다.(recursion)
    def find_paths(self, path, plen, dest):
        if plen == 0:
            return [path] if (path[-1] == dest) else []
        else:
            result = []
            for c in self.adjacent(path[-1], dest) - set(path):  # 지나온 경로 제외
                result += self.find_paths(path + [c], plen - 1, dest)

            return result

    def draw(self, path):
        n = self.brd[path[0]]
        for c in path[1:-1]:
            n += 1
            self.brd[c] = n
            self.inv_brd[n] = c

    def erase(self, path):
        n = self.brd[path[0]]
        for c in path[1:-1]:
            n += 1
            self.brd[c] = 0
            del self.inv_brd[n]

    def print_n_exit(self):
        arr = [['--' for y in range(self.size)] for x in range(self.size)]
        for x, y in self.brd.keys():
            arr[x][y] = "%02d--" % self.brd[(x, y)]

        output = ''
        for x in range(self.size):
            if x == self.size // 2:
                tmp = ''.join(arr[x])[:-2]
                output += tmp[:self.size * 2] + '--' + tmp[self.size * 2:]  + '\n'
            else:
                output += '--' * arr[x].count('--') + ''.join(arr[x][:-1]) + '\n'
        print(output)
        exit()

    def solve(self):
        if 0 not in self.brd.values():
            self.print_n_exit()
        else:
            n1, n2 = self.closest_nums()
            paths = self.find_paths([self.inv_brd[n1]], n2 - n1, self.inv_brd[n2])
            for path in paths:
                self.draw(path)
                self.solve()
                self.erase(path)

data = "------24--00--00--00------\n----00--00--26--36--00----\n--00--21--00--00--28--32--\n18--00--15------00--00--00\n--00--00--00--08--01--00--\n----00--10--00--00--03----\n------12--00--00--05------"
game = Rikudo(data)
game.solve()

import string
import re
import random
inputdata='''------24--00--00--00------
----00--00--26--36--00----
--00--21--00--00--28--32--
18--00--15------00--00--00
--00--00--00--08--01--00--
----00--10--00--00--03----
------12--00--00--05------'''

MAX=36
OUTnumbers=list(range(1,MAX+1))
INnumbers=[]
row=re.split('\n',inputdata)
datalen=len(row)

data=[]
lenlist=[]
for i in range(datalen):
    temp=[int(x) for x in re.split('[\-]+',row[i]) if x] #split rowdata
    data.append(temp)
    lenlist.append(len(data[i])) #datalength vector

##insert 'c' at enter
mid=int(datalen/2)
data[mid].insert(mid,0)
lenlist[mid]=lenlist[mid]+1

##make Axial coordinates
##https://www.redblobgames.com/grids/hexagons/
xy_to_axial={}
axial_to_xy={}
numbers_dic={}
for i in range(datalen):
    for j in range(lenlist[i]):
        xy_to_axial[(i,j)]=(-min(i,3)+j,i-mid)
        axial_to_xy[(-min(i,3)+j,i-mid)]=(i,j)
        if data[i][j]!=0:
            OUTnumbers.remove(data[i][j])
            INnumbers.append(data[i][j])
            numbers_dic[data[i][j]]=(i,j)
INnumbers.sort()

def nearindex(index,dest):
    # input : axial_coord output :  axial_coord
    # 빈칸이나 dest의 인덱스를 반환합니다.
    _near_indice=[]
    (q,r)=index
    for offset_q,offset_r in [(0,1),(1,0),(1,-1),(0,-1),(-1,0),(-1,1)]:
        index_new=(q+offset_q,r+offset_r)
        if (index_new in axial_to_xy) and (index_new!=(0,0)):
            _i,_j=axial_to_xy[index_new]
            if ((data[_i][_j]==0) or (index_new==dest)):
                _near_indice.append((q+offset_q,r+offset_r))
    return _near_indice


def location(num):
    #return xy cord
    index=()
    for i in range(datalen):
        if num in data[i]:
            index=(i,data[i].index(num))
    try:
        return xy_to_axial[index]
    except:
        return ()

def find_routes(route,plen,dest):
    if plen == 0:
        return [route] if (route[-1] == dest) else []
    else:
        result = []
        for c in set(nearindex(route[-1],dest)):
            result += find_routes(route + [c], plen - 1, dest)
        return result


def draw(route):
    (i,j)=axial_to_xy[route[0]]
    n=data[i][j]
    for c in route[1:-1]:
        n += 1
        (i,j)=axial_to_xy[c]
        if (not data[i][j]) and (location(n)==()):
            data[i][j] = n
def erase(route):
    (_i,_j)=axial_to_xy[route[0]]
    for c in route[1:-1]:
        (_i,_j)=axial_to_xy[c]
        if (data[_i][_j]) and (data[_i][_j] not in INnumbers):
            data[_i][_j] = 0
def check():
    data[mid][mid]='c'
    result=True
    for i in range(datalen):
        if 0 in data[i]:
            result=False
    return result

def printdata():
    result=''
    for i in data:
        result+='-'*(14-2*len(i))
        for j in i:
            temp = str(j)
            if len(temp)==1:
                temp='0'+temp
            if (i.index(j)==0):
                result=result+temp
            else:
                result=result+'-'*2+temp
        result+='-'*(14-2*len(i))
        result+='\n'
    print(result)

def solve(i):
        if (check()):
            print("hooray!",data)
            printdata()
            exit()
        else:
            if (i<13):
                n1=INnumbers[i]
                n2=INnumbers[i+1]
            else:
                n1=INnumbers[12]
                n2=INnumbers[13]

            routes = find_routes([location(n1)], n2 - n1, location(n2))
            for route in routes:
                erase(route)
                draw(route)
                solve(i+1)
                erase(route)

solve(0)

hooray! [[24, 25, 35, 34], [20, 23, 26, 36, 33], [19, 21, 22, 27, 28, 32], [18, 16, 15, 'c', 29, 30, 31], [17, 14, 9, 8, 1, 2], [13, 10, 7, 4, 3], [12, 11, 6, 5]] ------24--25--35--34------ ----20--23--26--36--33---- --19--21--22--27--28--32-- 18--16--15--0c--29--30--31 --17--14--09--08--01--02-- ----13--10--07--04--03---- ------12--11--06--05------

트랙백으로 풀었습니다. 01에서 여섯 방향으로 가능한 곳에 02를 넣어보고.. 36까지 계속 반복..

class rikudo:
    def __init__(self, s):
        self.solved = False
        self.board = [[i[j:j + 2] for j, k in enumerate(i) if j % 2 == 0] for i in s.split('\n')]
        self.rows = len(self.board)
        self.cols = len(self.board[0])

    def solve(self):
        # 01 번에서 시작
        for i in range(self.rows):
            for j in range(self.cols):
                if '01' == self.board[i][j]:
                    self.next(i, j, '01')
                    break

    def next(self, y, x, n):
        if n == '36':
            self.solved = True
            return

        # 1, 3, 5, 7, 9, 11시 방향
        direction = ((1, 1), (0, 2), (-1, 1), (-1, -1), (0, -2), (1, -1))
        for d in direction:
            # 다음좌표
            ny = y + d[0]
            nx = x + d[1]

            # 가능 범위
            if ny >= 0 and ny < self.rows and nx >= 0 and nx < self.cols:
                # 다음수
                next_n = self.next_num(n)

                # 00 이거나 다음수이면,
                if self.board[ny][nx] == '00' or self.board[ny][nx] == next_n:
                    self.board[ny][nx] = next_n
                    org_n = self.board[ny][nx]
                    # 계속해서 다음로...
                    self.next(ny, nx, next_n)

                    if self.solved:
                        return

                    # 롤백
                    self.board[ny][nx] = org_n

    # 다음 수 : 09 -> 10
    def next_num(self, n):
        if n[0] == '0':
            n = n[1]
        n = str(int(n) + 1)
        return n.zfill(2)

    def __str__(self):
        s = ''
        for i in self.board:
            s += ''.join(i) + '\n'
        return s


s = '''
------24--00--00--00------
----00--00--26--36--00----
--00--21--00--00--28--32--
18--00--15------00--00--00
--00--00--00--08--01--00--
----00--10--00--00--03----
------12--00--00--05------
'''
r = rikudo(s=s.strip())
print(r)
r.solve()
print(r)

import copy

direc = ((2,0), (-2,0), (1,1), (1,-1), (-1,1), (-1,-1))

# steps = []
def search(numbers, step, n = 0):
    def display(ns):        
        for y in range(7):
            _str = ''
            for x in range(13):
                if ns[(x,y)] == -1: _str = _str + '--'
                elif 0 <= ns[(x,y)] < 10: _str = _str + '0' + str(ns[(x,y)])
                elif ns[(x,y)] >= 10: _str = _str + str(ns[(x,y)])
            print(_str)
        print('')

    if n == 36:
        display(numbers)
        raise NotImplementedError
        #for i, step in enumerate(steps):


    def find_start(numbers):  # 시작점 찾기
        for key, value in numbers.items():
            if value == 1:
                return key
        print('start point not found')
        raise NotImplementedError

    if n == 0:  # 처음이라면 시작점에서 스타트
        search(numbers, find_start(numbers), 1)
        return

    _x, _y = step
    for dx, dy in direc: # 주변에 다음번호가 있다면 바로 건너가기
        x = _x + dx
        y = _y + dy
        if 0 <= x <= 12 and 0 <= y <= 6: # 범위를 벗어나지 않을떄
            if numbers[(x,y)] == n+1:
                temp = copy.deepcopy(numbers)
                temp[(x,y)] = n+1
                search(temp, (x,y), n+1)
                return

    for dx, dy in direc: # 0인 부분으로 건너가서 탐색(가지치기)
        x = _x + dx
        y = _y + dy
        if 0 <= x <= 12 and 0 <= y <= 6: # 범위를 벗어나지 않을떄
            if numbers[(x,y)] == 0:
                temp = copy.deepcopy(numbers)
                temp[(x,y)] = n+1
                search(temp, (x,y), n+1)

    # if no way
    return

print('문제를 입력하세요')
inputs = []
for i in range(7):
    inputs.append(input())

numbers = {}
for k, s in enumerate(inputs):
    for i in range(0, len(s), 2):
        if s[i:i+2]!='--': numbers[(i//2, k)] = int(s[i:i+2])
        else: numbers[(i//2, k)] = -1

try:
    print('')
    search(numbers, (0,0), 0)
    print('정답을 찾지 못했습니다.')
except NotImplementedError:
    print('탐색을 종료합니다.')

문제를 입력하세요
------24--00--00--35------
----00--00--00--00--00----
--00--21--00--00--28--32--
00--00--15------00--00--00
--17--00--00--08--01--00--
----00--10--00--00--00----
------12--00--00--05------

------24--25--36--35------
----20--23--26--34--33----
--19--21--22--27--28--32--
18--16--15------29--30--31
--17--14--09--08--01--02--
----13--10--07--04--03----
------12--11--06--05------

탐색을 종료합니다.

inp="""------24--00--00--00------
----00--00--26--36--00----
--00--21--00--00--28--32--
18--00--15------00--00--00
--00--00--00--08--01--00--
----00--10--00--00--03----
------12--00--00--05------"""
numlst=["0"+str(num) if len(str(num))==1 else str(num) for num in range(1,37)]
lst=[]
for ln in inp.split("\n"):
    elst=[""]*13
    for n in range(13):
        elst[n]=ln[n*2]+ln[n*2+1]
    lst.append(elst)
for ln in lst:
    for cmp in ln:
        print("%1s"%cmp, end="")
    print()

def findone(): #맨처음 "01"을 찾을 때 쓴 함수
    for y in range(len(lst)):
        for x in range(len(lst[0])):
            if lst[y][x]=="01":
                return x,y
x,y=findone()

n=1
maxX,maxY=len(lst[0]),len(lst)
def solve(y,x):
    global n
    if n==36:
        for ln in lst:
            for cmp in ln:
                print("%1s"%cmp, end="")
            print()
    else:
        for dx, dy in [(-1,-1),(1,-1),(2,0),(1,1),(-1,1),(-2,0)]:
            nx,ny=x+dx,y+dy
            if 0<=nx<maxX and 0<=ny<maxY and lst[ny][nx]!="--":
                if lst[ny][nx]=="00" or int(lst[ny][nx])==int(lst[y][x])+1:
                    on=lst[ny][nx]
                    lst[ny][nx]=numlst[n]
                    n+=1
                    solve(ny,nx)
                    lst[ny][nx]=on
                    n-=1
solve(4,9)

결과

------24--25--35--34------
----20--23--26--36--33----
--19--21--22--27--28--32--
18--16--15------29--30--31
--17--14--09--08--01--02--
----13--10--07--04--03----
------12--11--06--05------