首页 > 专题系列 > Java解POJ > POJ 3435 Sudoku Checker [解题报告] Java
2013
11-12

POJ 3435 Sudoku Checker [解题报告] Java

Sudoku Checker

问题描述 :

The puzzle game of Sudoku is played on a board of N2 × N2 cells. The cells are grouped in N × N squares of N × N cells each. Each cell is either empty or contains a number between 1 and N2.

The sudoku position is correct when numbers in each row, each column and each square are different. The goal of the game is, starting from some correct position, fill all empty cells so that the final position is still correct.

This game is fairly popular in the Internet, and there are many sites which allow visitors to solve puzzles online. Such sites always have a subroutine to determine a correctness of a given position.

You are to write such a routin.

输入:

Input file contains integer N, followed by N4 integers — sudoku position. Empty cells are denoted by zeroes.

Constraints

1 ≤ N ≤ 10.

输出:

Output file must contain a single string ‘CORRECT’ or ‘INCORRECT’.
 

样例输入:

Sample input 1
2
0 0 0 0
0 0 0 0
0 0 2 0
0 0 0 1
Sample input 2
2
2 1 3 0
3 2 4 0
1 3 2 4
0 0 0 1

样例输出:

Sample output 1
CORRECT
Sample output 2
INCORRECT

温馨提示:

Bold texts appearing in the sample sections are informative and do not form part of the actual data.

解题代码:

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
 
 public static void main(String args[])
{
 Scanner sc=new Scanner(System.in);
  
 int n,i,j,k1,k2,p[][]=new int[101][101];
 n=sc.nextInt();
	
 int len=n*n;
 for(i=0;i< len;i++)
   for(j=0;j< len;j++)
	p[i][j]=sc.nextInt();
 boolean bb[]=new boolean[101],is=true;
  //memset(bb,0,sizeof(bb));
 for(i=0;i< len;i++)
 {
	Arrays.fill(bb,false);
	for(j=0;j< len;j++)
	{
         if(p[i][j]==0)continue;
	  if(bb[p[i][j]])break;
	  bb[p[i][j]]=true;
	}
	if(j< len)break;
   }
  if(i< len)is=false;
  for(j=0;j< len;j++)
  {
	Arrays.fill(bb,false);
	for(i=0;i< len;i++)
	{
         if(p[i][j]==0)continue;
	  if(bb[p[i][j]])break;
	  bb[p[i][j]]=true;
	}
	if(i< len)break;
   }
   if(j< len)is=false;
   for(i=0;i< len;i+=n)
    {
	for(j=0;j< len;j+=n)
	{
	   Arrays.fill(bb,false);
	   for(k1=i;k1< i+n;k1++)
	   {
		for(k2=j;k2< j+n;k2++)
		{
	         if(p[k1][k2]==0)continue;
		  if(bb[p[k1][k2]])break;
		  bb[p[k1][k2]]=true;
		}
		if(k2!=j+n)break;
	    }
	   if(k1!=i+n)is=false;
	   if(is==false)break;
	}
	if(is==false)break;
     }
     if(is) System.out.println("CORRECT");
     else System.out.println("INCORRECT");	
   }
}