sudoku 最简单的 solver

mm 最近做题,于是也写了个简单的版本,没啥优化

#include <iostream>

namespace sudoku {
  struct board {
    static const std::size_t size = 9 ;
    char data [size][size];
  } ;

  inline std::ostream&
  operator<< (std::ostream& out, const board& b) {
    for (int i = 0 ; i < board::size ; ++ i) {
      for (int j = 0 ; j < board::size ; ++ j)
	out << static_cast<char> (b.data[i][j] + '1') ;
      out << "\n" ;
    }
    return out ;
  }

  inline std::istream&
  operator>> (std::istream& in, board& b) {
    for (int i = 0 ; i < board::size ; ++ i) {
      for (int j = 0 ; j < board::size ; ++ j) {
	in >> b.data[i][j] ;
	b.data[i][j] -= '1' ;
      }
    }
    return in ;
  }
}

这个部分解决了输入输出的问题,下面是 solver

#include <iostream>
#include <array>
#include <cassert>

typedef std::array<bool, sudoku::board::size> sub_con_type ;
typedef std::array<sub_con_type, sudoku::board::size> con_type ;
const int none = '0' - '1' ;
const sub_con_type default_sub = {false, false, false, false,
                                  false, false, false, false, false} ;

inline int
blk (int i, int j) {
  return (i / 3) * 3 + j / 3 ;
}

inline int
next_avail (sub_con_type& hc, sub_con_type& vc,
            sub_con_type& bc, int val) {
  for (int i = val + 1 ; i < sudoku::board::size ; ++ i)
    if (!(hc [i] || vc[i] || bc[i])) {
      if (val != none) {
        hc [val] = false ; vc [val] = false ; bc [val] = false ;
      }
      hc [i] = true ; vc [i] = true ; bc [i] = true ;
      return i ;
    }
  if (val != none) {
    hc [val] = false ; vc [val] = false ; bc [val] = false ;
  }
  return none ;
}

int
backtrack (const sudoku::board& src,
           sudoku::board& dst) {
  dst = src ;

  // initialize constraints
  con_type hc, vc, bc ;
  hc.fill (default_sub) ;
  vc.fill (default_sub) ;
  bc.fill (default_sub) ;

  // remove those from start
  for (int i = 0 ; i < sudoku::board::size ; ++ i)
    for (int j = 0 ; j < sudoku::board::size ; ++ j) {
      int val = src.data[i][j] ;
      int k = blk (i, j) ;
      if (val != none) {
        assert ((hc [i][val] || vc [j][val] ||
                 bc [k][val])== false) ;
        hc [i][val] = true ;
        vc [j][val] = true ;
        bc [k][val] = true ;
      }
    }

  // start back track
  int i = 0, j = 0 ;
  do {
    int k = blk (i, j) ;

    // check current value
    if (src.data [i][j] == none) { // not filled
      int u = dst.data[i][j] ;
      int v = next_avail (hc[i], vc[j], bc[k], u) ;
      if (v == none) { // back track, restore value and move back
        dst.data [i][j] = none ;
        do {
          // move back
          if (j == 0) {
            -- i ; j = sudoku::board::size - 1 ;
          } else
            -- j ;
        } while (src.data[i][j] != none && i != none) ;
        continue ;
      } else
        dst.data [i][j] = v ;
    }

    // filled, then move to the next
    if (j == sudoku::board::size - 1) { // end of row
      ++ i ; j = 0 ;
    } else
      ++ j ;
  } while (i != sudoku::board::size && i > -1) ;

  if (i == sudoku::board::size)
    return 1 ;
  return 0 ;
}

int
main (int argc, char* argv[]) {
  sudoku::board b, workspace ;
  std::cin >> b ;
  int ret = backtrack (b, workspace) ;
  if (ret)
    std::cout << "the solution is:\n"
              << workspace ;
  else
    std::cout << "the problem\n"
              << b << "might have no solution.\n" ;
  return 0 ;
}

感觉 backtrack 程序写的很生疏…

——————
And they dwelt from Havilah unto Shur, that is before Egypt, as thou goest toward Assyria: and he died in the presence of all his brethren.

Advertisements
sudoku 最简单的 solver

一个有关“sudoku 最简单的 solver”的想法

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s