title: What is a time complexity for Algorithm X for sudoku?
body: <p>I've found <a href="http://www.enggjournals.com/ijet/docs/IJET17-09-03-043.pdf" rel="nofollow noreferrer">here</a> a statement that <a href="https://arxiv.org/pdf/cs/0011047.pdf" rel="nofollow noreferrer">Algorithm X</a> for sudoku has O(N^3) time complexity where N is a board size. </p>
  
  <p>That's maybe logical, since for sudoku the binary matrix to compute has N^3 rows. But <b>that makes sudoku problem solvable in a polynomial time</b>, and sudoku is known to be NP problem, that means (as I understand it) </p>
  
  <ul>
  <li><p><b>not possible to always solve in a polynomial time</b></p></li>
  <li><p>possible to verify a solution in a polynomial time </p></li>
  </ul>
  
  <p>So what is the time complexity of Algorithm X for sudoku, 
  and is it possible to solve a sudoku in a polynomial time or not ?</p>
  
  <p>Thank you!</p>