6
내가 뭘 잘못하고 있는지 모르겠다. 하루 종일이 코드를 쳐다 보았다. 이것은 자바의 "표준"스도쿠 해결사로 공백이있는 곳의 숫자는 int[][]입니다. 저는 35 개의 구멍이있는 보드를 통과 할 뿐이므로이 문제의 대부분을 해결할 수 있어야하지만 ~ 66 % 만 해결할 수 있습니다. 나머지는 공백이 남아 있으며 해결할 수 없습니다 (즉, 부적절한 숫자는 board에 기록되었습니다.) 거의 항상 9 개가 누락됩니다.스도쿠 (Sudoku) 해답 버그
나는 그런 간단한 해결책으로 모든 스도쿠족을 해결할 수 없다는 것을 알고 있습니다. 나는 고의적으로 쉽게 그것들을주고있다.
import java.util.ArrayList;
import java.util.List;
public class SudokuSolver
{
public SudokuSolver()
{
init();
}
public boolean solve()
{
/* Each method checks (in different ways) to see if it can find a new number
If said method does find a number, it sets off a chain reaction, starting back at the beginning.
*/
int countdown = 20;
while(!solved() && --countdown > 0)
{
if(given())
continue;
if(findSingletons())
continue;
if(zerosLeft() <= 4)
justGuess();
}
return solved();
}
public boolean given()
{
boolean repeat = false;
//Iterate through every given number
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(board[i][j] != 0 && !found[i][j])
{
repeat = true;
foundNum(i, j, board[i][j]);
}
}
}
//Call given every time a new number is found
return repeat;
}
public boolean findSingletons()
{
boolean repeat = false;
//LOTS of iteration, but I'm out of ideas.
int[] values;
ArrayList<Integer> singletons = new ArrayList<Integer>();
for(int i=0;i<9;i++)
{
values = new int[10];
singletons.clear();
for(int j=0;j<9;j++)
for(int k=0;k<possible[i][j].size();k++)
values[possible[i][j].get(k)]++;
for(int j=1;j<10;j++)
if(values[j] == 1)
singletons.add(j);
for(int j=0;j<9;j++)
for(int k=0;k<singletons.size();k++)
if(possible[i][j].contains(singletons.get(k)))
{
foundNum(i, j, singletons.get(k));
repeat = true;
}
}
for(int i=0;i<9;i++)
{
values = new int[10];
singletons.clear();
for(int j=0;j<9;j++)
for(int k=0;k<possible[j][i].size();k++)
values[possible[j][i].get(k)]++;
for(int j=1;j<10;j++)
if(values[j] == 1)
singletons.add(j);
for(int j=0;j<9;j++)
for(int k=0;k<singletons.size();k++)
if(possible[j][i].contains(singletons.get(k)))
{
foundNum(j, i, singletons.get(k));
repeat = true;
}
}
int[] corners = {0,3,6};
for(int a=0;a<3;a++)
for(int l=0;l<3;l++)
for(int i=corners[a];i<corners[a]+3;i++)
{
values = new int[10];
singletons.clear();
for(int j=corners[l];j<corners[l]+3;j++)
for(int k=0;k<possible[i][j].size();k++)
values[possible[i][j].get(k)]++;
for(int j=1;j<10;j++)
if(values[j] == 1)
singletons.add(j);
for(int j=0;j<9;j++)
for(int k=0;k<singletons.size();k++)
if(possible[i][j].contains(singletons.get(k)))
{
foundNum(i, j, singletons.get(k));
repeat = true;
}
}
return repeat;
}
public void justGuess()
{
outer:
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(board[i][j] == 0)
{
foundNum(i, j, possible[i][j].get(0));
break outer;
}
}
public void foundNum(int x, int y, int numFound)
{
if(board[x][y] != 0 && board[x][y] != numFound)
{
throw new RuntimeException("Attempting to place a number where one was already found");
}
board[x][y] = numFound;
possible[x][y].clear();
possible[x][y].add(numFound);
found[x][y] = true;
for(int i=0;i<9;i++) {
if(i != x)
if(possible[i][y].indexOf(numFound) != -1)
possible[i][y].remove(possible[i][y].indexOf(numFound));
}
for(int i=0;i<9;i++) {
if(i != y)
if(possible[x][i].indexOf(numFound) != -1)
possible[x][i].remove(possible[x][i].indexOf(numFound));
}
int cornerX = 0;
int cornerY = 0;
if(x > 2)
if(x > 5)
cornerX = 6;
else
cornerX = 3;
if(y > 2)
if(y > 5)
cornerY = 6;
else
cornerY = 3;
for(int i=cornerX;i<10 && i<cornerX+3;i++)
for(int j=cornerY;j<10 && j<cornerY+3;j++)
if(i != x && j != y)
if(possible[i][j].indexOf(numFound) != -1)
possible[i][j].remove(possible[i][j].indexOf(numFound));
}
public boolean solved() {
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(!found[i][j])
return false;
return true;
}
public void reset(int[][] board)
{
this.board = board;
init();
}
public void init()
{
possible = new ArrayList[9][9];
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
possible[i][j] = new ArrayList<Integer>();
for(int k=1;k<10;k++)
possible[i][j].add(k);
}
found = new boolean[9][9];
}
public void print()
{
for(int i=0;i<9;i++)
{
if(i%3==0 && i != 0)
System.out.println("- - - | - - - | - - -");
for(int j=0;j<9;j++)
{
if(j%3==0 & j != 0)
System.out.print("| ");
System.out.print(board[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
private int zerosLeft()
{
int empty = 0;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(board[i][j] == 0)
empty++;
return empty;
}
private void data(int difficulty)
{
int empty = 0;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(board[i][j] == 0)
empty++;
System.out.println(empty);
}
public static void main(String[] args)
{
SudokuGenerator sg = new SudokuGenerator();
SudokuSolver ss = new SudokuSolver();
int[][] tempBoard = {{4, 0, 1, 0, 9, 7, 0, 5, 8 },
{2, 0, 0, 5, 3, 1, 4, 0, 6 },
{5, 0, 6, 4, 0, 2, 0, 3, 9 },
{0, 9, 0, 0, 0, 4, 3, 0, 2 },
{0, 0, 0, 9, 0, 0, 6, 4, 7 },
{7, 0, 4, 0, 0, 0, 9, 0, 5 },
{0, 0, 7, 0, 0, 3, 8, 9, 4 },
{8, 5, 0, 1, 4, 9, 7, 0, 0 },
{9, 0, 3, 8, 7, 6, 0, 0, 0 }};
ss.reset(tempBoard);
System.out.println(ss.solve());
ss.print();
ss.data(35);
}
int[][] board;
ArrayList<Integer>[][] possible;
boolean[][] found;
}
저는 아직 프로그래밍이 처음이므로이 문제를 해결하는 것 외에 다른 조언을 환영합니다. (특히 possible을 최적화하십시오. 지금까지 작성한 코드 중 가장 모호한 코드입니다.)
고마워요!
만들 수있는 방법을 찾을 수 있습니다 "그건 내가 지금까지 쓴 가장 모독 코드의를." Eric Lippert는 C#에서 그의 [그래프 채색 시리즈] (http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/)의 일부로 다소 아름다운 스도쿠 해결사를 작성했습니다. Java가 가지고 있지 않은 몇 가지 기능을 사용하지만, 어쨌든 한번 살펴 보는 것이 좋습니다. –
특정 메소드를 테스트하기 위해 jUnit 테스트를 작성하여 개발을 추진하십시오. TDD (Test Driven Development)에 대해 읽어보고, 객체 지향 디자인에 대해 읽어보십시오. 여기에 적용되어야하는 두 가지 명백한 코드 재분할이 있으며 지금은 전체 검토를 수행 할 시간이 없습니다. 그러나 여기에 몇 가지 주요 사항이 있습니다. findSingletons는 매우 길다. 이것을 작은 방법으로 리팩토링하는 것을 고려하십시오. print 메소드를 사용하는 대신 toString을 재정의하십시오. 비슷하지만 더 간단한 문제에 대해 작성한 코드를 여기에서 확인하십시오. https://github.com/RobertKielty/q8impl/tree/master/workspace/EightQueens –
@Rob : 자신 만의 주석을 삭제할 수 있습니다 (해당 의견에 대해 더 많은 평판이 필요합니까? ?) - 예를 들어 중간에 "enter"를 누르는 경우, 아마도 새로운 행을 만들기위한 것입니다. –