1

数独ソルバーを使用していますが、ソルバー関数を正しく返す/終了するのに問題があります。関数のshow()inmoveOn()が呼び出され、完了した数独が正常に表示されますが、solveはfalseを返します。問題が解決された場合はsolveがtrueを返し、解決できない場合はnullを返すようにしていますが、これを実現する方法がわかりません。

Lボードの長さです（9x9数独はL=9になります）

getSquare(r,c)数独ボードを表す2次元配列の値を返します

さまざまなチェック関数が、値が特定の場所に収まるかどうかをチェックします。それらは問題ではありません。

このshow()関数は、適切な数独ボードのように見えるように、コンソールに配列を出力します。

2D配列をチェックする関数もありisSolved()、それが有効な解決済みの数独がtrueを返す場合、otherweiseはfalseを返します。私はこれをメソッドに実装しようとしましたが、これsolve()を使用してtrueを返すことを望んでいますが、成功していません。

//This method's only purpose it to call the findNum function on the next location in the sudoku
public void moveOn(int row, int column) {
    //if the previous location was not the last in the row move to ne next cell in said row.
    //if it was the last location in the row, move to the first column of the next row
    if (column + 1 != L) {solve(row, column + 1);}
    else if (row + 1 != L) {solve(row + 1, 0);}
    else {show();}
}

//This method finds a valid number for a specific location on the sudoku grid\
public boolean solve(int row, int column) {
    if (row >= L) {return true;}
    //pass over any numbers that are not empty
    if (getSquare(row, column) != 0) {moveOn(row, column);}
    else {
        //attempt to find a valid number for the location
        for (int n = 1; n <= L; n++) {
            if (checkRow(row, n) && checkCol(column, n) && checkSquare(row, column, n)) {
                // If a number is allowed at a specific location set that location to the number
                setSquare(row, column, n);
                //Begin checking for a solution based on previous numbers changed           
                moveOn(row, column);
            }               
        }
        //If no number is allowed in this space backtrack to the last successful number 
        //changed and reset all locations that have been changed recursively
        setSquare(row, column, 0);          
    }
    //If the puzzle is unsolveable
    return false;
}

状況に光を当てるのを手伝ってくれる人に感謝します。より多くのコード/情報が必要な場合は、喜んで提供します

サンプル入力ファイル： http： //pastebin.com/6mSKT3ES

編集：完全なコードが削除されました

4

2 に答える 2

2

関数にはreturnステートメントが1つだけあり、それはsolve

return false;

これは関数の最後のステートメントであり、無条件に実行されるためsolve、例外がスローされない限り、常に。を返しfalseます。

解決策が見つかったかどうかを実際に示す戻り値を取得するには、戻り値を条件に依存させる必要があります。また、適切なパズルの解決策を見つけたら、検索を続けても意味がありません。

したがってreturn true;、検索ループに条件を追加する必要があります。そのためには、いつ解決策を見つけたかを知る必要があります。への中間呼び出しで再帰をラップするmoveOnので、最も簡単な変更は、に戻り値を追加することですmoveOn。

public boolean moveOn(int row, int column) {
    //if the previous location was not the last in the row move to ne next cell in said row.
    //if it was the last location in the row, move to the first column of the next row
    if (column + 1 != L) {return solve(row, column + 1);}
    else if (row + 1 != L) {return solve(row + 1, 0);}
    else {show(); return true;}  // reached end of grid, solved
}

