가로 숫자를 기준으로 가능한 모든 경우를 만든 후 세로 숫자와 일치하는지 검사합니다.

사람이 푸는 거 비슷하게 할 수도 있을 거 같은데, 아마 본인도 알아보기 힘든 코드가 나오지 않을까 싶어서. 나중에 해 보겠습니다.

# col_nums = [[3, 1], [1, 2], [5], [1, 2], [3, 1]]  세로 숫자들
# puzzle: nonogram()으로 만들어진 퍼즐
# col_nums로 puzzle의 유효성을 검사한다.
def check_cols(puzzle):
    for j in range(n_col):
        col = ''.join(row[j] for row in puzzle)  # puzze의 j열. 예: ' X X X'
        col = [len(x) for x in col.split()]      #                   => [1, 1, 1]
        if col_nums[j] != col:
            return False

    return True


# row_num으로 만들 수 있는 모든 경우를 리턴한다.
# 예) 입력 => 출력
#   [3]       => ['XXX  ', ' XXX ', '  XXX']
#   [5]       => ['XXXXX']
#   [1, 1, 1] => ['X X X']
def row_case_gen(row_num, prev):
    if not row_num:
        return [(prev+' '*n_col)[:n_col]]  # 모자라거나 남는 공백 처리

    # prev와 row_num[0] 사이에 넣을 수 있는 공백 개수, 뒤에 남은 가로 숫자들까지 고려함.
    n_space = n_col - len(prev) - row_num[0] - (sum(row_num[1:]) + len(row_num[1:]))
    lst = []
    cur = 'X' * row_num[0]
    for i in range(n_space + 1):
        space = ' ' * i
        lst += row_case_gen(row_num[1:], prev + space + cur + ' ')

    return lst


# row_nums = [[5], [1, 1, 1], [5], [3], [1, 1, 1]]  가로 숫자들
# puzzle: 만들어진 퍼즐
# row_nums[0]으로 만들어진 case들로 puzzle에 한 줄씩 추가해서 탐색한다.
def nonogram(row_nums, puzzle):
    if not row_nums:
        if check_cols(puzzle):
            print('\n'.join(puzzle))
        return

    for row in row_case_gen(row_nums[0], ''):
        nonogram(row_nums[1:], puzzle + [row])


n_col, n_row = 5, 5
col_data, row_data = '3 1\n1 2\n5\n1 2\n3 1', '5\n1 1 1\n5\n3\n1 1 1'
parse = lambda x: [[int(x) for x in line.split()] for line in x.splitlines()]
col_nums, row_nums = parse(col_data), parse(row_data)
nonogram(row_nums, [])

같은 알고리즘의 하스켈 버전입니다.

import Control.Monad (foldM)
import Data.List (transpose)

nonograms :: [[Int]] -> [[Int]] -> [[[Char]]]
nonograms rows cols = filter (columnMatches cols) $ mapM possibleSeq rows
    where
        possibleSeq :: [Int] -> [[Char]]
        possibleSeq row = do
            let dots = (`replicate` 'X') <$> row
            spaces <-  (`replicate` ' ') <$> fill (length cols - sum row) ([0] ++ replicate (length row - 1) 1 ++ [0])
            return $ concat $ interleave spaces dots

        columnMatches :: [[Int]] -> [[Char]] -> Bool
        columnMatches cols sol = cols == (fmap length . words <$> transpose sol)


interleave :: [a] -> [a] -> [a]
interleave a b = concat . transpose $ [a,b]

fill :: Int -> [Int] -> [[Int]]
fill n = foldM (\l m -> (:l) <$> [m .. n - sum l]) []

cols = [[3,1],[1,2],[5],[1,2],[3,1]]
rows = [[5],[1,1,1],[5],[3],[1,1,1]]

main = mapM (putStr.unlines) $ nonograms rows cols

import numpy as np
from itertools import permutations

