Java Reference
In-Depth Information
Note that there might be more than one closest pair of points with the same minimum dis-
tance. The program finds one such pair. You may modify the program to find all closest pairs
in Programming Exercise 8.8.
multiple closest pairs
Tip
It is cumbersome to enter all points from the keyboard. You may store the input in a file, say
FindNearestPoints.txt
, and compile and run the program using the following command:
input file
java FindNearestPoints < FindNearestPoints.txt
The problem is to check whether a given Sudoku solution is correct.
Key
Point
This section presents an interesting problem of a sort that appears in the newspaper every
day. It is a number-placement puzzle, commonly known as
Sudoku
. This is a very challeng-
ing problem. To make it accessible to the novice, this section presents a simplified version of
the Sudoku problem, which is to verify whether a Sudoku solution is correct. The complete
program for finding a Sudoku solution is presented in Supplement VI.A.
Sudoku is a 9
VideoNote
Sudoku
3 boxes (also called
regions
or
blocks
), as
shown in Figure 8.4a. Some cells, called
fixed cells
, are populated with numbers from
1
to
9
. The
objective is to fill the empty cells, also called
free cells
, with the numbers
1
to
9
so that every
row, every column, and every 3
*
9 grid divided into smaller 3
*
fixed cells
free cells
*
3 box contains the numbers
1
to
9
, as shown in Figure 8.4b.
53
7
53
46
7
8912
6
72
195
348
1
98
3425
6
7
8
597
6
142
3
4
26
8
5
3
79
1
7
139
2
485
6
9
6
1537284
287
419
63
5
3452
8
6
195
98
6
8
6
3
Solution
4
8
3
1
7
2
6
6
419
5
8
7
9
61
79
(a) Puzzle
(b) Solution
F
IGURE
8.4
The Sudoku puzzle in (a) is solved in (b).
For convenience, we use value
0
to indicate a free cell, as shown in Figure 8.5a. The grid
can be naturally represented using a two-dimensional array, as shown in Figure 8.5b.
representing a grid
5300
7
0000
00
int
[][] grid =
{{
5
,
3
,
0
,
0
,
7
,
0
,
0
,
0
,
0
},
{
6
,
0
,
0
,
1
,
9
,
5
,
0
,
0
,
0
},
{
0
,
9
,
8
,
0
,
0
,
0
,
0
,
6
,
0
},
{
8
,
0
,
0
,
0
,
6
,
0
,
0
,
0
,
3
},
{
4
,
0
,
0
,
8
,
0
,
3
,
0
,
0
,
1
},
{
7
,
0
,
0
,
0
,
2
,
0
,
0
,
0
,
6
},
{
0
,
6
,
0
,
0
,
0
,
0
,
2
,
8
,
0
},
{
0
,
0
,
0
,
4
,
1
,
9
,
0
,
0
,
5
},
{
0
,
0
,
0
,
0
,
8
,
0
,
0
,
7
,
9
}
};
600
195
0
0
0
98
0
0
0
0
6
8
00
0
6
0
00
00
00
00
00
0
3
4
00
8
0
3
1
7
00
0
2
0
6
0
6
0
0
0
0
0
0
0
0
419
5
79
0
0
0
0
8
0
(a)
(b)
F
IGURE
8.5
A grid can be represented using a two-dimensional array.
Search WWH ::
Custom Search