Results 1 to 6 of 6
  1. #1
    ariz is offline Member
    Join Date
    Feb 2009
    Posts
    6
    Rep Power
    0

    Default [SOLVED] why am i getting this exception" java.util.NoSuchElementException

    Hi I am a grad student. I am making a program to solve the Sudoku puzzle using depth first search with backtracking. The unsolved sudoku puzzle will be given as input to the program in the following manner:

    9 3 3
    _ _ _ _ 1 _ _ _ _
    7 _ _ _ _ _ 8 _ _
    _ _ 3 _ 6 _ 4 _ _
    3 1 _ _ 4 9 _ 6 _
    _ _ 8 _ 2 _ 7 _ _
    _ 5 _ 7 3 _ _ 1 8
    _ _ 9 _ 8 _ 3 _ _
    _ _ 4 _ _ _ _ _ 2
    _ _ _ _ 5 _ _ _ _
    the first number in the first line tells the dimension of the sudoku puzzle for example here its a 9x9 puzzle and 2nd and 3rd number tells the region dimension which is 3x3 here.
    I dont know why i keep getting this error
    Exception in thread "main" java.util.NoSuchElementException
    at java.util.LinkedList.remove(LinkedList.java:644)
    at java.util.LinkedList.removeLast(LinkedList.java:14 4)
    at sudoku2.Sudoku2.dfsBactracking(Sudoku2.java:180)
    at sudoku2.Sudoku2.main(Sudoku2.java:254)

    can anyone please help me solve this prob I have to submit the assignment on comming sunday. any knid of help will be really appriciated.


    package sudoku2;
    import java.util.*;
    import java.io.*;
    import java.io.FileNotFoundException;
    import java.io.IOException;



    class Space{
    Space parent = null;
    int[][] successorBoard=null;
    Boolean [] domain=null;
    int rowupper, rowLower, colUpper, colLower=0;
    String spaceloc=null;
    int spacerow, spacecol, spacePos=0;
    }
    public class Sudoku2 {
    public int boardDimension, regionLength, regionBreath, totalSpaces, partialSol , spaceNo= 0;
    public int[][] board ;
    public LinkedList <Space> spaceQueue = new LinkedList<Space>();
    public LinkedList <String> location=new LinkedList<String>();
    public String regex=" ";


    void readFile() throws IOException
    { String [] inputLine = null;
    try {
    FileReader fr = new FileReader("D:\\sudoku.txt");
    BufferedReader br = new BufferedReader(fr);
    inputLine = br.readLine().trim().split(regex);
    boardDimension = Integer.parseInt(inputLine[0]);
    regionLength = Integer.parseInt(inputLine[1]);
    regionBreath = Integer.parseInt(inputLine[2]);
    board = new int[boardDimension+1][boardDimension+1];
    inputLine = null;//reinitialize inputLine to get the rest of file
    int j = 1;
    Boolean flag = true;
    String s=null;


    while ( (s = br.readLine()) != null ){
    inputLine=s.trim().split(regex);
    for(int i=1 ; i<=inputLine.length ; i++){
    if(inputLine[i-1].equalsIgnoreCase("_")){
    location.add(String.valueOf(j)+" "+String.valueOf(i));
    totalSpaces++;
    flag = false;
    }
    if(flag == false){
    board[j][i]=0;
    flag = true;
    }
    else {
    board[j][i]=Integer.parseInt(inputLine[i-1]);

    }
    }
    j++;
    }
    for(int i=1 ; i< board.length ; i++){
    for(int k=1 ; k< board.length ; k++){
    System.out.print(board[i][k]+" ");
    }
    System.out.println();
    }
    }
    catch (FileNotFoundException e){
    e.printStackTrace();
    }
    catch (IOException e){
    e.printStackTrace();
    }
    }

    void findBounds(Space temp, int length, int breath){

    int iterLength = boardDimension/regionLength;
    int iterBreath = boardDimension/regionBreath;
    int temporary = regionLength;
    for(int j =0; j<= iterLength ; j++){
    if(length<=temporary){
    temp.rowLower = temporary - regionLength + 1;
    temp.rowupper = temporary;
    }
    else
    temporary = temporary + regionLength;
    }
    temporary = regionBreath;
    for(int j=0 ; j<=iterBreath ; j++){
    if(breath <= temporary ){
    temp.colLower = temporary - regionBreath + 1;
    temp.colUpper = temporary;
    }
    else
    temporary = temporary + regionBreath;
    }
    }

    void makeDomain(Space s, int length, int breath, int[][] parentBoard){
    LinkedList<Integer> antidomain = new LinkedList<Integer>();
    s.domain=new Boolean[boardDimension+1];
    for(int p=1; p< s.domain.length; p++){
    s.domain[p]=true;
    }
    for(int i = s.rowLower; i<= s.rowupper; i++){
    for(int j=s.colLower; j<= s.colUpper; j++){
    antidomain.add(parentBoard[i][j]);
    }
    }
    for(int k = 1; k<=boardDimension; k++ ){
    antidomain.add(parentBoard[k][breath]);
    antidomain.add(parentBoard[length][k]);
    }
    for(int m =1; m<s.domain.length; m++){
    if(antidomain.contains(m) == true){
    s.domain[m]=false;
    }
    }
    }
    void makeNode(Space parent, int valueAssigned, int length, int breath, int spaceLoc){
    Space child= new Space();
    child.parent=parent;
    child.successorBoard=new int[boardDimension+1][boardDimension+1];
    for(int i=1 ; i< parent.successorBoard.length ; i++){
    for(int k=1 ; k< parent.successorBoard.length ; k++){
    if(i==length && k==breath){
    child.successorBoard[i][k]=valueAssigned;
    }
    else
    child.successorBoard[i][k]=parent.successorBoard[i][k];
    }
    }
    findBounds(child, length, breath);
    makeDomain(child, length, breath, parent.successorBoard);
    int newSpace = spaceLoc+1;
    child.spaceloc=location.get(newSpace);
    String[] locs= child.spaceloc.split(regex);
    child.spacePos=newSpace;
    child.spacerow=Integer.parseInt(locs[0]);
    child.spacecol=Integer.parseInt(locs[1]);
    spaceQueue.add(child);


    }
    void dfsBactracking(){
    Space initial =new Space();
    int domainIter = 0;
    String sloc;
    initial.spacePos=spaceNo;
    initial.spaceloc=location.get(spaceNo);
    String[] locs= initial.spaceloc.split(regex);
    initial.spacerow=Integer.parseInt(locs[0]);
    initial.spacecol=Integer.parseInt(locs[1]);
    findBounds(initial,initial.spacerow,initial.spacec ol);
    initial.successorBoard = new int[boardDimension+1][boardDimension+1];
    for(int i=1 ; i< board.length ; i++){
    for(int k=1 ; k< board.length ; k++){
    initial.successorBoard[i][k]=board[i][k];
    }
    }
    makeDomain(initial,initial.spacerow,initial.spacec ol, initial.successorBoard);
    spaceNo=spaceNo+1;
    spaceQueue.add(initial);
    while(spaceNo != totalSpaces){
    Boolean flag=false;
    sloc=location.get(spaceNo);
    String[] loc=sloc.split(regex);
    Space extracted=new Space();
    extracted=spaceQueue.removeLast();
    domainIter=boardDimension;
    while(domainIter>0){
    if(extracted.domain[domainIter]==true){
    makeNode(extracted,domainIter, Integer.parseInt(loc[0]),Integer.parseInt(loc[1]),spaceNo);

    flag=true;
    partialSol++;
    }
    if(flag==false && domainIter==1){
    Space temp2 =new Space();
    temp2=spaceQueue.removeLast();
    spaceNo= temp2.spacePos+1;
    sloc= location.get(spaceNo);
    loc=sloc.split(regex);
    domainIter=boardDimension+1;
    }
    domainIter--;
    }
    spaceNo++;
    }
    if(spaceNo==totalSpaces){
    Space temp3=spaceQueue.removeLast();
    String []loc= temp3.spaceloc.split(regex);
    temp3.successorBoard = new int[boardDimension+1][boardDimension+1];
    for(int i = 1; i<temp3.domain.length; i++){
    if(temp3.domain[i]!= false){
    temp3.successorBoard[Integer.parseInt(loc[0])][Integer.parseInt(loc[1])] = i;
    }
    }
    for(int i = 1; i < boardDimension+1; i++){
    for(int j = 1; j < boardDimension+1; j++){
    System.out.print(" "+temp3.successorBoard[i][j]);
    }
    System.out.println();
    }
    System.out.println("The number of partial solutions explored: "+partialSol);
    }
    }

    public static void main(String[] args) throws IOException {
    Sudoku2 s = new Sudoku2();
    s.readFile();
    s.dfsBactracking();

    }

    }

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    25

    Default

    You're trying to access an element in the linked list when there are no more elements left. It is empty, though a quick look through the LinkedList API would tell you this.
    Last edited by Fubarable; 02-25-2009 at 06:17 AM.

  3. #3
    ariz is offline Member
    Join Date
    Feb 2009
    Posts
    6
    Rep Power
    0

    Default

    thx for the help, but can u tell me why the linked list is running out of objects when i am constantly adding new objects in the make node functions.

  4. #4
    toadaly is offline Senior Member
    Join Date
    Jan 2009
    Posts
    671
    Rep Power
    6

    Default

    I don't want to discourage you, but you have made it very difficult for us to help you.

    I think this is the line causing teh problem...

    Java Code:
    initial.spaceloc=location.get(spaceNo);
    ...unfortunately, spaceNo is global and used all over the place, so who knows what the hell it's value is. It can increase or decrease depending on a difficult to determine chain of events...

    Java Code:
    spaceNo=spaceNo+1;
    ...
    spaceNo= temp2.spacePos+1;
    ...
    spaceNo++;
    ...I don't even know what spaceNo conceptually represents!

  5. #5
    mtyoung is offline Senior Member
    Join Date
    Dec 2008
    Location
    Hong Kong
    Posts
    473
    Rep Power
    6

    Default

    maybe in loop of
    while (spaceNo != totalSpaces) {} ...
    value of spaceNo changed
    and the spaceQueue remove element several times,

    then java found spaceNo == totalSpaces
    and remove element again in if (spaceNo == totalSpaces) {}

  6. #6
    ariz is offline Member
    Join Date
    Feb 2009
    Posts
    6
    Rep Power
    0

    Default

    thanks for all the help..the problem is finally solved.Actually in the method "dfs backtracking" i was making new objects of space class every where. Instead i should have made just single object and used it in all the loops and ifs.
    Space extracted=new Space();
    extracted=spaceQueue.removeLast();
    domainIter=boardDimension;
    while(domainIter>0){
    if(extracted.domain[domainIter]==true){
    makeNode(extracted,domainIter, Integer.parseInt(loc[0]),Integer.parseInt(loc[1]),spaceNo); /* I am giving object extracted to the function makenode*/
    flag=true;
    partialSol++;
    }
    if(flag==false && domainIter==1){
    Space temp2 =new Space();
    temp2=spaceQueue.removeLast(); /*here temp2 has the new node and this should be sent to makenode.but I am sending extraxted to makenode function which just has the first node not any new ones.*/
    spaceNo= temp2.spacePos+1;
    sloc= location.get(spaceNo);
    loc=sloc.split(regex);
    domainIter=boardDimension+1;
    }
    domainIter--;

Similar Threads

  1. Replies: 12
    Last Post: 12-05-2008, 05:37 AM
  2. Exception in thread "main" java.util.NoSuchElementException
    By vileoxidation in forum New To Java
    Replies: 5
    Last Post: 09-17-2008, 07:29 AM
  3. setting JSTL locale "java.util.MissingResourceException"
    By sabelosimelane in forum JavaServer Pages (JSP) and JSTL
    Replies: 0
    Last Post: 09-04-2008, 04:12 PM
  4. Replies: 4
    Last Post: 06-08-2008, 02:19 PM
  5. Replies: 5
    Last Post: 05-14-2008, 01:43 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •