dominosolver

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.stream.Collectors;

public class Test
{
    public static void main(String[] args)
    {
        Chips chips = new Chips(chips());
        Board board = new Board(cells());

        process(board, chips, new History());
    }

    private static void process(Board board, Chips chips, History history)
    {
        if (!chips.isEmpty())
        {
            List<Hole> holes = board.holes();

            if (!holes.isEmpty())
            {
                for (Hole hole : holes)
                {
                    for (Chip chip : chips)
                    {
                        FitOrientation fitOrientation = board.fits(chip, hole);

                        if (fitOrientation != null)
                        {
                            Board newBoard = board.set(chip, hole, fitOrientation);
                            Chips newChips = chips.remove(chip);

                            process(newBoard, newChips, history.add(chip));
                        }
                    }
                }
            }
            else
            {
                System.out.print("ERROR");
            }
        }
        else
        {
            board.print();
            history.print();
            System.exit(0);
        }
    }

    private static Cells cells()
    {
        Cell cell00 = new Cell(0, 0);
        Cell cell01 = new Cell(0, 1);
        Cell cell02 = new Cell(0, 2);
        Cell cell03 = new Cell(0, 3);
        Cell cell04 = new Cell(0, 4);
        Cell cell05 = new Cell(0, 5);
        Cell cell06 = new Cell(0, 6);
        Cell cell10 = new Cell(1, 0);
        Cell cell16 = new Cell(1, 6);
        Cell cell17 = new Cell(1, 7);
        Cell cell20 = new Cell(2, 0);
        Cell cell21 = new Cell(2, 1);
        Cell cell22 = new Cell(2, 2);
        Cell cell23 = new Cell(2, 3);
        Cell cell24 = new Cell(2, 4);
        Cell cell25 = new Cell(2, 5);
        Cell cell26 = new Cell(2, 6);
        Cell cell30 = new Cell(3, 0);
        Cell cell34 = new Cell(3, 4);
        Cell cell36 = new Cell(3, 6);
        Cell cell40 = new Cell(4, 0);
        Cell cell44 = new Cell(4, 4);
        Cell cell46 = new Cell(4, 6);
        Cell cell50 = new Cell(5, 0);
        Cell cell51 = new Cell(5, 1);
        Cell cell52 = new Cell(5, 2);
        Cell cell53 = new Cell(5, 3);
        Cell cell54 = new Cell(5, 4);
        Cell cell55 = new Cell(5, 5);
        Cell cell56 = new Cell(5, 6);
        Cell fakeCell = new Cell(1, 8, 6);

        /*cell00.down(cell10);
        cell00.down(cell01);
        cell01.left(cell00);
        cell01.right(cell02);
        cell02.left(cell01);
        cell02.right(cell03);
        cell03.left(cell02);
        cell03.right(cell04);
        cell04.left(cell03);
        cell04.right(cell05);
        cell05.left(cell04);
        cell05.right(cell06);
        cell06.left(cell05);
        cell06.down(cell16);

        cell10.up(cell00);
        cell10.down(cell20);
        cell16.up(cell06);
        cell16.down(cell26);
        cell16.right(cell17);
        cell17.left(cell16);
        cell17.right(fakeCell);
        fakeCell.left(cell17);

        cell20.up(cell10);
        cell20.down(cell30);
        cell20.right(cell21);
        cell21.left(cell20);
        cell21.right(cell22);
        cell22.left(cell21);
        cell22.right(cell23);
        cell23.left(cell22);
        cell23.right(cell24);
        cell24.left(cell23);
        cell24.right(cell25);
        cell25.left(cell24);
        cell25.right(cell26);
        cell26.left(cell25);
        cell26.up(cell16);
        cell26.down(cell36);

        cell30.up(cell20);
        cell30.down(cell40);
        cell34.up(cell24);
        cell34.down(cell44);
        cell36.up(cell26);
        cell36.down(cell46);

        cell40.up(cell30);
        cell40.down(cell50);
        cell44.up(cell34);
        cell44.down(cell54);
        cell46.up(cell36);
        cell46.down(cell56);

        cell50.up(cell40);
        cell50.right(cell51);
        cell51.left(cell50);
        cell51.right(cell52);
        cell52.left(cell51);
        cell52.right(cell53);
        cell53.left(cell52);
        cell53.right(cell54);
        cell54.left(cell53);
        cell54.right(cell55);
        cell54.up(cell44);
        cell55.left(cell54);
        cell55.right(cell56);
        cell56.left(cell55);
        cell56.up(cell46);*/

        List<Cell> cells = new ArrayList<>();
        cells.add(cell00);
        cells.add(cell01);
        cells.add(cell02);
        cells.add(cell03);
        cells.add(cell04);
        cells.add(cell05);
        cells.add(cell06);
        cells.add(cell10);
        cells.add(cell16);
        cells.add(cell17);
        cells.add(cell20);
        cells.add(cell21);
        cells.add(cell22);
        cells.add(cell23);
        cells.add(cell24);
        cells.add(cell25);
        cells.add(cell26);
        cells.add(cell30);
        cells.add(cell34);
        cells.add(cell36);
        cells.add(cell40);
        cells.add(cell44);
        cells.add(cell46);
        cells.add(cell50);
        cells.add(cell51);
        cells.add(cell52);
        cells.add(cell53);
        cells.add(cell54);
        cells.add(cell55);
        cells.add(cell56);
        cells.add(fakeCell);

        return new Cells(cells);
    }

