POJ3076 Sudoku

  • The title is 16*16 GongGe
  • See code for pruning
 #include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=; #define res register int
int map[N][N];
unsigned short t[N][N];
//table[i,j]( Binary system ) Express (i,j) The number you can fill in ,0 Can be filled ,1 Can't fill in
int filled(); inline void my_fill(int x,int y,int a)//(x,y) fill a
{
filled++;
map[x][y]=a;
t[x][y] |=<<(a-);
for(res i= ; i< ; i++)
t[x][i] |=<<(a-),
t[i][y] |=<<(a-);
int r=x/*,c=y/*;//(r,c) Express (x,y) Where 16 The upper left corner of the grid ,( from (0,0) Start )
for(res i= ; i< ; i++)
for(res j= ; j< ; j++) t[r+i][j+c] |=<<(a-);
} // Judge x in 0 Is there only 1 individual
int count_zero(unsigned short x)
{
int p(-);
for(int i=;x;i++)
{
if(x&==)
{
if(p!=-) return -;
p=i;
}
x>>=;
}
return p;
} // The first x That's ok , Numbers k+1, return >0 Is the only one that can be filled in k+1 The location of ,-1 It means that there are multiple positions that can be filled or have been filled ,-2 It can't be filled in
inline int col(int x,int k)
{
int p(-);
for(res y= ; y< ; y++)
{
if(map[x][y]==k+) return -;// It has been filled in
if(map[x][y]>) continue;
if((t[x][y]&(<<k))==)
{
if(p!=-) return -;// Multiple occurrences
p=y;
}
}
if(p!=-) return p;
return -;
} // The first y Column , Numbers k
inline int row(int y,int k)
{
int p=-;
for(res x= ; x< ; x++)
{
if(map[x][y]==k+) return -;
if(map[x][y]>) continue;
if((t[x][y]&(<<k))==)
{
if(p!=-) return -;
p=x;
}
}
if(p!=-) return p;
return -;
} inline void grid(int r,int c,int k,int &x,int &y)
// With (r,c) It's in the upper left corner 16 GongGe , Numbers k+1,(x,y) Is the only fillable coordinate [
{
x=-;
for(res i= ; i< ; i++)
for(res j= ; j< ; j++)
{
if(map[r+i][c+j]==k+) {x=-; return ;}
if(map[r+i][c+j]>) continue;
if((t[r+i][c+j]&(<<k))==)
{
if(x!=-) {x=-; return ;}
x=i,y=j;
}
}
} inline int count_1(unsigned short x) {
int tmp();
while(x) {
if(x&) tmp++;
x>>=;
}
return tmp;
} bool search()
{
if(filled==) return true;
// Let's see if there is a certain grid
for(res x= ; x< ; x++)
for(res y= ; y< ; y++)
{
if(map[x][y]>) continue;
int k=count_zero(t[x][y]);
if(k!=-) my_fill(x,y,k+);
}
for(res x= ; x< ; x++)
for(res k= ; k< ; k++)
{
int y=col(x,k);
if(y==-) return false;
if(y!=-) my_fill(x,y,k+);
}
for(res y= ; y< ; y++)
for(res k= ; k< ; k++)
{
int x=row(y,k);
if(x==-) return false;
if(x!=-) my_fill(x,y,k+);
}
for(res r= ; r< ; r+=)
for(res c= ; c< ; c+=)
for(res k= ; k< ; k++)
{
int x,y;
grid(r,c,k,x,y);
if(x==-) return false;
if(x!=-) my_fill(r+x,c+y,k+);
}
if(filled==) return true;
int t_filled(filled);
int t_map[N][N];
unsigned short t_t[N][N];
for(res i= ; i< ; i++)
for(res j= ; j< ; j++)
t_map[i][j]=map[i][j],
t_t[i][j]=t[i][j];
// Find the least possible grid to enumerate
int mx,my,mn=;
for(res i= ; i< ; i++)
for(res j= ; j< ; j++)
{
if(map[i][j]>) continue;
int r=-count_1(t[i][j]);
// Undetermined
if(r<mn)
{
mn=r; mx=i; my=j;
}
}
for(res k= ; k< ; k++)
if((t[mx][my]&<<k)==)
{
my_fill(mx,my,k+);
if(search()) return true;
filled=t_filled;
for(res i= ; i< ; i++)
for(res j= ; j< ; j++)
map[i][j]=t_map[i][j],
t[i][j]=t_t[i][j];
}
return false;
} char ar[N];
int main()
{
while()
{
filled=;
memset(map,,sizeof(map)); memset(t,,sizeof(t));
for(int i= ; i< ; i++)
{
if(scanf("%s",ar)==EOF) return ;
for(int j= ; j< ; j++)
if(ar[j]!='-') my_fill(i,j,ar[j]-'A'+);
}
search();
for(res i= ; i< ; i++)
{
for(res j= ; j< ; j++) printf("%c",map[i][j]+'A'-);
puts("");
}
puts("");
}
return ;
}

POJ3076 Sudoku More articles about

  1. POJ3076 Sudoku Dance chain DLX

    Welcome to visit ~ The source of the original text is —— Blog Garden -zhouzhendong Go to the blog Garden to see the solution subject ( Portal ) Topic summary Give an incomplete 16*16 Sudoku , solve . Answer key DLX +  Matrix construction   ( Two portals ) After learning this , Again ...

  2. 【 turn 】Dancing Links Problem set

    from :http://blog.csdn.net/shahdza/article/details/7986037 POJ3740 Easy Finding [ Cover the basic questions accurately ]HUST1017 Exact ...

  3. dancing links The summer wind

    POJ3740     Easy Finding [ Cover the basic questions accurately ] HUST1017    Exact cover [ Precise coverage of the foundation ] HDOJ3663 Power Stations [ Precise coverage ] Z ...

  4. Sudoku(POJ2676/3074)

    Sudoku is one of the metaphysical techniques. If you understand the essence of it, you will have the ...

  5. Leetcode note 36 - Sudoku Solver

    Topic link :Sudoku Solver | LeetCode OJ Write a program to solve a Sudoku puzzle by filling the empty cells ...

  6. [LeetCode] Sudoku Solver Solving Sudoku

    Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by th ...

  7. [LeetCode] Valid Sudoku Verify Sudoku

    Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board could be ...

  8. LeetCode 36 Valid Sudoku

    Problem: Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board ...

  9. 【leetcode】Valid Sudoku

    A brief introduction to the topic : Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board cou ...

Random recommendation

  1. Android Imitating wechat QR code scanning

    Reprint :http://blog.csdn.net/xiaanming/article/details/10163203 Learn about QR code from wechat , At that time, wechat launched the QR code scanning function , I feel very novel , From one ...

  2. linux The use of message queue and the principle of kernel implementation

    mq_receive NAME mq_open - open a message queue SYNOPSIS #include <fcntl.h> /* For O_* constant ...

  3. Mac OS— Apple builds Android development environment

    How to be in MAC OS X install Android SDK The development environment I used to use was based on MAC OS install VMware Come and run different Windows OS, At present, the project to be developed is gradually changed from the traditional Wintel Transferred to the Mob ...

  4. opengl Micro development understanding

    1. What is? OpenGL? A program , Can interact with interface and graphics hardware . An open standard 2. Software pipeline Please look at the picture - Apllication layer     Show your program ( Call the render command . Such as opengl API) - ...

  5. IDEA mybatis mapper Class jump to xml file

    Installing a plug-in free mybatis plugin, Restart after installation ,ctrl+ Click to jump .

  6. input type file Compatibility

    input  Medium type  file type   stay ie10 And above are normal , stay ie9 You can't find him in the middle of the game To solve this kind of problem, we need to use it skillfully css    as well as input 了 You need two input Write in coordination with , One i ...

  7. Node.js Performance analysis artifact Easy-Monitor

    Abstract :  Use Easy-Monitor, You can pinpoint Node.js Performance bottleneck of application , Help us optimize code performance . When the application has performance problems , The biggest problem is : How to accurately locate the code that causes the performance bottleneck ? about Node.js developer ...

  8. Mvc_ Expand @html

    HtmlHelper An example of , It is defined in System.Web.Mvc Under the name space WebViewPage class , That is, it's for all MVC All pages are available ) After establishing the extension method : @Html.CreateGanderRad ...

  9. hold svn Upper mycelipse Lead to local eclipse in 【 primary 】

    myeclipse and eclipse Of web There are all kinds of problems in project mutual guidance , Now let's record what happened to me as follows : eclipse How to make svn On down Coming down myeclipseWeb The project becomes eclipse Of Web project : ...

  10. hadoop Building pseudo distributed environment linux System installation tutorial

    This article is a continuation of < Hyperdetail hadoop Virtual machine installation tutorial ( The steps are as follows )>, In the last article, someone asked why it wasn't written hadoop install . It has been explained at the beginning of the article ,hadoop The installation will write later , Because the whole series is about every ...