Arc Consistency in Java, questions on implementation

1.9k views Asked by At

So my goal is to write the method that solves a sudoku puzzle, we were given the method stub "public int[][] solve(int[][] board)". We are supposed to use arc consistency and domain splitting to find the solution.

-The way I started doing it was by making a hashMap of points on the board(keys) and their current domains(initialized to 1..9 unless given) -> HashMap<Point, ArrayList<Integer>> curDomains = new HashMap<Point, ArrayList<Integer>>(); though I'm not sure if this is the best data structure to use.

-My question is how do I represent the arcs and the constraints? I have pseudo code for the algorithm but I don't know how to represent the constraints/arcs in java. What is the best way to represent C:set of constraints to be satisfied (which are the valid placements on a sudoku board) as well as my arcs A < X, c> where X is a Point and c is the constraints.

I thank you in advance for your helpful comments.

1

There are 1 answers

5
TeaCupApp On BEST ANSWER

This would be the best to read for data structure related understanding while working with Arc consistency. Hope this will help you!

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.99.8824&rep=rep1&type=pdf&ei=XdqgTqmgDIblrAex-Z3fAg&usg=AFQjCNEKp1FtiYbaea6dvF6u7ppVOk-fFg&sig2=duzyH2nU89MYUskD8Blffw

Above link will give you redirect notice just go to that university website and download PDF.

Good Luck!