    private static List<Chip> chips()
    {
        List<Chip> chips = new ArrayList<>();

        chips.add(new Chip(2, 6, ChipType.HORIZONTAL));
        chips.add(new Chip(4, 2, ChipType.HORIZONTAL));
        chips.add(new Chip(4, 1, ChipType.HORIZONTAL));
        chips.add(new Chip(3, 2, ChipType.HORIZONTAL));
        chips.add(new Chip(6, 4, ChipType.HORIZONTAL));
        chips.add(new Chip(1, 5, ChipType.HORIZONTAL));
        chips.add(new Chip(1, 6, ChipType.HORIZONTAL));
        chips.add(new Chip(4, 4, ChipType.HORIZONTAL));
        chips.add(new Chip(3, 5, ChipType.HORIZONTAL));
        chips.add(new Chip(5, 3, ChipType.HORIZONTAL));

        chips.add(new Chip(3, 1, ChipType.VERTICAL));
        chips.add(new Chip(1, 4, ChipType.VERTICAL));
        chips.add(new Chip(4, 1, ChipType.VERTICAL));
        chips.add(new Chip(2, 4, ChipType.VERTICAL));
        chips.add(new Chip(4, 5, ChipType.VERTICAL));

        return chips;
    }

    private enum ChipType
    {
        HORIZONTAL,
        VERTICAL
    }

    private enum FitOrientation
    {
        UP,
        DOWN,
        LEFT,
        RIGHT
    }

    private static class Hole
    {
        private final Cell cell;
        private final int value;

        private Hole(Cell cell, int value)
        {
            this.cell = cell;
            this.value = value;
        }

        @Override
        public String toString()
        {
            return String.format("%s - Value=%d", cell.toString(), value);
        }
    }

    private static class Board
    {
        private final Cells cells;

        private Board(Cells cells)
        {
            this.cells = cells;
        }

        public List<Hole> holes()
        {
            List<Hole> holes = new ArrayList<>();

            for (Cell cell : cells)
            {
                holes.addAll(cell.holes(cells));
            }

            return holes;
        }

