{"action":"created","issue":{"url":"https://api.github.com/repos/jlaire/dlx-cpp/issues/1","repository_url":"https://api.github.com/repos/jlaire/dlx-cpp","labels_url":"https://api.github.com/repos/jlaire/dlx-cpp/issues/1/labels{/name}","comments_url":"https://api.github.com/repos/jlaire/dlx-cpp/issues/1/comments","events_url":"https://api.github.com/repos/jlaire/dlx-cpp/issues/1/events","html_url":"https://github.com/jlaire/dlx-cpp/issues/1","id":155201247,"number":1,"title":"nqueens solution generator is much slow than backtracking","user":{"login":"mhayter","id":2280494,"avatar_url":"https://avatars.githubusercontent.com/u/2280494?v=3","gravatar_id":"","url":"https://api.github.com/users/mhayter","html_url":"https://github.com/mhayter","followers_url":"https://api.github.com/users/mhayter/followers","following_url":"https://api.github.com/users/mhayter/following{/other_user}","gists_url":"https://api.github.com/users/mhayter/gists{/gist_id}","starred_url":"https://api.github.com/users/mhayter/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mhayter/subscriptions","organizations_url":"https://api.github.com/users/mhayter/orgs","repos_url":"https://api.github.com/users/mhayter/repos","events_url":"https://api.github.com/users/mhayter/events{/privacy}","received_events_url":"https://api.github.com/users/mhayter/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2016-05-17T08:17:48Z","updated_at":"2016-05-17T08:19:15Z","closed_at":"2016-05-17T08:19:15Z","body":"this runs > twice as fast on n = 15:\r\n`\r\n#include <bits/stdc++.h>\r\nusing namespace std;\r\n\r\nint N;\r\n\r\nchar grid[15][15];\r\nint nSols;\r\n\r\nbool rowUsed[15];\r\nbool upDiag[30];\r\nbool downDiag[30];\r\n\r\nbool isValid(int row,int col) {\r\n\r\n\tif (rowUsed[row]) return false;\r\n\tif (upDiag[row+col]) return false;\r\n\tif (downDiag[N+row-col]) return false;\r\n\tif (grid[row][col]=='*') return false;\r\n\treturn true;\r\n}\r\n\r\nvoid mark (int row,int col) {\r\n\trowUsed[row]=upDiag[row+col]=downDiag[N+row-col]=true;\r\n}\r\nvoid unMark(int row,int col) {\r\n\trowUsed[row]=upDiag[row+col]=downDiag[N+row-col]=false;\r\n}\r\n\r\nvoid dfs(int col) {\r\n\tif (col==N) {nSols++;return;}\r\n\tfor(int row=0;row<N;++row) {\r\n\t\tif(isValid(row,col)) {\r\n\t\t\tmark(row,col);\r\n\t\t\tdfs(col+1);\r\n\t\t\tunMark(row,col);\r\n\t\t}\r\n\t}\r\n}\r\n\r\n\r\nint main() {\r\n\tint caseNum=1;\r\n\twhile (true) {\r\n\t\tcin >> N;\r\n\t\tif (N==0) break;\r\n\t\tnSols=0;\r\n\t\tfor(int i=0;i<N;i++) {\r\n\t\t\trowUsed[i]=false;\r\n\t\t\tfor(int j=0;j<N;j++) {\r\n\t\t\t\tcin >> grid[i][j];\r\n\t\t\t\t//cout << \"grid \" << grid[i][j] << endl;\r\n\t\t\t\tupDiag[i+j]=false;\r\n\t\t\t\tdownDiag[N+i-j] = false;\r\n\t\t\t}\r\n\t\t}\r\n\t\t//cout << \"N = \" << N << endl;\r\n\t\tdfs(0);\r\n\t\tcout << \"Case \"<<caseNum++<<\": \"<<nSols << endl;\r\n\t}\r\n\treturn 0;\r\n}\r\n'"},"comment":{"url":"https://api.github.com/repos/jlaire/dlx-cpp/issues/comments/219650545","html_url":"https://github.com/jlaire/dlx-cpp/issues/1#issuecomment-219650545","issue_url":"https://api.github.com/repos/jlaire/dlx-cpp/issues/1","id":219650545,"user":{"login":"mhayter","id":2280494,"avatar_url":"https://avatars.githubusercontent.com/u/2280494?v=3","gravatar_id":"","url":"https://api.github.com/users/mhayter","html_url":"https://github.com/mhayter","followers_url":"https://api.github.com/users/mhayter/followers","following_url":"https://api.github.com/users/mhayter/following{/other_user}","gists_url":"https://api.github.com/users/mhayter/gists{/gist_id}","starred_url":"https://api.github.com/users/mhayter/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mhayter/subscriptions","organizations_url":"https://api.github.com/users/mhayter/orgs","repos_url":"https://api.github.com/users/mhayter/repos","events_url":"https://api.github.com/users/mhayter/events{/privacy}","received_events_url":"https://api.github.com/users/mhayter/received_events","type":"User","site_admin":false},"created_at":"2016-05-17T08:19:14Z","updated_at":"2016-05-17T08:19:14Z","body":"`#include <bits/stdc++.h>\r\nusing namespace std;\r\n\r\nint N;\r\n\r\nchar grid[15][15];\r\nint nSols;\r\n\r\nbool rowUsed[15];\r\nbool upDiag[30];\r\nbool downDiag[30];\r\n\r\nbool isValid(int row,int col) {\r\n\r\n\tif (rowUsed[row]) return false;\r\n\tif (upDiag[row+col]) return false;\r\n\tif (downDiag[N+row-col]) return false;\r\n\tif (grid[row][col]=='*') return false;\r\n\treturn true;\r\n}\r\n\r\nvoid mark (int row,int col) {\r\n\trowUsed[row]=upDiag[row+col]=downDiag[N+row-col]=true;\r\n}\r\nvoid unMark(int row,int col) {\r\n\trowUsed[row]=upDiag[row+col]=downDiag[N+row-col]=false;\r\n}\r\n\r\nvoid dfs(int col) {\r\n\tif (col==N) {nSols++;return;}\r\n\tfor(int row=0;row<N;++row) {\r\n\t\tif(isValid(row,col)) {\r\n\t\t\tmark(row,col);\r\n\t\t\tdfs(col+1);\r\n\t\t\tunMark(row,col);\r\n\t\t}\r\n\t}\r\n}\r\n\r\n\r\nint main() {\r\n\tint caseNum=1;\r\n\twhile (true) {\r\n\t\tcin >> N;\r\n\t\tif (N==0) break;\r\n\t\tnSols=0;\r\n\t\tfor(int i=0;i<N;i++) {\r\n\t\t\trowUsed[i]=false;\r\n\t\t\tfor(int j=0;j<N;j++) {\r\n\t\t\t\tcin >> grid[i][j];\r\n\t\t\t\t//cout << \"grid \" << grid[i][j] << endl;\r\n\t\t\t\tupDiag[i+j]=false;\r\n\t\t\t\tdownDiag[N+i-j] = false;\r\n\t\t\t}\r\n\t\t}\r\n\t\t//cout << \"N = \" << N << endl;\r\n\t\tdfs(0);\r\n\t\tcout << \"Case \"<<caseNum++<<\": \"<<nSols << endl;\r\n\t}\r\n\treturn 0;\r\n}`"}}