- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
所以我有这个程序可以解决 C 中的 futoshiki 难题这是从具有以下格式的文本文件加载的:
50 | 0 | 0 | 0 | 0- - - - v - - - - 0 > 0 | 0 | 0 | 3- - - - - - - - - 0 | 0 < 2 | 0 | 0- - - - v - - - - 0 | 0 | 0 | 0 | 4^ - v - - - - - - 0 | 0 | 0 | 0 | 0
where 5 is the size of the matrix, and the numbers adjcent to the operators <
, >
, ^
, v
must satisfy the condition imposed by them, from the file all the characters on rows are divided by spaces eg 0 |
...So I've managed to load the file, to check if it satisfies the math operators conditions, but I'm stuck on the recursive function
What I'd like to know:
Did i choose the right way to store the matrix or I've should have divided the numbers from the logical operators ?
How could I perform an recursive expansion on the matrix and how could I track the used number in a certain step(in case I would have to backtrack)?
eg. let's say I arrive at index[j][j]
where j<n
(size of matrix) , starting from there I would have to decrement j
("touching") only numbers and check if the sub-matrix satisfies the conditions
Here's what I've managed to code so far.
where :
char **readmat(int *n);
//reads the matrix from the file eliminating the spaces between chars
void print(char **mat,int n);
//prints the stored matrix
int check(char **mat,int n);
//checks if items of a matrix of size n satisfies the math operators
int expand (char **mat,int n,int i);
//this should be the recursive functions that gets an element at a time and checks if there's any condition to be satisfied, if so, increments it
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char **readmat(int *n);
void print(char **mat,int n);
int check(char **mat,int n);
int expand (char **mat,int n,int i);
int main(int argc, char *argv[])
{
char **mat;
int n, j;
mat=readmat(&n);
if(mat == NULL)
return 1;
if(check(mat,n)){
print(mat,n);
}
else if(expand(mat,n,0)==1){
print(mat,n);
}
else {
printf("Nessuna soluzione trovata.\n");
}
for(j=0; j<=n;j++)
free(mat[j]);
free(mat);
system("PAUSE");
return 0;
}
char **readmat(int *n){
FILE *fp;
char *line,nome[100];
int i,j,k;
char **mat;
printf("Inserire il nome del file: ");
scanf("%s",nome);
fp=fopen(nome,"r");
if(fp==NULL){
printf("Errore apertura file");
return NULL;
}
if(fgets(nome,100,fp)==NULL){
printf("Formato file non valido\n");
fclose(fp);
return NULL;
}
if(sscanf(nome,"%d",n)!=1){
printf("Errore nei parametri del file\n");
fclose(fp);
return NULL;
}
(*n)=(((*n)*2)-1);
mat=(char**)malloc((*n)*sizeof(char*));
for(i=0;i<=(*n);i++)
mat[i]=(char*)malloc((*n)*sizeof(char));
line=(char*)malloc(2*(*n)*sizeof(char));
i=0;
while(i<=2*(*n) && fgets(line,2*(*n)+2,fp)!=NULL){
j=0;
k=0;
while(j<=2*(*n)){
if(line[j]!=' '){
mat[i][k]=line[j];
k++;
}
j++;
}
i++;
}
return mat;
//print(mat, (*n));
}
void print(char **mat,int n){
int i=0,j=0;
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
printf("%c", mat[i][j]);
}
printf("\n");
}
}
int check(char **mat,int n) {
int i,j;
int k=1;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(mat[i][j]=='<'){
if(mat[i][j-1] >= mat[i][j+1])
k=0;
}
else if(mat[i][j]=='>'){
if(mat[i][j-1] <= mat[i][j+1])
k=0;
}
else if(mat[i][j]=='^'){
if(mat[i-1][j] >= mat[i+1][j])
k=0;
}
else if(mat[i][j]=='v'){
if(mat[i-1][j] <= mat[i+1][j])
k=0;
}
}
}
return k;
}
int expand (char **mat,int n,int i){
int j=i/n;
int k=i%n;
int p;
if(i>=n*n){
return 1;
}
else{
if((mat[j][k]>47)&&(mat[j][k]<58)){
if(mat[j][k]=='0'){
expand(mat,n,i+2);
}
for (p=(mat[j][k]-48); p<(10-(mat[j][k]-48)); p++) {
mat[j][k]=48+p;
if (check(mat,i)) {
if (expand(mat, n, i+2)) {
return 1;
}
}
}
i-=2;
mat[j][k]='0';
}
}
return 0;
}
示例的解决方案:如您所见,逻辑条件区域显然得到满足
0 | 0 | 1 | 0 | 0
- - - - v - - - -
1 > 0 | 0 | 0 | 3
- - - - - - - - -
0 | 0 < 2 | 0 | 0
- - - - v - - - -
0 | 1 | 0 | 0 | 4
^ - v - - - - - -
1 | 0 | 0 | 0 | 0
最佳答案
存储矩阵的方式无关紧要。可以任意存储,只要能方便地获取/设置每个点的数值,并评估操作者是否满意即可。
从广义上讲,您可以使用如下算法解决此类问题:
//returns true if this function solved the puzzle, false otherwise.
//gameData will be changed to the solved form of the puzzle if a solution exists, or remain unchanged if no solution exists.
//(so, whatever language you're using, ensure gameData is passed by reference here)
bool solve(gameData){
if (!isValid(gameData)){return false;} //oops, puzzle is unsolvable!
if (isComplete(gameData)){return true;} //puzzle is already solved; no further modification needed.
//choose a spot on the game board that hasn't been filled in yet.
int x;
int y;
getEmptySpot(gameData, &x, &y);
//iterate through all the possible values that could go into the empty spot.
//you don't need anything fancy here to generate legal values for i;
//if you accidentally supply an invalid value, then isValid()
//will notice in the next solve() call.
for (int i = 1; i <= 5; i++){
//try putting i in the empty spot.
setValue(gameData, x, y, i);
if (solve(gameData)){ //putting i in the spot led to a solution!
return true;
}
}
//didn't find a solution :(
//return gameData to its original state.
setValue(gameData, x, y, 0);
return false;
}
该算法进行强力递归搜索,为每个点尝试每个可能的值,如果进入非法状态则回溯。在 super 最坏的情况下,它以指数时间运行,但实际上,开始时的 isValid()
调用将短路任何明显不可行的分支,因此它应该以 5x5 的速度相当快地完成输入。
isValid、isComplete、getEmptySpot 和 setValue 的实现将取决于您如何定义 gameData。
isValid
应该检查游戏数据是否处于非法状态 - 在您的情况下,它应该检查所有大于比较是否正确,并检查每个数字是否出现每行和每列仅一次。这些检查应忽略值为 0 的点,因为它们只是一个占位符,表示“尚未填充”。
isComplete
应检查以查看没有任何点具有“尚未填充”占位符。 (isValid(gameData) && isComplete(gameData))
表示 gameData 已解决。
getEmptySpot
应该找到尚未填充的位置。如果您担心速度,它应该找到可以合法输入的最小数值的位置。这将大大减少搜索树的宽度。
最后,setValue
应该将给定点设置为给定值。
关于c - Futoshiki C递归求解器,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9211950/
所以我有这个程序可以解决 C 中的 futoshiki 难题这是从具有以下格式的文本文件加载的: 50 | 0 | 0 | 0 | 0- - - - v - - - - 0 > 0 | 0 | 0 |
我是一名优秀的程序员,十分优秀!