        public FitOrientation fits(Chip chip, Hole hole)
        {
            if (chip.type == ChipType.VERTICAL)
            {
                Cell up = hole.cell.up(cells);
                Cell down = hole.cell.down(cells);

                if (chip.valueB == hole.value)
                {
                    if (fits(up, chip.valueA))
                    {
                        return FitOrientation.UP;
                    }
                    else
                    {
                        System.out.print("");
                    }
                }
                else if (chip.valueA == hole.value)
                {
                    if (fits(down, chip.valueB))
                    {
                        return FitOrientation.DOWN;
                    }
                    else
                    {
                        System.out.print("");
                    }
                }
            }
            else if (chip.type == ChipType.HORIZONTAL)
            {
                Cell left = hole.cell.left(cells);
                Cell right = hole.cell.right(cells);

                if (chip.valueB == hole.value)
                {
                    if (fits(left, chip.valueA))
                    {
                        return FitOrientation.LEFT;
                    }
                    else
                    {
                        System.out.print("");
                    }
                }
                else if (chip.valueA == hole.value)
                {
                    if (fits(right, chip.valueB))
                    {
                        return FitOrientation.RIGHT;
                    }
                    else
                    {
                        System.out.print("");
                    }
                }
            }

            return null;
        }

        private boolean fits(Cell cell, int value)
        {
            if ((cell != null) && (cell.value == 0))
            {
                Cell up = cell.up(cells);
                Cell down = cell.down(cells);
                Cell left = cell.left(cells);
                Cell right = cell.right(cells);

                boolean upValid = (up == null) || (up.value == value) || (up.isEmpty());
                boolean downValid = (down == null) || (down.value == value) || (down.isEmpty());
                boolean leftValid = (left == null) || (left.value == value) || (left.isEmpty());
                boolean rightValid = (right == null) || (right.value == value) || (right.isEmpty());

                return upValid && downValid && leftValid && rightValid;
            }
            else
            {
                return false;
            }
        }

        public Board set(Chip chip, Hole hole, FitOrientation fitOrientation)
        {
            if (chip.type == ChipType.VERTICAL)
            {
                if (fitOrientation == FitOrientation.UP)
                {
                    Cell up = hole.cell.up(cells);
                    Board newBoard = set(up.i, up.j, chip.valueA);

                    return newBoard.set(hole.cell.i, hole.cell.j, chip.valueB);
                }
                else if (fitOrientation == FitOrientation.DOWN)
                {
                    Cell down = hole.cell.down(cells);
                    Board newBoard = set(down.i, down.j, chip.valueB);

                    return newBoard.set(hole.cell.i, hole.cell.j, chip.valueA);
                }
            }
            else if (chip.type == ChipType.HORIZONTAL)
            {
                if (fitOrientation == FitOrientation.LEFT)
                {
                    Cell left = hole.cell.left(cells);
                    Board newBoard = set(left.i, left.j, chip.valueA);

                    return newBoard.set(hole.cell.i, hole.cell.j, chip.valueB);
                }
                else if (fitOrientation == FitOrientation.RIGHT)
                {
                    Cell right = hole.cell.right(cells);
                    Board newBoard = set(right.i, right.j, chip.valueB);

                    return newBoard.set(hole.cell.i, hole.cell.j, chip.valueA);
                }
            }

            throw new RuntimeException();
        }

        public Board set(int i, int j, int value)
        {
            return new Board(cells.set(i, j, value));
        }

        //        public Cell get(int i, int j)
        //        {
        //            return cells.cell(i, j);
        //        }

        public void print()
        {
            StringBuilder builder = new StringBuilder();

            for (int i = 0; i < 6; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    Cell cell = cells.cell(i, j);

                    if (cell != null)
                    {
                        builder.append(cell.value).append(" ");
                    }
                    else
                    {
                        builder.append("x").append(" ");
                    }
                }

                builder.append("\n");
            }

            builder.append("\n");