def insert(temp,num):
    for _ in range(num):
        temp.append(1)
    temp.append(0)
    return temp

def possibles(data,Isrow):
    result=[]
    length=size[Isrow]
    num=len(data)
    blank=length-sum(data)-num+1
    #print("len num blank",length,num,blank)
    if blank==0:
        temp=[]
        for i in data:
            temp=insert(temp,i)       
        del(temp[length])
        result.append(temp)

    elif blank>0:
        member=[]
        #0은 빈칸 1~num 은 데이터 인덱스
        member+=list(range(1,num+1))
        for _ in range(blank):
            member.append(0)

        orders=list(permutations(member))

        for order in orders:
            #print('order',order)
            temp=[]
            i_prev=0
            for i in order:
                if (i>i_prev) or (i==0):
                    #여러가지 order 중에 
                    if i>0:
                        temp=insert(temp,data[i-1])
                        i_prev=i
                    elif i==0:
                        temp.append(0)
                    #temp가 length 보다 길면 자르기
                    try:
                        temp=temp[0:length]
                    except:
                        pass
                    #
                    if (len(temp)==length) and (temp not in result):
                        result.append(temp)
                        break
    return result

def printimage(image):
    for i in image:
        temp=''
        for j in i:
            if j:
                temp+='X'
            else:
                temp+='  '
        print(temp)

def erase(_image,i):
    return _image[:-(5-i)]

def makeimage(i,image,imageresult,a):
    if (i>=size[a]):
        imageresult.append(image)
        image=[]
    else:
        for posible in inputdata_possible[a][i]:
            if len(image)<size[a]:
                image.append(posible)         
            makeimage(i+1,image,imageresult,a)
            image=erase(image,i)

size=[5, 5]
inputdata=[[[5],[1, 1, 1],[5],[3],[1, 1, 1]],
           [[3,1],[1,2],[5],[1,2],[3,1]]]

inputdata_possible=[]
for i in range(2):
    temp=[]
    for j in range(len(inputdata[i])):
        temp.append(possibles(inputdata[i][j],i))    
    inputdata_possible.append(temp)

imageresult0=[]
makeimage(0,[],imageresult0,0)
imageresult1=[]
makeimage(0,[],imageresult1,1)

for a in imageresult1:
    a=np.array(a).T.tolist()
    if a in imageresult0:
        printimage(a)

from itertools import permutations
from itertools import product

def cont_num(v):
    cnt,ret = 1,[]
    for i in range(len(v)-1):
        if v[i] == '1':
            if v[i] == v[i+1]:
                cnt += 1
            else:
                ret.append(cnt)
                cnt = 1
    if v[-1] == '1': ret.append(cnt)
    return ret

def makelist(v,l):
    ret = ['0' if i&1 else '' for i in range(2*(l-sum(v))+1)]
    for i in permutations(range(0,2*(l-sum(v))+1,2), len(v)):
        for j,k in enumerate(i): ret[k] = '1'*v[j]
        yield ''.join(ret)
        for j in i: ret[j] = ''

def main():
    for i in product(*(makelist(i,row) for i in clmidx)):
        flag = True

        for j,k in enumerate(zip(*i)):
            if rowidx[j] != cont_num(k):
                flag = False
                break
        if flag:
            for j in zip(*i):
                print(''.join(j).replace('0',' ').replace('1','X'))
            return
    print('조합 없음')
    return


rowidx = '''\
5
1 1
1 1 1
1
3
1
1

1'''

clmidx = '''\
3
1
1 1 3 1
1 1
5'''

rowidx = [[*map(int,i.split())] for i in rowidx.split('\n')]
clmidx = [[*map(int,i.split())] for i in clmidx.split('\n')]
row, clm = len(rowidx), len(clmidx)

main()

import copy
import sys
import re

def display(steps, X, Y):
  for y in range(Y):
    _str = ''
    for x in range(X):
      _str = _str + str(steps[(x,y)])
    print(_str)

