|
說 明 |
應用問題區首頁 |
讀入數獨 (sudoku) 資料檔, 計算並印出數獨解.
數獨資料檔格式為若干點所構成的整數組成.
數獨的每一點包含三個整數, 分別為點座標 i j 與數字 n.
數獨資料 n 在 [1,M] 之間, i 與 j 都在 [0,M-1].
M 為整數的平方數, 例如 : 9, 16, 25 等等
本程式可讀取兩種輸入檔案格式
(1) sudoku.dat 資料檔如下 ( Coordinate 模式 )
0 2 1 0 3 8 0 5 7 0 6 3
1 1 7 1 4 2 1 7 9
2 0 4 2 4 1 2 8 5
3 0 3 3 3 4 3 5 5 3 8 2
4 1 5 4 2 6 4 6 1 4 7 3
5 0 9 5 3 6 5 5 1 5 8 7
6 0 2 6 4 5 6 8 8
7 1 8 7 4 6 7 7 4
8 2 9 8 3 1 8 5 2 8 6 5
(2) dudoku.dat2 資料檔如下 ( Entire_Map 模式 )
0 0 1 8 0 7 3 0 0
0 7 0 0 2 0 0 9 0
4 0 0 0 1 0 0 0 5
3 0 0 4 0 5 0 0 2
0 5 6 0 0 0 1 3 0
9 0 0 6 0 1 0 0 7
2 0 0 0 5 0 0 0 8
0 8 0 0 6 0 0 4 0
0 0 9 1 0 2 5 0 0
NOTE :
須使用第 19 章的集合容器
| |
#include <iostream>
#include <fstream>
#include <iomanip>
#include <set>
#include <cassert>
using namespace std ;
enum DataFile_Type { Coordinate , Entire_Map };
template <int S = 3>
class Sudoku {
private :
static const int M = S*S ;
set<int> v[M], h[M] , m[M] ;
// store number
int no[M][M] ;
// store whether number is fixed
bool fixed[M][M] ;
// (i,j) --> m
int index( int i , int j ) const { return (i/S) * S + (j/S) ; }
// check whether number n at position (i,j) is a valid number
bool valid_number( int n , int i , int j ) const {
assert( i > -1 && i < M && j > -1 && j < M ) ;
assert( n >= 1 && n <= M ) ;
if ( h[i].find(n) != h[i].end() ) return false ;
if ( v[j].find(n) != v[j].end() ) return false ;
int s = index(i,j) ;
if ( m[s].find(n) != m[s].end() ) return false ;
return true ;
}
// insert number n at position (i,j) to all related sets
void insert_number( int n , int i , int j ) {
assert( i > -1 && i < M && j > -1 && j < M ) ;
assert( n >= 1 && n <= M ) ;
h[i].insert(n) ;
v[j].insert(n) ;
m[index(i,j)].insert(n) ;
}
// delete number n at position (i,j) from all related sets
void delete_number( int n , int i , int j ) {
assert( i > -1 && i < M && j > -1 && j < M ) ;
assert( n >= 1 && n <= M ) ;
h[i].erase(n) ;
v[j].erase(n) ;
m[index(i,j)].erase(n) ;
}
public :
// read data from datafile
Sudoku( char* datafile , DataFile_Type data_type = Coordinate ) {
int i , j ;
for ( i = 0 ; i < M ; ++i ) {
for ( j = 0 ; j < M ; ++j ) {
no[i][j] = 0 ;
fixed[i][j] = false ;
}
}
// read data file
ifstream infile(datafile) ;
int n ;
if ( data_type == Coordinate ) {
// read position : (i,j) with value : n
while ( infile ) {
infile >> i >> j >> n ;
if ( i >= 0 && i < M && j >= 0 && j < M && n >= 1 && n <= M ) {
no[i][j] = n ;
fixed[i][j] = true ;
insert_number(n,i,j) ;
}
}
} else if ( data_type == Entire_Map ) {
// read entire map
for ( i = 0 ; i < M ; ++i ) {
for ( j = 0 ; j < M ; ++j ) {
infile >> n ;
if ( n > 0 ) {
no[i][j] = n ;
fixed[i][j] = true ;
insert_number(n,i,j) ;
}
}
}
}
cout << "initial chart : \n" << *this << endl ;
infile.close() ;
}
// find next position (i,j)
void next_position( int& i , int& j ) const {
if ( i == M ) return ;
do {
++j ;
if ( j == M ) { ++i ; j = 0 ; }
if ( i == M ) return ;
} while ( fixed[i][j] ) ;
}
// find proper number at position (s,t)
bool find_solution( int s = 0 , int t = 0 ) {
if ( s == M ) {
return true ;
} else {
if ( fixed[s][t] ) next_position(s,t) ;
int i = s , j = t ;
// find the next possible position (i,j)
next_position(i,j) ;
// fill possible numbers
int n ;
for ( n = 1 ; n <= M ; ++n ) {
if ( valid_number(n,s,t) ) {
no[s][t] = n ;
insert_number(n,s,t) ;
if ( find_solution(i,j) ) return true ;
no[s][t] = 0 ;
delete_number(n,s,t) ;
}
}
return false ;
}
}
// output
friend ostream& operator<< ( ostream& out , const Sudoku<S>& foo ) {
char * red = "[0,31m" ; // use ANSI terminal escape sequence
char * ec = "[0m" ;
int i , j ;
for ( i = 0 ; i < Sudoku<S>::M ; ++i ) {
if ( i % S == 0 )
out << " " << setw(3*(M+S)+1) << setfill('-') << "-" << setfill(' ') << endl ;
for ( j = 0 ; j < Sudoku<S>::M ; ++j ) {
if ( j % S == 0 ) out << setw(3) << "|" ;
if ( foo.fixed[i][j] ) out << red ;
if ( foo.no[i][j] )
out << setw(3) << foo.no[i][j] ;
else
out << setw(3) << " " ;
if ( foo.fixed[i][j] ) out << ec ;
}
out << setw(3) << "|" << endl ;
}
out << " " << setw(3*(M+S)+1) << setfill('-') << "-" << setfill(' ') << endl ;
return out ;
}
};
int main() {
Sudoku<3> foo("sudoku.dat") ;
if ( foo.find_solution() ) cout << "solution :\n" << foo << endl ;
Sudoku<3> bar("sudoku.dat2",Entire_Map) ;
if ( bar.find_solution() ) cout << "solution :\n" << bar << endl ;
/*
Sudoku<4> foo4("sudoku2.dat") ;
if ( foo4.find_solution() ) cout << foo4 << endl ;
*/
return 0 ;
}
|
輸 出 |
|---|
initial chart :
-------------------------------------
| 1 | 8 7 | 3 |
| 7 | 2 | 9 |
| 4 | 1 | 5 |
-------------------------------------
| 3 | 4 5 | 2 |
| 5 6 | | 1 3 |
| 9 | 6 1 | 7 |
-------------------------------------
| 2 | 5 | 8 |
| 8 | 6 | 4 |
| 9 | 1 2 | 5 |
-------------------------------------
solution :
-------------------------------------
| 5 9 1 | 8 4 7 | 3 2 6 |
| 8 7 3 | 5 2 6 | 4 9 1 |
| 4 6 2 | 3 1 9 | 7 8 5 |
-------------------------------------
| 3 1 8 | 4 7 5 | 9 6 2 |
| 7 5 6 | 2 9 8 | 1 3 4 |
| 9 2 4 | 6 3 1 | 8 5 7 |
-------------------------------------
| 2 3 7 | 9 5 4 | 6 1 8 |
| 1 8 5 | 7 6 3 | 2 4 9 |
| 6 4 9 | 1 8 2 | 5 7 3 |
-------------------------------------
initial chart :
-------------------------------------
| 1 | 8 7 | 3 |
| 7 | 2 | 9 |
| 4 | 1 | 5 |
-------------------------------------
| 3 | 4 5 | 2 |
| 5 6 | | 1 3 |
| 9 | 6 1 | 7 |
-------------------------------------
| 2 | 5 | 8 |
| 8 | 6 | 4 |
| 9 | 1 2 | 5 |
-------------------------------------
solution :
-------------------------------------
| 5 9 1 | 8 4 7 | 3 2 6 |
| 8 7 3 | 5 2 6 | 4 9 1 |
| 4 6 2 | 3 1 9 | 7 8 5 |
-------------------------------------
| 3 1 8 | 4 7 5 | 9 6 2 |
| 7 5 6 | 2 9 8 | 1 3 4 |
| 9 2 4 | 6 3 1 | 8 5 7 |
-------------------------------------
| 2 3 7 | 9 5 4 | 6 1 8 |
| 1 8 5 | 7 6 3 | 2 4 9 |
| 6 4 9 | 1 8 2 | 5 7 3 |
-------------------------------------
| |
|