            System.out.print(builder.toString());
        }
    }

    private static class Cells implements Iterable<Cell>
    {
        private final List<Cell> cells;

        private Cells(List<Cell> cells)
        {
            this.cells = cells;
        }

        public Cells set(int i, int j, int value)
        {
            List<Cell> newCells = new ArrayList<>();

            for (Cell cell : cells)
            {
                if ((cell.i == i) && (cell.j == j))
                {
                    newCells.add(cell.value(value));
                }
                else
                {
                    newCells.add(cell);
                }
            }

            return new Cells(newCells);
        }

        public Cell cell(int i, int j)
        {
            for (Cell cell : cells)
            {
                if ((cell.i == i) && (cell.j == j))
                {
                    return cell;
                }
            }

            return null;
        }

        @Override
        public Iterator<Cell> iterator()
        {
            return cells.iterator();
        }
    }

    private static class Cell
    {
        private final int i;
        private final int j;
        private final int value;

        private Cell(int i, int j, int value)
        {
            this.i = i;
            this.j = j;
            this.value = value;
        }

        private Cell(int i, int j)
        {
            this(i, j, 0);
        }

        public boolean isEmpty()
        {
            return (value == 0);
        }

        public Cell value(int value)
        {
            return new Cell(i, j, value);
        }

        public List<Hole> holes(Cells cells)
        {
            List<Hole> holes = new ArrayList<>();

            if (!isEmpty())
            {
                Cell up = up(cells);
                if ((up != null) && (up.isEmpty()))
                {
                    holes.add(new Hole(up, value));
                }

                Cell down = down(cells);
                if ((down != null) && (down.isEmpty()))
                {
                    holes.add(new Hole(down, value));
                }

                Cell left = left(cells);
                if ((left != null) && (left.isEmpty()))
                {
                    holes.add(new Hole(left, value));
                }

                Cell right = right(cells);
                if ((right != null) && (right.isEmpty()))
                {
                    holes.add(new Hole(right, value));
                }
            }

            return holes;
        }

        public Cell up(Cells cells)
        {
            return cells.cell(i - 1, j);
        }

        public Cell down(Cells cells)
        {
            return cells.cell(i + 1, j);
        }

        public Cell left(Cells cells)
        {
            return cells.cell(i, j - 1);
        }

        public Cell right(Cells cells)
        {
            return cells.cell(i, j + 1);
        }

        @Override
        public String toString()
        {
            return String.format("Cell(%d,%d,%d)", i, j, value);
        }
    }

    private static class Chips implements Iterable<Chip>
    {
        private final List<Chip> chips;

        private Chips(List<Chip> chips)
        {
            this.chips = chips;
        }

        public boolean isEmpty()
        {
            return chips.isEmpty();
        }

        public Chips remove(Chip chip)
        {
            List<Chip> newChips = chips.stream().filter(c -> !c.equals(chip)).collect(Collectors.toList());

            return new Chips(newChips);
        }

        @Override
        public Iterator<Chip> iterator()
        {
            return chips.iterator();
        }
    }

    private static class Chip
    {
        // from left to right and up to bottom

        private final int valueA;
        private final int valueB;
        private final ChipType type;

        private Chip(int valueA, int valueB, ChipType type)
        {
            this.valueA = valueA;
            this.valueB = valueB;
            this.type = type;
        }

        @Override
        public boolean equals(Object o)
        {
            if (this == o)
            {
                return true;
            }
            else if (o == null || getClass() != o.getClass())
            {
                return false;
            }

            Chip chip = (Chip) o;

            return (valueA == chip.valueA) && (valueB == chip.valueB) && (type == chip.type);

        }

        @Override
        public int hashCode()
        {
            int result = valueA;
            result = 31 * result + valueB;
            result = 31 * result + type.hashCode();
            return result;
        }

        @Override
        public String toString()
        {
            return String.format("%s(%d,%d)", type.toString(), valueA, valueB);
        }
    }

    private static class History
    {
        private final List<Chip> chips;

        private History(List<Chip> chips)
        {
            this.chips = chips;
        }

        private History()
        {
            this.chips = new ArrayList<>();
        }

        public History add(Chip newChip)
        {
            List<Chip> newChips = new ArrayList<>();
            newChips.addAll(chips);
            newChips.add(newChip);

            return new History(newChips);
        }

        public void print()
        {
            for (Chip chip : chips)
            {
                System.out.println(chip.toString());
            }
        }
    }
}