そしてそれを`solve'で使用します：

public boolean solve(int row, int column) {
    //pass over any numbers that are not empty
    if (getSquare(row, column) != 0) {return moveOn(row, column);}
    else {
        //attempt to find a valid number for the location
        for (int n = 1; n <= L; n++) {
            if (checkRow(row, n) && checkCol(column, n) && checkSquare(row, column, n)) {
                // If a number is allowed at a specific location set that location to the number
                setSquare(row, column, n);
                //Begin checking for a solution based on previous numbers changed           
                if (moveOn(row, column)) {
                    return true;       // solved, yay!
                }
            }               
        }
        //If no number is allowed in this space backtrack to the last successful number 
        //changed and reset all locations that have been changed recursively
        setSquare(row, column, 0);          
    }
    //If the puzzle is unsolveable
    return false;
}
于 2012-10-18T23:14:18.473 に答える
-1 
This code works...

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;


public class Sudoku {

    public static int suRows=9;
    public static int suColumns=9;
    public static int [][] suArray = new int[suRows][suColumns];
    public static int [] dummyRowArray = new int[suRows];
    public static int [] dummyColArray = new int[suColumns];
    public static int [][] dummy3x3Array = new int[3][3];
    public static int [] dummyArray = new int[9];

    //read the contents of the file into a 2 dimensional array
    public static void readSudoku() throws FileNotFoundException, IOException
    {  
        System.out.print("Please enter the full file name containing the Sudoku Puzzle (e.g:X:/sudoku_case1.txt):");
        Scanner scan = new Scanner (System.in);
        String filename = scan.nextLine();
        File file = new File( filename );

       if ( file.exists() )  
       {   
           Scanner inFile = new Scanner( file );
           for(int i=0; i<suRows; i++)
           {
                for(int j=0; j<suColumns; j++)
                {
                    if(inFile.hasNextInt())   suArray[i][j] = inFile.nextInt();
                }
            }   
       inFile.close();
       }    
    }

    public static boolean inOrder(int [] a, int i, int j)
    {
        return a[i]<=a[j];
    }

    public static void swap(int [] a, int i, int j)
    {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }


    public static void exchangeSort(int [] a)
    {
        for(int i=0;i<a.length;i++)
        {
            for(int j=1;j<a.length-i;j++)
            {
                if(!inOrder(a,j-1,j))    swap(a,j-1,j);
            }
        }
    }

    public static void displaySudoku(int [][] suArray)
    {
        for(int i=0; i<suArray.length;i++)
        {
            for(int j=0; j<suArray[i].length;j++)
            {
                System.out.print(suArray[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }    
    }    

    //Check if there are any more zeros
    public static boolean isComplete(int [][]suArray)
    {
        boolean result=true;

        //Check every element for 0
        for(int i=0; i<suArray[0].length; i++)
        {
            for(int j=0 ; j<suRows ; j++)
            {
                if(suArray[i][j]==0) return false;
            }
        }
        System.out.println("There are no zeros in this Sudoku");
        return result;
    }    


    //Check for adjacent duplicates
    public static boolean isAdjacentDup(int [] a)
    {
        for(int i=1; i<a.length; i++)
        {
            if((a[i-1]!=0 || a[i]!=0))
            {
                     if(a[i-1]==a[i]) return true;
            }  
        }
        return false;    
    }

    //Check for 1 through 9
    public static boolean is1to9(int [] a)
    {
        int j=1;
        for(int i=0; i<a.length; i++)
        {
            if(a[i]==j) j++;
            else return false;
        }
        return true;    
    }

    public static boolean isDuplicate(int [][]suArray)
    {
        boolean result=false;

        //Check every row for duplicates
        for(int i=0; i<suArray[0].length; i++)
        {
            for(int j=0 ; j<suRows ; j++)
            {
                dummyRowArray[j]=suArray[i][j];
            }

            //Sort dummyArray so that duplicates can be checked
            exchangeSort(dummyRowArray);


            //Now check Adjacent elements for duplicates
            if(isAdjacentDup(dummyRowArray)==true)
            {
                System.out.println("Duplicates are found in row");
                return true;
            }

        }

        displaySudoku(suArray);

        //Check every column for duplicates 
        for(int j=0; j<suArray[0].length; j++)
        {
            for(int i=0 ; i<suColumns ; i++)
            {
                dummyColArray[i]=suArray[i][j];
            }

            //Sort dummyArray so that duplicates can be checked
            exchangeSort(dummyColArray);


            //Now check Adjacent elements for duplicates
            if(isAdjacentDup(dummyColArray)==true)
            {
                System.out.println("Duplicates are found in columns");
                return true;
            }

        }

        displaySudoku(suArray);

        System.out.println("3X3:");

        //Check every 3X3 matrix for duplicates
        // 1st block 
        if(is3x3Duplicate(suArray,0,3,0,3)==true)
        {
            System.out.println("1st Block has a duplicate");
            return true;
        }
        else System.out.println("1st Block has no duplicate");
        // 2nd block 
        if(is3x3Duplicate(suArray,0,3,3,6)==true)
        {
            System.out.println("2nd Block has a duplicate");
            return true;
        }
        // 3rd block 
        if(is3x3Duplicate(suArray,0,3,6,9)==true)
        {
            System.out.println("3rd Block has a duplicate");
            return true;
        } 
        // 4th block 
        if(is3x3Duplicate(suArray,3,6,0,3)==true)
        {
            System.out.println("4th Block has a duplicate");
            return true;
        } 
        // 5th block 
        if(is3x3Duplicate(suArray,3,6,3,6)==true)
        {
            System.out.println("5th Block has a duplicate");
            return true;
        } 
        // 6th block 
        if(is3x3Duplicate(suArray,3,6,6,9)==true)
        {
            System.out.println("6th Block has a duplicate");
            return true;
        } 
        // 7th block 
        if(is3x3Duplicate(suArray,6,9,0,3)==true)
        {
            System.out.println("7th Block has a duplicate");
            return true;
        } 
        // 8th block 
        if(is3x3Duplicate(suArray,6,9,3,6)==true)
        {
            System.out.println("8th Block has a duplicate");
            return true;
        } 
        // 9th block 
        if(is3x3Duplicate(suArray,6,9,6,9)==true)
        {
            System.out.println("9th Block has a duplicate");
            return true;
        } 

        return result;
    }

    //Check every3X3 grid for duplicates
    public static boolean is3x3Duplicate(int [][]suArray, int x1, int x2, int y1, int y2)
    {
        boolean result=false;
        int k=0, l=0;

        for(int i=x1; i<x2;i++)
        {   
            for(int j=y1;j<y2;j++)
            {

                dummy3x3Array[k][l]=suArray[i][j];
                l++;
            }
            l=0;
            k++;
        }
        displaySudoku(dummy3x3Array);   

        for(int i=0; i<dummy3x3Array.length; i++)
        {
            for(int j=0; j<dummy3x3Array.length; j++)
            {
                dummyArray[(i*dummy3x3Array.length) + j] = dummy3x3Array[i][j];
            }
        }

        System.out.println(Arrays.toString(dummyArray));

        //Sort dummyArray so that duplicates can be checked
        exchangeSort(dummyArray);



        //Now check Adjacent elements for duplicates
        if(isAdjacentDup(dummyArray)==true)
        {
            System.out.println("Duplicates are found in blocks");
            return true;
        }

        return result;
    }

     //Check every3X3 grid for 1 trough 9
    public static boolean is3x3have1to9(int [][]suArray, int x1, int x2, int y1, int y2)
    {
        boolean result=false;
        int k=0, l=0;

        for(int i=x1; i<x2;i++)
        {   

            for(int j=y1;j<y2;j++)
            {

                dummy3x3Array[k][l]=suArray[i][j];
                l++;
            }
            l=0;
            k++;
        }


        for(int i=0; i<dummy3x3Array.length; i++)
        {
            for(int j=0; j<dummy3x3Array.length; j++)
            {
                dummyArray[(i*dummy3x3Array.length) + j] = dummy3x3Array[i][j];
            }
        }



        //Sort dummyArray so that duplicates can be checked
        exchangeSort(dummyArray);



        //Now check Adjacent elements for duplicates
        if(is1to9(dummyArray)==false)
        {
            System.out.println("Block doe snot have 1 through 9");
            return false;
        }

        return result;
    }



    public static boolean isValidSudoku(int [][] suArray)
    {
      //  boolean result=true;

        //All nos should be between 0 and 9 
        for(int i=0; i<suArray.length; i++)
        {
            for(int j=0; j<suArray[i].length; j++)
            {
                    if(suArray[i][j]<0 || suArray[i][j]>9){
                        System.out.println("Nos in the puzzle are out of range");
                        return false;
                    }
            }
        }

        //Call teh isDuplicate function to check for duplicates in the rows
        if( isDuplicate(suArray)==true) return false;

        return true;

    }

    public static boolean isSolvedSudoku(int [][] suArray)
    {
         //Check every row for 1 to 9
        for(int i=0; i<suArray[0].length; i++)
        {

            for(int j=0 ; j<suRows ; j++)
            {
                dummyRowArray[j]=suArray[i][j];
            }


            //Sort dummyArray so that duplicates can be checked
            exchangeSort(dummyRowArray);



            if(is1to9(dummyRowArray)==false)
            {
                System.out.println("1 through 9 not present in rows");
                return false;
            }


        } 
        //Check every column for 1 to 9
        for(int j=0; j<suArray[0].length; j++)
        {

            for(int i=0 ; i<suColumns ; i++)
            {
                dummyColArray[i]=suArray[i][j];
            }


            //Sort dummyArray so that duplicates can be checked
            exchangeSort(dummyColArray);



            //Now check Adjacent elements for duplicates
            if(is1to9(dummyColArray)==false)
            {
                System.out.println("1 through 9 not present in columns");
                return false;
            }

        }

         //Check every 3X3 matrix for 1 through 9
        // 1st block 
        if(is3x3have1to9(suArray,0,3,0,3)==true)
        {
            System.out.println("1st Block does not contain 1 through 9");
            return false;
        }
        // 2nd block 
        if(is3x3have1to9(suArray,0,3,3,6)==true)
        {
            System.out.println("2nd Block does not contain 1 through 9");
            return false;
        }
        // 3rd block 
        if(is3x3have1to9(suArray,0,3,6,9)==true)
        {
            System.out.println("3rd Block does not contain 1 through 9");
            return false;
        } 
        // 4th block 
        if(is3x3have1to9(suArray,3,6,0,3)==true)
        {
            System.out.println("4th Block does not contain 1 through 9");
            return false;
        } 
        // 5th block 
        if(is3x3have1to9(suArray,3,6,3,6)==true)
        {
            System.out.println("5th Block does not contain 1 through 9");
            return false;
        } 
        // 6th block 
        if(is3x3have1to9(suArray,3,6,6,9)==true)
        {
            System.out.println("6th Block does not contain 1 through 9");
            return false;
        } 
        // 7th block 
        if(is3x3have1to9(suArray,6,9,0,3)==true)
        {
            System.out.println("7th Block does not contain 1 through 9");
            return false;
        } 
        // 8th block 
        if(is3x3have1to9(suArray,6,9,3,6)==true)
        {
            System.out.println("8th Block does not contain 1 through 9");
            return false;
        } 
        // 9th block 
        if(is3x3have1to9(suArray,6,9,6,9)==true)
        {
            System.out.println("9th Block does not contain 1 through 9");
            return false;
        } 

        return true;
    }


    public static boolean solveSudoku(int [][] s)
    {
        //Check if Valid
        if(isValidSudoku(suArray)==true) System.out.println("Sudoku is valid");
        else
        {
            System.out.println("Not valid!");
            return false;
        }
        //Check if Complete - No 0's in any place
        if(isComplete(suArray)==true)
        {
            System.out.println("Sudoku is Complete");
            return true;
        }
        else System.out.println("Sudoku is not Complete");

        //Check if solved - 1-9 present in every row, column and 3x3
        if(isSolvedSudoku(suArray)==true) System.out.println("Sudoku is Solved!");
        else System.out.println("Not Solved");   

        //Locate the first 0 in the Sudoko puzzle
        for(int i=0; i<suArray.length; i++)
        {
            for(int j=0 ; j<suArray[i].length ; j++)
            {
                if(suArray[i][j]==0) 
                {
                    System.out.println("0 found in location: " + i +"   " + j );
                    for(int k=1;k<10;k++)
                    {
                        suArray[i][j]=k;
                        System.out.println("New value assigned to Sudoku: " + k);
                        displaySudoku(suArray);
                        if(solveSudoku(suArray))// isValidSudoku(suArray))
                        {
                            displaySudoku(suArray);
                            System.out.println("New value assigned to Sudoku");
                            return true;
                        }
                    }    

                    suArray[i][j]=0; 
                    return false;  // remove this
                }
            }
        }

        return true;
    }



    public static void main(String[] args) throws FileNotFoundException, IOException {


        readSudoku();
        displaySudoku(suArray);

        if( (isValidSudoku(suArray)!=true))
        {
            System.out.println("The given Sudoku Puzzle is not Valid!. Exiting....");
            System.exit(0);
        }

        do
        {
            if(isSolvedSudoku(suArray)==true)
            {
                System.out.println("Sudoku is Completely Solved!");

            }

            if(solveSudoku(suArray)==true) 
            {
                System.out.println("Sudoku is now solved");

            }
            else System.out.println("Not Complete");  


        }while(isSolvedSudoku(suArray)!=true);

        System.out.println("Sudoku is now completely solved:");
        displaySudoku(suArray);


    }
}
于 2013-04-21T14:25:23.197 に答える