nonogramsolver.java

package com.hafthor;

public class Main {
    public static void main(final String[] args) {
        Nonogram n = new Nonogram("1 3 9 122 42 42 122 9 3 1", "33 22 8 121 121 6 22 11 6 4"); // 9
        while(n.solve()) n.print();
        n.print();
    }

    public static class Nonogram {
        final int[][] h, v;
        final int maxHLen, maxVLen;
        final Boolean[][] grid;

        public Nonogram(final String hs, final String vs) {
            this(hs.split(" "), vs.split(" "));
        }

        public Nonogram(final String[] hh, final String[] vv) {
            grid = new Boolean[vv.length][hh.length];
            h = parseCounts(hh);
            v = parseCounts(vv);
            maxHLen = maxLen(h);
            maxVLen = maxLen(v);
        }

        private int[][] parseCounts(final String[] hh) {
            final int[][] h = new int[hh.length][];
            for (int hi = 0; hi < hh.length; hi++) {
                final char[] ca = hh[hi].toCharArray();
                h[hi] = new int[ca.length];
                for (int si = 0; si < ca.length; si++) {
                    h[hi][si] = Integer.parseInt("" + ca[si], 16);
                }
            }
            return h;
        }

        public int maxLen(final int[][] c) {
            int ml = 0;
            for (final int[] cc : c) {
                if (cc.length > ml) ml = cc.length;
            }
            return ml;
        }

        public Boolean solve() {
            int unknowns = countUnknowns();
            if(unknowns==0) return false;
            for (int i = 0; i < h.length; i++)
                writeGridCol(i, solve(h[i], readGridCol(i)));
            for (int i = 0; i < v.length; i++)
                writeGridRow(i, solve(v[i], readGridRow(i)));
            if (unknowns==countUnknowns()) return null;
            return true;
        }

        public Boolean[] readGridCol(final int c) {
            final Boolean[] b = new Boolean[v.length];
            for (int i = 0; i < v.length; i++) b[i] = grid[i][c];
            return b;
        }

        public Boolean[] readGridRow(final int r) {
            final Boolean[] b = new Boolean[h.length];
            for (int i = 0; i < h.length; i++) b[i] = grid[r][i];
            return b;
        }

        public void writeGridCol(final int c, final Boolean[] b) {
            for (int i = 0; i < v.length; i++) grid[i][c] = b[i];
        }

        public void writeGridRow(final int r, final Boolean[] b) {
            for (int i = 0; i < h.length; i++) grid[r][i] = b[i];
        }

        public int countUnknowns() {
            int unknowns = 0;
            for (final Boolean[] b : grid) unknowns += countUnknowns(b);
            return unknowns;
        }

        public int countUnknowns(final Boolean[] b) {
            int unknowns = 0;
            for (final Boolean bb : b) if (bb == null) unknowns++;
            return unknowns;
        }

        public Boolean[] solve(final int[] c, Boolean[] b) {
            final int[] extraSpaces = new int[c.length];
            final Boolean[] save = b.clone();
            Boolean[] setTo = null;
            for (; ; ) {
                b = save.clone();
                final int bi = assignCells(c, b, extraSpaces);
                if (bi > 0) {
                    if (setTo == null)
                        setTo = b.clone();
                    else
                        for (int i = 0; i < b.length; i++) if (setTo[i] != b[i]) setTo[i] = null;
                }
                int slop = b.length - (c.length - 1);
                for (int i = 0; i < c.length; i++) slop -= extraSpaces[i] + c[i];
                if (slop > 0) {
                    extraSpaces[c.length - 1]++;
                } else {
                    int xi = c.length - 1;
                    while (xi >= 0 && extraSpaces[xi] == 0) xi--;
                    if (xi >= 0) extraSpaces[xi--] = 0;
                    if (xi < 0) break;
                    extraSpaces[xi]++;
                }
            }
            return setTo;
        }

        private int assignCells(final int[] c, final Boolean[] b, final int[] extraSpaces) {
            int bi = 0;
            for (int ci = 0; ci < c.length; ci++) {
                if (bi > 0) if (b[bi] == Boolean.TRUE) return -1; else b[bi++] = false;
                for (int i = 0; i < extraSpaces[ci]; i++) if (b[bi] == Boolean.TRUE) return -1; else b[bi++] = false;
                for (int i = 0; i < c[ci]; i++) if (b[bi] == Boolean.FALSE) return -1; else b[bi++] = true;
            }
            while (bi < b.length) if (b[bi] == Boolean.TRUE) return -1; else b[bi++] = false;
            return bi;
        }

        public void print() {
            System.out.println();
            for (int hr = 0; hr < maxHLen; hr++) {
                System.out.printf("%" + maxVLen * 2 + "s", "");
                for (int hc = 0; hc < h.length; hc++) {
                    final int k = hr + h[hc].length - maxHLen;
                    System.out.print(k < 0 ? "  " : h[hc][k] + " ");
                }
                System.out.println();
            }
            for (int r = 0; r < v.length; r++) {
                for (int hc = 0; hc < maxVLen; hc++) {
                    final int k = hc + v[r].length - maxVLen;
                    System.out.print(k < 0 ? "  " : v[r][k] + " ");
                }
                for (int c = 0; c < h.length; c++) {
                    System.out.print(grid[r][c] == null ? '?' : grid[r][c] ? '@' : '.');
                    System.out.print(' ');
                }
                System.out.println();
            }
        }
    }
}