Implement sudoku puzzle 9x9 by Graph

Question

I have a sudoku puzzle 9x9 in a text file and I wondering how can we create a Graph from sudoku puzzle.Sudoku puzzle is a int[][] Example puzzle

0 0 0 0 9 8 0 4 5 
0 0 4 3 2 0 7 0 0 
7 9 0 5 0 0 0 3 0 
0 0 0 9 0 0 4 0 0 
0 4 5 0 0 2 8 0 0 
8 7 9 6 0 4 0 1 0 
0 3 0 0 7 9 0 6 4 
4 5 0 2 1 3 9 0 8 
0 8 7 4 6 5 0 0 0

and class Graph

    class Graph
    {
        private int V; 
        private LinkedList<Integer> adj[]; 
        Graph(int v)
        {
            V = v;

            adj = new LinkedList[v];
            for (int i=0; i<v; ++i)
                adj[i] = new LinkedList();
        }

        void addEdge(int v,int w)
        {
            adj[v].add(w);
            adj[w].add(v); 
        }
        public int getV()
        {
            return V;
        }
 public LinkedList<Integer> getListAdj(int u)
    {
        return adj[u];
    }

I write a function to read puzzle from a text file and implement it to graph

public boolean readGraph(String input_name, int result[])
    {

          return true;
    }

But I stuck in this step.

Welcome to Stack Overflow! Please [take the tour](http://stackoverflow.com/tour) to see how the site works and what questions are on topic here, and edit your question accordingly. See also: [Why is "Can someone help me?" not an actual question?](http://meta.stackoverflow.com/q/284236) — Joe C, Apr 22 '17 at 19:06
How is a Sudoku matrix a graph? What benefit do the links between numbers provide? An `int[][]` makes more sense — OneCricketeer, Apr 22 '17 at 19:09
You are not stuck with writing code. You are actually stuck on a higher level - as you need rules defining the rules and the meaning of such a graph. In other words: you don't solve such problems by writing code. You first clarify requirements and algorithms before turning on your computer. And you aren't showing any evidence that you spend that time so far. So how should we be able to tell you how to write your code when you can't even communicate what that code is *really*to about!? — GhostCat, Apr 22 '17 at 19:13
@cricket_007 Probably trying to take advantage of figuring out how each node in the puzzle is linked to other nodes. Rather than linking each node to simply adjacent node, they might be linking them to each node that is linked logically in sudoku (ie: linked to each node in its horizontal and vertical alignment). Kind of a neat idea and a fun way to explore Graphs. — Glen Pierce, Apr 22 '17 at 19:16
@GlenPierce Perhaps, but that explanation should be in the question for us to assist in helping with that — OneCricketeer, Apr 22 '17 at 19:18

score -1 · Answer 1 · edited May 23 '17 at 12:09

-1

Here goes:

First, I already know that the puzzle is 9x9, so the newlines in the text file are meaningless to me. I can ignore them. Also, I know that each element of the puzzle is only ever going to be a single character long so (after getting the text file into memory like so: Reading a plain text file in Java):

I get my String puzzle which is that text file into memory. Now I want to iterate over that String like so:

Graph graph = new Graph(81); //9x9 graph with 81 verticies
int whichVertextAreWeOn = 0;

for (int i = 0; i < puzzle.length(); i++){
    char c = puzzle.charAt(i);
    if(c>'0' && c > '9'){
       int integer = Integer.parseInt(c);
       //now I need to add this to my Graph... Saving my work now, comments are appreciated
       //Turns out you simply add edges to each vertex in a graph, the vertex itself has no value...
       //so I'm going to keep track of which vertex I'm on, this is starting to seem like a bad data structure for this purpose, but I shall carry on. -Adding an iterator to keep track of which vertex I'm on.
       for(int w = 0; w < graph.V(); w++;){
         if(vertextIsLinked(whichVertextAreWeOn, w))
           graph.addEdge(whichVertextAreWeOn, w);
       }
       //hum... from here I need to add an edge to this vertex for each connected vertex...
     }
}

private boolean vertextIsLinked(int vertexWeAreOn, int possibleVertext){
  //use rules of Sukdoku to figure out if these two verticies should be linked. This would return true for any vertex in horizontal or vertical alignment to the vertexWeAreOn.
}

edited May 23 '17 at 12:09

Community

1
1

answered Apr 22 '17 at 19:24

Glen Pierce

4,401
5
31
50

Tks and I want to ask How can we know edges in puzzel 9x9 on Graph ? Thank you for answer my question again. – YoungAlistar Apr 22 '17 at 19:27
At this point, I think that the Graph idea is neat, but probably bad unfortunately. Here's why: the Graph is not really designed for keeping track of the values on each of its nodes which is important to Sudoku. Just getting the puzzle into this data structure is already proving pretty hard and once it's there, I'm not sure I'll be able to use it in an efficient fashion. I think the int[][] is a better storage solution. I'd go with that. – Glen Pierce Apr 22 '17 at 19:37
How do you know a vertex is the connected vertex ? – YoungAlistar Apr 22 '17 at 19:37
Sudoku rules: each vertex is connected to all the vertexes in horizontal and vertical alignment to it. – Glen Pierce Apr 22 '17 at 19:41
graph.addEdge(whichVertextAreWeOn, int w); What it int w ?i have never seen type int in function call like this. – YoungAlistar Apr 22 '17 at 19:57
@YoungAlistar, I was still editing the post when that appeared. You would never put that in a method. The problem you face is figuring out which vertices are linked, which isn't particularly hard, but would be a very likely place to make an error. It's certainly possible, but I leave it to you to come up with a good algorithm to figure this out if you want to continue on this path. – Glen Pierce Apr 22 '17 at 20:30

Implement sudoku puzzle 9x9 by Graph

1 Answers1