def isCorrect(steps, inputs2, X, Y):
  for x in range(X):
    _str = ''
    for y in range(Y):
      _str = _str + str(steps[(x,y)])
    exp = list(map(len, re.split('0+', _str.strip('0'))))
    #exp = list(map(len, _str.strip('0').split('0')))
    if exp != inputs2[x]: return False
  return True

def isSafe(steps, inputs2, X, Y):
  for x in range(X):
    _str = ''
    for y in range(Y):
      _str = _str + str(steps[(x,y)])
    exp = list(map(len, re.split('0+', _str.strip('0'))))
    for i in range(len(exp)):
      try:
        if exp[i] > inputs2[x][i]:
          return False
        if exp[i] != inputs2[x][i] and i < len(exp)-1:
          return False
      except IndexError:
        return False
  return True


def search(steps, inputs, inputs2, x, y, X, Y):
  if not isSafe(steps, inputs2, X, Y):
    return
  if not inputs:
    if isCorrect(steps, inputs2, X, Y):
      print('\n정답:')
      display(steps, X, Y)
      raise NotImplementedError
      return
    else: return

  if inputs[0][0] == 0:
    Q = copy.deepcopy(inputs)
    Q.pop(0)
    search(steps, Q, inputs2, 0, y+1, X, Y)

  for i in range(x, X):
    temp = copy.deepcopy(steps)
    if i+inputs[0][0]-1 >= X: break
    for j in range(inputs[0][0]):
      temp[(i+j, y)]=1
    if i+inputs[0][0]<X: temp[i+inputs[0][0]]=0
    Q = copy.deepcopy(inputs)
    Q[0].pop(0)
    if not Q[0]:
      Q.pop(0)
      search(temp, Q, inputs2, 0, y+1, X, Y)
    else: search(temp, Q, inputs2, i+inputs[0][0]+1, y, X, Y)


X = int(input('가로길이를 입력하세요 :'))
Y = int(input('세로길이를 입력하세요 :'))


print('가로방향의 노노그램을 입력하세요:')
inputs = []
for x in range(X):
  s = input()
  inputs.append(list(map(int, s.strip().split(' '))))

print('세로방향의 노노그램을 입력하세요:')
inputs2 = []
for y in range(Y):
  s = input()
  inputs2.append(list(map(int, s.strip().split(' '))))

steps = {(x,y) : 0 for x in range(X) for y in range(Y)}

import time
t = time.time()
try:
  print('탐색을 시작합니다.')
  search(steps, inputs, inputs2, 0, 0, X,Y)
  print('정답을 찾지 못했습니다.')
except NotImplementedError:
  pass
print(round(time.time() - t,2), '초 걸렸습니다.')

public class NoNogram {
    private static final int SIZE = 5;
    private static boolean[][] HORIZONTAL_MAP = new boolean[SIZE][SIZE];
    private static boolean[][] VERTICAL_MAP = new boolean[SIZE][SIZE];
    private static int INPUT = 0;

    public static void main(String[] args) {
        int count = 0, startIDX = 0;

        System.out.println("< 가로 >");
        for (int i = 0; i < SIZE; i++) {
            count = 0;
            while(count != SIZE) {
                System.out.print("[" + (i+1) + " 열] " + (SIZE - count) + " 이하의 숫자를 입력해주세요.");
                INPUT = KunheeUtil.scanIntData(INPUT);

                startIDX = count;

                for (int j = startIDX; j < (startIDX + INPUT); j++) {
                    HORIZONTAL_MAP[j][i] = true;
                    count++;
                }
                if(count < 5) {
                    HORIZONTAL_MAP[count][i] = false;
                    count++;
                }
            }
        }

        System.out.println("\n< 세로 >");
        for (int i = 0; i < SIZE; i++) {
            count = 0;
            while(count != SIZE) {
                System.out.print("[" + (i+1) + " 행] " + (SIZE - count) + " 이하의 숫자를 입력해주세요.");
                INPUT = KunheeUtil.scanIntData(INPUT);
                startIDX = count;

                for (int j = startIDX; j < (startIDX + INPUT); j++) {
                    VERTICAL_MAP[i][j] = true;
                    count++;
                }
                if(count < 5) {
                    VERTICAL_MAP[i][count] = false;
                    count++;
                }
            }

        }
        System.out.println("\n< 합체 >");
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                System.out.print((HORIZONTAL_MAP[i][j] && VERTICAL_MAP[i][j]) ? "[X]" : "[ ]");
            }
            System.out.println();
        }
    }
}

사람이 푸는 것처럼 구성하여 더 어려운 노노그램도 풀 수 있도록 작성하였습니다.

class nonogram:
  def __init__(self, x, y):
    self.xsize = list(x).count('\n')+1
    self.board = [[' ']*self.xsize for _ in range(self.xsize)]
    self.xclue = self.clueseeker(a)
    self.yclue = self.clueseeker(b)
    self.finish = True

  def lookup(self):
      log = []
    while self.finish:
      self.xdeduction()
      self.ydeduction()
      if log = self.board:
        print('There is no solution!')
        break
      log = self.board[:][:]
    print('finished!')  
    for line in self.board:
      print(''.join(line).replace('X', ' '))

  def clueseeker(self, x):
    return [[int(n) for n in i.split(' ')] for i in x.split('\n')]

  def xdeduction(self):
    finishtest=[]
    for i in range(self.xsize):
      candidates = self.choose(self.xclue[i], self.board[i])
      finishtest.append(len(candidates)==1)
      for j in range(self.xsize):
        if all([candidate[j]=='#' for candidate in candidates]):
          self.board[i][j]='#'
        if all([candidate[j]==' ' for candidate in candidates]):
          self.board[i][j]='X'
    if all(finishtest):
      self.finish = False

  def ydeduction(self):
    finishtest=[]
    for i in range(self.xsize):
      candidates = self.choose(self.yclue[i], [self.board[j][i] for j in range(self.xsize)])
      finishtest.append(len(candidates)==1)
      for j in range(self.xsize):
        if all([candidate[j]=='#' for candidate in candidates]):
          self.board[j][i]='#'
        if all([candidate[j]==' ' for candidate in candidates]):
          self.board[j][i]='X'
    if all(finishtest):
      self.finish = False      

  def choose(self, x, y):   #line, oldline
    void = [0]+[1]*(len(x)-1)+[0]
    rest = self.xsize-(sum(x)+len(x)-1)
    voidplus, front, deletelist = [], [], []
    self.divide(len(x)+1, rest, [], voidplus)
    for voidline in voidplus:
      frontline = []
      for i in range(0, len(x)+1):
        voidline[i]+=void[i]
        frontline += voidline[i]*[' ']
        if i<=len(x)-1: frontline += x[i]*['#']
      front.append(frontline)
    for i in range(self.xsize):
      if y[i]=='#':
        for candidate in front:
          if candidate[i]==' ':
            deletelist.append(candidate)
      if y[i]=='X':
        for candidate in front:
          if candidate[i]=='#':
            deletelist.append(candidate)
    for delete in deletelist:
      try:
        front.remove(delete)
      except:
        pass
    return front

  def divide(self, x, y, numlist, numlistlist): #boxnum, 구슬
    if x == 1:
      numlist+=[y]
      numlistlist.append(numlist)
      numlist=[]
    if x>1:
      for i in range(0, y+1):
        self.divide(x-1, y-i, numlist+[i], numlistlist)





a = '''7
1 4
4
4
2 3
3 2
5
2 1 2
1 1 1 2
3 2'''
b='''2
2
1 1
2 2
1 3 2
1 2 1
4 3
5
6 3
6 3'''
x = nonogram(b, a)
x.lookup()